Q61 — How would you design a distributed ID generator (like Twitter's Snowflake)?

Why can't you just use auto-increment?

In a single-database system, auto-increment IDs are perfect: the database generates a monotonically increasing integer, guaranteed unique, no coordination needed. Every INSERT gets the next ID. Simple.

In a distributed system, auto-increment breaks immediately:

Multiple writers. If you shard your database across 5 nodes (Q36), each node's auto-increment counter generates IDs independently. Node 1 generates 1, 2, 3. Node 2 also generates 1, 2, 3. You now have ID collisions — two different records with ID 1, two with ID 2. The IDs are no longer globally unique.

The coordination problem. You could use a central counter service — every ID request goes to one machine that atomically increments and returns the next value. But this single machine is now a bottleneck for every write operation in your entire system. It's a single point of failure and a throughput ceiling.

No horizontal scale. A central auto-increment counter can handle maybe 50,000–100,000 requests per second. At Twitter scale (hundreds of thousands of tweets per second), this is immediately saturated.

You need IDs that are: globally unique across all nodes, generated without coordination (no central authority required per-request), monotonically increasing (so they sort by creation time and work well with B-tree indexes), and compact (fit in 64 bits so they're efficient to store and index).

What properties does a good distributed ID have?

Globally unique: no two IDs generated by any node at any time should be the same.

Roughly time-ordered (monotonically increasing within a node): IDs generated later should be larger than IDs generated earlier. This property is critical for database performance — B-tree indexes perform best when new values are inserted at the end (sequential writes vs. random writes). If IDs are random (like UUID v4), every insert potentially causes a B-tree page split somewhere in the middle of the tree — expensive at scale. Sequential IDs insert at the leading edge — predictable and efficient.

No coordination required per-ID: generating an ID should not require a network call. The generator on each node must be self-sufficient.

Compact: 64-bit integers, not 128-bit UUIDs. Indexes on 64-bit integers are half the size of UUID indexes. Smaller means more fits in cache, faster lookups.

The Snowflake structure — 64 bits divided into three parts

Twitter's Snowflake is the canonical solution. A 64-bit integer (signed, so 63 usable bits) divided into:

┌─────────────────────────────────────────┬────────────┬──────────────┐
│           41 bits: timestamp            │ 10 bits:   │ 12 bits:     │
│   (milliseconds since custom epoch)     │ machine ID │ sequence num │
└─────────────────────────────────────────┴────────────┴──────────────┘

41 bits for timestamp (milliseconds since a custom epoch): 41 bits can represent 2^41 - 1 = 2,199,023,255,551 milliseconds ≈ 69 years of unique timestamps from the chosen epoch. Twitter chose November 4, 2010 as its epoch — giving the system ~69 years of range before overflow (until ~2079).

Why a custom epoch? Unix epoch (Jan 1 1970) would waste the first ~40 years of bits. Starting from 2010, all bits are useful.

10 bits for machine ID (worker ID): 2^10 = 1,024 unique machine IDs. Each node in the system is assigned a unique ID at startup. No two nodes share an ID. This ensures IDs generated by different nodes don't collide, even if they generate IDs at the same millisecond.

12 bits for sequence number: 2^12 = 4,096 unique values per millisecond per machine. If a node generates more than one ID in the same millisecond, it increments this sequence counter. At the next millisecond, the sequence resets to 0.

This means each machine can generate up to 4,096 IDs per millisecond = 4,096,000 IDs per second per node. Across 1,024 nodes: 4 billion IDs per second total throughput — far beyond any realistic requirement.

How does generation work?

On each node, the generator maintains:

• Its assigned machine_id (configured at startup)
• The last_timestamp of the most recent ID generated
• The current sequence counter

On every ID request:

current_ms = current_time_in_milliseconds()

if current_ms == last_timestamp:
    sequence += 1
    if sequence > 4095:  # overflow — wait for next millisecond
        sleep until next_ms
        sequence = 0
else:
    sequence = 0
    last_timestamp = current_ms

id = (current_ms - epoch) << 22 | machine_id << 12 | sequence

The ID is constructed by bit-shifting the three components into the correct positions within the 64-bit integer. This is a pure in-memory operation — no network call, no database lookup, no lock contention beyond the local sequence counter. Each node generates IDs independently.

The resulting ID is a 64-bit integer that encodes timestamp, machine identity, and a local sequence. IDs from the same machine are strictly monotonically increasing. IDs across machines are roughly monotonically increasing (time-ordered to within the precision of clock synchronization — typically milliseconds).

What happens when the clock goes backward?

This is the critical failure mode. System clocks drift and are periodically corrected by NTP (Network Time Protocol). If NTP corrects a clock backward — say the clock on node 7 jumps from 14:32:08.500 to 14:32:08.300 — the generator might reuse a timestamp that node 7 already generated IDs for. Combined with a previously-used sequence range, this could produce duplicate IDs.

Solutions:

Refuse to generate IDs until the clock catches up: if current_ms < last_timestamp, the clock went backward. Block ID generation (spin-wait or sleep) until current_ms >= last_timestamp. For small backward adjustments (a few milliseconds), this is a brief pause. For large adjustments, it's a prolonged outage.

Use a monotonic clock: operating systems provide a monotonic clock that never goes backward (separate from the wall clock that NTP adjusts). The tradeoff: monotonic clocks are not synchronized across machines — they measure elapsed time since boot, not wall time. IDs from different machines would not be time-comparable. You'd need to calibrate the initial epoch offset carefully.

Detect and raise an alarm: if the clock skew exceeds a threshold (say, 2 seconds), treat it as a serious error — alert, log, potentially restart the generator with a new sequence range.

In practice, most Snowflake implementations track last_timestamp and spin on clock backward; NTP adjustments are typically sub-millisecond and the pause is imperceptible.

Alternatives to Snowflake

UUID v4: 128-bit random. Globally unique without coordination. But: not time-ordered (random inserts cause B-tree fragmentation), 16 bytes (twice the storage of int64), not human-friendly. Good default when sort order doesn't matter and you want zero infrastructure.

UUID v7: a newer standard (RFC 9562, 2024) that encodes a Unix timestamp in the high bits, making UUIDs monotonically increasing. 128-bit but time-ordered. Good for systems that want UUID format (interoperability, no machine ID assignment) with sequential insert performance.

Database sequence with range pre-allocation: a central service allocates ranges of IDs to nodes. Node 1 gets IDs 1–10,000, node 2 gets 10,001–20,000, etc. Each node uses its range without coordination until exhausted, then requests a new range. Fewer coordination round-trips, still centralized control. Simple but the central service is still a dependency.

ULID (Universally Unique Lexicographically Sortable Identifier): 26-character base32 string encoding a 48-bit timestamp and 80 bits of randomness. Monotonically sortable, URL-safe, 128-bit. An alternative UUID v7 in textual form.

The mental model

Why auto-increment fails in distributed systems:
  Multiple shards → each generates independent sequence → collisions
  Central counter → single point of failure + throughput ceiling

Snowflake 64-bit structure:
  [41 bits: ms since epoch] [10 bits: machine_id] [12 bits: sequence]
  
  41 bits → ~69 years of ms timestamps (custom epoch: 2010)
  10 bits → 1,024 unique nodes
  12 bits → 4,096 IDs per ms per node = 4M IDs/sec/node

Generation (pure local, no network):
  same_ms: increment sequence (max 4095) → else spin until next ms
  new_ms: reset sequence to 0
  id = (ms - epoch) << 22 | machine_id << 12 | sequence

Properties:
  ✅ Globally unique (machine_id separates nodes)
  ✅ ~Time-ordered (larger ID = later time, roughly)
  ✅ Sequential B-tree inserts (leading edge, no page splits)
  ✅ 64-bit integer (compact, half the size of UUID)
  ✅ No coordination per ID (in-memory generation)
  ⚠️  Requires machine_id assignment (configuration at node startup)
  ⚠️  Clock skew → potential duplicates → detect and pause on backward clock

Failure: clock goes backward → same timestamp reused + old sequence range
  Fix: spin until current_ms >= last_timestamp (brief pause for NTP corrections)

Alternatives:
  UUID v4: 128-bit random, unordered — use when sort order doesn't matter
  UUID v7: 128-bit, time-ordered — good interop, no machine_id needed
  ULID: text-friendly UUID v7 equivalent
  Range pre-allocation: central service gives each node a batch of IDs

Snowflake is the right design when:
  64-bit integers required (DB int column, not UUID)
  Time-ordering matters (sequential B-tree inserts, sortable by creation time)
  Very high throughput needed (millions of IDs/sec across many nodes)
  Self-contained nodes (no per-ID network call acceptable)

Snowflake solves a subtle problem: how do you get the properties of a single monotonic counter — globally unique, time-ordered, compact — across many machines with no coordination? The answer is to encode time (naturally monotonic), space (machine identity that partitions the namespace), and local state (sequence) into a single integer. Each dimension handles one part of the uniqueness guarantee, and together they eliminate the need for any cross-node coordination.