Clocks, ordering, leases and fencing

Why it matters

"Use the timestamp to decide which write wins" and "take a lock with a 30-second TTL" sound reasonable and lose data. Clocks on different machines disagree and can jump backwards, and a process can stop for seconds without noticing. Interviewers probe this to see whether you know which orderings are trustworthy and how to keep an exclusive role safe when its holder may be slow rather than dead.

Core ideas

Physical clocks. Time-of-day clocks are synchronized over the network and can step forwards or backwards; monotonic clocks only move forward and are right for measuring durations on one machine, but mean nothing across machines. Skew between nodes is usually small but has no hard bound in bad cases, so wall-clock last-writer-wins can silently drop the later write.

Logical clocks. Lamport defined happened-before: a precedes b if they occur in that order in one process, if a is a send and b the matching receive, or by transitivity. A Lamport clock is a counter incremented at each event and set to max(local, received) + 1 on receipt. If a happened before b, then L(a) < L(b); the converse fails, so Lamport timestamps cannot reveal whether two events were concurrent. Breaking ties by node ID yields a total order consistent with causality, enough for a fair mutual-exclusion queue but not for detecting conflicts.

A vector clock keeps one counter per node. Event a precedes b exactly when a's vector is less than or equal to b's in every component and differs in at least one; if neither dominates, the events are concurrent. Version vectors apply this to replicas of a key, so concurrent updates are kept as siblings instead of one overwriting the other.

Leases. A lease is a lock that expires. The holder may act only while sure the lease is valid, so it measures the lease from before it sent the request and stops early by a margin covering clock-rate drift. Leases cut coordination traffic (a leader can serve reads locally while its lease holds), but their safety rests on timing assumptions.

Pauses break leases; fencing repairs them. A holder can check its lease, pause for a long garbage collection, and then write after the lease expired and someone else acquired it. The fix is a fencing token: the lock service returns a number that increases with every grant, clients send it with each write, and the storage rejects any token lower than the highest it has seen. Raft terms and other epochs play the same role between leaders.

client A: acquire -> token 33 ... long pause ... write(token 33) -> rejected
client B: acquire after A's lease expired -> token 34 -> write(token 34) -> accepted
storage: remembers the highest token seen (34) and rejects anything lower

Coordination services. ZooKeeper and etcd run consensus internally and expose small, strongly ordered stores with sessions or leases, ephemeral keys that vanish when their owner's session ends, watches for change notification, and increasing versions or revisions that can serve as fencing tokens. Use them for leader election, membership, configuration and locks; keep bulk data elsewhere. Read their guarantees precisely: ZooKeeper may answer reads from a lagging server unless the client syncs first, while etcd reads are linearizable by default and can be relaxed to faster, possibly stale serializable reads.

Ordering needs consensus. Total order broadcast (every node delivers the same messages in the same order) is equivalent to consensus, which is why a globally ordered log needs a consensus-backed sequencer or a single leader per partition.

Common misconceptions

• "Timestamps from synchronized clocks order events correctly." Skew and steps can invert causally related writes; use logical clocks or a single sequencer when order matters.
• "A lock with a TTL guarantees mutual exclusion." Not if the holder can pause or its clock runs slow; the protected resource must check a fencing token or epoch.
• "Lamport clocks detect concurrent writes." They impose a total order but lose concurrency information; vector clocks or version vectors detect conflicts.
• "A lock in a cache store with expiry is fine." Fine for efficiency (avoiding duplicate work); correctness-critical exclusion needs a consensus-backed service plus fencing.
• "Leases need perfectly synchronized clocks." They need bounded drift rates and a margin, not identical clocks; the real dangers are pauses and unbounded drift.

How to approach it

Read DDIA Ch. 8 on clocks and fencing, then Lamport's paper and Kleppmann's locking article, which together cover most interview questions. Practice computing clocks on drawn message diagrams and build the lock in the 6.5840 key/value lab on top of conditional writes. Graduates should explain why wall clocks are unreliable. Mid-level candidates should design a lease with fencing. Senior candidates should state the timing assumptions of a whole design and know when to avoid distributed locks by giving each partition a single owner.