Design a Unique ID Generator

Requirements

Every tweet, message, order and photo needs a primary key. On a single database an auto-increment column is enough, but once data is sharded across many databases and written from many services, you need a way to mint IDs that are unique everywhere without asking one central box for each one.

Functional

• nextId() returns an ID that is never returned again, by any node, ever.
• IDs are 64-bit integers (fit in a BIGINT and a Java long).
• IDs are roughly sortable by creation time: an ID created a second later is almost always larger.
• Optionally decode an ID back into its creation time and origin node (handy for debugging).

Non-functional

• Throughput: at least 10,000 IDs per second per node, with headroom for bursts.
• Latency: sub-millisecond; ideally an in-process call with no network hop.
• Availability: generating an ID must not depend on a single server staying up.
• Scalability: adding nodes must not require reconfiguring the others.
• Longevity: the scheme should not run out of IDs for decades.

Capacity Estimates

Assume a large social product: 500 M new objects per day on average, peaks of 10x, and a fleet of a few hundred application servers.

The math shows that throughput is never the issue: one node can mint millions per second. The real problems are uniqueness without coordination and clock behaviour.

API Design

The generator is usually a library embedded in each service. A small network service is offered for clients that cannot embed it.

// In-process library
long   nextId()
IdInfo decode(long id)  -> { timestampMs, datacenterId, workerId, sequence }

// Optional HTTP service
GET /v1/ids?count=100
  200: { "ids": [7372036854775807, ...] }
  503: worker has no valid lease or clock is behind; retry another instance

GET /v1/ids/{id}/decode
  200: { "createdAt": "2026-10-30T12:34:56.789Z", "datacenter": 3, "worker": 17, "sequence": 42 }

Batch requests (count=100) amortise the network round trip for remote callers.

Data Model

There is no table of issued IDs; uniqueness comes from the bit layout. The only persistent state is which worker ID each running node owns.

Worker leases live in a coordination service such as ZooKeeper or etcd:

/idgen/dc-3/workers/17  ->  { host: "app-0421", leaseExpiresAt: ..., lastTimestampMs: ... }

Using an ephemeral node (ZooKeeper) or a TTL lease (etcd) means a crashed host's worker ID is released automatically, but only after its lease expires.

High-Level Design

flowchart LR
  subgraph App["Application server"]
    S[Service code] --> G[Embedded ID generator]
  end
  G -- "lease worker ID at startup" --> ZK[(ZooKeeper / etcd)]
  G -- "time sync" --> NTP[NTP / time service]
  Other[Non-JVM clients] --> LB[Load Balancer] --> IDS[ID Service fleet]
  IDS --> ZK
  S --> DB[(Sharded database)]

1. On startup a node claims a free (datacenter, worker) pair from the coordination service and keeps its lease alive.
2. Each nextId() call reads the local clock, bumps a sequence counter, and packs the three fields into a long. No network calls.
3. The resulting ID is used directly as the primary key; because its high bits are a timestamp, newer rows sort after older ones.

The coordination service is on the startup path only, so a ZooKeeper outage does not stop running nodes from generating IDs.

Deep Dives

Comparing the classic approaches

The Snowflake generator

The algorithm is a few lines: if we are still in the same millisecond as the previous ID, increment the sequence; if the sequence overflows, spin until the next millisecond; otherwise reset the sequence to zero.

public final class SnowflakeIdGenerator {
    private static final long EPOCH = 1_704_067_200_000L;          // 2024-01-01T00:00:00Z
    private static final int WORKER_BITS = 10, SEQUENCE_BITS = 12;
    private static final long MAX_WORKER = (1L << WORKER_BITS) - 1;
    private static final long SEQUENCE_MASK = (1L << SEQUENCE_BITS) - 1;
    private static final long MAX_BACKWARD_MS = 5;

    private final long workerId;                                  // datacenter (5 bits) + worker (5 bits)
    private long lastMillis = -1L;
    private long sequence = 0L;

    public SnowflakeIdGenerator(long workerId) {
        if (workerId < 0 || workerId > MAX_WORKER) throw new IllegalArgumentException("workerId out of range");
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long now = System.currentTimeMillis();
        if (now < lastMillis) {                                   // clock went backwards
            long drift = lastMillis - now;
            if (drift > MAX_BACKWARD_MS) throw new IllegalStateException("Clock moved back " + drift + " ms");
            now = waitUntil(lastMillis);                          // small drift: just wait it out
        }
        if (now == lastMillis) {
            sequence = (sequence + 1) & SEQUENCE_MASK;
            if (sequence == 0) now = waitUntil(lastMillis + 1);   // 4096 IDs used in this ms
        } else {
            sequence = 0;
        }
        lastMillis = now;
        return ((now - EPOCH) << (WORKER_BITS + SEQUENCE_BITS)) | (workerId << SEQUENCE_BITS) | sequence;
    }

    public static long timestampOf(long id) {
        return (id >>> (WORKER_BITS + SEQUENCE_BITS)) + EPOCH;
    }

    private static long waitUntil(long target) {
        long now = System.currentTimeMillis();
        while (now < target) { Thread.onSpinWait(); now = System.currentTimeMillis(); }
        return now;
    }
}

Choosing a custom epoch close to launch day, instead of 1970, gives the full ~69 years of range from the day you go live. Bit splits are tunable: Instagram, for example, used 13 bits for a logical shard ID and 10 for the sequence, generating IDs inside PostgreSQL so each ID also encodes which shard owns the row.

Assigning worker IDs safely

Two nodes with the same worker ID will eventually produce duplicate IDs, so worker assignment is the one place that needs coordination.

• Static config: set the worker ID in each host's config. Fine for a small, stable fleet; error-prone with autoscaling.
• Coordination service: at startup, create a sequential or ephemeral node in ZooKeeper/etcd and use its number modulo 1,024. Renew the lease with heartbeats.
• Derived from infrastructure: use a Kubernetes StatefulSet ordinal or part of the private IP. Cheap, but you must prove the mapping is collision-free.

On losing its lease (network partition), a node must stop issuing IDs until it re-acquires one, because another node may now own that worker ID.

Clock skew and clocks moving backwards

Snowflake assumes the local clock never goes backwards. NTP corrections, VM migrations and leap-second smearing can break that.

• Small backward jumps: wait until the clock catches up with the last timestamp used (the code above tolerates 5 ms).
• Large backward jumps: refuse to generate and alert; the load balancer or caller retries on another node.
• Persist the high-water mark: periodically save lastTimestampMs with the lease so a restarted node does not reuse a time range it already used.
• Prefer slewing over stepping: configure NTP/chrony to adjust the clock gradually rather than jumping it.

Ordering, privacy and hot spots

• What ordering you get: within one node, IDs are strictly increasing. Across nodes, they are ordered to within the clock skew, typically a few milliseconds.
• Information leakage: time-based IDs reveal creation time and, by sampling, business volume. If that matters, expose an encrypted or hashed public ID and keep the Snowflake internally.
• Write hot spots: in range-partitioned stores (HBase, Bigtable), monotonically increasing keys send every insert to the last region. Hash-partition the key, or prefix it with a shard ID.

Scaling & Reliability

• Horizontal scaling is just adding nodes until you hit 1,024 workers; beyond that, steal bits from the timestamp or sequence, or give each datacenter its own epoch.
• No hot-path dependency: generation needs only the local clock and an already-held worker ID, so it keeps working during coordination-service outages.
• Failover: callers of the remote ID service retry another instance on a 503; every instance is interchangeable.
• Monitoring: alert on clock-drift errors, sequence-overflow waits (a sign of a hot node), and lease churn.
• Multi-region: dedicate datacenter bits to each region so regions never coordinate with each other.

Trade-offs

Interview Tips

• Start by listing the requirements that eliminate options: "64-bit and sortable" rules out UUID v4 immediately.
• Walk through at least three approaches (auto-increment, UUID, ticket server or range lease, Snowflake) before choosing.
• Draw the bit layout and justify each width with arithmetic: 41 bits ≈ 69 years, 12 bits = 4,096 per ms.
• Proactively raise clock drift and worker ID uniqueness; they are the two classic follow-up questions.
• Be precise about ordering: strictly increasing per node, approximately ordered across nodes.
• Mention the database angle: time-prefixed keys keep B-tree inserts local and caches small.
• If asked about UUIDs, mention UUID v7 as the modern, sortable, coordination-free alternative.

References

• System Design Primer: additional interview questions (random ID generation)
• Twitter Snowflake (archived source and design notes)
• Flickr: Ticket Servers, distributed unique primary keys on the cheap
• RFC 9562: Universally Unique IDentifiers (UUID v4 and v7)
• ByteByteGo System Design 101