Unique ID Generation
Give every order, tweet and message a unique ID across thousands of servers without clashes.
37.1 Why is it used?
- Auto-increment is enough in a single DB, but with a sharded DB or multiple data centers the same ID can be created in 2 places.
- Calling a central DB for every ID becomes a bottleneck and a single point of failure.
- Time-sortable IDs make it fast to sort and index the latest orders/tweets.
- If sequential IDs appear in public URLs, a competitor can guess your order count (security/business leak).
- Idempotency keys, trace IDs and file names all need collision-free IDs.
37.2 How it works
- DB Auto-increment: simple, short and ordered IDs; but a single-writer bottleneck and clashes under sharding.
- Ticket server / ranges: a Flickr-style central server, or allot each server an ID block (1-1000, 1001-2000).
- UUID v4: 128-bit random, no coordination; but 36 characters long, and being random it fragments the B-tree index.
- UUID v7: the newer standard (RFC 9562) with a Unix timestamp in the leading bits, so it is time-ordered and index-friendly.
- Snowflake (64-bit): 1 sign bit + 41 bit timestamp (ms) + 10 bit machine ID + 12 bit sequence; one machine makes 4096 IDs per ms.
- ULID: 128-bit, 48 bit timestamp + 80 bit random, a 26 character Crockford Base32 string, lexicographically sortable.
- Clock skew: if a server clock goes backwards, Snowflake risks duplicate IDs, so NTP and a clock-backward check are essential.
- 1.1 bit sign (always 0)
- 2.41 bit timestamp (ms, from a custom epoch)
- 3.10 bit machine ID (1024 nodes)
- 4.12 bit sequence (4096 per ms)
The timestamp is at the front, so IDs are time-sorted. Within the same ms on the same machine only the sequence increases. Example ID: 1849203857120034816; send it as a string in JSON because a JS number loses precision.
- 1.Wrong: Order pods -> central MySQL AUTO_INCREMENT (every ID is a network call, bottleneck + SPOF, clashes under sharding)
- 2.Right: ZooKeeper / config assigns each pod a worker ID (w1, w2, w3)
- 3.Each order pod generates Snowflake IDs locally, no central DB call
Even lakhs of orders per minute on sale day run without a bottleneck.
37.3 Tools you can use
| Tool | Type | How it is used |
|---|---|---|
| Twitter Snowflake (and clones: Sonyflake, Baidu UidGenerator) | ID generation algorithm | Each node generates a 64-bit time-ordered ID locally; only a unique machine ID has to be assigned. |
| UUID libraries (java.util.UUID, Python uuid, gen_random_uuid()) | Standard library | No infrastructure, generate anywhere; PostgreSQL has gen_random_uuid() built in. |
| ULID libraries | Open-source library | When you need sortable string IDs, e.g. logs, events, object keys. |
| MySQL / PostgreSQL AUTO_INCREMENT / SEQUENCE | Relational DB | For primary keys in single-DB apps; a gap-based scheme with auto_increment_increment/offset in multi-master. |
| Redis INCR | In-memory counter | A fast global counter via atomic INCR, e.g. order number; persistence must be configured. |
| MongoDB ObjectId | NoSQL built-in | 12-byte ID: timestamp + random + counter, generated client side. |
37.4 Comparison: DB Auto-increment vs UUID v4 vs Snowflake vs ULID
| Point | DB Auto-increment | UUID v4 | Snowflake | ULID |
|---|---|---|---|---|
| Size | 4-8 bytes | 16 bytes | 8 bytes (64-bit) | 16 bytes |
| Time sortable | Yes, sequential | No | Yes, roughly | Yes |
| Coordination | Needs a central DB | None at all | Only machine ID assignment | None at all |
| Scale | Single writer limit | Unlimited | 4096 per ms per node | Unlimited |
| Index performance | Best | Poor, random inserts | Good | Good |
| Guessable | Yes, sequential | No | Slightly, reveals time | Slightly, reveals time |
| Best for | Small apps, single DB | Public tokens, idempotency keys | Tweets, orders at huge scale | Event logs, sortable string keys |
37.5 When to choose which
- Auto-increment: when there is a single DB and the scale is moderate.
- UUID v4: when you need an unguessable ID and ordering does not matter; for DB keys UUID v7 is better.
- Snowflake: when you need a very high write rate and a compact, time-ordered 64-bit ID.
- ULID / UUID v7: when you need a string ID that is sortable and needs no coordination.
37.6 Real-world example
Real world: Twitter Snowflake and Flipkart order IDs
- While moving from MySQL to a distributed store like Cassandra, Twitter built Snowflake and open-sourced it in 2010.
- Each ID generator node gets a unique machine/worker ID (from ZooKeeper or config).
- When a tweet arrives, the node joins the current milliseconds, its worker ID and a sequence number into a 64-bit ID, with no network call.
- If more than 4096 IDs are needed in the same millisecond, it waits until the next millisecond.
- IDs are time-ordered, so sorting the latest tweets in a timeline is easy.
- Such a scenario: on sale day an e-commerce site sees lakhs of orders per minute; with Snowflake-style IDs each order service pod creates order IDs locally and the central DB does not become a bottleneck.
37.7 Interview tips
- Using UUID v4 as the MySQL InnoDB clustered primary key: random inserts cause page splits and slow writes.
- Assigning a duplicate machine ID in Snowflake (two pods with the same ID) makes IDs clash.
- Sending a 64-bit Snowflake ID as a number type in JavaScript loses precision; send it as a string in JSON.
- Interview tip: always mention the Snowflake bit layout (1+41+10+12) and the clock skew problem.