Distributed Consistency

Every widget here counts time in ticks. A tick is one step of a clock we control, and nothing happens between two ticks. A message posted on tick 4 that takes two ticks to travel is delivered on tick 6, and until then it exists but has not arrived.

Real networks work in thousandths of a second, which is far too fast to watch and far too vague to reason about. Ticks let you press a button and see exactly one thing happen. Everything you learn about ticks is true of milliseconds; you are just able to see it.

Selling one jumper is not one action. The client has to find out how many there are, work out the new number, and send that new number back. That is a read, some arithmetic, and a write: two trips across the network with a gap in the middle.

The gap is where everything goes wrong for the rest of this page. While one client is thinking, the number it read is already out of date, and it does not know. Nothing in the network can tell it, because nothing in the network is watching.

Because one machine is one power cut away from a shop that cannot sell anything, and one broken disk away from a shop that has lost its records. A second machine holding a copy means the shop survives losing either one. That is the reason people put up with everything in this course.

The second reason is size. One machine can only answer so many requests a second, and one machine in London answers a customer in Sydney slowly no matter how fast it is. Copies close to the customer are the only fix and a copy is a second machine with its own opinion.

The counting is exact. The wobbling is not. A quartz crystal is cut to shiver at a chosen rate, and the rate it actually manages depends on how it was cut, how warm it is now, and how old it is. A typical one is out by a few seconds a month and a warm one in a badly cooled machine is worse.

Nothing about that is a fault, and no amount of money fixes it, because a clock that is out by one part in ten million is still out. Atomic clocks in laboratories are out by less, and they still drift. The lesson is not that clocks are bad. It is that two of them are never quite the same and a rule that compares readings from two different clocks is resting on a difference that nobody measured.

Machines do exactly that. There are servers whose only job is to say what time it is, and your machine quietly asks one every few minutes. It helps a great deal: instead of drifting for a day, a machine drifts for a few minutes and is then pulled back.

What it cannot do is make two clocks equal. The answer arrives by message, and a message takes time. Your machine knows the round trip took 40 thousandths of a second, but not whether that was 20 out and 20 back or 35 out and 5 back, so the time it sets itself to is a good guess with a margin around it. In practice machines on the same network land within a few thousandths of a second of each other, which sounds close until you remember that two writes to the same value can easily be less than a thousandth of a second apart.

When you say one write is later than another, you mean something about the real world: this one happened after that one, so it should win. When a machine compares stamps, it is doing arithmetic on two numbers that came from two different clocks. Those are not the same question, and the second one is only a useful stand-in for the first while the skew is smaller than the gap between the writes.

That is the whole trap. The rule looks like it is asking "which happened later" and is really asking "which clock was reading higher", and nobody notices the difference until two writes land close together.

Whatever you decide to write down. In the picture below, each machine does three things, and each of those is one event with a name like a1 or c2. The letter says which machine, the number says which of that machine's own events came first.

The choice of what to record does not change the answers. If you split one event into two, both halves happen on the same machine in a known order, so every chain that ran through the old event runs through both halves. The reasoning survives being more or less detailed, which is the sign that it is about the messages rather than about the bookkeeping.

Look at what it is made of: no clocks, no assumption about how fast anything runs, nothing that can drift or be set wrongly. Walking the arrows uses two facts and no others, and both are things a machine would report about itself. I did these two things in this order. This message left here before it got there.

So the answer it gives is exactly what the machines could have known, and nothing more. That is also why it stays silent so often. A pair of events with no chain between them is a pair the system holds no evidence about. Putting them in an order anyway is not a measurement. It is a guess wearing the clothes of one.

Two concurrent events can be an hour apart. Concurrent here means "no chain of arrows connects them", which is a statement about who knew what, not about when. An event on a machine in Tokyo on Monday and an event on a machine in Peru on Friday are concurrent if no message passed between those machines in between.

The useful way to read it is: neither one could have influenced the other. That is why the ordering does not matter, and why claiming an order anyway is the mistake. A pair that nothing could distinguish is a pair you are free to put in either order, and any two machines are free to make opposite choices without either being wrong.

Because the arriving message is proof that something already happened somewhere else. If a message says "I was at 7 when I sent this", then everything the sender had done was numbered 7 or less, and the receiving of it comes after all of that. A counter that answered 3 would be claiming this event came before things it demonstrably came after.

Jumping up is how one machine's history gets folded into another's. It is also why the counters do not stay near each other: a machine that talks to a busy machine inherits its high numbers, and a machine nobody talks to stays low.

They agree on it in advance, from a shared list of names. Position one is n1 because everybody was handed the same list, and a row of numbers means nothing to a machine that does not have that list. In real systems the row is usually stored as pairs, a name and a number together, which costs more room and saves the argument.

Adding a machine later makes every row longer. Every older row then has to be read as though it carried a zero in the new position, which is exactly what it means: nobody had heard of that machine yet. Taking a machine away is the harder direction. Its number holds real evidence about what it did before it left, and dropping the position throws that evidence away.

Because of size. One number per machine means a stamp on every message that grows with the number of machines, which is fine for five and awkward for five thousand. A single counter is one number whatever the size of the system, and it never needs a shared list of names to be understood.

It also does one thing vectors cannot. Vectors leave concurrent events unordered, honestly, and sometimes a system needs to pick one anyway so that every machine picks the same one. A single counter always yields an order, and the machine's own name breaks the ties, so everybody agrees on a winner even though nobody is claiming it really happened first. Knowing that a cheap answer is approximate is more useful than pretending it is not.

Because the only evidence either way is a message arriving, and all three situations produce the same thing: no message. There is no signal for "the machine you want is gone" and no signal for "your messages are not getting through", because whatever sent that signal would have to reach you, and reaching you is the thing that is broken.

You could add a second, separate wire to check on the first, and people do. Now there are two things that can break, and a machine that hears nothing on either one is in exactly the position it started in, with a bit more equipment. The uncertainty is not a gap in the design. It is a fact about being at one end of a connection.

Telling every machine you can reach what you now hold, and letting them pass it on. There is no leader in that arrangement and no list of who has heard what: each machine repeats what it knows and the information spreads like a rumour, which is where the name comes from.

It has one good property that matters for the rest of this course. If the machines keep gossiping and the network eventually works, everybody eventually hears everything, without anybody having to know who is up. This provides eventual convergence, but it does not promise when convergence occurs or what a read may return before then. Step 11 tests whether that guarantee fits the application.

A conflict is two writes to the same thing where neither happened before the other. Not two writes that arrive in a funny order, and not two writes that disagree. Concurrent writes, proved concurrent by their vectors, with nothing in the data saying which should win.

Something has to happen next, and whatever you choose is a merge rule. Keep the later stamp. Keep the bigger value. Keep both and hand them to a person. Add them together. Every one of those is a real rule that real systems use, and Lab 10 makes you look at what each one destroys.

A cut divides five machines into two groups, and only one of those groups can hold three or more of them. So "answer only if you can reach more than half of the machines" has a property no other rule has: at most one group can ever satisfy it, whatever the shape of the cut. A group of more than half is called a majority, and this is why the rule is majority rather than "at least two".

Two out of five would let both sides carry on, which is the split brain from Step 5 with extra steps. More than half is the smallest rule that makes two halves unable to both feel in charge.

It depends entirely on the question, which is why this is a decision and not a rule. An out-of-date count of likes on a video costs nothing: it is a number nobody checks twice. An out-of-date bank balance means an overdraft the bank did not agree to. An out-of-date seat map means two people with the same seat, and a very long conversation at the gate.

So real systems make the choice per question rather than once for the whole company. The same shop will happily show you a stale count of how many people are viewing this item, and will not sell the last one twice. Both live in the same building, and the interesting engineering is deciding which values sit on which side of that line.

People call it the CAP theorem, from consistency, availability and partition tolerance. It is often quoted as "pick two of three", which is a poor way to say it, because a partition is not a thing you pick. Networks get cut whether you approve or not.

The experiment gives the precise choice: when the network is cut, a machine can answer without knowing the other side's state or refuse to answer. When the network is fine, you can have both, and a great deal of practical work goes into keeping the periods of being cut short and rare so that the choice hardly ever has to be made.

Every write is given a number that goes up, and each machine stores that number next to the value. So a read that asks three machines gets back three pairs, and the newest is simply the one with the biggest number. That is all the vector clock machinery from Step 4 collapsed into one counter. It is allowed here because the writes all go through the same counting.

The read does not need a majority to work out which answer is newest. It only needs to have asked at least one machine that saw the newest write. That is the entire subject of this step: not counting for the sake of counting, but making sure two sets of machines cannot avoid each other.

Put five books on a shelf. Somebody puts a bookmark in two of them. Somebody else, who cannot see the bookmarks, opens four of the five. Can they miss both bookmarks? No: only one book is left unopened, and there are two bookmarks, so at least one bookmarked book was opened.

Two plus four is six, and six does not fit in five without something being in both groups. That is the whole proof, and it is why the rule needs R plus W to be strictly bigger than N. Two bookmarks and two books opened, out of four books, is exactly enough room for the two groups to keep apart. It is the case that catches almost everybody.

The next lab has you edit one line of a program. A function is a named piece of a program that takes some values in and hands one value back. function safe(n, r, w) { starts a function called safe that expects three numbers, and inside it those three numbers are called n, r and w. Anything after // on a line is a note to the reader and is ignored by the machine.

return is how the function hands its answer back and stops. return false; means "the answer is no". The two answers a yes-or-no question can have are written true and false. So return r + w > n; hands back true when r plus w is bigger than n, and false when it is not, and > is the ordinary greater-than sign. The lab checks your line by calling it with ten different sets of numbers and comparing the answers, so it is grading what your rule does rather than how you wrote it.

They are two servers. The hills are two machines, the valley is a network that loses messages, and attacking together is any decision two machines have to take identically: both charge the card, or neither does. The story is from 1975 and it stuck because the picture is easier to hold in your head than the machines are.

Everything in the story maps onto something in Step 5. A messenger caught in the valley is a lost message. A commander waiting and hearing nothing is a machine that cannot tell a cut from a crash. The answer the story gives applies to the machines exactly, and it is not a comforting answer.

Suppose somebody hands you a plan that always works and uses exactly six messages. Look at the sixth one. Whoever sent it never finds out whether it arrived, so that sender must behave the same way in both cases, so the plan works just as well if the sixth message is never sent at all. You now have a plan that uses five.

Run that argument again on the fifth, and the fourth, until you have a plan that uses no messages, where one commander attacks with no idea what the other will do. That plainly loses, so the six-message plan cannot have worked either. Nothing in the argument mentioned six, which is why the answer is not "use more messages".

What is impossible is certainty: no plan makes both sides sure, in every possible run, using finitely many messages. What is entirely possible is being confident enough. Send the confirmation three times and the chance that all three are lost is small, and you can make it as small as you can afford.

The other move real systems make is to stop needing both sides to decide at the same instant. Write down what you intend to do first, agree afterwards, and make the action safe to repeat so that doing it twice by accident has the same effect as doing it once. Almost every payment system you have used works that way, and it works because it stopped asking for the thing that cannot be had.

Three reasons, and they are the reasons from Step 1 again. A follower can take over if the leader dies, which turns a disaster into a pause. A follower can answer reads, so a hundred readers do not all queue behind one machine. And a follower close to the customer answers quickly, which no amount of leader is going to fix for a customer on the other side of the world.

Being a little behind is a small price for those three, and often the value being read has not changed for hours anyway. The trouble is not lag by itself. It is lag that nobody accounted for in a place where a stale answer causes harm, and lag that grows without limit while nobody is watching.

When a follower has written an entry into its own copy, it sends a small message back to the leader saying so. That message is an acknowledgement, usually shortened to ack. It is the only way the leader ever learns that a copy landed.

So the leader has a decision on every write. Tell the customer it is done immediately, and be fast but hand out stale reads. Or wait for the acks first, and be slower but never have a copy behind. There is no third option, and the next lab races the two.

The version of lag that customers actually complain about is this one. You change your name, the leader accepts it, the page reloads, the reload happens to be answered by a follower that has not heard yet, and your old name comes back. Nothing is broken and no data was lost, and every person this happens to is certain the site lost their change.

The usual fix is small and worth knowing: for a short while after somebody writes, send that person's reads to the leader, or to a follower that has caught up past their write. It costs almost nothing, and it turns an alarming bug report into a promise you can write down. Step 11 asks you to check exactly this promise against a running system.

All sorts of ordinary reasons. Its disk is busy, so the write it was doing took twenty times as long as usual. The machine it shares a building with started a backup and the network between them filled up. Its own memory needed tidying, and the tidying stopped everything else for a moment.

None of that means the machine is unwell in any way that matters, and all of it produces a gap in the heartbeats. This is why the timeout cannot simply be set low: a low timeout does not detect more deaths, it invents them.

It is the split brain from Step 5, arrived at by a different route. Both leaders accept writes, neither knows about the other, and the two lists of entries diverge. When somebody notices, one of the two lists has to be thrown away and the customers whose writes were in it were told those writes had succeeded.

Real systems defend against this by making the old leader unable to do damage rather than by trying harder to detect it. Every leader carries a number that goes up each time a new one is chosen, and followers refuse anything carrying an old number. The demoted leader can shout as much as it likes and nobody is listening. The next course in this stream builds that machinery.

Nobody good picks one number and leaves it. The machine watches how long the gaps between heartbeats usually are for this particular machine, and suspects it when the current silence is far outside its own usual range. A machine that is normally slow gets more rope than one that is normally instant, which is the rule you are about to write.

The other half of the answer is to stop treating suspicion as a verdict. Instead of "dead" or "alive", keep a number saying how suspicious things look, and let whatever depends on it decide how much suspicion is enough. A leader takeover can demand a lot of evidence, and a load balancer sending a request elsewhere can act on very little, and both read the same number.

"Every request gets an answer" is availability."A second read never shows something older than the first" is monotonic reads."You always see your own last write" is read your own writes."Once the network is mended, every copy ends up the same" is eventual consistency. And a write that is accepted and never quietly discarded is durability of the accepted write.

Learning the names is worth ten minutes because they are how the promise is written in a manual, and a manual that promises eventual consistency is telling you, in two words, that it does not promise the other four. Reading that sentence properly is most of what this course was for.

It sounds like the weakest promise on the list, and it is. It is still the difference between a system that heals itself and one that needs a person. It says that if the machines can talk again and somebody keeps gossiping, the copies stop disagreeing without anybody being told who is up or what broke. A system that does not promise it has to be repaired by hand after every cut.

What it does not tell you is when, and it does not tell you what happens to conflicting writes on the way. Those are separate questions with separate answers and a system can promise this one and still throw away your write. Reading the promise for exactly what it says, and no more, is the habit worth keeping.

The way Lab 22 does it. Write down what the customers did and what they were told, in order, then check the list of promises against that record. Nobody's opinion is involved: either a customer was shown a value older than one they had already seen, or no customer was.

This is a real technique with real tools behind it. People test databases by running a pile of clients against a cluster while cutting its network at random, recording every answer, and then checking whether any promise in the manual was broken by that record. The number of well-known databases caught breaking their own manuals this way is larger than you would hope.

Linearizability is normally stated per object. Strict serializability combines serializable multi-object transactions with real-time order. Do not claim the second after testing only the first.

The token names the minimum version this client has already observed. A replica can compare that requirement with its local version instead of guessing from elapsed time.

State-based replicas merge whole or delta states with a join. Operation-based replicas deliver operations under stated ordering and delivery assumptions. The proof obligations differ.

Repair changes how long replicas disagree. The read and write rules decide which disagreement a client may observe before repair finishes.

The world may have changed since the original action. A refund can fail, a seat may have been resold, and an email cannot be unsent. Design retries, escalation and a visible incomplete state.

Google Spanner uses a bounded time interval plus waiting and replicated transaction machinery to provide external consistency. The clock interval is one component, not a replacement for consensus or concurrency control.

Internal logs can agree while clients receive an impossible result. Build the checked history from request and response boundaries, then use internal traces to explain a violation.