Start practising

SYSTEM DESIGN · CONCEPTS · DISTRIBUTED SYSTEMS · EPISODE 32

Clocks, Ordering and Unique IDs

Why server clocks disagree and what that breaks, last-write-wins losing data, logical clocks (Lamport timestamps) and vector clocks for ordering and detecting conflicts, and how to generate unique IDs at scale: auto-increment, UUIDs, ULID / UUIDv7 and Twitter-style Snowflake IDs.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 11

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

Clock drift

Every server's clock drifts, by tens of milliseconds a day. NTP keeps correcting them, usually to within a few milliseconds, but on a bad network it can be a hundred or more, and a correction can even jump the clock backwards. So two servers can disagree about the time, and you don't know by how much.

Physical clocks drift
  • quartz drifts ~ tens of ms
  • per day
  • NTP corrects it, usually to
  • within a few ms… or 100+ ms
  • on a bad network
  • NTP can jump the clock
  • BACKWARDS
  • leap seconds, VM pauses

Last write wins

Here's the damage. Server B, whose clock runs fast, writes version one. Moments later server A writes version two, but A's timestamp is earlier. A database using last-write-wins by timestamp keeps B's write and silently throws away the newer edit. No error, no log line. Cassandra's default conflict rule works this way.

Silent data loss
real order:
  B writes v1, then A writes v2

timestamps:
  B: 12:00:00.180 (fast clock)
  A: 12:00:00.050

last-write-wins keeps .180
→ v1 wins, v2 is lost
   no error, no log line

Logical clocks

The fix is to stop trusting wall clocks for ordering and count events instead. A Lamport clock is a counter on each node. Increment it on every event, attach it to every message, and on receiving, jump to the larger value plus one. Now if event A caused event B, A's number is smaller. Order follows cause and effect, not drifting quartz.

Lamport clock
each node keeps a counter

local event:   c = c + 1
send message:  attach c
receive m:     c = max(c, m) + 1

if A caused B, then
L(A) < L(B)

gives an order consistent
with cause and effect

Vector clocks

Lamport clocks give an order, but can't tell you whether two edits were truly concurrent. Vector clocks can. Each version carries one counter per node. If every counter in one version is at least the other's, it came after. If neither dominates, the edits were concurrent: a real conflict, so keep both and merge or ask the user. Dynamo-style systems and Riak use this.

Vector clock
one counter PER NODE

edit 1:  [A:1, B:0]
edit 2:  [A:1, B:1]  ← saw edit 1
edit 3:  [A:2, B:0]  ← did not

edit 2 vs edit 3:
neither ≥ the other
→ CONCURRENT: a real conflict
  keep both, merge or ask user

TrueTime

Some systems fix the clocks instead. Google Spanner's TrueTime uses GPS and atomic clocks to know the time within a few milliseconds of uncertainty, and makes each commit wait out that uncertainty. CockroachDB uses hybrid logical clocks: wall time plus a logical counter, close to real time but safe for ordering.

Or: better physical time
  • Google Spanner TrueTime:
  • GPS + atomic clocks give
  • time ± a few ms
  • commit WAITS out the
  • uncertainty → safe ordering
  • hybrid logical clocks (HLC):
  • wall time + a logical counter
  • (CockroachDB, YugabyteDB)

Unique IDs

Now the related problem: IDs. With one database, auto-increment works. With a thousand servers and sharded databases, you want IDs that are unique without a round trip to one central counter. Ideally they're also roughly sortable by time, so indexes stay efficient, and fit in sixty-four bits.

ID requirements
  • unique across all servers
  • generated without a round
  • trip to one database
  • nice to have:
  • • roughly time-sortable
  • (good index locality)
  • • 64-bit (fits a BIGINT)
  • • not guessable, if public

Options

The options. Auto-increment: simple, but one writer, guessable, and awkward with sharding. Random UUIDs: no coordination at all, but a hundred and twenty-eight random bits make B-tree inserts land everywhere, which hurts. ULID and UUID version seven put a timestamp first, so they sort by time. And Snowflake IDs fit it all into sixty-four bits.

The options
  • auto-increment: simple, one
  • writer, guessable, hard to shard
  • UUIDv4: 128 random bits, no
  • coordination, but random order
  • → slow B-tree inserts
  • ULID / UUIDv7: timestamp first,
  • random after → sortable
  • Snowflake: 64-bit, sortable

Snowflake

Snowflake, from Twitter, packs forty-one bits of milliseconds since a chosen epoch, ten bits of machine id and a twelve-bit sequence. That's sixty-nine years, a thousand machines, and four thousand IDs per millisecond each, roughly time-sorted with no coordination. One rule: if the clock goes backwards, the generator must wait, or it could repeat IDs.

Snowflake ID (64 bits)
| 41 bits  | 10 bits | 12 bits |
| ms since | machine | sequence|
|  epoch   |   id    | per ms  |

~69 years of timestamps
1024 machines
4096 IDs per ms per machine

sorted by time, no coordination
clock goes back? wait or refuse

Say it like this

In the interview: never order events across servers by wall-clock time. Use version numbers, Lamport clocks, or vector clocks when you need to detect conflicts. For IDs at scale, propose Snowflake or UUID version seven, and explain why a random UUID makes a poor primary key on a large B-tree table.

In the interview
  • ordering across servers:
  • don’t trust wall clocks;
  • version numbers, Lamport or
  • vector clocks for conflicts
  • unique IDs at scale:
  • Snowflake (64-bit, sortable)
  • or UUIDv7 / ULID
  • not UUIDv4 as a primary key
  • on a big B-tree table

Interview questions

Why can’t you order events across servers by timestamp?

Each server’s clock drifts and is only approximately synchronised by NTP, sometimes by tens or hundreds of milliseconds, and corrections can move clocks backwards, so timestamps from different machines do not reliably reflect real order.

How can last-write-wins lose data?

If the server performing the later write has a clock behind the server that performed the earlier write, the later write gets the smaller timestamp and is discarded, silently losing the newest update.

What is a Lamport clock?

A logical counter per node, incremented on each event, attached to messages, and set to max(local, received) + 1 on receipt. If event A causally precedes B, A’s Lamport timestamp is smaller.

What do vector clocks add over Lamport clocks?

A counter per node, so two versions can be compared: if one is greater or equal in every component it happened after; if neither dominates, the updates were concurrent, revealing a genuine conflict to resolve.

How does Google Spanner order transactions?

TrueTime exposes current time as an interval with bounded uncertainty using GPS and atomic clocks, and a transaction waits out the uncertainty before committing, so commit timestamps reflect real order.

What is a Snowflake ID?

A 64-bit ID made of a millisecond timestamp (41 bits), a machine or worker id (10 bits) and a per-millisecond sequence (12 bits), giving unique, roughly time-ordered IDs without central coordination.

Why is a random UUIDv4 a poor primary key for a large table?

Its random values spread inserts across the whole B-tree index, causing page splits, poor cache locality and larger indexes; time-ordered IDs such as UUIDv7, ULID or Snowflake insert near the end of the index.

What must a Snowflake generator do if the clock moves backwards?

Refuse or wait until the clock passes the last timestamp it used, otherwise it could generate duplicate IDs.