Design a Unique ID Generator (Snowflake, ULID, TSID, UUIDv7)

TL;DR. A unique ID generator hides a four-way trade-off between throughput, ordering, coordination cost, and ID width. Twitter Snowflake packs 41 bits of millisecond timestamp, 10 bits of machine ID, and 12 bits of sequence into 64 bits, yielding 4,096 IDs per ms per worker with zero hot-path coordination^[1]. UUIDv7 (RFC 9562, 2024) spends 128 bits to get the same time-ordering without a worker-ID registry^[2]. The pivotal decision: if 64 bits matters (halved index size at a billion rows), use Snowflake; if zero coordination matters more, use UUIDv7.

Learning Objectives#

• Defend a choice between Snowflake, ULID, UUIDv7, TSID, and a ticket server on specific workload criteria
• Compute the timestamp-exhaustion date and per-worker throughput ceiling from a Snowflake bit layout
• Design clock-skew resilience (bound-wait, logical-clock fallback, NTP alerting) for a distributed ID generator
• Justify why time-sortable IDs improve B-tree insert performance by 12-27x over random UUIDs^[3]
• Design worker-ID allocation across multiple data centers without coordination at ID-generation time

Intuition#

Generating a unique ID looks trivial. Call uuid.v4() and move on. At 10 users, that works. At 10 million IDs per second across three data centers, it collapses for two reasons.

First, random UUIDs destroy your database. A credativ benchmark on PostgreSQL 18 measured 50 million UUIDv4 inserts into a pre-populated table at 46 minutes wall time. The same workload with time-ordered UUIDv7 finished in 1 minute 40 seconds^[3:1]. The v4 index was 26% larger with 50% leaf fragmentation versus zero for v7^[3:2]. Random keys scatter inserts across the entire B-tree; time-ordered keys concentrate writes at the rightmost leaf.

Second, coordination kills throughput. A single auto-increment counter caps you at one database's insert rate. A distributed counter (Raft consensus per ID) adds milliseconds of latency to every write. The insight that unlocks the design: embed time in the high bits so IDs are naturally ordered, embed a machine identifier in the middle bits so workers never collide, and use a local sequence counter in the low bits so each worker generates thousands of IDs per millisecond without talking to anyone.

That is Snowflake. The rest of this chapter is about when to use it, when to use something else, and what breaks when clocks misbehave.

Requirements#

Clarifying Questions#

• Q: What is the target aggregate throughput? Assume: 10M IDs/sec aggregate, 100K IDs/sec per single worker at peak.

• Q: Must IDs fit in 64 bits? Assume: 64 bits preferred (fits in BIGINT, halves index size vs 128-bit). UUIDv7 is acceptable if 128 bits is tolerable.

• Q: How long must the scheme last? Assume: At least 69 years from a custom epoch (Snowflake's 41-bit millisecond timestamp gives exactly this)^[4].

• Q: Strictly monotonic or approximately ordered? Assume: Monotonic within a single worker. Globally ordered within clock-skew bounds. Strict global monotonic only for specific flows (audit logs, invoice numbers).

• Q: Multi-region active-active? Assume: Yes, 3 regions. No coordination on the hot path.

• Q: Can we rely on NTP-synced clocks? Assume: Yes within ~10 ms, but the design must survive a 1-second backward jump without duplicating IDs.

Functional Requirements#

• Generate a unique 64-bit ID on every call with no coordination on the hot path.
• Embed a millisecond timestamp recoverable from the ID for debugging, TTL enforcement, and time-range sharding.
• Survive a single worker crash without duplicating any previously issued ID.
• Support rolling worker redeployment with safe worker-ID reassignment.

Non-Functional Requirements#

• Availability: 99.999% on the generate path (called inline with every write).
• Latency: p99 under 1 ms local, under 5 ms including a network hop if run as a service.
• Throughput: 10M IDs/sec aggregate, 100K/sec per worker.
• Uniqueness: zero duplicates under any single-node failure, including clock rewind up to 10 seconds.
• Ordering: monotonic within a single worker; globally ordered within worker-clock-skew.

Capacity Estimation#

With 100 active workers each handling ~100K IDs/sec, the system runs at 2.4% of its theoretical ceiling. Three orders of magnitude of headroom before a layout redesign is needed.

API and Data Model#

API Design#

# Local library call (preferred for latency)
id = snowflake.next_id()   # returns int64

# Remote service (for polyglot environments)
POST /v1/ids:generate
Body: { "count": 100 }
Response: { "ids": [7234567890123456789, ...], "issued_at_ms": 1735689600000 }

# Bulk-allocation for batch jobs
POST /v1/ids:reserve-range
Body: { "count": 1000000 }
Response: { "start": 7234..., "end": 7234..., "ttl_ms": 60000 }

The library form is the hot path. The service form serves Ruby, PHP, and short-lived Lambdas that cannot safely hold a worker-ID. The range-reservation API amortizes network round-trips for ETL and backfill jobs.

Data Model#

-- Worker state (local, persistent file)
last_timestamp_ms   BIGINT   -- last ms we issued in
last_sequence       INT      -- last sequence within that ms
worker_id           INT      -- assigned at startup
custom_epoch_ms     BIGINT   -- e.g. 2020-01-01 UTC in ms

-- Worker-ID registry (ZooKeeper / etcd)
-- Path: /id-gen/workers/{worker_id}
-- Value: { "hostname": "...", "dc": "us-east-1", "lease_expires_at": "..." }
-- Ephemeral node with 30-second TTL

On startup, a worker claims the lowest free slot via an ephemeral ZooKeeper node^[1:3]. On graceful shutdown, the node is released. On crash, the lease expires and the slot becomes reclaimable.

High-Level Architecture#

flowchart LR
    subgraph Clients["Application Services"]
        A[Service A]
        B[Service B]
        C[Service C]
    end
    subgraph IDGen["ID Generator (library mode)"]
        direction TB
        G1[Generator<br/>worker_id=1]
        G2[Generator<br/>worker_id=2]
        G3[Generator<br/>worker_id=3]
    end
    subgraph Coord["Coordination (boot only)"]
        ZK[(ZooKeeper / etcd)]
    end
    subgraph Fallback["Strict-Monotonic Fallback"]
        T1["Ticket Server 1<br/>offset=1, incr=2"]
        T2["Ticket Server 2<br/>offset=2, incr=2"]
    end
    A --> G1
    B --> G2
    C --> G3
    G1 -.->|startup lease| ZK
    G2 -.->|startup lease| ZK
    G3 -.->|startup lease| ZK
    A -.->|audit logs only| T1
    A -.->|audit logs only| T2

Each application service embeds a Snowflake generator as a library. ZooKeeper is consulted once at boot for worker-ID assignment; the hot path is lock-free. The ticket-server fallback handles the rare flows requiring strict monotonicity.

Library mode (default): The ID generator is a JAR, crate, or Go package linked into every service. It reads worker-ID from ZooKeeper at boot. The hot path is a single CAS on (timestamp, sequence).

Service mode (polyglot): A small fleet of "id-service" pods sits behind a load balancer. Each pod holds its own worker-ID. Clients batch-request 100 IDs per call to amortize RPC overhead.

Ticket-server mode (strict monotonic): A MySQL primary with a single-row table using REPLACE INTO to advance an auto-increment^[8]. Used only for invoice numbers, audit logs, and customer-facing ticket IDs where strict ordering is a hard requirement.

Observability: Emit metrics for ids_per_second_per_worker, clock_drift_ms, sequence_exhaustion_events, and worker_id_reassignments.

Deep Dives#

Snowflake bit-layout anatomy#

The 64-bit Snowflake ID is a capacity-planning exercise encoded in a single integer.

The 1+41+10+12 bit partition: each field is packed and extracted by shift-and-mask. The sign bit keeps the ID positive as a signed BIGINT.

Construction is three shifts and two ORs: id = ((now_ms - epoch) << 22) | (worker_id << 12) | sequence^[4:2]. Extraction is equally cheap: timestamp = (id >> 22) + epoch^[7:1].

Twitter's epoch is 1288834974657 ms (2010-11-04T01:42:54.657Z)^[5:1][6:1]. This gives Twitter IDs until approximately 2080. Discord uses epoch 1420070400000 (2015-01-01), extending exhaustion to ~2084^[7:2].

Instagram's variant reallocates bits: 41 timestamp + 13 shard-ID + 10 sequence^[9]. The shard-ID in the ID means reading an ID tells the application which PostgreSQL shard to query without a metadata lookup. The trade-off: per-shard ceiling drops to 1,024 IDs/ms (10 sequence bits) versus Snowflake's 4,096^[9:1].

Sonyflake uses 39 bits at 10-ms resolution (174-year lifetime), 8 bits of sequence (256 per 10 ms = 25,600/sec/machine), and 16 bits of machine-ID (65,536 machines)^[10]. It derives machine-ID from the lower 16 bits of the private IPv4 address, which is globally unique within an AWS VPC assigned a /16 CIDR^[10:1].

Clock-skew resilience#

Clock skew (a backward jump) is the failure mode, not clock drift (a slow clock). When NTP steps time backwards, a naive generator can issue duplicate IDs or produce an out-of-order sequence^[1:4][2:1].

RFC 9562 section 6.2 defines three monotonicity methods^[2:2]:

1. Fixed-length counter seeded at random per new timestamp tick.
2. Monotonic random that increments by a random delta when the timestamp has not advanced.
3. Sub-millisecond fraction replacing the top random bits with a clock fraction.

For Snowflake-style generators, production systems combine two strategies:

Bound-wait: If now_ms < last_timestamp_ms and the delta is small (under 10 ms), sleep until time catches up. This is the pattern used by later derivatives such as Baidu's uid-generator and Meituan's Leaf; Twitter's original IdWorker.scala instead takes the stricter "refuse to issue" path described below^[1:5].

Logical-clock fallback: Treat last_timestamp_ms as a Lamport-style monotonic counter. If the wall clock went backwards, keep incrementing the stored timestamp and sequence. IDs remain unique and ordered, though the embedded timestamp is slightly ahead of reality.

Refuse to issue: If skew exceeds a threshold (e.g., 10 seconds), fail fast and alert. A generator that loops on "wait for time to advance" could deadlock during a large backward jump. Twitter's original IdWorker.scala takes this path unconditionally: on any backward jump it throws InvalidSystemClock with the message "Clock moved backwards. Refusing to generate id for N milliseconds"^[1:6].

The 2012 leap-second event is the canonical real-world anchor. On June 30, 2012, a leap-second insertion livelocked Linux kernels at Reddit, LinkedIn, and multiple Cassandra clusters^[11][12]. Systems relying on clock_gettime hung or produced out-of-order timestamps. Any Snowflake-like generator built on that kernel was vulnerable.

Detection: Monitor clock_drift_ms = now_ms - last_timestamp_ms. Alert on negative values or deltas exceeding 1 second.

ULID handles monotonicity differently: within the same millisecond, the 80-bit random component increments by 1 at the least significant bit^[13]. This guarantees sort order without a worker-ID registry. The trade-off: if the random component overflows (2^80 IDs in one ms, practically unreachable), the generator throws rather than silently wrapping^[13:1].

Worker-ID allocation across data centers#

The 10-bit worker-ID field supports 1,024 concurrent generators. Assigning these without collision is the one coordination problem in the system.

Four patterns are in production use:

1. ZooKeeper ephemeral nodes: First-come-first-served claim with a lease. Originally used by Twitter's Snowflake^[1:7][4:3]. On startup, claim the lowest free slot. On crash, the lease expires (30-second TTL) and the slot is reclaimable.

2. Kubernetes StatefulSet ordinal: Pod id-gen-0 gets worker-ID 0, id-gen-1 gets 1. Zero external coordination, but only works for dedicated ID-service deployments.

3. IP-derived (Sonyflake): Lower 16 bits of the private IPv4 address. Works inside an AWS VPC with a /16 CIDR because the low 16 bits are then unique across the VPC^[10:2]. No external service needed.

4. Environment variable / static config: Hardcoded in a deployment manifest. Simple but fragile; a typo silently causes collisions. TSID's library reads TSIDCREATOR_NODE from the environment and falls back to random if unset^[14].

The 5+5 bit split (5 datacenter + 5 worker) supports 32 DCs with 32 workers each. An alternative 3+7 split supports 8 DCs with 128 workers each. Choose based on your deployment topology.

Lease-based reclamation is critical for blue-green deployments. With 1,024 slots and 50 Kubernetes clusters doing rolling updates, short TTLs (30 seconds) ensure retired workers release their IDs before new workers need them^[4:4].

UUIDv7 versus Snowflake: the modern choice#

UUIDv7, standardized by RFC 9562 in May 2024^[2:3], is a 128-bit time-ordered UUID: 48 bits of Unix ms timestamp, 4-bit version, 12 bits of rand_a (often a monotonic counter), 2-bit variant, and 62 bits of rand_b.

UUIDv7 layout per RFC 9562: the 48-bit timestamp prefix ensures B-tree locality; the 12-bit rand_a field provides monotonicity within a millisecond.

PostgreSQL 18 ships native uuidv7() and uuid_extract_timestamp() functions^[3:3]. In credativ's benchmark, the UUIDv7 primary-key index achieved perfect page-order correlation (1.0 in pg_stats) versus -0.002 for UUIDv4^[3:4]. Leaf fragmentation: 0% for v7, ~50% for v4^[3:5].

When UUIDv7 wins: Greenfield systems, polyglot environments, no worker-ID registry available, 128 bits is acceptable. Zero coordination, IANA-standardized, native database support.

When Snowflake wins: 64 bits matters (halves index size at a billion rows), you can afford the worker-ID coordination, and you need the embedded machine-ID for debugging or routing (Instagram's shard-ID pattern^[9:2]).

Decision tree for choosing an ID scheme: 64-bit versus 128-bit is the first fork; coordination feasibility is the second.

Real-World Example#

Twitter built Snowflake in 2010 to replace a MySQL-based ID generator that could not keep up with tweet volume^[1:8]. The design goal was "tens of thousands of ids per second" in a highly available manner^[1:9]. The actual ceiling (4,096 IDs/ms = 4.1M/sec/worker) gave orders-of-magnitude headroom over the original target.

Twitter ran Snowflake as a standalone Thrift service coordinated via ZooKeeper^[1:10]. Clients made an RPC to a pool of Snowflake nodes; each node held a ZooKeeper-assigned worker-ID and a local monotonic counter. The project was archived in 2021 with a note that Twitter was rewriting it on top of Finagle and Twitter-server^[15].

Instagram adapted the layout in 2012 for their sharded PostgreSQL architecture^[9:3]. Their next_id() PL/pgSQL function runs inline with the INSERT, generating the ID atomically with the row:

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
    our_epoch bigint := 1314220021721;
    seq_id bigint;
    now_millis bigint;
    shard_id int := 5;
BEGIN
    SELECT nextval('insta5.table_id_seq') % 1024 INTO seq_id;
    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
    result := (now_millis - our_epoch) << 23;
    result := result | (shard_id << 10);
    result := result | (seq_id);
END;
$$ LANGUAGE PLPGSQL;

The key insight: embedding the shard-ID in the ID eliminates a metadata lookup on every read. When a service receives an ID, it extracts bits 10-22 to determine which PostgreSQL shard owns the row^[9:4]. At Instagram's scale (25 photos and 90 likes per second in 2012, orders of magnitude more today), this saves billions of routing lookups daily.

Discord adopted a similar 64-bit Snowflake layout (42 bits timestamp + 5 worker + 5 process + 12 sequence) for every message, user, channel, and guild ID^[7:3]. With trillions of messages stored across a ScyllaDB cluster (migrated from 177 Cassandra nodes to 72 ScyllaDB nodes, dropping p99 read latency from 125 ms to 15 ms)^[16], the snowflake timestamp drives the shard key for time-bucketed message storage. Discord serializes IDs as decimal strings in JSON to avoid 64-bit integer overflow in JavaScript clients^[7:4].

Beyond Snowflake variants, other production systems make different trade-offs. MongoDB's ObjectId uses 12 bytes (4-byte second-resolution timestamp + 5 random + 3 counter)^[17], optimized for BSON document storage. Segment built KSUID (160 bits: 32-bit second timestamp + 128-bit random) for S3 object keys where collision resistance matters more than compactness^[18]. Firebase push-IDs use 120 bits (48-bit ms timestamp + 72-bit random) with client-side monotonic correction on reconnect^[19].

Trade-offs#

The single biggest meta-decision: 64 bits versus 128 bits. At one billion rows, a 64-bit primary key index is roughly 8 GB smaller than a 128-bit one. If your system has dozens of tables with billion-row counts, that difference compounds into hundreds of gigabytes of RAM for hot indexes. If you have fewer tables or can tolerate the extra storage, UUIDv7's zero-coordination property eliminates an entire class of operational failures.

B-tree insert locality: UUIDv4 scatters inserts across random pages causing splits and fragmentation; time-ordered IDs append sequentially to the rightmost leaf, achieving 27x faster inserts^[3:7].

Scaling and Failure Modes#

At 10x load (100M IDs/sec): The 1,024-worker ceiling becomes relevant. With 100 workers at 1M/sec each, you are at 24% capacity. No layout change needed, but worker-ID lease management must handle faster churn.

At 100x load (1B IDs/sec): You need more than 1,024 workers. Options: widen the worker-ID field (steal bits from sequence, reducing per-worker ceiling), or shard by tenant with separate generator pools per tenant.

At 1000x load: The 41-bit timestamp itself becomes the constraint. Consider widening to 128 bits (UUIDv7) or adopting a hierarchical scheme where a top-level coordinator assigns epoch ranges to regional sub-generators.

Failure modes:

• Clock backward jump (NTP step): Generator stalls for the skew duration (bound-wait) or uses logical-clock fallback. If skew exceeds threshold, generation fails fast. The 2012 leap-second incident crashed systems across the industry^[11:1][12:1].
• Worker-ID collision (two workers claim same ID): Both emit IDs with identical machine bits. If they generate in the same ms with the same sequence, IDs collide. Detection: startup verification against ZooKeeper. Mitigation: ephemeral nodes with TTL^[1:12].
• Sequence exhaustion within a ms: A single worker tries to emit more than 4,096 IDs in one ms. The correct fallback is spin-wait for the next ms, not overflow^[1:13]. Monitor sequence_exhaustion_events.

Common Pitfalls#

Follow-up Questions#

Exercise#

Exercise 1: Design a custom bit layout#

Your system needs to support 200 data centers, 50 workers per DC, and at least 500 IDs per ms per worker. You have 64 bits. Design the bit layout and compute the timestamp exhaustion date assuming a 2025 epoch.

Key Takeaways#

• Use Snowflake when 64 bits matters and you can solve worker-ID allocation. Use UUIDv7 when 128 bits is acceptable and you want zero coordination.
• The bit layout is a capacity-planning exercise. Derive your timestamp-exhaustion date and per-worker throughput ceiling before you ship.
• Clock skew is the failure mode, not clock drift. Design for backward jumps (bound-wait, logical-clock fallback), not just slow clocks.
• Time-sortable IDs yield 12-27x better B-tree insert performance than random UUIDs^[3:10]. This alone justifies Snowflake/ULID/UUIDv7 over UUIDv4 for any primary key at scale.
• The ticket server is not obsolete. It is the correct answer when strict monotonicity is a hard requirement (audit logs, invoice numbers, customer-facing ticket IDs).

Further Reading#

• Announcing Snowflake (Twitter Engineering, 2010). The original blog post and canonical bit-layout reference; explains the ZooKeeper coordination model.
• Sharding and IDs at Instagram (2012). The embedded shard-ID variant with full PL/pgSQL source; shows how ID design drives database routing.
• RFC 9562: Universally Unique IDentifiers (2024). The definitive standard; obsoletes RFC 4122, defines v6, v7, v8, and monotonicity methods.
• A deeper look at UUIDv4 vs UUIDv7 in PostgreSQL 18 (credativ, 2025). The most rigorous Postgres benchmark comparing insert performance, index size, and fragmentation.
• Ticket Servers: Distributed Unique Primary Keys on the Cheap (Flickr, 2010). The two-MySQL-servers trick that has run since 2006.
• ULID Specification. The 48+80 bit layout, Crockford base-32 encoding, and monotonic-within-ms rules.
• How Discord Stores Trillions of Messages (2023). Scale context for Snowflake IDs in production: 177 Cassandra nodes to 72 ScyllaDB nodes.
• Sonyflake (Sony). The 39+8+16 variant with VPC-friendly IP-derived machine-ID; good reference for alternative bit allocations.

Flashcards#

References#