Distributed ID generation

Deep dive

How it works

In: wall-clock time, worker number (Snowflake) or random bytes (UUIDv7) · Out: a unique, roughly time-sorted 64- or 128-bit ID · State: last_ms, seq, worker (about 16 bytes) · Cost: O(1), one clock read, no network

1. Pick a layout. 64-bit (fits a signed i64 and an 8-byte key): 0 | 41 bit ms since custom epoch | 10 bit worker | 12 bit sequence. 128-bit UUIDv7: 48 bit Unix ms | ver 7 | 12 rand | var 10 | 62 rand.
2. Snowflake: read the clock. If ms == last_ms, increment the sequence; if it would pass 4095, wait for the next ms. If ms > last_ms, reset the sequence to 0. If ms < last_ms the clock went backwards: refuse or sleep, never issue.
3. Worker numbers must be unique among live generators. Assign them from a registry or a lease (ZooKeeper/etcd/DB row); a restarted node must not reuse a live node's number.
4. UUIDv7: take the ms, fill the rest with random bytes, set version and variant bits. For ordering within one ms on one node, RFC 9562 allows a counter in the leftmost random bits (Method 1) or a randomly seeded counter that is incremented (Method 2).

Snowflake  [0][ 41 ms ......................][10 worker][12 seq ]   8 bytes
UUIDv7     [ 48 ms .........][7][12][10][ 62 random ............]  16 bytes

Code

use std::time::{SystemTime, UNIX_EPOCH};

const WORKER_BITS: u32 = 10;
const SEQ_BITS: u32 = 12;
const SEQ_MASK: u64 = (1 << SEQ_BITS) - 1;
const TS_MASK: u64 = (1 << 41) - 1;
/// Custom epoch (2020-01-01 UTC) in Unix ms: 41 bits last ~69.7 years from it.
pub const EPOCH_MS: u64 = 1_577_836_800_000;

#[derive(Debug, PartialEq)]
pub enum IdError {
    ClockBackwards(u64), // ms the clock is behind the last issued id
    SequenceExhausted(u64), // 4096 ids issued this ms; retry at this ms
    EpochOverflow,
}

/// 1 sign bit (0) | 41 bits ms since EPOCH_MS | 10 bits worker | 12 bits sequence
pub struct Snowflake {
    worker: u64,
    last_ms: u64,
    seq: u64,
}

impl Snowflake {
    /// `worker` must be unique among live generators (lease it, see Pitfalls).
    pub fn new(worker: u64) -> Self {
        assert!(worker < (1 << WORKER_BITS));
        Snowflake { worker, last_ms: 0, seq: 0 }
    }

    /// Pure core: the clock is a parameter so rollback and overflow are testable.
    pub fn next_at(&mut self, now_unix_ms: u64) -> Result<u64, IdError> {
        let ts = now_unix_ms.saturating_sub(EPOCH_MS);
        if ts > TS_MASK { return Err(IdError::EpochOverflow); }
        if ts < self.last_ms { return Err(IdError::ClockBackwards(self.last_ms - ts)); }
        if ts == self.last_ms {
            // Check before mutating: a retry in the same ms must not wrap to a used seq.
            if self.seq == SEQ_MASK { return Err(IdError::SequenceExhausted(ts + 1 + EPOCH_MS)); }
            self.seq += 1;
        } else {
            self.last_ms = ts;
            self.seq = 0;
        }
        Ok((ts << (WORKER_BITS + SEQ_BITS)) | (self.worker << SEQ_BITS) | self.seq)
    }

    /// Blocking wrapper: sleeps through short stalls, surfaces long rollbacks.
    pub fn next(&mut self) -> Result<u64, IdError> {
        loop {
            let now = SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_millis() as u64;
            match self.next_at(now) {
                Err(IdError::SequenceExhausted(_)) => std::thread::sleep(std::time::Duration::from_micros(100)),
                Err(IdError::ClockBackwards(d)) if d <= 5 => std::thread::sleep(std::time::Duration::from_millis(d)),
                r => return r,
            }
        }
    }
}

pub fn unpack(id: u64) -> (u64, u64, u64) {
    ((id >> 22) + EPOCH_MS, (id >> SEQ_BITS) & 0x3FF, id & SEQ_MASK)
}

/// UUIDv7 (RFC 9562 section 5.7): 48-bit Unix ms | ver 7 | 12 rand | var 10 | 62 rand.
pub fn uuid_v7(unix_ms: u64, rand: [u8; 10]) -> [u8; 16] {
    let mut u = [0u8; 16];
    u[..6].copy_from_slice(&unix_ms.to_be_bytes()[2..]);
    u[6..].copy_from_slice(&rand[..10]);
    u[6] = (u[6] & 0x0F) | 0x70; // version 7
    u[8] = (u[8] & 0x3F) | 0x80; // variant 10
    u
}

next_at takes the clock as a parameter so rollback and sequence exhaustion are testable; the exhaustion check happens before mutating state, otherwise a retry in the same ms would wrap to an already-used sequence. Compiled and run with asserts: 4096 distinct increasing IDs in one ms, then SequenceExhausted, rollback detected, unpack round-trips, no duplicates across 5000 attempts in one ms; one worker reached about 4.0 million IDs/s on an Apple-silicon Mac, which is the 4096/ms cap, not CPU.

Complexity and constants

• O(1) time and state per generator: 16 bytes (last_ms, seq, worker), one clock read per ID. No syscall beyond the clock (a vDSO read on Linux, order of tens of ns), no network, no fsync.
• Size: Snowflake 8 bytes; UUID 16 bytes (36 characters as text); ULID 26 characters; KSUID 20 bytes, 27 characters.
• Capacity: Snowflake 2^10 workers and 4096 IDs/ms each (about 4.1 million/s/worker); Sonyflake 2^16 machines but only 256 IDs per 10 ms.
• UUIDv7 collisions: with n IDs in the same ms across all nodes, probability is about n^2 / 2^75 (about 3e-17 for n = 1000) when all 74 bits are random.

Efficiency

• Cost: one clock read (a vDSO read on Linux, order of tens of ns) plus a few shifts; about 4.1 million IDs/s per Snowflake worker at the 4096/ms cap. No syscall beyond the clock, no network, no fsync. The real cost is downstream: index size and write locality.
• Levers:
  • time-prefixed keys — new rows land at the right edge of a B+tree, so hot pages stay cached; RFC 9562 notes random keys can hurt database locality dramatically — B-tree and LSM primary keys
  • 64-bit instead of 128-bit — 8-byte keys halve key bytes in every secondary index that stores the primary key — wide tables
  • one clock read per block of IDs — fewer reads under bursts — batch inserts
  • hi/lo block allocation from a DB sequence (reserve 1000 IDs per round trip) — one round trip per block — IDs that need not be time-sortable
  • single-node AtomicU64 counter — a few ns per ID — one process, no cross-node uniqueness
• Naive → standard → state of the art:
  • central auto-increment · one network round trip per ID, single point of failure
  • random UUIDv4 · no coordination, random index pages, 16 bytes
  • Snowflake or UUIDv7 · coordination-free, time-ordered, 8 or 16 bytes

Implementation notes

• Use a custom epoch close to launch (here 2020-01-01), not 1970: 41 bits are consumed from the epoch you choose. Store the epoch as a constant forever; changing it changes every ID.
• Wait out small rollbacks (a few ms, NTP slew or step) by sleeping; on large ones refuse and alarm. Persisting last_ms across restarts closes the restart-after-rollback hole, but costs an fsync; amortize by persisting a high-water mark ahead of use (every second) and refusing to issue below it on restart.
• Multiple threads: one generator per thread with distinct worker numbers (bits are cheap), or a single Mutex/CAS loop on a packed (ms, seq) u64. Avoid cross-core contention on the hot path.
• Worker bits can be split (e.g. datacenter + machine) or shrunk to give more sequence bits; the layout is a design choice, not a standard.
• Sorting: big-endian byte order of the ID equals numeric order; UUID bytes sort correctly as bytes, and as hex text.

Pitfalls

• Duplicate worker IDs (two pods booted with the same number) silently produce identical IDs in the same ms. Lease the number and fence on it; a paused old holder keeps minting.
• Clock rollback (NTP step, VM migration, leap-second smearing differences) issues out-of-order or duplicate IDs if ms < last_ms is not checked.
• 63-bit IDs exceed JavaScript's 2^53: serialize as strings in JSON.
• Snowflake IDs are guessable and leak creation time and volume; do not use them as capability tokens.
• UUIDv7 leaks creation time too; sort order is only per-millisecond unless a counter is used.
• Mixing generators with different epochs or bit layouts in one column.

Variants and alternatives

In production

Twitter (Snowflake, now archived), Instagram (shard-embedded IDs in PostgreSQL), Discord and other systems with Snowflake-derived 64-bit IDs, Flickr (ticket servers), Sony (Sonyflake), MongoDB (ObjectId); UUIDv7 is the default time-ordered choice in the RFC and supported by the Rust uuid crate.

Implementations

Sources

• P. Leach, K. Davis, B. Peabody, Universally Unique IDentifiers (UUIDs), RFC 9562, 2024. rfc
• Twitter, Announcing Snowflake, 2010. code
• Instagram Engineering, Sharding & IDs at Instagram, 2012.
• Flickr, Ticket Servers: Distributed Unique Primary Keys on the Cheap, 2010. post
• ULID specification. spec
• Segment, ksuid. code
• Sony, Sonyflake. code