11 — Clocks, consensus and distributed locks

The problems so far came from having more than one machine. This chapter covers the deepest ones: how machines agree on order, and on anything else, when messages can be delayed and machines can pause.

Three unreliable things

Distributed systems face three basic uncertainties.

The network. A message can be lost, delayed, duplicated or reordered. When a reply doesn’t arrive, the sender can’t tell whether the request was lost, the reply was lost, or the other side is just slow.

Clocks. Each machine’s clock drifts. Network Time Protocol corrects it, but the correction can make a clock jump, even backwards.

Processes. A process can freeze at any moment, for a garbage collection pause, a virtual machine migration, or a swap storm. It then carries on with no idea that time has passed.

A process that pauses for 30 seconds just after checking a condition will act on a fact that’s no longer true. Much of what follows exists to handle that.

Time and order

Time-of-day clocks and monotonic clocks serve different purposes. A monotonic clock only moves forward, so it’s the right tool for measuring durations and timeouts. A time-of-day clock can jump, so subtracting two of its readings can give nonsense.

Timestamps from different machines can’t reliably establish order. If two writes occur a few milliseconds apart on different machines, clock error can be larger than the gap. So “last write wins” by timestamp can quietly discard the newer write.

Logical clocks

Leslie Lamport’s 1978 paper offered a different way to think about this. What usually matters isn’t the exact time, but whether one event could have influenced another.

Event A happens before B if they’re in the same process and A came first, or if A sends a message that B receives.

A Lamport clock is a counter:

1. Each node increments its counter on every event.
2. Each message carries the sender’s counter.
3. A receiver sets its counter to the larger of its own and the received value, plus one.

If A happened before B, then A’s number is smaller. The reverse doesn’t hold: a smaller number doesn’t prove influence.

Vector clocks fix that by keeping one counter per node, which makes it possible to tell “A happened before B” from “these were concurrent”. The cost is size, which grows with the number of nodes. Two writes with incomparable vectors are a real conflict.

Hybrid logical clocks combine physical time with a logical counter, so timestamps stay close to real time while still respecting causality. Several modern databases use them.

Spanner takes another route. Its TrueTime API gives time as an interval with bounded uncertainty, using GPS and atomic clocks, and transactions wait out that uncertainty before committing.

Detecting failure

Since a slow node looks like a dead one, failure detection is always a guess. Nodes exchange heartbeats, and a missing heartbeat raises suspicion. The trade-off is between false alarms and slow detection.

Gossip protocols spread membership information by having each node regularly exchange state with a few random others. News spreads through a cluster in a small number of rounds, with no central point.

The consensus problem

Consensus means getting several nodes to agree on a value, even if some fail. It sounds simple, and it underlies leader election, atomic commit and replicated logs.

A famous result, known as FLP, shows that in a purely asynchronous system, no algorithm can guarantee agreement if even one process can fail. Practical systems get around this by using timeouts, so they stay safe always, and make progress when the network behaves.

Raft

Raft was designed to be understandable. It splits consensus into three parts.

Leader election. Time is divided into numbered terms. Followers expect heartbeats from a leader. If none arrives within a randomized timeout, a follower becomes a candidate, increments the term, and asks for votes. Each node votes once per term, and a candidate with a majority becomes leader. Random timeouts make repeated split votes unlikely.

Log replication. The leader appends each command to its log and sends it to followers. Once a majority has stored an entry, it’s committed, and can be applied.

Safety. A candidate can’t win unless its log is at least as up to date as a majority’s. So a new leader has every committed entry.

The majority requirement is the key idea. Any two majorities overlap, so a new leader always includes at least one node that saw each committed entry.

Even numbers add little: four nodes still survive only one failure. And a network split can’t produce two leaders, because only one side can have a majority.

Consensus has a cost: every commit needs a majority round trip, and a single leader handles writes. So systems use it for small, critical state, such as configuration and leadership, rather than for all data. etcd and ZooKeeper are common examples, and Kubernetes keeps its state in etcd.

Paxos is the older algorithm, and Multi-Paxos is similar in effect to Raft.

Linearizable reads

A leader can’t simply answer reads from memory, because it may have been replaced without knowing. Options include confirming leadership with a majority before answering, or using a time-based lease, which relies on bounded clock drift.

Distributed locks

A distributed lock ensures that only one worker at a time does something across machines. There are two very different reasons to want one.

• Efficiency. Avoid doing the same work twice. A rare failure just wastes a bit of work.
• Correctness. A failure would corrupt data.

For efficiency, a simple Redis lock with a timeout is fine. For correctness, a lock alone isn’t enough, for the reasons below.

Why a lock with a timeout isn’t safe

Locks in distributed systems have to expire, or a crashed holder would block everyone forever. That creates this scenario:

1. Client 1 gets the lock, which expires in 30 seconds.
2. Client 1 pauses for a minute, in garbage collection.
3. The lock expires, and client 2 gets it.
4. Client 2 writes to storage.
5. Client 1 wakes up, still believing it holds the lock, and writes too.

Both clients thought they held the lock, and the second write can corrupt data. No lock service can prevent this on its own, because the pause occurs inside the client, after the check.

Fencing tokens

Martin Kleppmann’s fix is a fencing token: a number that increases every time the lock is granted. Each write carries the token, and storage rejects any token lower than one it’s already seen.

Client 1 gets lock, token 33, then pauses
Client 2 gets lock, token 34, writes with 34: accepted
Client 1 wakes, writes with 33: rejected, 33 < 34

Safety now lives in the resource, where it can actually be enforced. In ZooKeeper, the transaction ID can serve as the token. His article also criticises the Redlock algorithm, and Salvatore Sanfilippo, the creator of Redis, replied. Both accept that correctness-critical uses need something like fencing.

A practical rule follows: if correctness matters, prefer the guarantees of a database, such as a unique constraint or a compare-and-swap, over a separate lock service.

Leases

A lease is a lock with a time limit, and it needs renewing. It’s the standard tool when a holder may die. Everything above applies: the holder has to stop acting before its lease ends, and allow for clock drift and pauses.

Atomic commit across nodes

Two-phase commit makes several nodes commit together. A coordinator asks each one to prepare, and if all agree, tells them to commit. Its well-known weakness is that if the coordinator dies after the prepare step, participants hold locks and can’t decide alone. Running the coordinator on top of consensus, as Spanner does, solves that at the cost of latency. Chapter 13 covers the common alternatives.

Byzantine faults

Everything here assumes nodes fail by stopping or going slow, not by lying. Byzantine fault tolerance handles nodes that send false messages. It’s expensive, needing $3f+1$ nodes to tolerate $f$ faulty ones, and it’s mainly used in blockchains and some aerospace systems, not in systems inside a single organisation’s datacenter.

The takeaway

Clocks can’t establish order, networks can’t distinguish slow from dead, and processes can pause at any moment. Consensus gives reliable agreement at a cost, so it guards small critical state. A distributed lock isn’t safe for correctness without a fencing token checked at the resource.