← CatZep/Engineering Guides/System Design/Foundations

Designing a Unique ID Generator

A system design interview guide to handing out identifiers that are unique across every machine in a distributed system, without a central bottleneck, while staying small, numeric, and roughly ordered by time.

Distributed ID allocation separates uniqueness, ordering, and availability. A counter can use replicated authority and range allocation; it is not inevitably a single point of failure or a per-ID bottleneck. Snowflake trades coordination frequency for strict worker identity, clock, sequence, restart, and horizon requirements.

Concepts to understand first

Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.

1. Requirements

Before choosing a design, pin down what an ID actually has to satisfy. In an interview these constraints are what justify ruling out simpler options, so state them explicitly.

Clarifying questions to ask first: How many IDs per second at peak? How many data centers and generator machines? Must IDs be strictly increasing, or is “roughly by time” enough? Can an ID reveal anything (creation time, volume)? Will IDs be used in JavaScript clients?

2. Back-of-the-Envelope Estimation

3. Approaches and Their Drawbacks

There are several well-known ways to generate IDs in a distributed setting. Each makes a different trade, and walking through why the first three fall short is the cleanest way to motivate the fourth.

The pattern across the first three is a tug-of-war between coordination and independence. Multi-master and the ticket server stay correct by coordinating, which limits scaling and creates bottlenecks. UUIDs avoid coordination entirely but pay for it in size and the loss of ordering. Snowflake threads the needle: it needs no coordination on the hot path, yet still produces compact, ordered, numeric IDs.

4. The Snowflake Approach

The key insight behind Snowflake (originally from Twitter) is to divide and conquer the 64 bits. Instead of treating an ID as one opaque counter, you partition the bits into sections, and let a different source of uniqueness fill in each section. As long as the combination of all sections is unique, the whole ID is unique — and crucially, each section can be filled in locally, with no call to a central server.

Reading the layout from the most significant bit to the least:

• A zero sign bit yields a nonnegative signed integer, including zero. The layout's timestamp/worker/sequence combination is unique only if those fields are allocated without reuse under the stated restart and worker-ownership model.
• The timestamp (41 bits) sits in the high-order positions. Because it is the most significant field, IDs naturally sort by time: a later timestamp produces a numerically larger ID.
• The data center ID (5 bits) and machine ID (5 bits) together identify the exact node that produced the ID. They make IDs from different nodes unique even when those nodes generate at the same millisecond.
• The sequence number (12 bits) distinguishes IDs produced by the same node within the same millisecond.

Two correctly allocated timestamp/worker/sequence tuples differ, but duplicated worker assignment, clock/sequence reuse, or unsafe restart can repeat every field. The allocation preconditions, not the encoding alone, guarantee uniqueness.

# Use the complete bounded-wait Python model below.
# Preconditions: exclusive worker identity, safe restart/nonreuse, finite horizon.
value = generator.next_id()
# On rollback/exhaustion timeout, state remains unchanged.
# Approximate timestamp order is not a delivery cursor or global causal order.

Here is a complete, runnable version in Python. It checks for a backward clock, handles the sequence running out, and includes a decoder:

import math, threading, time

def pack_id(elapsed_ms, worker, sequence):
    """Encode the 41/10/12 unsigned fields. Not an allocator: callers must
    ensure exclusive worker ownership and restart-safe nonreuse of field tuples."""
    for value, bits in ((elapsed_ms, 41), (worker, 10), (sequence, 12)):
        if type(value) is not int or not 0 <= value < 1 << bits:
            raise ValueError(f"integer field must fit {bits} bits")
    return (elapsed_ms << 22) | (worker << 12) | sequence

class Snowflake:
    """Bounded-wait, single-process model. Pre: this worker is exclusively
    owned and no previous process used these timestamp/sequence tuples.
    NOT restart-safe: production allocation must enforce those preconditions.
    State changes only after a valid tuple can be returned; failures preserve it.
    """
    def __init__(self, worker, epoch_ms=1577836800000, wall_ms=None,
                 monotonic=time.monotonic, pause=time.sleep, wait_seconds=0.01):
        pack_id(0, worker, 0)  # validate worker, not an optimizable assert
        if type(epoch_ms) is not int or not math.isfinite(wait_seconds) or wait_seconds <= 0:
            raise ValueError("integer epoch and finite positive wait required")
        self.worker, self.epoch = worker, epoch_ms
        self.wall = wall_ms or (lambda: time.time_ns() // 1_000_000)
        self.monotonic, self.pause, self.wait = monotonic, pause, wait_seconds
        self.last, self.sequence = -1, 0
        self.lock = threading.Lock()

    def next_id(self):
        with self.lock:
            deadline = self.monotonic() + self.wait
            target = self.last + (self.sequence == 4095)
            # Invariant: generation state is unchanged until a valid tuple exists.
            # Bound: at most 1000 polls, also bounded by a local elapsed deadline.
            for _ in range(1000):
                timestamp = self.wall() - self.epoch
                pack_id(timestamp, self.worker, 0)  # timestamp horizon/type
                if timestamp >= target:
                    sequence = self.sequence + 1 if timestamp == self.last else 0
                    value = pack_id(timestamp, self.worker, sequence)
                    self.last, self.sequence = timestamp, sequence
                    return value
                remaining = deadline - self.monotonic()
                if remaining <= 0:
                    break
                self.pause(min(remaining, 0.0001))
            raise TimeoutError("clock rollback or exhausted millisecond; state unchanged")

def decode(value):
    if type(value) is not int or not 0 <= value < (1 << 63):
        raise ValueError("nonnegative signed-63-bit ID required")
    return {"ms_since_epoch": value >> 22, "datacenter": (value >> 17) & 31,
            "machine": (value >> 12) & 31, "sequence": value & 4095}

# Demo only: exclusive worker ownership and a fresh process are assumed.
generator = Snowflake(worker=(3 << 5) | 7)
values = [generator.next_id() for _ in range(10_000)]
assert len(set(values)) == len(values) and values == sorted(values)
print("Single-process uniqueness/order checks pass; restarts need durable allocation.")

Decoding by hand: the ID 517815304351786 splits into 517815304351786 >> 22 = 123456789 ms after the epoch, data center 3, machine 7, and sequence 42.

5. Snowflake Fields and the Math

Each field's bit width sets a concrete limit. Working through the arithmetic shows why these particular sizes are a sensible default, and what each one buys you.

The layout offers 4096 sequences per millisecond per worker and 1024 workers: a bit-space ceiling of about 4.19 billion encoded tuples/s across workers, not measured throughput. Compute, locks, clock granularity, and allocation safety determine real capacity.

Timestamp-ID order can support approximate chronological range queries, but a highest-seen ID is not a safe delivery/commit cursor: a late commit with a smaller ID may be skipped. Use an ordered committed stream and a contiguous cursor for reliable replay.

6. Assigning Machine IDs Safely

The 10 worker bits in the common layout provide 1024 identities, not automatic allocation. Use a configured exclusive assignment or a durable coordinator. Do not recycle an ID just because its previous lease expired: the old process may be paused and can still generate IDs when it resumes.

A safe allocation scheme needs a documented incarnation/fencing rule plus prevention of timestamp/sequence reuse. Options include a larger incarnation field, durable range reservations, or a persisted high-water mark that the new holder waits strictly beyond. The uniqueness contract must include crash ordering: record a reservation durably before issuing any ID from it. A local saved timestamp without sequence or strict restart waiting is not enough.

A coordinator's lease is a liveness mechanism. It cannot instantly stop local ID issuance by a frozen holder; downstream token checks can reject old effects but cannot erase duplicate IDs that have already escaped.

7. Clock Skew and Rollback

Wall time may move backward, and its millisecond epoch field has a finite horizon. Validate worker fields and 0 ≤ elapsed_ms < 2^41 with explicit exceptions, not assertions that Python can disable. Use a monotonic deadline to bound any waiting; a local monotonic reading is not a globally shared timestamp epoch.

On rollback or sequence exhaustion, either wait within that bound or fail without changing the last issued timestamp/sequence. Never reset the sequence early and then return an error after a timeout. A production implementation must also handle process restart at an already-used timestamp and concurrent calls with serialization.

The sign bit set to zero yields a nonnegative integer, including zero. The 4096 IDs/ms/worker figure is the bit-space ceiling, not measured Python throughput. A finite 64-bit space cannot promise unlimited-lifetime uniqueness. The epoch, timestamp horizon, throughput, and worker reuse policy must be explicit.

8. Tradeoffs and Alternatives

Worked example: one millisecond, two workers, one restart

Use a small sequence space to make exhaustion and reuse visible.

Run a small, testable model

Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:

python3 concepts.py ids
python3 concepts.py test

The model checks field bounds and encoding/decoding, and demonstrates why a restarted timestamp/sequence pair repeats an ID. It is not a restart-safe allocator.

The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.

9. A 45-Minute Interview Walkthrough

10. Common Mistakes

• Two nodes with the same machine ID. Every other safeguard is useless if this happens.
• Using the Unix epoch. It wastes about 50 years of the 41-bit range on the past.
• Sending 64-bit IDs to JavaScript as numbers. JS numbers are exact only up to 2⁵³ ≈ 9.0 × 10¹⁵. Larger IDs get silently rounded. Send them as strings too (Twitter's API added an id_str field for this reason).
• Claiming strict global ordering. Across nodes, IDs are only roughly ordered, and clock skew between nodes makes it rougher.
• Forgetting IDs leak information. Anyone can decode the creation time, and sequential IDs reveal how many records you create. If that matters, do not expose raw IDs, or use random IDs for public URLs.

11. Summary

Designing a unique ID generator is an exercise in getting global uniqueness without global coordination. Snowflake achieves it by partitioning 64 bits so each part can be filled in locally.

12. Check Yourself

1. How many years does a 41-bit millisecond timestamp last, and why use a custom epoch?
   Answer

   2⁴¹ ms ≈ 69.7 years. Counting from a recent date means the whole range lies in the future instead of wasting decades since 1970.

2. You need 4,000 generator machines but only 500 IDs per millisecond per node. How could you re-budget the 22 non-time bits?
   Answer

   4,000 nodes need 12 bits (4,096). That leaves 10 bits of sequence = 1,024 per ms, which covers 500. So use 41 time + 12 node + 10 sequence (+1 sign).

3. Decode the ID (1000 << 22) | (2 << 17) | (5 << 12) | 9.
   Answer

   Timestamp 1,000 ms after the epoch, data center 2, machine 5, sequence 9.

4. A node's clock jumps back by 2 seconds while it is running. What should the generator do, and why?
   Answer

   Refuse to use the old timestamps. 2 s is probably above the tolerance, so raise an error and leave rotation instead of blocking for 2 s or risking duplicates.

5. Why is a random 64-bit ID risky at one billion IDs, while a 122-bit random UUID is fine?
   Answer

   Birthday bound: about n²/(2·2^b). For b = 64 that is about 2.7% chance of some collision. For b = 122 it is about 10^-19.

6. Why can two IDs made 0.3 ms apart on different nodes sort in the “wrong” order?
   Answer

   Within one millisecond, the lower bits are ordered by node ID and sequence, not by the true instant. Clock skew between nodes can also shift them by a few ms.

13. Key Terms

Snowflake ID

A 64-bit ID made of timestamp, node ID and sequence number.

Custom epoch

The chosen “time zero” that the timestamp counts from.

Sequence number

A counter that separates IDs made in the same millisecond on one node.

Clock skew

Clocks on different machines disagreeing, or one clock jumping.

NTP

Network Time Protocol, which keeps machine clocks in sync.

Monotonic clock

A clock that never goes backwards, good for measuring intervals.

Ticket server

A central counter service that hands out the next ID or block of IDs.

UUID v4 / v7

128-bit IDs: v4 is random, v7 starts with a millisecond timestamp.

Birthday paradox

Collisions become likely after about √(2^b) random b-bit values.

14. Further Reading

• Twitter engineering blog, “Announcing Snowflake” (2010), and the original open-source Snowflake repository.
• Instagram engineering, “Sharding & IDs at Instagram” (2012).
• Flickr (code.flickr.com), “Ticket Servers: Distributed Unique Primary Keys on the Cheap” (2010).
• RFC 9562, “Universally Unique IDentifiers (UUIDs)” (2024), which defines UUID v7.
• Alex Xu, System Design Interview, Vol. 1, chapter “Design a Unique ID Generator in Distributed Systems”.