Using Simulation to Evaluate Consistency Protocols for Replicated Data

Introduction

In a distributed system, data are often replicated for protection against site failures and network partitions. When data are replicated at several sites, a consistency control policy must be chosen to ensure a consistent view of the data and maintain the appearance that there is only a single replica of the data. The view presented to the user must remain consistent even in the presence of site failures and network partitions. Sites recovering from a failure must present the data stored at that site in such a way that it is consistent with the global view of the data. Several consistency control protocols have been proposed, and the most promising are variants of available copy schemes and schemes based on quorum consensus.

Costs or space limitations may make it impossible to replicate a data object at enough sites to guarantee an acceptable level of fault tolerance. If new replicas of a data object can be created faster than a system failure can be repaired, then better reliability can be achieved by creating new replicas on other sites in response to site failures. This technique, known as regeneration, approximates the protection provided by additional replicas with only a modest increase in storage costs.

The degree of fault tolerance achieved depends on both the degree of data redundancy and on the consistency protocol that is used to manage the object. The most common measures of fault tolerance include reliability, which is the probability that a replicated data object will remain continuously available over a given time period, and availability, which is the steady-state probability that the data object is available at any given moment. Availability has received much more attention, in part because its analysis is more tractable than that of reliability.

The requirements of the application that manipulates the data object affects the relative importance of the measures. While reliability is perhaps the best indicator of the dynamic behavior of the system, if the objective is to simply minimize the inaccessibility of the data being replicated, then availability is often of primary concern. By contrast, enhanced reliability is usually the main objective for applications that incur disproportionately large costs for any failure of the data object.

Simulation plays a crucial role in evaluating the performance of these protocols. Consistency control protocols limit access to the data object to ensure that only current copies of the data can be accessed. The effect these protocols have on the accessibility of the replicated data is investigated by simulating the operation of the network and measuring the performance. Several strategies for replica maintenance are considered, and the benefits of each are analyzed using simulators which have been validated by numeric solutions derived from Markov models. The details of the simulations are discussed. Measurements of the reliability and the availability of the replicated data are compared and contrasted. In particular, the sensitivity of the protocols to common patterns of site failures and repairs is studied in detail, and the effect the second moments have on the results is analyzed. The relative performance of competing protocols is shown to be only marginally affected by non-exponential distributions, validating the robustness of the exponential approximations.