6.824 2001 Lecture 13: Consistency What is consistency? Relationship between views of data/events from different clients / servers This has come up already, will come up again NFS/Sprite cache consistency Zebra file version numbers Ticker tape lab Paper for next Thursday (Bayou) Example situations Multiprocessor What if you write data, then clear a lock variable I should see the new data before the released lock Network file system I write foo.c on one machine, then compile it on another Mailing list Replicated on each client I send a message, you reply Everybody should see the same order Typical replication arrangements (high level view) Many clients, one NFS server Many clients, replicated NFS servers Many symmetric clients that each store data or see events There are many reasonable definitions of consistency Ease of programming Match to particular application Ease of implementation Approach Going to talk about this somewhat abstractly Try to define notions of consistency independent of implementation But need to consider ease of implementation Strict consistency Def: Events are visible in the order in which they occurred E.g., a read returns the value from the most recent write E.g., NFS server executes ops in correct *time* order of issue Why is strict consistency good? I send "meeting at 3pm" e-mail I tell you (by voice), you tell me you can't make it You send "meeting at 4pm" e-mail Everybody sees the e-mails in the right order In general, very intuitive programming model; no surprises. Do you get strict consistency naturally in e.g. NFS or Sprite or e-mail? Network causes issue order to differ from execution order. My e-mail/NFS-write delayed in transit, or has to be re-sent. So it is executed/stored after yours, which was issued later. Why is strict consistency hard? How would you implement it? Client need to time-stamp operations. Client clocks need to be correct and synchronized. (I'm not even sure what that would mean, if anything.) No two operations (in different clients) allowed at the same time. Server or other clients must execute in time-stamp order. What can we save from strict consistency? 1. Everybody saw the same order. 2. It was the "right" order. Let's work on #1 first. Sequential consistency Everybody sees the same order of events/updates Each process's events are in the order it issued them Is sequential consistency easy to implement? If all updates go through one server, then yes. Or you can have a simple sequencing server. Just hands out a sequence of ordering numbers. Why is sequential consistency good? Everybody sees the same order, so we can e.g. maintain replicas. Preserves causality: If I see event 1, then generate event 2, everybody sees 1 then 2. When might sequential consistency be non-intuitive? Many interleavings are valid. Different runs of a program might act differently. Execution order may be very different from time order of issue. Might get the "meeting at 3pm/4pm" example wrong. Since our e-mails are simultaneous, as far as the system is concerned. Can we get back some notion of "right order"? Linearizable consistency Like sequential, but extra rule: Give each event a loose time stamp; e.g. granularity 5 seconds. Order execution by loose time stamp. Requires only loosely synced clocks. Why is this good/bad? Stronger than sequential. Probably possible to implement, unlike strict consistency. But no order guarantee within any one "unit" of time. So application has to be aware of potential oddities. Problem: Sequential consistency is expensive. You need some central node to assign time stamps. So not scalable. Even unrelated events are ordered. E.g. unrelated/simultaneous e-mail on a mailing list. So often does too much work. Does it make sense to relax "same order" rule, while keeping some notion of "the right order" for related events? Causal consistency Events that are causally related must be seen by everybody in the same order. Unrelated ("concurrent") events can be seen in different orders. Why is this good for programmers? Preserves intuition about event relationships. Why might this be easier to implement? Ordering could be specified w/ local info. Why might this not be right for some systems? Not good for replication, since not total order. Where does the ticker lab fit in this taxonomy? Is it strict? no Is it sequential? yes Linearizable? yes Causal? hard to say