System design practice

Snowflake IDs

easy Based on a system published by Twitter id-generation coordination availability real-world

Unique, time-ordered ids at 20k a second with no central counter.

Solve it in your browser Read the lesson first

In 2010 Twitter was moving tweets from MySQL to Cassandra, which has no auto-increment. They needed a service that hands out ids that are unique, fit in 64 bits, and are roughly sortable: two tweets posted at about the same time get ids close to each other, because that is how Twitter and its clients sort tweets. The answer was Snowflake.

Build it: a fleet of id generators that the Tweet Service calls for every new tweet.

Functional requirements

Use these use case names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

What is given

problem.proschi declares the tweets service (the caller, four replicas) and zk, a three-node ZooKeeper cluster that already exists. Add the generators, the connections and the two use cases.

Based on

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 13 min read

Learn it: Snowflake IDs #

What you'll learn #

The problem, explained #

In 2010 Twitter moved tweets from MySQL, which handed out ids with auto-increment, to Cassandra, which has no such thing (any node can take a write). It needed a new source of ids with four properties:

Their answer was Snowflake, a small service that makes ids from the clock. You build it here.

Two use cases:

The non-functional requirements:

given.proschi fixes the caller, tweets (four replicas), and zk, an existing three-node ZooKeeper cluster. Both are on your bill. You add the generators, connections and both use cases.

The tests, in plain words:

  1. An id is made without a round trip to shared storage: Get ID starts at tweets and never calls any database or cache.
  2. Each generator claims its worker id once, at startup: Start generator calls zk and writes to it before responding, and Get ID never calls zk.

Back-of-the-envelope #

ids at peak
20,000 / s
of 41-bit millisecond timestamps
≈ 69.7 years
workers addressable with 10 bits
1,024
ids per worker per millisecond
4,096
the writes one MySQL primary can take
4×
QuantityArithmeticResult
Ids per secondgiven20,000
Ids per day20,000 × 86,400≈ 1.7 billion
Time range of 41 bits of milliseconds2⁴¹ ms ÷ (1000 × 3600 × 24 × 365)≈ 69.7 years
Workers addressable with 10 bits2¹⁰1,024
Ids per worker per millisecond (12-bit sequence)2¹²4,096
Ids per worker per second, theoretical4,096 × 1,000≈ 4 million
Generator starts1 per minute≈ 0.017 per second

What a shared counter would face, with the simulation's per-replica defaults:

DesignWhere every id goesCapacityLoad / capacity
Ticket table in MySQLthe one primary (writes)5,000 writes/s per shard20,000 / 5,000 = 400%
Counter in Redisone counter key100,000 ops/s20%, but a round trip and a dependency per id
Snowflakenowhere: made in memory——

MySQL gets four times the writes it can take, and replicas don't help: all writes go through one primary. Redis survives the load but still puts a shared component in the path of every tweet.

The generators themselves are services. A [gRPC] service handles about 2,000 rps per replica in the simulation, so 20,000 rps needs at least 10 replicas just to reach 100%: saturation, not a design. Keep the fleet well below 70% busy, and remember that survive any node failure removes one replica and re-checks that nothing saturates and p99 still holds. (Real Snowflake processes are far faster: Twitter asked for 10k ids per second each; the model's services are deliberately generic.)

Other numbers in the Analysis tab:

Concepts #

Composite ids: time + worker + sequence #

What it is. A Snowflake id is a 64-bit integer built from three fields:

BitsFieldMeaning
1signalways 0, so the id is positive
41timestampmilliseconds since a custom epoch
10worker idwhich generator made it
12sequencecounter within the current millisecond

(The original code splits the 10 worker bits into 5 bits of datacenter and 5 of worker: the same idea.)

Why it's unique without coordination. Ids from different workers differ in the worker field. Ids from the same worker differ in the timestamp or, within one millisecond, in the sequence. A worker that uses all 4,096 sequence values in a millisecond waits for the next one. Nothing needs another machine.

Why it sorts by time. The timestamp is in the high bits, so comparing ids compares times first. Ids from different workers in the same millisecond are ordered by worker id, not by the real order of events. That's roughly (or k-sorted): sorted to within the clock skew between machines.

Trade-offs. It depends on clocks: if NTP (the protocol that keeps machine clocks in sync) steps a clock backwards, a worker could repeat timestamps, so the original Snowflake refuses to make ids until the clock passes the last timestamp it used. Ids also leak the creation time, and roughly how busy a worker is.

When not to use it. When ids must be unguessable (use random tokens), strictly ordered (you need a single sequencer), or dense with no gaps (invoice numbers).

title "Local id generation"

caller "Order Service" [REST API] x3
gen    "ID Generator"  [gRPC]     x3 "time | worker | sequence, all in memory"

caller -> gen : RPC

usecase "New id" {
  caller -> gen    : GET next id
  gen   --> caller : 200 {"id": 7194012332411158528}
}

Coordinate once, at startup #

What it is. The only thing two generators must never share is the worker id. So a process claims one from a coordination service once, when it starts, and keeps it for its lifetime. Every id after that is made in memory.

Why ZooKeeper. ZooKeeper is a small, strongly consistent store built for exactly this kind of agreement:

Trade-offs. If ZooKeeper is down, new generators can't start, but running ones keep serving: coordination is off the hot path, so its outages and latency don't touch tweets. The risk is a process that loses its session but keeps running: it must stop serving ids, or another could claim the same worker id.

title "Claim at startup"

worker "Worker"      [gRPC]      x3
coord  "Coordinator" [ZooKeeper] x3

worker -> coord : claim slot

usecase "Boot" {
  worker -> coord  : CREATE /workers/ ephemeral sequential
  coord --> worker : slot 12
}

The usual alternatives #

Interviewers like to see you weigh options first:

ApproachHowUpsideCost
Auto-increment in one databaseOne table's counterSimple, dense, strictly orderedEvery id is a write to one primary: a throughput ceiling and a single point of failure
Ticket servers (Flickr's approach)A MySQL table that only auto-increments, often on two servers with interleaved sequences (one odd, one even)Cheap and provenA round trip per id; ordering across the two is only approximate
Block allocationEach server claims a block of, say, 10,000 numbers from a central counterOne round trip per block, not per idNot time-ordered across servers
Random UUIDs (version 4)Random 128 bitsNo coordination at allNo time order; inserts land in random index places
Time-ordered UUIDs (such as UUIDv7)Time plus randomnessNo coordination, sorts by timeStill 128 bits
Instagram's variantTime, logical shard id and sequence, made inside each PostgreSQL shardThe composite idea without a separate serviceLives in the database

When to pick something other than Snowflake. If a few thousand ids per second is all you'll ever need, a ticket server is simpler to run. If ids never need to sort, UUIDs need no infrastructure at all.

Deep dive A ticket server pair in Proschi

For comparison, a ticket server pair puts a store on every id:

title "Ticket servers"

app  "App"           [REST API] x4
odd  "Tickets odd"   [MySQL]    x1 "auto_increment_offset 1, increment 2"
even "Tickets even"  [MySQL]    x1 "auto_increment_offset 2, increment 2"

app -> odd  : SQL
app -> even : SQL

usecase "New id" {
  app  -> odd : REPLACE INTO Tickets64
  odd --> app : LAST_INSERT_ID()
}

Designing it step by step #

Step 1: Scope #

Pin the properties: unique, 64-bit, roughly time-ordered, fast, highly available. Ask how strict the ordering is ("within a second is fine" unlocks the design), whether gaps are allowed (yes), and how many generators you might run (under a thousand fits 10 bits). Note the scale: 20k ids per second.

Step 2: High-level design #

Start from the simplest thing that works and break it on purpose: "Auto-increment works, but 20k writes a second to one primary is four times the 5k it takes, and it's a single point of failure." Try Redis INCR: fast enough, but every tweet now depends on one key on one cache, and a failover with asynchronous replication can hand out the same number twice.

Then introduce the composite id. The Tweet Service calls the generators directly; any generator can answer any request, so no load balancer is needed. Connect the generators to ZooKeeper and write two use cases: Get ID (one hop, made in memory) and Start generator (one write to ZooKeeper).

Step 3: Deep dive #

The bit layout. Walk through the 41/10/12 split and the arithmetic above. A custom epoch (say 2010 instead of 1970) keeps 41 bits useful for decades longer.

Sequence overflow. A worker that hands out 4,096 ids in one millisecond waits for the next. At 20k ids per second spread over a fleet, that never happens; say so.

Clocks. Run NTP, configured to slew (slow the clock down until it is right) rather than step backwards, and have the generator refuse to make ids if its clock is behind the last timestamp it used: a brief error for callers, never a duplicate.

Worker ids. Claimed in ZooKeeper at startup with an ephemeral node; released when the process dies. In Start generator, the write to zk comes before the generator responds (or serves anything).

Sizing. Divide 20k rps by the per-replica capacity, add headroom to stay well below 70%, and recheck with one replica gone. Then read the Analysis tab: p99 of Get ID under 40 ms, utilisation, and the total against $4,000 with ZooKeeper.

Step 4: Wrap up #

"Each generator claims a worker id from ZooKeeper once, then makes ids from its clock, its worker id and a per-millisecond sequence. No shared state on the hot path: any generator can answer, ZooKeeper can be down without stopping ids, and ids sort by time to within clock skew." Then list what you'd watch: clock drift, sequence exhaustion (it shouldn't happen), worker id reuse after a crash.

Common mistakes #

The ticket table in MySQL (wrong/ticket-table-in-mysql). Every id is an auto-increment row on one primary: fine at a few thousand ids per second, and Flickr ran it for years. At 20k per second it saturates: the primary takes about 5k writes per second in the model, and read replicas add no write capacity. Caught by An id is made without a round trip to shared storage and p99 of Get ID < 40 ms.

Asking ZooKeeper on every id (wrong/coordinates-every-id). The generator checks "is worker 37 still mine?" before each id. Correct, but the coordination cluster is now on the hot path: each id waits for a ZooKeeper round trip, and any hiccup (a leader election, a slow disk) stalls tweet creation across the company. Caught by Each generator claims its worker id once, at startup; it also fails the p99 limit and the shared-storage test (ZooKeeper is a store).

One generator (wrong/one-generator). A single process is a single point of failure, and at 20k rps it's saturated anyway. Caught by survive any node failure; it also fails p99 and the 99.99% availability target.

Random UUIDs. Not a wrong design here (the tests can't see id formats), but a wrong interview answer: 128 bits breaks the 64-bit requirement, and random ids don't sort by time.

In the interview #

Follow-up questions:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems