Information Technology Reference
In-Depth Information
Data Replication
Different techniques are used to achieve eventual consistency, and we will discuss these
shortly one by one.
To understand fault tolerance, you must first understand the correct behavior of a repli-
cated resource, linearizability, and sequential consistency of operations. Correct behavior is
desirable to ensure fault tolerance. The correctness refers to the freshness of data and timely
delivery. Imagine a scenario where a web service offers flight information data to two clients
and upon two requests of exactly the same kind, but separated by a few seconds, the data
displayed to the two clients is different. This is incorrect behavior.
There are two main kinds of correctness criteria for replicated data. Most strictly cor-
rect systems are linearizable. Consider a scenario where two clients perform read and write
operations on a single system simultaneously. The correctness criteria in such a scenario
would be defined as virtual interleaving of operations of the two clients. Thus, a replicated
service is said to be linearizable if for any execution there is some interleaving that specifies
the following two conditions:
The execution meets the specification of a nonreplicated service.
The execution meets the real-time order of operations in the real execution.
However, there is a problem with the linearizability criteria: it is impractical for real-world
scenarios, where it is impossible for all the clients to receive exactly the same piece of infor-
mation because clocks cannot always be synchronized to have absolutely no time lag. Clock
synchronization is one of the hardest problems in distributed computing. We will not go into
the details of clock synchronization because it is beyond the scope of this chapter. You may
think of it as a process whereby clocks share their time among a number of geographically
distributed machines in order to adjust the machines' internal clocks to the exact relative time
that is expected. The need to synchronize results emanates from the problem of establishing
coordination among distant systems.
Since we cannot always ensure practicality of linearizability, a weaker correctness
condition is used. Sequential consistency replaces the notion of real time and replaces it
with the order of operations. A replicated service becomes sequentially consistent if for
any execution there is some interleaving that matches following conditions:
The execution meets the specification of a nonreplicated service.
The execution order of operations matches the program order of operations in which
each client executed them.
There is no notion of “real time” in sequential consistency, nor is there any
condition of maintaining the total order of events. The only requirement is
to have an order of events at each client that matches the program order.
Search WWH ::




Custom Search