Design a Distributed Unique ID Generator

Almost every distributed system needs IDs: for tweets, orders, messages, log lines. A single database's auto-increment column stops working once writes are spread across many machines and regions. This question asks you to build an ID service that many servers can call at the same time without ever handing out the same ID twice.

Requirements#

• IDs are unique across the whole system, forever.
• IDs are numeric and fit in 64 bits, so they index well and stay compact.
• IDs are roughly sortable by time: an ID made later is usually larger.
• The service generates 10,000+ IDs per second per machine with low latency.
• No single point of failure.

Approaches compared#

UUIDs are attractive because they need no coordination at all, but they are 128 bits, random, and fragment B-tree indexes because inserts land all over the tree. A Snowflake-style layout is the usual answer.

The Snowflake layout#

Split the 64 bits into fields:

| 1 bit  | 41 bits                 | 5 bits     | 5 bits     | 12 bits  |
| sign 0 | ms since custom epoch   | datacenter | machine    | sequence |

• 41 bits of milliseconds last about 69 years from a custom epoch (for example, the day the company launched).
• 10 bits of machine identity (datacenter plus machine) allow 1,024 generators.
• 12 bits of sequence allow 4,096 IDs per millisecond per machine, about 4 million per second.

Because the timestamp is in the high bits, sorting IDs sorts them by creation time.

const EPOCH = 1704067200000n; // 2024-01-01

class IdGenerator {
  private lastMs = -1n;
  private sequence = 0n;

  constructor(private readonly machineId: bigint) {} // 0..1023

  next(): bigint {
    let now = BigInt(Date.now());
    if (now < this.lastMs) throw new Error('Clock moved backwards');
    if (now === this.lastMs) {
      this.sequence = (this.sequence + 1n) & 4095n;
      // Used all 4,096 IDs this millisecond: wait for the next one
      if (this.sequence === 0n) while ((now = BigInt(Date.now())) <= this.lastMs);
    } else {
      this.sequence = 0n;
    }
    this.lastMs = now;
    return ((now - EPOCH) << 22n) | (this.machineId << 12n) | this.sequence;
  }
}

Architecture#

The generator is usually a library embedded in each service, not a network hop. The only coordination happens at startup, when the process leases a unique machine ID from ZooKeeper or etcd.

Deep dives#

Clock skew

Snowflake trusts the local clock. If NTP moves the clock backwards, the generator could repeat timestamps. Options:

• Refuse to generate until the clock passes lastMs again (fine for small jumps).
• For large jumps, fail loudly and take the node out of rotation.
• Keep machines on a well-behaved time source, and alert on drift.

Assigning machine IDs

Hard-coding machine IDs breaks with autoscaling. Lease them instead: on boot a node claims a free ID in ZooKeeper with an ephemeral node, and the lease disappears if the process dies. Make sure a crashed node cannot come back with the same ID while its old IDs are still in the same millisecond window, for example by waiting a few seconds before reusing a lease.

Running out of sequence

If one machine needs more than 4,096 IDs in a millisecond it simply waits for the next millisecond. If that is a real limit, borrow bits: fewer machine bits, more sequence bits.

Wrapping up#

The strong answer explains the bit layout, why time goes in the high bits, how machine IDs are assigned without manual work, and what happens when clocks misbehave. Mention alternatives (UUIDv7 is a newer time-ordered 128-bit option) to show you know the landscape.