Design a Unique ID Generator in Distributed Systems

1. Problem & Real-World Context

Design a service that generates unique IDs at scale, across multiple servers, with no single point of coordination on the hot path. This looks trivial (AUTO_INCREMENT works on one database) until the system is sharded across many machines — the moment two independent nodes can both accept writes, "just increment a counter" stops being an answer. This exact sub-problem already showed up inline in [[Design a URL Shortener]] (short-code generation), [[News Feed - Twitter Feed]] (post ordering), and [[WhatsApp Chat]] (message ordering) — this page is the canonical, standalone treatment all three point back to.

2. Requirements

Functional: generate an ID whenever called; IDs must be unique across the entire distributed system.

Non-functional: IDs should be roughly sortable by creation time (a huge practical convenience — see §5); high throughput (thousands to millions of IDs/sec across the fleet); no single point of coordination on the generation hot path (a central "next ID" service that every request round-trips to is itself a bottleneck and a SPOF); IDs should fit in 64 bits (fits a native integer type in every mainstream language/DB, unlike a 128-bit UUID).

3. Approaches

Multi-Master Replication (Auto-Increment with Offset)

Each database server auto-increments, but with a different starting offset and a step size equal to the number of servers — e.g., server 1 generates 1, 4, 7...; server 2 generates 2, 5, 8...

flowchart LR
    S1[Server 1<br/>auto_increment_increment=3<br/>offset=1] -->|1,4,7,10...| DB
    S2[Server 2<br/>offset=2] -->|2,5,8,11...| DB
    S3[Server 3<br/>offset=3] -->|3,6,9,12...| DB

Pros: no coordination needed after initial config — each server independently generates non-colliding IDs. Cons:

• doesn't scale horizontally without reconfiguring every server's offset/step (adding a 4th server means changing the step size on all of them);
• IDs aren't time-sortable across servers in any clean way;
• hard to scale in a multi-datacenter setup.

UUID

A 128-bit random (or partially structured) identifier, generated independently on any machine with no coordination at all.

import uuid
new_id = uuid.uuid4()   # 128-bit random UUID, e.g. 550e8400-e29b-41d4-a716-446655440000

Pros:

• genuinely zero coordination,
• trivially horizontally scalable,
• works fully offline. Cons:
• 128 bits is 2x the storage/index cost of a 64-bit ID at scale;
• not sortable by time at all (uuid4 is fully random — inserting into a B-tree index in random order causes page splits and index fragmentation, a real, measurable cost on write-heavy tables);
• not human-friendly to pass around.

Ticket Server (Flickr's Approach)

A centralized, dedicated database (or small cluster) whose only job is handing out unique IDs via auto_increment — decoupled from the actual data-serving database.

Pros:

• simple, and the centralized DB can be scaled/replicated somewhat independently. Cons:
• the ticket server(s) themselves are a potential bottleneck and a SPOF unless carefully replicated (and replicating an auto-increment counter reintroduces the same multi-master coordination problem it was meant to avoid) — this approach doesn't fully escape centralization, it just relocates it.

Twitter Snowflake (the Standard Interview Answer)

A 64-bit ID composed of fixed-width bit fields, generated independently on each machine with zero coordination, while still being roughly time-sortable.

[ 1 bit: unused/sign ] [ 41 bits: timestamp ] [ 10 bits: machine ID ] [ 12 bits: sequence ]

import time

EPOCH = 1_700_000_000_000  # custom epoch (ms since Unix epoch) — maximizes usable range
MACHINE_ID_BITS = 10
SEQUENCE_BITS = 12
MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1

class SnowflakeGenerator:
    def __init__(self, machine_id: int):
        assert 0 <= machine_id < (1 << MACHINE_ID_BITS)
        self.machine_id = machine_id
        self._sequence = 0
        self._last_ts = -1

    def next_id(self) -> int:
        ts = int(time.time() * 1000)
        if ts == self._last_ts:
            self._sequence = (self._sequence + 1) & MAX_SEQUENCE
            if self._sequence == 0:               # exhausted this millisecond's sequence space
                while ts <= self._last_ts:         # spin until the clock ticks forward
                    ts = int(time.time() * 1000)
        else:
            self._sequence = 0
        self._last_ts = ts

        return ((ts - EPOCH) << (MACHINE_ID_BITS + SEQUENCE_BITS)) \
             | (self.machine_id << SEQUENCE_BITS) \
             | self._sequence

Bit budget, precisely:

• 41 bits for timestamp (milliseconds since a custom epoch): 2^41 ms ≈ 69 years of range — a custom epoch (not Unix epoch 1970) is chosen so those 69 years start now, not decades ago, maximizing usable lifetime.
• 10 bits for machine ID: 2^10 = 1024 distinct machines/shards — assigned via config or a coordination service (ZooKeeper) at startup, not generated dynamically.
• 12 bits for sequence: 2^12 = 4096 IDs per machine per millisecond before the generator has to wait for the clock to tick forward — this bounds worst-case throughput per machine to 4.096M IDs/sec, comfortably above real-world needs.

Pros: zero coordination on the hot path (each machine only needs its own pre-assigned machine ID, decided once at startup), genuinely time-sortable (the timestamp is the highest-order bits, so numeric sort ≈ chronological sort — this is the exact mechanism [[News Feed - Twitter Feed]] relies on for "recent posts by author" being a natural sorted scan), fits in a 64-bit integer.

Cons: requires roughly synchronized clocks across machines (clock skew can produce IDs that aren't perfectly time-ordered across different machines, though each individual machine's own IDs are always strictly increasing); a machine whose clock jumps backward (NTP correction) must detect and handle this explicitly (below) rather than silently generating a duplicate or non-monotonic ID.

4. Clock Skew & the Backward-Clock Edge Case

The one genuinely hard follow-up on this problem: what happens if time.time() returns a value earlier than the last-seen timestamp (NTP stepped the clock backward)?

def next_id_safe(self) -> int:
    ts = int(time.time() * 1000)
    if ts < self._last_ts:
        raise ClockMovedBackwardsError(
            f"Clock moved backwards by {self._last_ts - ts}ms — refusing to generate an ID"
        )
    # ... rest of next_id logic

Why refuse rather than silently proceed: generating an ID against a backward-moved clock risks producing a timestamp bit-pattern that's smaller than an ID already issued moments ago on the same machine — silently breaking the "time-sortable" guarantee the whole design exists to provide. The standard production answer is to detect this and either block briefly until the clock catches back up, or fail the request loudly — never silently emit a potentially-duplicate or out-of-order ID.

5. Why Time-Sortability Matters in Practice

This isn't a nice-to-have — it's the property that makes several other designs in this KB work cleanly:

• [[News Feed - Twitter Feed]] partitions posts by user_id and clusters by post_id DESC in Cassandra — this is a plain sorted-column scan specifically because the ID itself encodes creation order, with no separate timestamp column or secondary index needed.
• [[Distributed Job Scheduler]]'s "find jobs due now" query benefits from the same principle — a time-sortable key lets a range scan double as a time-range query.
• Any pagination cursor (see [[API Design Principles]]) that uses "last seen ID" as the cursor implicitly relies on IDs being monotonic within the scope being paginated.

6. Comparison Table

7. Interview Drill Questions

1. Why is Snowflake preferred over a plain UUID for a system that needs to sort records by creation time? — A UUID (v4) is fully random, carrying no time information at all — sorting by UUID gives no meaningful order. Snowflake places the timestamp in the highest-order bits, so a numeric/lexicographic sort of Snowflake IDs is equivalent to a chronological sort — a property several other designs in this KB (News Feed's partition clustering, in particular) depend on directly.
2. Two machines generate a Snowflake ID at the exact same millisecond. How do they avoid colliding? — Each carries a distinct, pre-assigned machine ID in its middle bit field — even with an identical timestamp and an identical sequence number, the machine-ID bits differ, so the full 64-bit IDs can never collide across machines by construction.
3. A machine's clock is corrected backward by NTP mid-operation. What's the correct behavior, and why not just keep generating IDs normally? — The generator must detect current_ts < last_seen_ts and refuse (or block until the clock catches up) rather than proceeding — generating an ID with a smaller timestamp bit-pattern than one already issued would violate the core guarantee (monotonically increasing, time-sortable IDs from this machine), silently corrupting any downstream logic relying on it.
4. What caps the maximum ID-generation throughput of a single Snowflake machine, and what happens when that cap is hit? — The 12-bit sequence field, giving 4096 distinct IDs per machine per millisecond (4.096M/sec) — if a machine tries to generate more than that within one millisecond, the generator must spin-wait until the clock advances to the next millisecond before issuing the next ID, rather than silently reusing a sequence number.
5. Why does the multi-master auto-increment approach (offset + step size) scale poorly compared to Snowflake? — Adding or removing a server requires reconfiguring the step size and offsets on every existing server (a coordinated, disruptive change), whereas adding a Snowflake machine just needs one new unused machine-ID assigned to it — every other machine's behavior is completely unaffected.

Cross-links

[[Design a URL Shortener]] · [[News Feed - Twitter Feed]] · [[WhatsApp Chat]] · [[Distributed Job Scheduler]] · [[API Design Principles]] · [[CAP Theorem & Consistency Models]]