LESSON 17.3
Clocks and stale workers
Wall-clock skew, monotonic elapsed time, Lamport and vector clocks, and why fencing tokens protect against work arriving from an expired owner.
6 min read
Clocks drift, synchronization makes corrections, and paused processes can wake believing their leases still hold. Answering "which update came first?" needs different tools for calendar time, elapsed time, causality and ownership.
Deliver a write before creating another to see how causal history changes the vector.
Wall clocks and elapsed time
Wall clocks describe dates and times. They can disagree across machines and may jump during correction. If A's clock is two seconds ahead, its earlier write can look newer than B's later write. Last-write-wins based on those clocks can discard the later real-world change.
Use a monotonic clock for local durations: request timeouts, retry delays and measuring latency. It avoids backward wall-clock adjustments. Its origin is local, so two machines' monotonic readings aren't directly comparable. Monotonic time also doesn't stop a process from pausing or a packet from arriving late.
Clock synchronization reduces skew; it doesn't make arbitrary timestamps a proof of causal order. Systems using explicit uncertainty bounds need a protocol that accounts for those bounds, not just an assumption that NTP is running.
Happened before
Event A happened before B if A precedes B on one process, A sends a message that B receives, or those relationships connect transitively. Events with no such relationship are concurrent in this model, even if an observer could assign them physical times.
Lamport clocks
Each process keeps a counter. Increment before a local event, attach it to outgoing messages, and on receiving a timestamp set the counter to max(local, received) + 1. If A happened before B, its Lamport timestamp is smaller.
The converse is false: smaller doesn't prove causation. Adding a process-id tie-breaker creates a deterministic total order compatible with causality, but doesn't reveal physical time or make every process agree on which events have arrived. Lamport's original paper defines this logical ordering.
Vector clocks
A vector tracks a counter for each participant. Increment your own entry when creating an event and merge received vectors component by component using the maximum, with an increment for the receive event. Compare vectors componentwise to reason about their tracked histories.
- Version X
- [2, 0]
- Version Y
- [1, 1]
- X versus YNeither is at least as large in every component
- Concurrent
- Later merged history ZDominates both X and Y
- [2, 2]
Dominance identifies a causal successor; incomparable vectors identify concurrency. It doesn't choose how to merge two document bodies. Metadata also grows with participants, so real implementations need membership and compaction rules that preserve the promised semantics.
Fencing stale work
A lease expires while worker A is paused. Worker B becomes owner and writes. A resumes and sends an old write. Checking the lease before the pause wouldn't prevent that request; even checking just before sending leaves a delay window.
A fencing token is an increasing ownership generation, issued by an authority that doesn't reuse or regress it. Each write includes the token. The resource atomically remembers the highest accepted generation and rejects lower ones. Once B's token 42 has been accepted, A's token 41 can't overwrite it.
Fencing orders ownership generations, not every operation within one lease. A current owner still needs suitable sequencing, conditional writes or idempotency for its own concurrent requests.
Try it
Distributed Lock Service HLD
Protect a shared resource from a paused worker that resumes after its lease expires.