1CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TARecap… Consistent cutsn On Monday we saw that simply gathering the state of a system isn’t enoughn Often the “state” includes tricky relationshipsn Consistent cuts are a way of collecting state that “could” have arisen concurrently in real-timeWhat time is it?n In distributed system we need practical ways to deal with timen E.g. we may need to agree that update A occurred before update Bn Or offer a “lease” on a resource that expires at time 10:10.0150 n Or guarantee that a time critical event will reach all interested parties within 100msBut what does time “mean”?n Time on a global clock?n E.g. with GPS receivern … or on a machine’s local clockn But was it set accurately?n And could it drift, e.g. run fast or slow?n What about faults, like stuck bits?n … or could try to agree on timeLamport’s approachn Leslie Lamport suggested that we should reduce time to its basicsn Time lets a system ask “Which came first: event A or event B?”n In effect: time is a means of labeling events so that…n If A happened before B, TIME(A) < TIME(B)n If TIME(A) < TIME(B), A happened before BDrawing time-line pictures:pmsndp(m)qrcvq(m) delivq(m )D2Drawing time-line pictures:n A, B, C and D are “events”. n Could be anything meaningful to the applicationn So are snd(m) and rcv(m) and deliv(m)n What ordering claims are meaningful?pmACBsndp(m)qrcvq(m) delivq(m )DDrawing time-line pictures:n A happens before B, and C before Dn “Local ordering” at a single processn Write and pqmACBrcvq(m) delivq(m )sndp(m)BAp→ DCq→DDrawing time-line pictures:n sndp(m) also happens before rcvq(m)n “Distributed ordering” introduced by a messagen WritepqmACBrcvq(m) delivq(m )sndp(m))m(rcv)m(sndqMp→DDrawing time-line pictures:n A happens before Dn Transitivity: A happens before sndp(m ), which happens before rcvq(m), which happens before DpqmDACBrcvq(m) delivq(m )sndp(m)Drawing time-line pictures:n B and D are concurrentn Looks like B happens first, but D has no way to know. No information flowed…pqmDACBrcvq(m) delivq(m )sndp(m)Happens before “relation”n We’ll say that “A happens before B”, written A→B, if1. A →PB according to the local ordering, or2. A is a snd and B is a rcv and A →MB, or3. A and B are related under the transitive closure of rules (1) and (2)n So far, this is just a mathematical notation, not a “systems tool”3Logical clocksn A simple tool that can capture parts of the happens before relationn First version: uses just a single integern Designed for big (64-bit or more) countersn Each process p maintains LTp, a local countern A message m will carry LTmRules for managing logical clocksn When an event happens at a process p it increments LTp. n Any event that matters to pn Normally, also snd and rcv events (since we want receive to occur “after” the matching send)n When p sends m, setn LTm= LTpn When q receives m, setn LTq= max(LTq, LTm)+1Time-line with LT annotationsn LT(A) = 1, LT(sndp(m)) = 2, LT(m) = 2n LT(rcvq(m ))=max(1,2)+1=3, etc…pqmDACBrcvq(m) delivq(m )sndp(m)5543331111000LTq3333222222110LTpLogical clocksn If A happens before B, A→B,then LT(A)<LT(B)n But converse might not be true:n If LT(A)<LT(B) can’t be sure that A→Bn This is because processes that don’t communicate still assign timestamps and hence events will “seem” to have an orderCan we do better?n One option is to use vector clocksn Here we treat timestamps as a listn One counter for each processn Rules for managing vector times differ from what did with logical clocksVector clocksn Clock is a vector: e.g. VT(A)=[1, 0]n We’ll just assign p index 0 and q index 1n Vector clocks require either agreement on the numbering, or that the actual process id’s be included with the vectorn Rules for managing vector clockn When event happens at p, increment VTp[indexp]n Normally, also increment for snd and rcv events n When sending a message, set VT(m)=VTpn When receiving, set VTq=max(VTq, VT(m))4Time-line with VT annotationspqmDACBrcvq(m) delivq(m )sndp(m)2 42 3232 22 22 20 10 10 10 10 00 00 0VTq3 03 0303 02 02 02 02 02 02 01 01 00 0VTpVT(m)=[2,0]Could also be [1,0] if we decide not to increment the clock on asnd event. Decision depends on how the timestamps will be used.Rules for comparison of VTsn We’ll say that VTA= VTBifn ∀I, VTA[i] = VTB[i]n And we’ll say that VTA< VTBifn VTA= VTB but VTA? VTBn That is, for some i, VTA[i] < VTB[i]n Examples?n [2,4] = [2,4]n [1,3] < [7,3]n [1,3] is “incomparable” to [3,1]Time-line with VT annotationsn VT(A)=[1,0]. VT(D)=[2,4]. So VT(A)<VT(D)n VT(B)=[3,0]. So VT(B) and VT(D) are incomparablepqmDACBrcvq(m) delivq(m )sndp(m)2 42 3232 22 22 20 10 10 10 10 00 00 0VTq3 03 0303 02 02 02 02 02 02 01 01 00 0VTpVT(m)=[2,0]Vector time and happens beforen If A→B, then VT(A)<VT(B)n Write a chain of events from A to Bn Step by step the vector clocks get largern If VT(A)<VT(B) then A→Bn Two cases: if A and B both happen at same process p, trivialn If A happens at p and B at q, can trace the path back by which q “learned” VTA[p]n Otherwise A and B happened concurrentlyConsistent cutsn If we had time, we could revisit these using logical and vector clocksn In fact there are algorithms that find a consistent cut byn Implementing some form of clockn Asking everyone to record their state at time now+δ (for some large δ)n And this can be made to work well…Replicationn Another use of time arises when we talk about replicating data in distributed systemsn The reason is that:n We replicate data by multicasting updates over a set of replicasn They need to apply these updates in the same ordern And order is a temporal notion5… and replication is powerful!n Replicate data or a service for high availabilityn Replicate data so that group members can share loads and improve scalabilityn Replicate locking or synchronization staten Replicate membership information in a data center so that we can route requestsn Replicate management information or parameters to tune performanceLet’s look at time vis-à-vis updatesn Maybe logical notions of time can help us understand when one update comes before another updaten Then we can think about building replicated update algorithms that are optimized to run as fast as possible while preserving the needed orderingDrill down: Life of a grouppqrstQ does an update. It
View Full Document
Unlocking...