Distributed Systems Essentials: Consistency Models And Consensus

Distributed Systems essentials:Consistency models andConsensusSome slides from Michael Freedman andothers

ReplicationqMotivationØØØØPerformance EnhancementEnhanced availabilityFault toleranceScalability§qtradeoff between benefits of replication and work required to keepreplicas consistentRequirementsØMemory Consistency (*not* Consistency in ACID)§§ØDepends upon applicationRequests for different replicas of the same logical data item shouldnot obtain different resultsReplica transparency desirable for most applications2

Consistency ModelsnConsistency Model is a contract between processes and adata storennnNeeded for understanding how concurrent reads andwrites behave with respect to shared dataRelevant for shared memory multiprocessorsnnif processes follow certain rules, then store will work “correctly”cache coherence algorithms; memory consistency modelsShared databases, filesnnindependent operationstransactions3

What is consistency?qConsistency model:ØqA constraint on the system state observable byapplicationsExamples:ØLocal/disk memory :write x 5ØSingle object consistency, alsocalled “coherence”read x (should be 5)timeDatabase:x: x 1; y: y-1assert(x y const)Consistency across 1 objectstime

Consistency challengesnConsistency is hard in (distributed) systems:nnnnData replication (caching)ConcurrencyFailuresNo right or wrong consistency modelsnTradeoff between ease of programmability and efficiency

Example application programCPU 1CPU 0READ/WRITEREAD/WRITEMemory systemx 1If y 0critical sectionqIs this program correct?y 1If x 0critical section

Examplex 1If y 0critical sectionnnnCPU0’s instruction stream: W(x) R(y)CPU1’s instruction stream: W(y) R(x)Enumerate all possible inter-leavings:nnnnny 1If x 0critical sectionW(x)1 R(y)0 W(y)1 R(x)1W(x)1 W(y)1 R(y)1 R(x)1W(x)1 W(y)1 R(x)1 R(y)1 .None violates mutual exclusion

An example distributed shared memoryqqqEach node has a local copy of stateRead from local stateSend writes to the other node, but do not wait

Consistency challenges: exampleW(x)1W(y)1x 1If y 0critical sectiony 1If x 0critical section

Does this work?W(x)1R(y)0x 1If y 0critical sectionW(y)1R(x)0y 1If x 0critical section

What went wrong?W(x)1W(y)1R(x)0R(y)0CPU0 sees:W(x)1R(y)0CPU1 sees:W(y)1R(x)0

Linearizability example

Sequential Consistency - 1Sequential consistency: the result of any execution is the same as if the read andwrite operations by all processes were executed in some sequential order and theoperations of each individual process appear in this sequence in the order specifiedby its program [Lamport, 1979].Note: Any valid interleaving is legal but all processes must see the same interleaving.a)b)P3 and P4 disagreeon the order of the writesA sequentially consistent data store.A data store that is not sequentially consistent.14

Sequential Consistency - 2Process P1Process P2Process P3x 1;print ( y, z);y 1;print (x, z);z 1;print (x, y);x 1;print (y, z);y 1;print (x, z);z 1;print (x, y);x 1;y 1;print (x,z);print(y, z);z 1;print (x, y);y 1;z 1;print (x, y);print (x, z);x 1;print (y, z);y 1;x 1;z 1;print (x, z);print (y, z);print (x, y);Prints: 001011Prints: 101011Prints: 010111Prints: 111111(a)(b)(a)-(d) are all legal interleavings.(c)(d)15

Linearizability vs. SequentialConsistency16

Causal consistencynPartial order: only causally related ops seenthe same order everywherennnn means replicas eventually convergeConcurrent ops may be ordered differentlyPro: better performance/concurrencyCons: Need to reason about concurrency

Causal consistency

In a nutshellnStrict consistency: total order, real-time guarantees over transactionsnLinearizability: total order, real-time guarantees over operationsnSequential consistency: total order program ordernnCausal consistency: Causally ordered operations ( refers to eventualagreement)Eventual consistency: we eventually agree

Figure from Martin Klepmann22

CAP theoremnConsistency, Availability, Partition resilientnnnGeneral/intuitive but not precisennCan only have two of threeProposed by Brewer (2000), and proved/formalized byGilbert and Lynch (2002)Brewer in 2012: “Misleading because it tended tooversimplify the tension between the elve-years-later-howthe-rules-have-changedStill CAP was influentialnBASE vs. ACID, NoSQL, 23

CONSENSUS INTRO

What do clients see?nDistributed stores use replicationnnFault tolerance and scalabilityDoes replication necessitate inconsistency?nHarder to program, confusing for clients

ProblemnnHow to reach consensus/dataconsistency in distributed system thatcan tolerate non-malicious failures?We saw some consistency models –how to implement them?

Another perspectivenLock is the easiest way to manageconcurrencynnnMutex and semaphore.Read and write locks.In distributed system:nnNo master for issuing locks.Failures.

3 Consistency Models n Consistency Model is a contract between processes and a data store n if processes follow certain rules, then store will work "correctly" n Needed for understanding how concurrent reads and writes behave with respect to shared data n Relevant for shared memory multiprocessors n cache coherence algorithms; memory consistency models n Shared databases, files