Almost every system needs IDs that are unique across machines, sortable by time, and cheap to generate without a round trip. The Snowflake scheme is the canonical answer — one machine's clock, one machine ID, and one counter that fits in 64 bits. The trace:
trace stepSystem
The generator reads the wall clock: milliseconds since a custom epoch (Twitter's: 2010-11-04). At ~1.7 × 10^12 ms since epoch, this fits in 41 bits — which is exactly why Snowflake dies in the year 2080-ish. Reading the clock is a single syscall (~100ns). No coordination, no network: this is the entire point.
trace stepSystem
The generator shifts in its 10-bit machine ID (bits 41–50). That ID comes from an assignment mechanism — a config file, a ZooKeeper sequence, a hash of the hostname, or a gossip-resolved member table. It must be unique among live nodes; two nodes with the same machine ID are the only way this scheme can ever collide.
trace stepSystem
The generator takes the low 12 bits:
sequence = (sequence + 1) & 4095. Each ID is a monotonically increasing counter within the same millisecond, so 4,096 IDs per millisecond per node — 4 million per second — come from one node before it must do anything clever. The sequence is often reset to 0 when the timestamp advances.trace stepSystem
At the 4,097th ID in one millisecond, the counter wraps. The generator does not panic or block on a lock: it busy-waits until the next millisecond (
while (now == lastMs) yield()), then starts a fresh sequence. The cost of overdrive is a spin — microseconds to milliseconds — not a lost ID.trace stepSystem
id = (timestamp << 22) | (machineId << 12) | sequence — one shift and two ORs, ~5ns. The result is a big-endian-ordered 64-bit integer, which means sorting the integers sorts the creation times: index-friendly, range-query-friendly, and trivially comparable across machines.trace stepSystem
NTP steps the clock backwards;
now < lastMs. Without care, the sequence could re-issue IDs from an earlier millisecond — a uniqueness violation. Standard handling: stall until lastMs is reached again (Snowflake's approach), or keep a lastMs floor and refuse to generate IDs below it. Clock forward jumps are harmless — the next ID just gets a bigger timestamp, leaving a gap.now = wall_clock_ms() # 41 bits
if now > lastMs: seq = 0; lastMs = now
else: seq += 1 # 12 bits, wraps at 4096
if seq >= 4096: spin until now > lastMs
id = (now << 22) | (machineId << 12) | seq # 64-bit intThe arithmetic is the whole story: 41 + 10 + 12 = 63 bits of payload plus a sign bit, giving 4,096 IDs per millisecond per node, monotonic within a millisecond, sortable, and zero round trips. Systems that need more headroom widen the timestamp or shard the sequence per-machine-group — but the shape, timestamp-first, machine-second, sequence-third, is the pattern every modern ID generator is a variant of.