Step 6: ID Generation Strategies

Written out in order, the fields are:

[timestamp: 41 bits][region+machine: 10 bits][seq: 12 bits]

Anyone who knows the layout can take an ID apart, which is why this format is not opaque. Teams often ship the decoding as a small helper that turns an ID from a log line into the exact node and millisecond that produced it:

def decode(id_value):
    return {
        "created_at_ms": (id_value >> 22) + EPOCH,
        "region":  (id_value >> 17) & 0x1F,
        "machine": (id_value >> 12) & 0x1F,
        "sequence": id_value & 0xFFF,
    }

3. Building the ID safely on one node

When the accounts service asks for Priya's ID, the node runs a short routine:

def next_id():
    with lock:
        now = current_millis() - EPOCH
        if now < last_ms:
            raise ClockMovedBackwards(last_ms - now)    # Step 8 decides: wait or leave the pool
        if now == last_ms:
            seq = (seq + 1) & 0xFFF
            if seq == 0:                                 # 4,096 used in this millisecond
                now = wait_until_after(last_ms)
        else:
            seq = 0
        last_ms = now
        return (now << 22) | (machine_id << 12) | seq

The lock guards two comparisons and an increment, which a CPU runs millions of times per second, so it costs almost nothing. The routine runs in well under a microsecond, so most of a request's latency is network time. The node returns the 64-bit value as a decimal string, as Step 4 requires, because JavaScript would turn a 64-bit number into a float and lose its last digits.

Each node keeps its own machine number, last timestamp, and counter, but none of that state is shared, so no request depends on any other node. The routine is safe only if two things hold: no two live nodes share a machine number, and no node's clock runs backward.

Machine numbers. A ZooKeeper cluster, a coordination service, hands out the 10-bit machine numbers. When a generator starts, it creates an ephemeral node such as /id-generators/<region>/<machine_id>, an entry that ZooKeeper deletes automatically when the creating session ends. Because ZooKeeper tracks the live entries, two live generators never hold the same number. The coordinator is used once, at startup, and is never on the path of Priya's request.

If ZooKeeper becomes unreachable, nodes that already hold numbers keep generating, and only new nodes cannot join. Because an expired session deletes its entry, a generator should keep using its number, re-register it when the coordinator returns, and ask for a new one only if it was taken in the meantime.

When a generator dies, its machine number becomes free, but reissuing it at once is unsafe. If the new holder's clock is behind the old holder's last timestamp, the two can produce the same ID. Step 8 therefore holds a freed number back for a quarantine period longer than the clock error we are willing to accept.

Clocks. Every generator runs an NTP (Network Time Protocol) daemon, which keeps its clock within a few milliseconds of true time. Small differences between nodes only reorder IDs slightly and never create duplicates. That is also why IDs are strictly ordered within one node but only roughly ordered across the fleet: two nodes read their own clocks, which differ by a few milliseconds.

The real danger is a clock that moves backward, which a sudden NTP correction, a virtual machine restored from a snapshot, or a manual change can each cause. If the clock of the node serving Priya moves back 100 ms, it repeats timestamps it has already used, with the same machine number and a reset sequence, which is exactly how a duplicate is made. The routine therefore refuses to generate while the clock is behind the last timestamp it used. NTP can fix a clock by stepping it to the right time at once or by slewing it, running it slightly fast or slow until it catches up. Slewing never moves the clock backward, so generator hosts allow only slewing in normal operation, and they take time from a source that spreads a leap second across many hours instead of repeating a second. A clock that jumps forward is less dangerous: IDs stay unique and only look out of place in a sorted list. Step 8 covers the remaining clock repairs.

4. Priya's opaque profile ID

The opaque path has nothing to coordinate. The node takes random bytes from a CSPRNG, a cryptographically secure pseudo-random number generator, sets the version and variant bits that UUIDv4 requires, and formats the result in the standard form, such as f47ac10b-58cc-4372-a567-0e02b2c3d479. This takes microseconds, and a generator per thread removes any contention.

The service does not check for duplicates. At 10^10 IDs a day, the system is nowhere near the volume at which a collision becomes plausible, so the size of the space is the guarantee. The one thing to get right is the randomness source, because a weak generator, or one seeded the same way on several machines, can repeat values. This path needs no coordinator and no clock, so none of the failures in section 3 can affect it.

The format exists for its security property. If Priya's profile link used a sequential ID, an attacker could step from her ID to the next one and walk through other people's records. A random ID makes that search hopeless, and it reveals neither when she signed up nor how many users exist. The trade-off is that opaque IDs cannot be sorted by creation time, so a caller that needs the time stores it in a separate field. The guidance to callers is short: use sortable IDs when order or a compact key matters, and opaque IDs when the value will be public.

5. What the service stores, and what happens when parts fail

Uniqueness here is computed, never looked up. The service keeps no record of issued IDs, which avoids a store that would have to accept every ID at the rate they are made, and there is no database or cache on the request path. Operational logs record counts, not IDs: IDs per second, sequence waits, and backward clock events.

The only durable state is in the coordinator: about one small entry per active generator, at most around a thousand. That state must survive a full restart, because losing it while every node restarted could assign one machine number twice. The coordinator therefore runs with disk persistence and is recovered before any generator starts. If its data were ever lost, the safe procedure is to assign numbers by hand from a recorded mapping.

A generator node fails. IDs it already issued stay valid, because they are only numbers that clients hold. ZooKeeper notices the lost session, a replacement starts and registers, and it does not receive the dead node's number until that number's quarantine ends.

A data center fails. Its clients move to another region. The region number is part of every sortable ID, so IDs from the other region remain unique. When the failed region returns, its clocks have moved forward, so its new IDs are larger than its old ones, and the gap does not matter because IDs never need to be consecutive.

The coordinator fails. As section 3 described, existing nodes keep generating and only new nodes cannot join.

A bug slips through. Each node keeps the last ID it issued and checks that every new sortable ID is larger. Keeping millions of recent IDs per node would be expensive, but keeping one costs nothing, and a failed check points straight at a clock or sequence bug.

The fleet outgrows 1,024 nodes. Bits can move from the sequence to the machine field: 12 machine bits and 10 sequence bits allow 4,096 nodes at 1,024 IDs per millisecond each.

Priya's two IDs come from two algorithms in one service. The sortable one depends on the bit layout, the machine numbers, and the clocks, and the opaque one only on a good random source.