Cruxly › System design › Foundations of Data Systems

Clocks, Ordering and Partial Failure

you cannot tell crashed from slow, and you cannot trust the clock to say which write came last

A network call can succeed, fail loudly, or say nothing at all, and the third outcome is the one that shapes every distributed design. This lesson covers what silence can mean, why wall clocks cannot order events across machines, how a paused process becomes a zombie leader, and the logical tools (Lamport clocks, version vectors, hybrid clocks) that order events without trusting time. It ends with the interview answer to "just use last write wins".

The network gives you three outcomes, and one is silence

A remote call can return a result, return an error, or return nothing, and designs fail on the third. On one machine a function call either finishes or the process dies, and you learn which. Across a network you send a request and wait. If no reply arrives, at least five different worlds are possible, and from your side they look identical:

• the request was lost on the way, so nothing happened;
• the request is queued behind others at the receiver, so it will happen, later;
• the receiver crashed before processing it;
• the receiver processed it and crashed before replying, so it happened but you never saw the reply;
• the receiver processed it and the reply was lost or delayed.

Distributed-systems papers call a network where delays have no upper bound asynchronous. In that model no algorithm can distinguish a crashed node from a slow one, because "slow" has no limit. That is not a theoretical nicety. It is the reason every failure detector you will ever use is a guess.

A timeout is that guess, with a price on each side. Too short and you declare healthy nodes dead: load balancers eject nodes that were merely busy, a leader election fires during a garbage-collection pause, and the extra work from retries pushes more nodes past the timeout. Too long and real failures take that long to detect, during which every caller waits. There is no correct constant, only a trade you set from measured latency. Tune it from a high percentile of the real distribution, not the average, and keep it well below the caller's own deadline.

The tail matters more than people expect. The Dean and Barroso paper (The Tail at Scale, CACM 2013) gives the arithmetic: if a server answers in 10 ms typically but one request in 100 takes a second, a request that needs all of 100 such servers in parallel is slow for 63% of users. That is 1 - 0.99^100 = 0.634 (the paper's figure, which the arithmetic reproduces). Fan-out turns a rare outlier into the common case, so any timeout you set on a fan-out path is hit routinely.

The consequence for design is one rule: any operation that might be retried must be safe to repeat. The sender cannot tell "did not happen" from "happened, reply lost", so the only safe move after silence is to retry something harmless: an idempotency key, a conditional write, or a natural overwrite. Failure Is a Mode, Not an Exception covers timeouts, retries and breakers as defences; this lesson is the reason they are needed.

Partial failure: a timeout cannot tell crashed from slow

In a distributed system, parts fail while the rest keep running, and the parts that survive disagree about what happened. Single-machine software is mostly all-or-nothing: a crash takes everything with it. A cluster has a different failure shape: one replica is slow, one link drops 5% of packets, one disk stalls, and the system as a whole is neither up nor down. These partial or "grey" failures are harder than clean crashes because the detector's verdict depends on who asks.

Different observers reach different verdicts. Node A cannot reach node B but node C can. Is B alive? Under a partition both answers are right from their own side. A system that lets each side act on its own verdict gets two leaders, two lock holders, or two copies of the same job running. That is why membership and leadership are decided by a quorum of observers, not by one node's opinion (Distributed Consensus covers the protocol). A single node that cannot reach the others cannot tell whether it is the one that failed.

Consequences you can name in the room:

• Duplicate side effects. A retry after a lost reply runs the action twice unless it is idempotent.
• Split decision. Two nodes both believe they are the primary. The usual defence is a majority rule: a node acts as leader only while a majority acknowledges it, so at most one side of a partition can.
• Cascading timeouts. One slow dependency makes callers wait, their callers time out, and retries multiply the load on the already-slow node. Bound retries and use a budget.
• Unknown outcome. The caller must treat a timed-out write as "maybe committed" and read back, or use an idempotency token, never as "failed".

:::warn "Timeout means the other node is down" is the wrong premise It means no answer arrived in your window. Treat the node as suspected, not dead, and make the next step safe if the suspicion is wrong: fence the old leader, deduplicate retries, read back the outcome. :::

What a staff engineer asks. "What does this component do when a dependency is slow rather than down?" Slow is the case the design usually forgot, because tests kill processes cleanly and production degrades them. Ask for the answer in terms of the caller's deadline, the retry budget and what is logged when the outcome is unknown.

Wall clocks lie: skew, drift, leap seconds, NTP steps

Every machine has its own clock, and they disagree by an amount you can only bound, never remove. Quartz oscillators run slightly fast or slow (drift), so two clocks that agree now will not agree in an hour. NTP corrects them by comparing against a server over the network, and the network's variable delay limits how well it can do that. The 2014 hybrid-logical-clock report from Kulkarni and colleagues puts numbers on it: NTP usually holds time to within tens of milliseconds over the public internet and can reach about one millisecond on a local network under ideal conditions, while asymmetric routes and congestion can occasionally cause errors of 100 ms or more.

:::key Verified November 2026: what the sources say about NTP and clocks

• NTP accuracy (Kulkarni et al. HLC report, 2014): tens of ms on the public internet, about 1 ms on a LAN under ideal conditions, occasionally 100 ms or more.
• chrony 4.6 manual: by default chronyd slews (speeds up or slows down) the clock; makestep steps it, and is meant mainly for boot, before programs that expect time to move forward start. The default maximum slew rate is 83333.333 ppm (one twelfth).
• Google's leap smear: a linear smear over 24 hours (noon to noon UTC), at most just under 0.5 s from true UTC, a rate change of about 11.6 ppm, in use since 2008. Amazon uses a smear on AWS.

:::

Two kinds of clock; use each for its job. The wall clock (time.time(), System.currentTimeMillis()) tells the date, is synchronised with NTP, and can jump backwards when it is stepped. The monotonic clock (System.nanoTime(), time.monotonic()) only moves forward and is right for measuring elapsed time on one machine, but its value means nothing on another machine. Timeouts and durations belong on the monotonic clock. Timestamps that leave the machine belong on neither if you need ordering.

The leap second incident. At 00:00 UTC on 1 January 2017 a leap second was added. Cloudflare's own post-incident write-up says its RRDNS resolver, written in Go, took time differences with time.Now(), which does not guarantee monotonic behaviour at that time. A measured round-trip time came out negative, the smoothed average went negative after enough samples, and the weighted server-selection code passed it to rand.Int63n(), which panics on negative input. About 0.2% of DNS queries to Cloudflare were affected at the peak and under 1% of HTTP requests saw errors, only for customers using CNAME records. The worst-hit machines were patched within 90 minutes, and the fix was out worldwide by 06:45 UTC. The lesson in Cloudflare's words was the assumption that time cannot go backwards. The fix to a clock bug is rarely a better clock; it is code that does not assume the clock is well behaved.

Smearing versus stepping. A step inserts the extra second as a jump, so some timestamps repeat or run backwards. A smear spreads it across a window so time never repeats. The risk is mixing: during Google's 24-hour window a smeared server can differ from a stepping server by nearly 0.5 s, so a fleet should use one policy everywhere. chrony shows the same trade: its leapsecmode slew spreads the correction (about 12 seconds at the default slew rate, per the manual) and its smoothtime option serves a smoothed time, with a warning that the server is intentionally not serving its best estimate of true time.

Why this breaks last-write-wins. Worked arithmetic: node A writes at true time T. Node B writes the same key 20 ms later. If A's clock runs 50 ms ahead (well inside what NTP over a WAN allows), A's timestamp is T+50 and B's is T+20, so A's older write wins and B's newer, acknowledged write is discarded without any error. The two writes lost nothing in transit; the clock ordered them wrongly. The window of danger is any pair of writes closer together than the skew.

Process pauses (GC, VM freeze) and the stale-leader problem

A process can stop running for seconds and not know it. Kleppmann's 2016 essay on distributed locking lists the causes: stop-the-world garbage collection, page faults, disk reads that turn into synchronous network requests (for example on network-attached volumes), CPU contention, and an accidental SIGSTOP. He notes that some HBase garbage-collection pauses have lasted several minutes, and that in a GitHub incident packets were delayed by about 90 seconds. The paused process sees nothing: when it resumes its own clock may show time has passed, but the code that checked its lease a moment earlier is already past that check.

The stale-leader bug. The pattern that breaks:

1. Client 1 gets a lock or lease valid for 10 s.
2. It checks "do I still hold it?" and starts a write.
3. It pauses for 30 s. The lease expires and the lock service grants it to client 2.
4. Client 1 wakes up, finishes the write it believes is protected, and corrupts data client 2 has already changed.

No amount of checking inside client 1 fixes this, because the pause can fall between the check and the use. A lease timeout alone is therefore not a safe mutual exclusion.

The fix is to move the check to the resource. A fencing token is a number the lock service increases each time it grants the lock. The client attaches it to every write, and the storage remembers the highest token it has accepted and rejects lower ones. In Kleppmann's example, client 1 holds token 33, pauses, and client 2 gets 34 and writes. When client 1 resumes and writes with 33, storage rejects it. The storage must do the comparing; a lock service that only says "yes" cannot protect anything.

Senior checklist for any "leader" or "lock" in a design:

• What stops a deposed leader from writing? Name the fencing check at the storage layer.
• Is the lease measured with the monotonic clock on the holder, and is its length much larger than the longest realistic pause? You cannot make it large enough to be the only defence.
• Does the replicated log or consensus group already give a monotonically increasing term or epoch? Use it as the token. A consensus log's term plays this role (see Distributed Consensus).

:::warn "We check the lease before every write" does not close the race The pause can occur after the check. Only the resource rejecting the stale writer closes it. :::

Happens-before and Lamport clocks

When physical time cannot order events, causality can. Lamport's 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System" (Communications of the ACM 21(7), July 1978, pp. 558-565) starts from the observation that events in different places have no shared clock, and defines a partial order called happened-before, written a -> b. Three rules define it, and they are the well-established core:

1. If a and b are events in the same process and a comes first, a -> b.
2. If a is the sending of a message and b is its receipt, a -> b.
3. If a -> b and b -> c, then a -> c (transitivity).

If neither a -> b nor b -> a, the events are concurrent: no chain of messages connects them, so neither could have influenced the other. Concurrent does not mean "at the same instant"; it means "causally unrelated". Everything else in this lesson builds on that distinction.

Lamport clocks give every event a number consistent with that order. Each process keeps a counter. It increments the counter before each event, stamps outgoing messages with the counter, and on receipt sets its counter to the maximum of its own and the message's value, plus one. The guarantee is one-directional: if a -> b then L(a) < L(b). The converse is false. A smaller number does not prove a happened first, because two concurrent events get numbers too. Breaking ties with a process id gives a total order that is consistent with causality, which Lamport's own commentary on the paper says can be used to implement any distributed state machine, illustrated with distributed mutual exclusion.

What it buys and what it does not.

Where it shows up. A replicated log numbers its entries so every replica applies them in the same order (Distributed Consensus). Applications with a single sequencer, such as a database that assigns monotonically increasing transaction ids, use the same idea without calling it a Lamport clock. The limits are real: the order is arbitrary among concurrent events, and you cannot ask "what was true at 14:00" because the numbers carry no wall time.

:::key When Lamport clocks are enough You need every node to agree on one order of operations and you do not need to know which were concurrent. When you must detect concurrency, you need vector clocks, next. :::

Vector clocks and version vectors: concurrent versus ordered

A vector clock stores one counter per node so you can tell ordered from concurrent. Where a Lamport clock is a single number, a vector clock is a list of (node, counter) pairs. Compare two vectors entry by entry. If every entry in A is less than or equal to the same entry in B, then A is an ancestor of B and B can replace it. If neither dominates the other, the versions were written without knowledge of each other: they are concurrent siblings and something must reconcile them.

The Dynamo paper (DeCandia et al., SOSP 2007) is the standard production example, and its Figure 3 walk-through is worth knowing by shape. A node Sx handles a write and creates version D1 with clock [(Sx,1)]; an update through Sx gives D2 with [(Sx,2)], which descends from D1. A later update handled by Sy gives D3 with [(Sx,2),(Sy,1)]. A different client reads D2 and updates through Sz, producing D4 with [(Sx,2),(Sz,1)]. D3 and D4 are concurrent: neither clock dominates. Dynamo keeps both and returns both on the next read. The client merges them, and the write that carries the merged context collapses them into D5 with [(Sx,3),(Sy,1),(Sz,1)]. A client updates by passing back the context from its read, which is how the system knows what the client had seen.

Version vectors versus vector clocks. They look the same; the difference is what they label. Baquero and colleagues' Bounded Version Vectors (DISC 2004) puts it this way: vector clocks order the events of processes, while version vectors track causality among the versions of data held by replicas. Databases use the second, because the question they ask is "is this replica's copy newer than that one?". Dynamo's paper calls its per-object clocks vector clocks; in this sense they behave as version vectors.

:::key Verified November 2026: Dynamo's production numbers (SOSP 2007 paper)

• Over a 24-hour profile of the shopping cart service, 99.94% of requests saw exactly one version; 0.00057% saw two, 0.00047% saw three and 0.00009% saw four.
• The paper says divergence came less from failures than from many concurrent writers, often automated clients.
• Clock size is bounded by truncation: each (node, counter) pair also stores a timestamp, and when the list reaches a threshold (the paper says "say 10") the oldest pair is dropped. The paper admits this can lose exact ancestry, and says the problem had not surfaced in production.

:::

The costs. Size grows with the number of nodes that coordinate writes. Dynamo's truncation shows the escape hatch and its price. Siblings push work to the application: someone must write the merge function (union a cart, keep the maximum, ask the user). A version vector detects conflict; it never resolves it. Deleted items reappearing from a merged cart is the known cost of union semantics.

Where you meet them. Dynamo-style stores and systems that expose siblings use them. Systems that built on timestamp last-write-wins did not, and CAP and PACELC, Precisely and Consistency models, for the person choosing explain why that is a conscious choice for some workloads.

Hybrid logical clocks and bounded-uncertainty clocks

Hybrid clocks try to get both properties: causality and closeness to real time. Lamport and vector clocks ignore physical time, so you cannot ask for a snapshot "as of 14:00". Physical clocks give that but break causality when skew exceeds the gap between events. Two real designs sit between them, and the details of both are in Distributed SQL: Spanner, CockroachDB, Aurora and friends; here is how to place them.

Hybrid logical clock (HLC). The Kulkarni and colleagues report ("Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases", 2014) proposes a timestamp that pairs a physical component kept close to the NTP clock with a small logical counter. It preserves the Lamport property (if e happened before f then hlc(e) < hlc(f)), fits in the 64-bit NTP timestamp format, only reads the physical clock and does not change it, and does not need special hardware. Its stated limitation is the one every NTP-based design shares: it relies on loosely bounded skew for the physical part to stay meaningful. CockroachDB uses HLCs and pays for imprecision with a configured maximum offset and read restarts, per its architecture docs summarised in the distributed-SQL lesson.

Bounded-uncertainty clocks (TrueTime). Spanner takes the other route: expose the clock's uncertainty as an interval and wait it out. Writers pay a commit wait roughly proportional to the interval (the 2012 paper reports uncertainty of about 1 to 7 ms and commit wait of about 5 ms in its test, covered in the distributed-SQL lesson). The HLC report's own critique is that this needs special hardware and delays events when clocks are loosely synchronised.

Which would you choose? For a replicated log, a consensus term and index. For a Dynamo-style store with siblings, version vectors. For a multi-region transactional database that must offer snapshot reads by time, HLC if you accept a bounded-skew assumption on commodity hardware, TrueTime-style if you can afford the hardware and the wait.

:::key What a bounded-skew assumption means operationally The design is safe only while real skew stays under the configured bound. So you monitor clock offset as a first-class signal and decide what a node does when it exceeds it. CockroachDB's documentation states the policy it chose: a node that finds its clock out of sync with at least half of the other nodes in the cluster crashes immediately, rather than serve reads and writes on a clock it cannot trust. :::

What to say in an interview about last write wins

"Last write wins" is not a design, it is a policy that quietly deletes data, and the question is whether that is acceptable here. Whenever an interviewer proposes it, or a store you recommend uses it, say what "last" means and who decides.

What the real systems do. Cassandra's Dynamo architecture page says that conflicts between replicas are resolved by last-write-wins using a timestamp on every mutation, deletes included, that the client can supply the timestamp and otherwise the coordinator's clock is used, and that "Cassandra's correctness does depend on these clocks", advising a time-sync process such as NTP. The Dynamo paper (2007) names timestamp-based last-write-wins as one of the reconciliation strategies applications can choose, next to semantic merge in the business logic. Both are honest about the dependency: correctness is only as good as the clocks.

The failure, stated precisely. LWW loses an acknowledged write silently whenever two writers are closer together than the clock error. At 50 ms of skew, any two writes to one key within 50 ms of each other can resolve in the wrong order (worked arithmetic from the clocks section). Hot keys, retries, and automated writers produce exactly that pattern.

The answer shape that earns the point.

1. Ask what the data is. Last-known-state data where any recent value is acceptable (a user's last-seen time, a cache entry, an idempotent overwrite of a whole record) tolerates LWW.
2. Name what is lost if two writes race: one of them, with no error. Say it aloud.
3. Offer the alternatives and their prices.

1. Close with the safeguards if you keep LWW: assign timestamps on the server not the client, alert on clock offset beyond a threshold, and make updates per field so unrelated changes do not overwrite each other (Cassandra resolves per column, per the same page).

Follow-ups to expect

Further reading. The book for this phase is Designing Data-Intensive Applications by Martin Kleppmann, which treats unreliable networks, clocks and ordering at book length. Read Lamport's 1978 paper in its original form, and Dean and Barroso's The Tail at Scale for why fan-out turns rare slowness into the norm.

How to say it in the interview

"A timeout tells me only that I got no answer in time, not whether the node is dead, slow, or the reply was lost, so I make every retried operation idempotent. I never order writes across machines by wall-clock time, because NTP over the internet is good to tens of milliseconds and sometimes off by 100 ms or more, so last-write-wins silently drops a write whenever two writers are closer than the skew. For leaders and locks I use a fencing token that the storage checks, because a paused process can wake up after its lease expired. When I need ordering I use a consensus log, a logical clock, or a version vector that exposes concurrent writes instead of hiding them."

Checklist

• Said that a timeout means no answer in the window, and listed at least three situations it cannot distinguish
• Made every retried operation idempotent (key, conditional write or overwrite)
• Set timeouts from a high percentile of measured latency and under the caller's deadline, and accounted for fan-out
• Never ordered cross-node writes by wall-clock time without stating the skew window
• Used the monotonic clock for durations and timeouts, and handled the wall clock stepping backwards
• Gave every leader or lock a fencing token that the storage checks
• Chose the ordering tool deliberately: consensus log, Lamport clock, version vector or hybrid clock
• Wrote the merge rule wherever siblings are kept, and named what it can resurrect or lose
• Monitored clock offset and defined what a node does when it exceeds the bound

Related lessons

• Reliable, Scalable, Maintainable: Measuring a System
• Choosing a Datastore
• How Indexes Actually Work
• Replication and Consistency
• Partitioning and Sharding
• Transaction Isolation Levels