Design a Unique ID Generator

A unique ID generator produces identifiers that never repeat across many machines, without every ID request passing through one database. Primary keys, message IDs, order numbers, and event IDs all need this. In a single-node database, an auto-increment column is enough. In a distributed system, several nodes must create IDs concurrently, and they must not collide. Some designs also require IDs to be sortable by creation time.

Requirements

Functional requirements

• IDs are unique across the whole system, including across data centers.
• IDs fit in 64 bits (a common database integer type). A 128-bit ID is acceptable when this constraint is dropped.
• IDs are roughly sortable by creation time (k-sortable): an ID created later is larger, up to a small time tolerance.
• IDs consist of numeric values only, if used in numeric columns.

Non-functional requirements

• High throughput. Tens of thousands of IDs per second at least, with headroom for much more.
• Low latency. ID generation must not require a network round trip on the hot path, ideally.
• High availability. No single point of failure. The generator must keep working when a node or a data center fails.
• Uniqueness under failure. Restarts, clock adjustments, and concurrent generation must never produce duplicates.

Estimation

Assumptions: 10,000 IDs per second on average and 30,000 at peak, running for 30 years.

• Total IDs over 30 years at average rate: 10,000 x 86,400 x 365 x 30 ≈ 9.5 x 10^12.

• Bits needed: log2(9.5 x 10^12) ≈ 43.1, so at least 44 bits are needed even for a perfectly dense counter. A 64-bit ID has ample room: a timestamp plus a machine ID plus a sequence uses the remaining space with slack, because the space is sparse, not dense.

• Time bits: 41 bits of millisecond timestamps cover 2^41 ms = 2,199,023,255,552 ms ≈ 69.7 years.

• Per-machine rate: with 12 sequence bits, one machine can produce 4,096 IDs per millisecond, which is about 4.1 million per second. The peak of 30,000 per second is spread over several machines, so one machine is far below the limit.

• Storage: an 8-byte ID for 9.5 x 10^12 records is 76 TB just for the ID column, which shows why compact IDs matter compared with 16-byte UUIDs (about 151 TB, twice as much).

• Bandwidth: 30,000 IDs per second x 8 bytes is 240 KB/s if served over the network, and a request with headers is perhaps 200 bytes, so about 6 MB/s at peak. Network is not a constraint; round-trip latency (about 0.5 ms in a data center) is.

• Ticket-server load: at 30,000 per second, a database that does one write per ID needs 30,000 durable writes per second, which is beyond a single MySQL node with commit-per-write (typically a few thousand). With blocks of 1,000, it is 30 lease writes per second, trivial.

• Index cost: with 1 billion rows, a UUID v4 primary key is 16 GB of key data versus 8 GB for a 64-bit ID, before secondary indexes, which each repeat the primary key. Random inserts also touch any leaf page, so the working set for writes is the whole index, while time-ordered IDs touch only the rightmost pages.

What the numbers imply: throughput and bit-space are not the constraint (one Snowflake worker does about 4 million per second, and 64 bits last about 70 years), so the choice is driven by coordination, clock dependence, and index behavior. Use at least 3 workers for availability, not for throughput, and size the machine-ID field for instance count (1,024 workers) rather than for load.

See back-of-envelope estimation for the arithmetic method.

API design

Most deployments embed the generator as a library or run it as a small internal service.

GET /v1/ids                -> { "id": 7231498234872832 }
GET /v1/ids?count=100      -> { "ids": [ ... ] }

Library form: next_id() -> u64. A batch call amortizes network cost when the generator runs as a service. IDs should be treated as opaque by clients, so the format can change. When IDs are exposed to end users, remember that a time-ordered ID reveals its creation time and, for counters, the approximate volume of records.

Data model

The generator itself is nearly stateless. The state it needs is:

The worker ID assignment needs a durable, consistent source such as ZooKeeper or etcd (see consensus) or a static configuration per host. It happens once at startup, not per ID.

High-level design

Several approaches exist. Their comparison:

Architecture of the Snowflake approach:

flowchart LR
    S1[Service A with ID library] --> ID1[Worker 1]
    S2[Service B with ID library] --> ID2[Worker 2]
    S3[Service C with ID library] --> ID3[Worker 3]
    ID1 -. worker ID at startup .-> ZK[(Coordination service)]
    ID2 -. worker ID at startup .-> ZK
    ID3 -. worker ID at startup .-> ZK
    NTP[Time source: NTP] -. clock sync .-> ID1
    NTP -.-> ID2
    NTP -.-> ID3

Each worker generates IDs entirely from local state and the local clock. There is no network call per ID.

Deep dive

UUIDs

A UUID (universally unique identifier) is 128 bits, standardized in RFC 9562 (which superseded RFC 4122). Version 4 fills 122 bits with random data. The chance that two random UUIDs collide is so low that it is ignored in practice: generating about 2.7 x 10^18 UUIDs gives a 50% probability of at least one collision, according to the birthday bound for 122 bits. Advantages are complete independence between generators and no coordination. Disadvantages:

• 16 bytes per ID, double a 64-bit integer, and it doubles the size of every index that includes it.
• Random order. In a B-tree primary key index, inserts land at random leaf pages, which causes page splits, poor cache locality, and higher write amplification (see database indexing).
• Not human-friendly, and not numeric.

UUID version 7 (defined in RFC 9562) puts a 48-bit Unix millisecond timestamp in the most significant bits, so new IDs append near the end of an index. ULID is a similar earlier format: a 48-bit timestamp plus 80 random bits. These keep the coordination-free property and fix the locality problem, but remain 128 bits.

Database ticket servers

A ticket server is a dedicated database whose only job is to hand out numbers. Flickr described this design: a table with an auto-increment column, and REPLACE INTO followed by SELECT LAST_INSERT_ID() to obtain a new value. To avoid a single point of failure, run two ticket servers, one issuing odd numbers and the other even numbers (auto-increment step 2, offsets 1 and 2), and let clients alternate between them. If one fails, the other continues, and the ID space never overlaps.

Limits: every ID needs a network round trip and a database write; IDs from the two servers interleave only approximately in time order; scaling beyond a few servers requires wider steps and careful offset management; and the servers are a centralized dependency. Clients can reduce load by requesting a block of, say, 1,000 IDs per call and issuing them locally. Crashing loses the unused part of the block, which is harmless since the ID space is large.

Why chosen or not: ticket servers give strictly unique, compact IDs with almost no clock risk, and blocks fix the throughput problem, but IDs from different clients are only ordered per block, and every client depends on the ticket database during refills. Sizing a block: it should last longer than a database failover, so at 3,000 IDs per second per client, a block of 1,000 lasts 0.3 s (too small); use 100,000 (about 33 s) or prefetch the next block when 20 percent remains. The cost is a larger gap after a crash, harmless in a 64-bit space.

Snowflake-style IDs

Twitter's Snowflake divides 64 bits into fields:

| 1 bit  | 41 bits            | 10 bits    | 12 bits  |
| unused | timestamp (ms)     | machine ID | sequence |

• Sign bit (1). Always 0, so the ID stays positive as a signed 64-bit integer.
• Timestamp (41). Milliseconds since a custom epoch (for example, the service launch date). 41 bits last about 69.7 years.
• Machine ID (10). Split as needed (for example, 5 bits data center and 5 bits machine), for up to 1,024 workers.
• Sequence (12). A counter within one millisecond on one worker, 4,096 values. It resets to 0 each millisecond.

Because the timestamp occupies the high bits, sorting IDs numerically sorts them by creation time (to millisecond granularity, across workers within clock skew). Different workers never produce the same ID because their machine IDs differ, and one worker never repeats because its (timestamp, sequence) pairs are strictly increasing.

Implementation, with the clock passed in so the behavior is deterministic:

import java.util.List;

public class Main {
    static final long EPOCH_MS = 1_700_000_000_000L;
    static final int MACHINE_BITS = 10;
    static final int SEQUENCE_BITS = 12;
    static final long MAX_SEQUENCE = (1L << SEQUENCE_BITS) - 1;

    // Closed set of outcomes: an ID, or one of two reasons for refusing.
    sealed interface IdResult {
        record Issued(long id) implements IdResult {}
        record ClockMovedBackwards(long byMs) implements IdResult {}
        // all 4,096 values used in this millisecond: caller retries in the next one
        record SequenceExhausted() implements IdResult {}
    }

    record Parts(long timestampMs, long machine, long sequence) {}

    static final class Snowflake {
        private final long machineId;
        private long lastMs;
        private long sequence;

        Snowflake(long machineId) {
            if (machineId < 0 || machineId >= (1L << MACHINE_BITS)) {
                throw new IllegalArgumentException("machine id out of range: " + machineId);
            }
            this.machineId = machineId;
        }

        // synchronized: the check and the update of (lastMs, sequence) must be one step
        synchronized IdResult nextId(long nowMs) {
            if (nowMs < lastMs) {
                return new IdResult.ClockMovedBackwards(lastMs - nowMs);
            }
            if (nowMs == lastMs) {
                if (sequence == MAX_SEQUENCE) {
                    return new IdResult.SequenceExhausted();
                }
                sequence++;
            } else {
                sequence = 0;
            }
            lastMs = nowMs;
            return new IdResult.Issued(((nowMs - EPOCH_MS) << (MACHINE_BITS + SEQUENCE_BITS))
                    | (machineId << SEQUENCE_BITS)
                    | sequence);
        }
    }

    static Parts describe(long id) {
        long sequence = id & MAX_SEQUENCE;
        long machine = (id >> SEQUENCE_BITS) & ((1L << MACHINE_BITS) - 1);
        long ts = (id >> (MACHINE_BITS + SEQUENCE_BITS)) + EPOCH_MS;
        return new Parts(ts, machine, sequence);
    }

    public static void main(String[] args) {
        var ids = new Snowflake(7);
        long t = EPOCH_MS + 1_000;
        for (long now : List.of(t, t, t, t + 1)) {
            if (ids.nextId(now) instanceof IdResult.Issued issued) {
                System.out.println(issued.id() + " -> " + describe(issued.id()));
            }
        }
        System.out.println(ids.nextId(t - 5));
    }
}

4194332672 -> Parts[timestampMs=1700000001000, machine=7, sequence=0]
4194332673 -> Parts[timestampMs=1700000001000, machine=7, sequence=1]
4194332674 -> Parts[timestampMs=1700000001000, machine=7, sequence=2]
4198526976 -> Parts[timestampMs=1700000001001, machine=7, sequence=0]
ClockMovedBackwards[byMs=6]

Details that matter:

• Sequence overflow. After 4,096 IDs in one millisecond, the generator must wait for the next millisecond instead of reusing a value. The code above returns SequenceExhausted, and the caller retries once the clock advances.
• Clock moving backwards. NTP corrections or a virtual machine restore can move the clock back. A generator that ignores this can reissue a (timestamp, sequence) pair and produce duplicates. Safe reactions: refuse and return an error, wait until the clock catches up (for small offsets), or persist the last timestamp and refuse to start below it after a restart. The code above returns an error.
• Restarts. After a crash the in-memory lastMs is lost. If the clock has not moved back, new timestamps are larger than any previous ones anyway. Persisting the last timestamp periodically guards against a restart onto a clock that is behind.
• Machine ID collisions. Two workers with the same machine ID would produce duplicates. Assign IDs from a coordination service with leases, or from a static per-host configuration, and never reuse a worker ID while an older holder may still be running.
• Clock skew across machines. Two workers with clocks that differ by tens of milliseconds produce IDs that are ordered by their local clocks, not by real time. IDs are only approximately time-ordered. Do not use them to establish strict causal order. See time, clocks and ordering.

Concrete handling policy for clock regression: if the clock is behind by at most 5 ms, sleep until it catches up (the caller sees a few ms of latency); if more, fail requests from that worker and alert, and let load balancers route to other workers. Never generate from a wall-clock that jumps: prefer a monotonic clock for elapsed time anchored to a synchronized wall-clock reading at startup, and re-anchor slowly (slew). Skew in practice is sub-millisecond to a few ms with well-run NTP inside a data center, and tens of ms across the internet; leap seconds are best handled by smearing. Worker ID leases: a TTL of about 30 to 60 seconds renewed every third of the TTL, and a worker that fails to renew stops generating before the lease expires, so a reassigned ID is never used by two live workers (this relies on bounded clock drift between the worker and the coordination service; a safety margin covers it).

Alternatives to per-worker clocks: a central sequencer (strict global order, one round trip per ID or block, and a bottleneck), or hybrid logical clocks, which stay close to physical time and never go backward by taking the maximum of the local physical time and the last value seen, at the cost of a logical counter in the ID and more complex layout. Snowflake is chosen when 64-bit compact, roughly sorted IDs are needed with no per-ID coordination; UUID v7 is chosen when 128 bits are acceptable and worker ID management is unwanted.

Hot-shard note: time-ordered IDs concentrate inserts on the newest range. If the ID is used directly as a range-partitioned shard key, all new writes hit one partition; hash the ID (or put a shard ID in the high bits) for the partition key while keeping the ID itself sortable for the index.

Choosing bit allocations

The layout can be adapted to the workload:

• More machine bits allow more workers and fewer sequence bits reduce per-worker throughput per millisecond.
• Fewer timestamp bits shorten the lifetime. With a 1-second resolution, 32 bits last 136 years, and the freed bits go to the sequence.
• A shard or tenant ID can replace part of the machine ID, so the ID also locates its data partition (as in Instagram's ID scheme, which embeds a logical shard ID).

Failure modes

At 10x scale (300,000 IDs per second): still trivial for one worker, so nothing changes in throughput. The parts that change are operational: more instances means more worker-ID churn (leases with reclaim matter, and 1,024 IDs can be exhausted by autoscaling containers, so move to 12 or 13 machine bits by taking bits from the sequence, which is unused at this rate), more clock-monitoring, and, for ticket servers, the need for wider steps or block leasing. Downstream, ID-column size and hot inserts matter more than generation.

Bottlenecks and scaling

• Throughput. A worker generates millions of IDs per second from memory. Add workers for fault tolerance and locality, not for throughput.
• Worker ID space. 1,024 workers is the ceiling with 10 machine bits. Long-lived services with many short-lived instances (containers) can exhaust it if IDs are not released. Use leases with expiry and reclaim IDs from dead workers only after the lease period elapses.
• Coordination service. It is consulted only at startup, so its failure prevents new workers from starting but does not stop existing ones.
• Clock quality. The dependency on clocks is the main risk. Run NTP or a more accurate time source and alert on clock offset and on backward-jump errors.
• Multi-region. Encode a region in the machine ID bits so regions cannot collide and need no cross-region coordination.

Trade-offs and follow-up questions

• Why not a single auto-increment database? It is a throughput bottleneck and a single point of failure, and it needs a round trip per ID. It also reveals order volume.
• UUID or Snowflake? UUIDs need no coordination and no clock discipline, at twice the size and (for v4) poor index locality. Snowflake IDs are compact and time-ordered but require worker ID management and reasonable clocks.
• Are IDs strictly increasing across machines? No. They are ordered by timestamp with millisecond resolution and by worker and sequence within the same millisecond. Events from different workers within the same millisecond have arbitrary relative order.
• What if two workers get the same machine ID? IDs collide only if they generate in the same millisecond with the same sequence, which makes the bug intermittent and hard to find. Prevent with leases and fencing; detect with unique constraints and an alert.
• What if the clock goes back 2 seconds after a VM restore? The worker refuses (offset above the 5 ms wait threshold), traffic shifts to other workers, and it resumes once its clock passes the last persisted timestamp.
• What if you need more than 4,096 IDs per millisecond per worker? Take bits from machine ID or timestamp, or run more workers on the same host with distinct IDs; 4 million per second per worker is rarely the limit.
• What if you need strictly ordered IDs (not k-sortable)? Use a single sequencer with block leasing and accept its availability cost, or a consensus-backed counter; strict order across nodes cannot be had for free.
• What if IDs need to be unpredictable? Use UUID v4, or encrypt or permute a counter or Snowflake ID with a keyed block cipher at the API boundary and store the internal ID.
• What about the UUID collision risk? For v4, about 2.7 x 10^18 IDs for a 50 percent chance; at 30,000 per second that is far beyond any practical horizon, so the real risks are bad random sources (for example duplicated VM images), not the math.
• Can IDs be guessed? Time-ordered IDs are predictable. If an ID grants access to a resource, authorize the access separately and do not rely on ID secrecy. See design a URL shortener for scrambling counters into non-sequential keys.
• How would IDs work across shards for a sharded database? Embedding a logical shard ID in the ID (as described above) lets the ID locate its shard without a lookup and keeps inserts time-ordered within each shard. Assigning shards round robin or by hash of another field spreads the load evenly. See sharding and partitioning.