DISTRIBUTED SYSTEMS Principles and Paradigms Second Edition ANDREW S. TANENBAUM MAARTEN VAN STEEN Chapter 7 Consistency And Replication
DISTRIBUTED SYSTEMS Principles and Paradigms Second Edition ANDREW S. TANENBAUM MAARTEN VAN STEEN Chapter 7 Consistency And Replication
Reasons for Replication
Data are replicated to increase the reliability of a system.
Replication for performance
Scaling in numbers
Scaling in geographical area
Caveat
Gain in performance
Cost of increased bandwidth for maintaining replication
Replication
Synchronous replication
A read operation returns the same results on every copy;
Write operations are atomic: they are propagated on all nodes before other operations can happen.
To improve synchronization the consistency constraints can be “relaxed”.
Data-centric Consistency Models
Figure 7-1. The general organization of a logical data store, physically distributed and replicated across multiple processes.
Consistency model
Consistency model
A “Contract” between processes and data store
Continuous consistency measure deviations in replicas:
numerical value: absolute/relative;
staleness: last time the replica was updated;
ordering of update operations.
Consistency unit
Conit: measure of inconsistency.
Continuous Consistency (1)
Figure 7-2. An example of keeping track of consistency deviations [adapted from (Yu and Vahdat, 2002)].
Continuous Consistency (2)
Figure 7-3. Choosing the appropriate granularity for a conit. (a) Two updates lead to update propagation.
Continuous Consistency (3)
Figure 7-3. Choosing the appropriate granularity for a conit. (b) No update propagation is needed (yet).
Sequential Consistency (1)
Figure 7-4. Behavior of two processes operating on the same data item. The horizontal axis is time.
Sequential Consistency (2)
A data store is sequentially consistent when:
The result of any execution is the same as if the (read and write) operations by all processes on the data store …
were executed in some sequential order and …
the operations of each individual process appear …
in this sequence
in the order specified by its program.
Sequential Consistency (3)
Figure 7-5. (a) A sequentially consistent data store. (b) A data store that is not sequentially consistent.
Sequential Consistency (4)
Figure 7-6. Three concurrently-executing processes.
6!=720 possible execution sequences
Sequential Consistency (5)
Figure 7-7. Four valid execution sequences for the processes of Fig. 7-6. The vertical axis is time.
Sequential Consistency (6)
Examples of not valid sequences
000000:
statements must be executed in program order;
001001:
00: y=z=0 both statements of P1 executed;
10: P2 must run after P1 starts;
01: P3 complete before P1 starts.
Causal Consistency (1)
For a data store to be considered causally consistent, it is necessary that the store obeys the following condition:
Writes that are potentially causally related …
must be seen by all processes
in the same order.
Concurrent writes …
may be seen in a different order
on different machines.
Causal Consistency (2)
Figure 7-8. This sequence is allowed with a causally-consistent store, but not with a sequentially consistent store.
W1(x)c and W2(x)b are concurrent
Causal Consistency (3)
Figure 7-9. (a) A violation of a causally-consistent store.
Causal Consistency (4)
Figure 7-9. (b) A correct sequence of events in a causally-consistent store.
Note: this is not acceptable in sequentially consistency
Critical sections
Mutual exclusion, transactions
Use synchronization variables:
Acquire when enter in section
Release when leave the section
Comments