Data Synchronisation · Lesson 02

Who Decides the Order?

Two people, offline, both set the same card's title. When both edits reach the rest of the system, one has to win. "The later one" is the obvious answer, and it hides the whole problem: later by whose clock?

Why the clock on the wall is not enough

In calibration you said the server needs to know “when each change was performed.” Take that literally — each client stamps its edit with Date.now() — and follow it through. Kleppmann's notes define clock skew as the “difference between two clocks at a point in time” and note that NTP “reduces clock skew to a few milliseconds in good network” — a laptop that has been asleep, a phone whose owner set the time by hand, a VM whose clock jumps, are not that. And the two edits we care about may be a hundred milliseconds apart.

The failure is not that the wrong edit wins sometimes. It is that the system cannot tell. A physical timestamp says nothing about whether the second writer had seen the first write. It cannot distinguish “Bob overwrote Alice's title on purpose” from “Bob never saw Alice's title.” The notes put the same point as a warning: “Systems that rely on clock sync need to monitor clock skew!” That is a maintenance burden you take on to get an answer that is wrong in exactly the case you cared about.

So the field replaced the question. Not when did each edit happen, but: could one have caused the other?

Happens-before

Lamport's 1978 relation, as Kleppmann states it (slide 62). An event is something happening at one node — sending a message, receiving one, or a local step. Event a happens before event b, written a → b, if and only if:

Two things follow. First, it is a partial order: for some pairs neither a → b nor b → a, and those pairs are called concurrent, written a ∥ b. Kleppmann: “here, 'concurrent' does not mean literally 'at the same time', but rather that a and b are independent in the sense that there is no sequence of messages leading from one to the other.” Two edits made an hour apart on two offline laptops are concurrent. Second, the relation “encodes potential causality”: a → b means a could have influenced b, not that it did.

Your two title edits are concurrent. That is the precise statement of what the wall clock could not express, and everything that follows is machinery for either detecting concurrency or deciding it.

Lamport clocks: a counter that respects causality

// Kleppmann, slide 66, in TypeScript
let t = 0                                   // each node has its own

function onLocalEvent()          { t = t + 1 }
function send(m: Msg)            { t = t + 1; network.send({ t, m }) }
function onReceive({ t: t2, m }) { t = Math.max(t, t2) + 1; deliver(m) }

Let L(e) be the counter's value after event e. The property (slide 67):

Read the three clauses as: consistent with causality; but silent about concurrency; and not unique. The second clause is the one to hold onto. A bigger Lamport timestamp tells you b did not happen before a. It does not tell you a happened before b — they might be concurrent. Detecting concurrency needs a vector clock, which is a later lesson.

Uniqueness is fixed by attaching the node's name. Slide 68 defines a total order ≺ on (timestamp, node) pairs:

(a ≺ b)  ⟺  L(a) < L(b)  ∨  (L(a) = L(b) ∧ N(a) < N(b))

Kleppmann: “This relation ≺ puts all events into a linear order … It is a causal order: whenever a → b we have a ≺ b. However, if a ∥ b we could have either a ≺ b or b ≺ a, so the order of the two events is determined arbitrarily by the algorithm.” That sentence is the honest specification of last-writer-wins.

Last-writer-wins, stated correctly

Slide 95, on two clients setting the same key concurrently:

“Last writer wins (LWW): Use timestamps with total order (e.g. Lamport clock). Keep v₂ and discard v₁ if t₂ > t₁. Note: data loss!”

So “last” in LWW does not mean latest by the clock. It means greatest in a total order that every replica computes identically. The order must be total — any two edits comparable — so that all replicas pick the same winner, and it must be causal, so that an edit made after seeing another never loses to it. Between concurrent edits it is, by Kleppmann's word, arbitrary. The loser is discarded; that is the data loss, and the notes say when to accept it: “in some systems, discarding concurrent updates is fine.” A card title is usually such a system. A shopping cart is not, which is what the multi-value register is for, later.

Now return to the calibration question. What does the server need to pick the same winner every other client will pick? A total order over the two edits. There are two ways to get one.

Route one: timestamps. Route two: a sequencer.

The first route is what you just read: each client carries a Lamport clock, stamps its edit with (t, clientId), and every replica compares pairs. No node has to be special. The cost is that each client must keep its clock, and the order between concurrent edits is whatever the arithmetic says.

The second route is the one your design already has. Kleppmann's slide 86 lists it first under total order broadcast: “Single leader approach: One node is designated as leader (sequencer). To broadcast message, send it to the leader; leader broadcasts it via FIFO broadcast.” Arrival order at one node is a total order for free. Figma chose exactly this:

“The document will just end up with the last value that was sent to the server. This approach is similar to a last-writer-wins register in CRDT literature except we don't need a timestamp because the server can define the order of events.”

The two routes are the same idea. A Lamport timestamp is a distributed way of agreeing on a sequence number; a server assigns the sequence number directly. Slide 86 also names the price of the second route: “Problem: leader crashes ⟹ no more messages delivered.” A server-authoritative engine accepts a single point of ordering in exchange for never having to compare timestamps. Whether that is the right trade is lesson 04's question. For this lesson the point is narrower: in both routes, “last” is a position in a total order, never a reading of a physical clock.

The unacknowledged flag is a rebase

One consequence of route two, and it closes a loop with lesson 01. The server orders edits by arrival. A client's own edit may not have arrived yet when a broadcast from someone else's edit to the same property comes in. Figma's client:

“[discards] incoming changes from the server that conflict with unacknowledged property changes … our change is our best prediction because it's the most recent change we know about in last-to-the-server order.”

That is view(c) from lesson 01: the authoritative state advances (the other user's edit lands), and the pending edit is replayed on top of it and wins locally. When the server later confirms, the client learns whether its prediction held. Same mechanism, Figma's vocabulary: unacknowledged is pending.

Glossary — added this lesson

What this unlocks

You can now say what a server must do to be an ordering authority, and what replaces it when there is none: a total order every replica computes identically. Lesson 03 removes the server entirely and asks what a data structure has to look like so that no order is needed. After both, lesson 04 can state Figma's argument for keeping the server, and lesson 06 can pick up the part of this lesson that was deferred — detecting concurrency with vector clocks rather than deciding it away.

Sources: Kleppmann, Distributed Systems lecture notes (slides 62–68, 86, 95) · Wallace, How Figma's multiplayer technology works · RESOURCES.md