Failure and Time¶

What makes a system distributed¶

A program on one machine either works or crashes. A system spread over several machines has partial failure: one node is down, a link drops packets, a process is paused for seconds by GC or a VM migration — while everything else keeps running. Worse, a node cannot tell these apart. A request that gets no reply might mean:

• the request was lost;
• the remote node crashed before handling it;
• the remote node handled it, and the reply was lost;
• the remote node is just slow (overloaded, paused, swapping);
• the network is partitioned and the remote node is fine on its side.

The only tool a node has is a timeout, and a timeout cannot distinguish "dead" from "slow". Every protocol on the following pages — Raft, leases, linearizable reads — exists to stay correct despite this ambiguity. The background is in Replication, CAP Theorem, and Raft Consensus; the runnable code for this section is in labs/raft, labs/raftkv, labs/lincheck, labs/hlc, and labs/lease.

Failure models¶

Model	What a faulty node may do	Typical assumption in
Crash-stop	Stop forever	Simple textbook protocols
Crash-recovery	Stop, lose volatile state, restart from stable storage	Raft, Paxos, databases — the realistic model for most infrastructure
Omission	Drop some messages	Covered by retries and idempotency
Byzantine	Anything, including lying	Blockchains, some aerospace systems; not assumed inside one organization's cluster

Raft assumes crash-recovery: whatever a node promised before crashing (its vote, its log) must be on disk before the promise is sent. That is why the node saves to storage before a vote or an append is acknowledged (Raft: Leader Election).

Network model: messages can be lost, duplicated, delayed arbitrarily, and reordered, but not corrupted undetectably (checksums handle that). Protocols must be safe under all of these, and only need to make progress when the network behaves well enough for long enough (partial synchrony). Raft's safety never depends on timing; only its liveness (electing a leader) does.

Physical clocks can't order events¶

Each machine's clock drifts (quartz oscillators are off by tens of parts per million — roughly a second per day) and is corrected by NTP, which can step it backwards. Typical skew between machines in one datacenter is from under a millisecond to tens of milliseconds; across regions or with misconfigured NTP, far more.

Consequences:

• Timestamps from different machines don't give causal order. If A sends a message and B receives it, B's clock may say the receive happened before the send.
• "Last write wins" by timestamp loses writes: a write from a node with a slow clock is silently discarded in favour of an older write from a node with a fast clock.
• Time-based leases assume clocks advance at roughly the same rate; a paused process breaks that assumption completely (Leases and Fencing).
• Use the monotonic clock for durations. Go's time.Now() carries a monotonic reading, and time.Since/Sub use it, so durations measured within one process are immune to wall-clock steps. Wall time is only for display and cross-machine coordination.

Logical clocks¶

Lamport clocks: every node keeps a counter; increment it on each event, attach it to messages, and on receive set it to max(local, received) + 1. If A causally precedes B, then L(A) < L(B). The converse does not hold, and the counter has no relation to real time.

Vector clocks: one counter per node; comparing two vectors tells whether events are ordered or concurrent. Used by Dynamo-style stores to detect conflicting writes. Cost: a vector per value, growing with the number of writers.

Hybrid logical clocks¶

An HLC timestamp is a pair (wall, logical): wall tracks the largest physical time seen anywhere, logical breaks ties. It preserves causality like a Lamport clock and stays within the clock skew of real time, so it can be used where physical timestamps are expected (MVCC versions, TTLs, "as of" queries). CockroachDB and YugabyteDB use HLCs for transaction timestamps.

type Timestamp struct {
    Wall    int64  // nanoseconds: max physical time seen
    Logical uint32 // breaks ties among events with the same Wall
}

// Now timestamps a local event or a message send.
func (c *Clock) Now() Timestamp {
    c.mu.Lock()
    defer c.mu.Unlock()
    if pt := c.physical(); pt > c.last.Wall {
        c.last = Timestamp{Wall: pt}
    } else {
        c.last.Logical++ // physical clock hasn't advanced (or went backwards)
    }
    return c.last
}

// Update timestamps the receipt of a message stamped remote; the result
// is greater than both remote and every earlier local timestamp.
func (c *Clock) Update(remote Timestamp) Timestamp {
    c.mu.Lock()
    defer c.mu.Unlock()
    pt := c.physical()
    wall := max(c.last.Wall, remote.Wall, pt)
    var logical uint32
    switch {
    case wall == c.last.Wall && wall == remote.Wall:
        logical = max(c.last.Logical, remote.Logical) + 1
    case wall == c.last.Wall:
        logical = c.last.Logical + 1
    case wall == remote.Wall:
        logical = remote.Logical + 1
    default: // our physical clock is ahead of everything seen
        logical = 0
    }
    c.last = Timestamp{Wall: wall, Logical: logical}
    return c.last
}

Measured¶

Two nodes exchange 10,000 messages A→B (and replies B→A), with 1–5 ms of network delay. B's clock is behind A's by a fixed skew. For each message: is the receive stamped strictly after the send?

Skew	Receive stamped at or before send — physical clocks	HLC	Max HLC lead over B's own clock
3 ms	5,928 (59.3%)	0	2 ms
100 ms	10,000 (100%)	0	99 ms

With 3 ms of skew and 1–5 ms delays, every message delivered in 3 ms or less appears to arrive before it was sent — 3 out of 5 equally likely delays, so the expected rate is 60%, and 59.3% was measured. Skew comparable to network latency is entirely normal, so ordering events across machines by raw timestamps is wrong most of the time, not occasionally. HLC never violated causality; the price is that B's HLC runs ahead of its own clock by up to the skew. A clock that steps backwards (an NTP correction) is also handled: the test sets the physical clock from 1000 back to 500 and the next timestamp still increases.

HLC does not give you real-time ordering between unrelated events on different nodes. For that, systems either bound the skew and wait it out (Spanner's TrueTime "commit wait", CockroachDB's uncertainty intervals) or route everything through one sequencer (a Raft leader).

What this means for designs¶

Need	Use
Durations, timeouts	Monotonic clock (time.Since)
Order of operations on one piece of state	A single leader assigning a sequence (Raft log index)
Causal order across nodes	Lamport clock or HLC carried on messages
Detect concurrent conflicting writes	Vector clocks / version vectors
Timestamps that look like real time and respect causality	HLC
Mutual exclusion across nodes	A lease plus fencing tokens (Leases and Fencing)
Linearizability	Consensus (Replicated Key-Value Store)

Common pitfall¶

Resolving conflicts with wall-clock "last write wins". Two services update a user's profile; the store keeps whichever write has the later time.Now(). One host's clock is 2 seconds ahead after an NTP glitch. For as long as the skew lasts, every update from the other host that lands within 2 seconds of one from the fast host is silently discarded — no error, no conflict, just data that never existed as far as readers can tell. Nothing in testing shows it, because test machines have synchronized clocks. Use a sequence assigned by a single owner (a leader, a database's version column with compare-and-set), or version vectors that surface the conflict, and keep wall-clock timestamps for display.

Review questions¶

1. List four reasons a request can get no reply, and explain why a timeout cannot distinguish them.
2. What does the crash-recovery model require of a node before it sends a vote or acknowledges a write?
3. Why did 59.3% of messages appear to arrive before they were sent with only 3 ms of skew?
4. How does Update guarantee the receive timestamp is greater than the send timestamp, even when the receiver's clock is behind?
5. What can HLC not give you, and how do Spanner and CockroachDB deal with that?