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
Get ID: the Tweet Service asks a generator for a new id and gets it back with 200. Ids are 64-bit, unique across all generators, and roughly ordered by time.
Start generator: a generator process starts and claims a worker id that no other running generator has, by writing to ZooKeeper (zk), before it serves any id.
Use these use case names exactly: the traffic, requirements and tests in problem.proschi refer to them.
Scale
Tens of thousands of ids a second: 20k rps at peak. Twitter's own requirement was at least 10k ids a second per process.
Generators start rarely: about one a minute across the fleet.
Constraints
No shared counter: making an id never calls a database, a cache or ZooKeeper. Coordination happens once per process, at startup.
p99 of Get ID under 40 ms. Twitter asked for 2 ms per id plus the network; the simulation's services are slower, so the limit is set for them.
Get ID available 99.99% of the time ("highly available" was a requirement).
Losing any single machine must not stop id generation.
At most $4,000 / month, the existing ZooKeeper cluster and Tweet Service included.
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
Ryan King, Announcing Snowflake, Twitter Engineering, June 2010: the requirements (at least 10k ids per second per process, 2 ms per id, roughly sortable, highly available) and the design (timestamp, worker number and sequence; ZooKeeper for worker numbers).
twitter-archive/snowflake, the original code: 41 bits of milliseconds, 10 bits of worker id, 12 bits of sequence.
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.
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:
Unique across every machine that makes them.
64 bits, so they fit in a long integer everywhere (128-bit UUIDs were too big for their systems).
Roughly sortable by time: tweets posted around the same moment get nearby ids, because timelines and APIs like "tweets since id X" sort by id.
Fast and highly available: at least 10k ids per second per process, about 2 ms each plus network, and never the reason a tweet can't be posted.
Their answer was Snowflake, a small service that makes ids from the clock. You build it here.
Two use cases:
Get ID: the Tweet Service asks a generator for an id and gets it with 200.
Start generator: a starting generator claims a worker id no other running generator holds, by writing to ZooKeeper, before serving any id.
The non-functional requirements:
Scale: 20k ids per second at peak. Generators start about once a minute across the fleet.
No shared counter: making an id never calls a database, a cache or ZooKeeper.
Latency: p99 of Get ID (the time 99% of requests beat) under 40 ms, looser than Twitter's 2 ms because the simulation's services are slower.
Availability: Get ID up 99.99% of the time.
Fault tolerance: losing any single machine doesn't stop id generation.
Budget: $4,000 a month, including the existing ZooKeeper cluster.
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:
An id is made without a round trip to shared storage: Get ID starts at tweets and never calls any database or cache.
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.
What a shared counter would face, with the simulation's per-replica defaults:
Design
Where every id goes
Capacity
Load / capacity
Ticket table in MySQL
the one primary (writes)
5,000 writes/s per shard
20,000 / 5,000 = 400%
Counter in Redis
one counter key
100,000 ops/s
20%, but a round trip and a dependency per id
Snowflake
nowhere: 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:
Latency. Get ID is a single hop, caller to generator, about 10 ms idle. The 40 ms p99 catches queueing (a fleet run too hot, or a saturated MySQL primary) and a slow extra round trip (asking ZooKeeper per id). A 1 ms Redis hop slips under it, which is why a flow test, not the latency limit, forbids shared storage.
Availability. One service replica is up 99.5% in the model, far short of 99.99%. Two give 99.9975%; a fleet is effectively always up, because any generator can answer.
Cost. About $100 per service replica per month. The given nodes count too: ZooKeeper's three at about $400 each and the Tweet Service's four at $100 each, $1,600 before you add anything. That leaves $2,400 for generators.
What it is. A Snowflake id is a 64-bit integer built from three fields:
Bits
Field
Meaning
1
sign
always 0, so the id is positive
41
timestamp
milliseconds since a custom epoch
10
worker id
which generator made it
12
sequence
counter 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] x3gen "ID Generator"[gRPC] x3 "time | worker | sequence, all in memory"caller -> gen : RPCusecase"New id" { caller -> gen : GET next id gen --> caller : 200 {"id": 7194012332411158528}}
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:
An ephemeral node disappears automatically when the session of the process that created it ends (its connection to ZooKeeper, kept alive by heartbeats). Created under a path like /snowflake/workers/, the claim lives while the process lives; if it dies, the worker id is released for reuse.
A sequential node gets a unique, increasing suffix, a convenient way to hand out numbers. In practice you'd map it into the 0–1,023 range, or try to create /workers/<n> for the lowest free n.
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.
Every 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 proven
A round trip per id; ordering across the two is only approximate
Block allocation
Each server claims a block of, say, 10,000 numbers from a central counter
One round trip per block, not per id
Not time-ordered across servers
Random UUIDs (version 4)
Random 128 bits
No coordination at all
No time order; inserts land in random index places
Time-ordered UUIDs (such as UUIDv7)
Time plus randomness
No coordination, sorts by time
Still 128 bits
Instagram's variant
Time, logical shard id and sequence, made inside each PostgreSQL shard
The composite idea without a separate service
Lives 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:
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.
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).
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.
"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.
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.
"What if the clock goes backwards?" Refuse to generate until the clock catches up (or wait if it's a few milliseconds), alert, and run NTP in slew mode.
"What if two processes get the same worker id?" They could produce duplicates. That's why claims are ephemeral nodes in a strongly consistent store, and why a process that loses its session must stop serving.
"How many ids per second can one worker make?" Up to 4,096 per millisecond, about 4 million per second, before it waits for the next millisecond.
"When do you run out?" 41 bits of milliseconds last about 70 years from the custom epoch.
"Can clients tell when an id was created?" Yes: shift right by 22 bits and add the epoch. Fine for tweets; for private objects, a leak.
"Could you skip the service and generate ids in the caller?" Yes, as a library, if each caller process gets a unique worker id; Instagram did it inside the database. A service is easier to version and monitor.
Sharding & IDs at Instagram: the composite-id idea inside PostgreSQL shards, with a comparison of the alternatives.
System Design Interview – An Insider's Guide, Vol. 1 (Alex Xu), chapter "Design A Unique Id Generator In Distributed Systems": the interview-format comparison of these approaches.