System Design HLD-19.05
Design a unique ID generator
Design a 64-bit, time-sortable id generator: Snowflake layout, assigning worker ids with leases, and handling clocks that move backwards.
The problem
Every tweet, order, message and log line needs an id. In a single database, an auto-increment column does the job. Once writes spread across hundreds of shards and services, you need ids that are unique across all of them, generated in microseconds, without a central counter that every write must call.
Usually there are extra wishes: ids that sort roughly by creation time (so "newest first" is an index scan), that fit in 64 bits (so they are cheap to store and index, and fit in a long integer in every language), and that are produced locally by each server. The hard parts are not the bit layout. They are making sure no two servers ever share a worker id, and surviving a clock that jumps backwards.
Requirements
Functional
next_id()returns an id never returned before, anywhere in the system.- Ids are 64-bit integers, roughly sortable by creation time.
- Ids can be decoded into creation time for debugging.
Non-functional
- Scale: up to 1,000 generator instances, peaks of a few hundred thousand ids per second overall, up to tens of thousands on one instance.
- Latency: microseconds; no network call per id.
- Availability: id generation keeps working if any central component is briefly down.
- Lifetime: decades without running out.
Out of scope
- Strictly gap-free or strictly ordered ids (requires a single sequencer), unguessable ids for security tokens.
Estimates
The 64 bits are a budget to split between time, workers and sequence:
- Time: 41 bits of milliseconds is 2^41 ms, about 69.7 years from a custom epoch. Choose the epoch as the system's start date, not 1970, so those years lie ahead.
- Workers: 10 bits give 1,024 worker ids, enough for the 1,000 instances in the requirements, without much room to spare.
- Sequence: 12 bits give 4,096 ids per worker per millisecond, over 4 million per second per worker. The requirement of tens of thousands per instance uses about 1 percent of that.
- Sign bit: the top bit stays 0 so ids are positive in languages with signed 64-bit integers.
If you need more workers, take bits from the sequence: 13 worker bits and 11 sequence bits still allow over 2 million ids per second per worker.
API
Two ways to expose it:
In-process library: id = idgen.next() no network, microseconds
Network service: POST /v1/ids?count=100 -> [ ... 100 ids ... ]
We choose the library inside each service: no extra hop, no extra service to keep alive. The only shared piece is worker id assignment at startup. A network service is useful for languages or jobs that cannot run the library; it should hand out batches to keep the call rate low.
Data model
Each id is self-describing:
| Bits | Field | Meaning |
|---|---|---|
| 1 | sign | always 0 |
| 41 | timestamp | ms since the custom epoch |
| 10 | worker id | which generator made it |
| 12 | sequence | counter within one millisecond |
The coordination store holds one record per worker id: /idgen/workers/0417 -> { owner: "orders-7f9c", lease_expires: ... }.
High-level design
- Startup: claim a worker id The instance creates a key for the lowest free worker id in the coordination store, attached to a lease with a time to live of, say, 30 seconds. The create succeeds only if the key does not exist, so two instances can never hold the same id.
- Hot path: local generation Each next() reads the clock, compares it with the last timestamp used, bumps or resets the sequence, and packs the three fields. No network, no locks beyond the generator's own.
- Background: keep the lease The instance renews its lease every few seconds. If it cannot renew before the lease expires, it must stop issuing ids, because another instance may soon claim the same worker id.
Deep dives
Deep dive 1: Assigning worker ids safely
Two generators with the same worker id will produce duplicates the moment their clocks and sequences line up. The options:
- Static configuration: a worker id per host in a config file. Simple, but breaks with autoscaling and copy-pasted configs.
- Derived from the environment: for example, a stateful set's pod ordinal, or bits from the machine's IP address. Works when the derivation is guaranteed unique; IP bits are not, across subnets.
- Leased from a coordination service (chosen): claim a free id with a create-if-absent write tied to a leaseA time-limited claim on a resource that the holder must keep renewing; if it stops renewing, the claim expires and someone else may take it., renew it, and stop generating if the lease is lost ( Coordination services (ZooKeeper, etcd) ).
The lease approach has one subtle gap: a process that freezes (a long garbage collection pause, a suspended VM) may wake up after its lease expired and another process took its id. Guard against it by checking the lease's local expiry time before every id, with a safety margin, and by not reusing a worker id for some minutes after its lease ends. The coordination store is needed only at startup and for renewals, so a brief outage does not stop id generation, as long as leases are long enough to ride it out.
Deep dive 2: Clocks that move backwards
The timestamp comes from the local clock, and clocks do jump backwards: NTP corrections, a VM migrated to another host, a leap second handled by stepping. If the generator issues ids with a timestamp it has already used, it can repeat (timestamp, sequence) pairs and create duplicates. Watch it happen with a 3 ms step back:
# A Snowflake generator with a fake clock that jumps back 3 ms.
# 41 bits time | 10 bits worker | 12 bits sequence
EPOCH = 1_700_000_000_000
class Gen:
def __init__(self, worker, clock, guard=True):
self.w, self.clock, self.guard = worker, clock, guard
self.last, self.seq, self.waits = -1, 0, 0
def next_id(self):
now = self.clock()
while self.guard and now < self.last: # clock went backwards
self.waits += 1 # wait for it to catch up
now = self.clock()
if now == self.last:
self.seq = (self.seq + 1) & 0xFFF
if self.seq == 0: # 4,096 used: next ms
while now <= self.last:
now = self.clock()
else:
self.seq = 0
self.last = now
return ((now - EPOCH) << 22) | (self.w << 12) | self.seq
def fake_clock():
# ms readings: steady, then NTP steps back 3 ms, then recovers
t = [EPOCH + 1000 + i for i in range(10)]
t += [EPOCH + 1006 + i for i in range(10)]
it = iter(t)
return lambda: next(it)
for guard in (False, True):
g = Gen(worker=7, clock=fake_clock(), guard=guard)
ids = [g.next_id() for _ in range(14)]
dups = len(ids) - len(set(ids))
print(f"guard={guard!s:5} ids={len(ids)} duplicates={dups} "
f"waited {g.waits} clock reads sorted={ids == sorted(ids)}")
i = ids[-1]
print("decode last id: ms", (i >> 22) - 1000,
"after start, worker", (i >> 12) & 0x3FF, "seq", i & 0xFFF)
print(f"ids per worker per second: {4096 * 1000:,}")
print(f"41-bit ms lasts {2**41 / 1000 / 86400 / 365.25:.1f} years")Output
guard=False ids=14 duplicates=4 waited 0 clock reads sorted=False
guard=True ids=14 duplicates=0 waited 3 clock reads sorted=True
decode last id: ms 12 after start, worker 7 seq 0
ids per worker per second: 4,096,000
41-bit ms lasts 69.7 years Without the guard, four ids were duplicates. With it, the generator noticed the clock was behind the last timestamp it used, waited until the clock caught up, and produced no duplicates and correctly sorted ids. The policy should depend on the size of the step:
- Small step (a few ms): wait, as above. Generation pauses briefly; nothing breaks.
- Large step (seconds or more): waiting would stall the service, so refuse to issue ids, raise an alert, and let the instance be taken out of rotation. Some designs instead keep using the last timestamp and advance it artificially, borrowing from the future, which keeps ids unique but drifts from real time.
- Prevention: configure NTP to slew (adjust the clock gradually) rather than step, so backwards jumps become rare ( Time and clocks ).
Deep dive 3: Ordering and what ids reveal
Ids from one worker are strictly increasing. Across workers they are only roughly ordered, because clocks differ by a few milliseconds and ids within the same millisecond are ordered by worker id, not by real arrival. That is fine for "newest first" feeds and pagination by id ( Pagination patterns ), but not for anything that needs a true global order, such as a ledger sequence or the order book of an exchange ( Design a stock exchange / order matching engine ), which use a single sequencer instead.
Ids also leak information: anyone can decode the creation time, and watching ids over time reveals roughly how many you create. Use them as database keys, not as secrets, and use random tokens wherever guessing an id must be impossible.
Try it
Try this:
- Press Generate 3 in same ms. Which field changes, and how many ids could you make in this millisecond?
- Change the machine id and generate again in the same millisecond. Does the new id sort after the previous one? Why is ordering across machines only rough?
- Switch to the Instagram-style layout. What did it trade between shard bits and sequence bits, and when would you choose that split?
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| Two instances share a worker id | Duplicate ids | Create-if-absent leases; stop when the lease is lost |
| Clock steps back a few ms | Duplicates if unguarded | Wait until the clock passes the last timestamp |
| Clock steps back seconds | Long stall | Refuse, alert, remove the instance; NTP slewing |
| Sequence exhausted in a ms | Generator would wrap | Wait for the next millisecond |
| Coordination store down | New instances cannot start | Existing leases keep working; long enough lease TTL |
| Process paused past its lease | Possible duplicate worker | Check lease expiry before issuing; quarantine released ids |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Snowflake-style 64-bit (chosen) | Compact, local, time-sortable, millions per second per worker | Needs worker id assignment and clock discipline |
| UUIDv4 | No coordination at all, unguessable | 128 bits, random order hurts index locality |
| Central ticket server | Strictly increasing, simple | A network call and a bottleneck on every id |
| Library over service (chosen) | No network hop, nothing extra to keep running | Every language needs an implementation |
Extensions
- Embedding the shard id in the id so a router knows where a row lives without a lookup.
- Multi-region: reserve a few worker id bits for the region so regions never need to coordinate.
- Time-ordered UUIDs (UUIDv7) when 128 bits are acceptable and you want no worker ids at all.
In the wild
Where you will see this: social networks and messaging apps use Snowflake-style 64-bit ids for posts and messages, and many databases and frameworks ship time-ordered id generators. The well-documented examples, Twitter's Snowflake and Instagram's sharded variant, are covered with their sources in Generating unique IDs at scale .
Check yourself
-
How long do 41 bits of milliseconds last?
Show answer
B. About 70 years 2^41 ms is about 69.7 years, which is why the epoch is set to the system's start date.
-
Why must an instance stop issuing ids if it cannot renew its worker id lease?
Show answer
B. Another instance may claim the same worker id and produce duplicates The lease is the only thing that makes the worker id exclusive; without it two generators could collide.
-
The clock steps back 3 ms. What should the generator do?
Show answer
B. Wait until the clock passes the last timestamp it used Reusing earlier timestamps can repeat (timestamp, sequence) pairs; a short wait avoids that.
-
You need 2,000 instances. What is the simplest change to the layout?
Show answer
B. Move one bit from the sequence to the worker id 11 worker bits give 2,048 workers and 11 sequence bits still allow about 2 million ids per second per worker.
Recap
- Split 64 bits into time, worker and sequence; size each field from the requirements.
- Generate ids in-process; coordinate only to claim a worker id.
- Lease worker ids with create-if-absent and stop if the lease is lost.
- Guard against backward clock steps: wait for small ones, refuse and alert on large ones.
- Ids are only roughly ordered across workers and reveal creation time; do not use them as secrets.
Next up
- Crack the system design round learning path