Snowflake 64-bit ID Generator

This lab generates unique 64-bit ids at millions per second per process. The ids sort roughly by creation time, and generating one needs no coordination with other processes. Workers only need to agree on a worker id when they start.

Where it shows up

• Primary keys for sharded databases: auto-increment only works on a single primary, and random UUIDv4 keys fragment B-tree indexes. Time-ordered ids append to the right edge of the index.
• Public object ids: tweets, Discord messages, Instagram media, Mastodon statuses.
• Event and log ids: they sort by time without needing a separate timestamp column, and you can pull the creation time back out of the id.
• Cursor pagination: an id that is ordered by time works as a stable cursor on its own (see the keyset-pagination lesson).

Layout

63 | 62 ....................................... 22 | 21 ...... 12 | 11 ...... 0
  0 |      41 bits: ms since custom epoch           | 10: worker   | 12: sequence
    |      2^41 ms ≈ 69.7 years                     | 1024 workers | 4096 ids/ms

id = (now - epoch) << 22 | workerId << 12 | sequence. The top bit stays 0, so ids fit a signed int64 (Java long, Postgres BIGINT). Everything here is BigInt, because JS Number is exact only up to 2^53. Demo step 6 shows a real id losing its low bits. Send ids to clients as decimal strings. Twitter's API added id_str for this reason.

Algorithm and invariants

now = clock()
if now < last:                              # clock went backwards
    if last - now > tolerance: throw ClockRollbackError
    spin until clock() >= last
if now == last:
    seq = (seq + 1) & 4095
    if seq == 0: spin until clock() > last  # 4096 ids already issued this ms
else:
    seq = 0
last = now
return compose(now, worker, seq)

1. Unique per worker. For a fixed (timestamp, worker), the sequence values are distinct. The timestamp never goes backwards, because a rollback is either waited out or refused.
2. Strictly increasing per worker. The timestamp is non-decreasing and the sequence increases within a millisecond.
3. *Unique globally, if worker ids are unique among live processes. This is the one piece of coordination the scheme needs. Worker ids are usually handed out by ZooKeeper or etcd leases, a DB table, or a Kubernetes StatefulSet ordinal.
4. K-sorted across workers. Ids are ordered by millisecond. Within the same millisecond, the worker id breaks ties, not the true issue order (demo step 3). Clock skew between machines blurs ordering by that many milliseconds.

Clock rollback. NTP can step* a clock backwards, and restoring a VM from a snapshot can move it back by hours. Issuing ids with a past timestamp could repeat (ts, seq) pairs that were already handed out. A small drift (at most rollbackToleranceMs, default 5) is waited out. A larger drift throws ClockRollbackError, and the caller should fail over or alert. Twitter's original implementation refused all rollbacks.

Complexity

• nextId: O(1) amortized. In the worst case it spins for up to 1 ms when the sequence overflows, or up to tolerance ms on a rollback.
• decode / compose: O(1). Space: O(1) per generator.
• Throughput ceiling: 4096 ids/ms per worker, about 4.1M/s. Across all 1024 workers that is about 4.2 billion ids/s.

Failure modes and trade-offs

• Duplicate worker ids. Two processes sharing a worker id will collide within the same millisecond. This is the most common real-world bug. Use leases that expire, and fence them.
• Restart inside the same millisecond. A process that restarts and reuses its worker id right away could reissue ids from its last millisecond. Keep a persisted high-water mark, or wait for at least one tolerance window on startup.
• Busy-waiting. The spin burns CPU. An async generator could await the next tick instead, at the cost of latency jitter.
• Information leakage. Ids reveal creation time, which shard or worker issued them, and roughly how many ids that worker issues. Don't expose them where that is sensitive.
• Low traffic means sequence 0 most of the time. If you shard by id % N, the shards will be badly skewed. Hash the id first.
• Bit budget. More worker bits leave fewer sequence bits or less lifetime. Choose the split for your fleet size and peak rate per worker.

How production systems do it

• Twitter Snowflake (2010): a Scala Thrift service using this exact 41/10/12 split, where the 10 bits were 5 datacenter plus 5 worker. It used the epoch 1288834974657, claimed its configured worker id in ZooKeeper at startup, and refused to issue ids while the clock was behind the last timestamp.
• Discord: 42-bit ms timestamp from epoch 2015-01-01, 5-bit worker, 5-bit process, 12-bit increment. Anyone can decode message creation times from the ids.
• Instagram: generates ids inside PostgreSQL with PL/pgSQL. The layout is 41-bit ms, 13-bit logical shard id, and 10-bit per-shard sequence (nextval % 1024), so an id also encodes where its row lives.
• Sonyflake: 39 bits of 10 ms units (about 174 years), 8-bit sequence and 16-bit machine id. It trades throughput (256 ids per 10 ms) for lifetime and number of machines.
• Baidu UidGenerator: seconds-resolution timestamp. Its CachedUidGenerator pre-fills a ring buffer and "borrows" future seconds to absorb bursts.
• UUIDv7 (RFC 9562, 2024): a 48-bit Unix-ms timestamp plus random bits in 128 bits. It sorts by time like Snowflake but needs no worker id, at the cost of being twice as wide.

Extension exercises

1. Add a lease-based worker id allocator. It claims workerId from a shared table with a TTL and renews it. What must the generator do if renewal fails?
2. Persist a high-water mark (last ms) to a file in os.tmpdir() every second. On startup, refuse to issue ids until clock() > mark. Test it with a simulated restart.
3. Make the layout configurable, for example Sonyflake's 39/8/16 with 10 ms ticks. Keep decode and compose consistent, and add a test that the lifetime is about 174 years.
4. Implement "borrow the future": within the tolerance, keep issuing ids at lastMs instead of waiting. When is this safe, and what breaks if the process restarts before real time catches up?
5. Write a UUIDv7 generator with a monotonic counter (RFC 9562 method 1) and compare index-insert locality against UUIDv4 in a simple sorted-array model.