Clock skew, Lamport clocks and hybrid logical clocks: an interactive simulator
Every machine’s clock drifts, and even with NTP two servers can disagree by milliseconds, or by seconds after a bad sync or a paused VM. Systems that order events by wall-clock timestamps, such as last-writer-wins replication, then quietly keep the wrong value. Logical clocks order events by what each machine has seen instead: a Lamport clock is a counter, and a hybrid logical clock keeps wall time but never lets it run backwards.
The playground replays a profile rename across three replicas. Make B’s clock slow, switch the timestamp scheme, and see what replica C ends up with.
A user renames their profile to "Ann" on replica A. The change replicates to B, and the user, now routed to B, corrects it to "Anna". Both changes reach replica C, which keeps whichever has the later timestamp. B's clock is 300 ms slow. B stamps "Anna" with its slow clock, 00:00.800, earlier than "Ann" at 00:01.000, so C keeps "Ann": the newer write is silently lost, with no error anywhere.
How skew loses writes
The user renames their profile to “Ann” on replica A at 12:00:01.000 real time; B receives the change, and the user corrects it to “Anna” on B a tenth of a second later. With B’s clock 300 ms slow, B stamps “Anna” 00:00.800, earlier than “Ann” at 00:01.000. Replica C applies last-writer-wins and keeps “Ann”: the user’s correction disappears without any error. With 50 ms of skew the order happens to survive, because the writes were 100 ms apart; any two causally related writes closer together than the skew can be reversed.
Lamport clocks and hybrid logical clocks
- Lamport clocks keep a counter per node: add one for every event, and on receiving a message jump to one more than the larger of your counter and the message’s. If one event could have influenced another, it gets a smaller number. But the numbers carry no time, so you cannot ask for “everything before 3 p.m.”
- Hybrid logical clocks (HLC) carry a wall time and a counter. A node takes the larger of its clock, its last timestamp and any received timestamp, and bumps the counter on ties. Causal order is preserved like Lamport’s, and timestamps stay within the clock skew of real time. CockroachDB and YugabyteDB use them.
- Vector clocks go further and detect when two writes are truly concurrent, so the application can merge them instead of picking one.
- Bounded uncertainty is the other route: Google Spanner’s TrueTime exposes the clock error bound and waits it out before committing, so wall-clock order is safe.
None of these make a slow clock right. They make the system not depend on it: causality comes from the messages, and wall time is only a hint.
A hybrid logical clock in code
import time
class HybridLogicalClock:
"""Timestamps that never go backwards and stay close to wall time."""
def __init__(self):
self.wall, self.count = 0, 0
def now(self): # a local event or a send
pt = int(time.time() * 1000)
if pt > self.wall:
self.wall, self.count = pt, 0
else:
self.count += 1 # the wall clock has not moved past what we have seen
return (self.wall, self.count)
def receive(self, msg_wall, msg_count):
pt = int(time.time() * 1000)
top = max(self.wall, msg_wall, pt)
if top == self.wall == msg_wall:
self.count = max(self.count, msg_count) + 1
elif top == self.wall:
self.count += 1
elif top == msg_wall:
self.count = msg_count + 1
else:
self.count = 0
self.wall = top
return (self.wall, self.count)In a system design interview
Whenever a design says “last write wins” across machines, say what “last” means: “Each replica stamps writes with a hybrid logical clock and replication carries the stamp, so a write made after reading another always gets a larger stamp, even if this server’s clock is behind. Truly concurrent edits to the same field are rare here and last-writer-wins is acceptable; for carts we use CRDTs instead.” Expect the follow-ups: what happens when a clock jumps far ahead, and how much skew NTP actually allows.
Read the guide to logical clocks or time and dates, see CRDTs for merging concurrent writes, or watch a strong candidate design a key-value store.
Questions people ask
What is clock skew?
The difference between the clocks of two machines at the same moment. NTP usually keeps servers within a few milliseconds, but skew can reach seconds after network problems, virtual machine pauses or misconfiguration, and it is never zero.
Why is last-writer-wins with wall clocks dangerous?
Because a write made later on a machine whose clock is behind can carry an earlier timestamp than the write it replaced. Last-writer-wins then keeps the older value and discards the newer one silently, with no error to notice.
What is a Lamport clock?
A counter kept by each process: it increments on every event, and on receiving a message it jumps to one more than the maximum of its own value and the message’s timestamp. If event a could have caused event b, a has the smaller timestamp, but the counter says nothing about real time.
What is a hybrid logical clock?
A timestamp combining physical time with a logical counter. Each node uses the largest of its wall clock, its previous timestamp and any received timestamp, incrementing the counter on ties. It preserves causal order like a Lamport clock while staying within the clock skew of real time.
What is the difference between Lamport clocks and vector clocks?
A Lamport clock is a single number that orders causally related events but cannot tell whether two events were concurrent. A vector clock keeps one counter per node, so it can detect concurrency, at the cost of size growing with the number of nodes.
How does Google Spanner handle clock skew?
Its TrueTime API returns an interval guaranteed to contain the real time, backed by GPS and atomic clocks. A transaction waits until the uncertainty has passed before its commit becomes visible, so commit timestamps reflect real-time order.
Which databases use hybrid logical clocks?
CockroachDB and YugabyteDB use hybrid logical clocks to order transactions without specialised hardware, and MongoDB uses a similar cluster time for causal consistency. They bound the maximum allowed clock offset and reject nodes whose clocks drift too far.