Unique ID generation in distributed systems: snowflake

A traditional primary key uses auto_increment on one database: each insert takes the next integer. That works while one server holds all writes. Split writes across databases and the single counter becomes a bottleneck, cross-database ordering breaks, and adding or removing a server reshuffles the scheme. The interview sets five requirements up front: IDs must be unique, numeric only, fit in 64 bits, ordered by date, and flow at over 10,000 per second. Every candidate below is judged against exactly these five.

The chapter tries three designs before snowflake. Multi-master replication staggers auto_increment by server count, so two servers mint odd and even IDs. It fails three ways: painful across data centers, IDs do not rise with time across servers, and membership changes hurt. UUIDs need no coordination at all, but they are 128 bits, unsorted, and can carry non-numeric characters. Ticket servers centralize auto_increment in one allocator, which is simple for small scale yet is a single point of failure, and fixing that with more ticket servers reintroduces synchronization.

Snowflake stops generating an ID and starts composing one. The 64 bits are five fields: 1 sign bit fixed at 0, 41 bits of milliseconds since a custom epoch, 5 bits of datacenter ID, 5 bits of machine ID, and a 12-bit sequence number. Because the timestamp sits in the most significant bits, IDs sort by creation time with plain integer comparison. The custom epoch matters: Twitter used 1288834974657, which is Nov 04 2010, so the 41-bit counter starts near birth instead of wasting its range on the decades before the system existed.

1. Sign, 1 bit, always 0: reserved, keeps values non-negative.

2. Timestamp, 41 bits: ms since custom epoch. Max 2^41 minus 1 ms, about 69 years of runway.

3. Datacenter ID, 5 bits: 32 datacenters.

4. Machine ID, 5 bits: 32 machines per datacenter, 1,024 minting nodes total.

5. Sequence, 12 bits: 4,096 IDs per ms per machine. Zero except when a millisecond carries more than one ID.

Datacenter and machine IDs are picked at startup and then frozen: changing them mid-flight risks two nodes minting as one. Only the timestamp and sequence move at request time. When a request arrives, the generator reads the wall clock in milliseconds. If the millisecond matches the previous ID, it bumps the sequence. If the clock has advanced, it resets the sequence to zero. Then it packs the five fields into one integer and returns it. The two timing paths below are the whole state machine.

1. Read current time in ms. If it is behind the last timestamp, wait: never mint on a stale clock.

2. If time equals last timestamp, sequence plus 1. If sequence overflows 4,096, wait for the next ms.

3. If time is ahead, take the new timestamp and reset sequence to 0.

4. Shift and OR the fields: time at bit 22, datacenter at 17, machine at 12, sequence at 0.

5. Return the integer. Evening IDs exceed morning IDs by construction.

Four weaknesses, each with a price tag. Clock synchronization is the big one: the design assumes every generator shares the same clock, which breaks across cores and machines, so NTP plus monitoring is part of the system, not an afterthought. A backward clock must stall ID generation until time catches up, or new rows sort before old ones. Bursts past 4,096 IDs in one ms on one machine also stall into the next millisecond, trading latency for uniqueness. Node IDs are operationally load-bearing: a duplicated datacenter or machine ID mints true collisions, so allocation needs a registry and a review, not a config edit. And the 69-year timestamp eventually overflows, which a fresh epoch or a migration must handle.

In the field, Twitter mints tweet IDs with snowflake because timelines and cursors sort directly on the ID. Flickr chose ticket servers instead because photo uploads fit a central allocator at their scale. Same problem, different price accepted: coordination-free minting paid for with clock discipline, or simplicity paid for with a single point of failure. An ID generator is mission-critical either way, so high availability is a requirement, not a stretch goal.

The lines that matter are the clock guard, the sequence overflow wait, and the bit shifts. Everything else is argument plumbing.

EPOCH = 1288834974657  # Nov 04 2010, custom epoch saves range
SEQ_BITS, M_BITS, DC_BITS = 12, 5, 5
MAX_SEQ = (1 << SEQ_BITS) - 1

class Snowflake:
    def __init__(self, datacenter_id, machine_id):
        assert 0 <= datacenter_id < 32 and 0 <= machine_id < 32
        self.dc, self.mc = datacenter_id, machine_id
        self.last_ms, self.seq = -1, 0

    def _now_ms(self):
        import time
        return int(time.time() * 1000) - EPOCH

    def next_id(self):
        ms = self._now_ms()
        if ms < self.last_ms:
            raise ClockBackwardError(ms, self.last_ms)  # never mint stale time
        if ms == self.last_ms:
            self.seq += 1
            if self.seq > MAX_SEQ:
                ms = self._wait_next_ms(self.last_ms)  # burst: trade latency
                self.seq = 0
        else:
            self.seq = 0  # fresh millisecond, fresh sequence
        self.last_ms = ms
        return (ms << 22) | (self.dc << 17) | (self.mc << 12) | self.seq

    def _wait_next_ms(self, last):
        ms = self._now_ms()
        while ms <= last:
            ms = self._now_ms()
        return ms

class ClockBackwardError(Exception):
    pass

g = Snowflake(3, 9)
ids = [g.next_id() for _ in range(5)]
print(ids)
print('sorted by time:', ids == sorted(ids))
print('all unique:', len(set(ids)) == len(ids))