Pattern · Identifiers
Distributed IDs
Generating globally unique, roughly time-ordered 64-bit and 128-bit identifiers across distributed nodes. Database auto-increment bottlenecks, UUIDv4 random IO thrashing, UUIDv7 and ULID, Twitter Snowflake bit layouts, clock skew mitigation, and B-tree index locality.
10 min read
In a monolithic architecture backed by a single relational database, generating primary keys is trivial: the database increments an integer sequence (AUTO_INCREMENT in MySQL or BIGSERIAL in PostgreSQL).
Once writes are distributed across multiple database shards, microservices, or geographic regions, a single centralized counter becomes an untenable bottleneck and a single point of failure. Distributed systems require an identifier generation strategy that guarantees global uniqueness without requiring cross-node coordination on every insert.
The problem with auto-increment
Traditional auto-increment IDs fail in distributed systems for three reasons:
- Central bottleneck: Every new record requires a network round-trip to the sequence master, capping write throughput to a single machine's lock speed.
- Multi-master collisions: If two database shards both assign auto-increment IDs, they assign identical values (
1, 2, 3...) to different records unless configured with striped offsets (e.g. node 1 writes odd numbers, node 2 writes even numbers). Striping is rigid and difficult to rebalance as shard counts grow. - Information leakage: Monotonically increasing sequential IDs (
/orders/1001,/orders/1002) allow competitors to scrape your platform and calculate exact order volumes.
The UUIDv4 dilemma: Randomness destroys B-Trees
A common quick fix is using random 128-bit UUIDs (UUIDv4). Because UUIDv4 relies on 122 bits of pseudo-random entropy, collision probability is virtually zero (1 in 2^122), allowing any client or server to generate unique IDs locally with zero network coordination.
However, using UUIDv4 as a primary key in relational databases causes severe storage and performance degradation:
Furthermore, at 16 bytes raw (or 36 bytes formatted as a string), UUIDs double or triple the size of secondary indexes, which store primary keys as pointers.
Time-ordered 128-bit IDs: UUIDv7 and ULID
To solve the B-tree fragmentation of UUIDv4 while retaining coordination-free generation, modern standards combine a millisecond timestamp prefix with random entropy:
- UUIDv7 (RFC 9562): A standardized 128-bit format starting with a 48-bit Unix timestamp in milliseconds, followed by 74 bits of randomness and version metadata.
- ULID (Universally Unique Lexicographically Sortable Identifier): A 128-bit ID encoded in Crockford's Base32 (26 characters), consisting of a 48-bit timestamp followed by 80 bits of cryptographic randomness.
Because new IDs share an increasing timestamp prefix, successive inserts always append to the right edge of the B-Tree leaf pages, preserving index locality and preventing page splits while maintaining decentralized generation.
64-bit Distributed IDs: Twitter Snowflake
While 128-bit IDs preserve index locality, many applications (like social timelines, messaging, and search indexes) require compact 64-bit integers that fit directly into standard hardware registers and indexing engines.
The standard pattern for distributed 64-bit IDs is Twitter Snowflake:
- Sign bit (1 bit): Always
0to keep the integer positive in signed 64-bit environments (like Javalong). - Timestamp (41 bits): Milliseconds since a custom epoch (e.g. the company founding date). 41 bits gives approximately 69.7 years of unique timestamps.
- Worker / Node ID (10 bits): Typically 5 bits for datacenter ID (0–31) and 5 bits for worker node ID (0–31), supporting up to 1,024 independent ID-generating generator instances.
- Sequence counter (12 bits): A local in-memory counter rolled over every millisecond. Provides 4,096 unique IDs per millisecond per worker node (over 4 million IDs per second per machine).
If a worker receives more than 4,096 requests within a single millisecond, the generator pauses until the system clock advances to the next millisecond.
The clock skew problem
Snowflake's Achilles' heel is NTP clock drift:
Production generators mitigate clock skew through three mechanisms:
- Clock skew detection: If
current_time < last_timestamp, the service immediately refuses to generate IDs and waits for the clock to catch up, or throws an alert if the skew exceeds 50 milliseconds. - Monotonic drift: Running NTP daemons with slewing (
chronyorntpd -x) rather than stepping, preventing abrupt backward time jumps. - Sequence borrowing: Incrementing the sequence forward across logical ticks rather than relying purely on the physical clock reading.
Centralized alternatives: Ticket servers and Redis ranges
If bit-packing services add too much operational overhead, centralized range allocators provide a middle ground:
- Flickr Ticket Servers: Dedicated MySQL instances running tables with
REPLACE INTO Tickets64 (stub) VALUES ('a'). Workers call the ticket server to fetch blocks of 1,000 IDs, incrementing local memory counters until the block is exhausted. - Redis Range Allocation: An application worker calls
INCRBY global_id_counter 1000in Redis, granting that worker exclusive ownership of IDs[N, N+999]. Even if Redis restarts, the next allocation claims the next block safely.
Comparing ID strategies
UUIDv4
- Completely decentralized
- Zero network calls
- Supported in every language standard library
- 128 bits (heavy storage overhead)
- Completely random (destroys B-tree index performance)
Pick it when: Temporary tokens, tracing spans, non-indexed IDs.
UUIDv7 / ULID
- 128 bits with 48-bit timestamp prefix
- B-tree friendly (sequential inserts)
- No central coordination required
- 128 bits instead of compact 64-bit integer
- Slightly larger storage footprint than Snowflake
Pick it when: General-purpose microservice primary keys, document stores.
Snowflake (64-bit)
- Fits in 64-bit integer
- Roughly time-ordered
- Up to 4M IDs/sec per node with zero coordination
- Requires managing worker IDs (1024 max)
- Vulnerable to NTP clock skew
- Requires dedicated ID service or library
Pick it when: High-throughput messaging, social feeds, high-performance relational tables.
Redis Block Allocator
- Simple to implement
- Pure sequential numbers without bitwise complexity
- Network dependency on Redis
- Gaps in sequence if workers crash
Pick it when: Internal batch pipelines, lightweight distributed workloads.
Numbers to quote
- Snowflake capacity per node
- 4,096 IDs per millisecond (4.096M/sec)
- Snowflake timestamp lifetime
- 41 bits = 69.7 years from custom epoch
- Snowflake machine address space
- 10 bits = 1,024 worker nodes
- UUIDv7 millisecond resolution
- 48 bits timestamp = 8,925 years
- B-tree insert penalty (UUIDv4 vs v7)
- UUIDv4 is 5x to 10x slower on large tables due to page splits
Where it bites
- JavaScript 53-bit integer limit: JavaScript's
Numbertype only safely represents integers up to 2^53 - 1 (9,007,199,254,740,991). A 64-bit Snowflake ID will silently lose precision in frontend web clients unless serialized and transmitted as a JSON string. - Worker ID coordination: If two worker containers in Kubernetes accidentally spin up with identical
worker_idvalues, they will emit duplicate IDs during the same millisecond. Worker IDs must be assigned deterministically via StatefulSet ordinal indices or ZooKeeper/etcd leases.
Try it
Distributed ID Generator HLD
Design a high-throughput, horizontally scalable unique ID generator that produces roughly time-ordered 64-bit identifiers.