Unique ID generator

Why did a rider jump two kilometres backwards?

Every rider phone sends a location every four seconds: about 1,000 events a second, spread over two location servers. Each event gets a Snowflake-style id from the server that receives it, the layout from lesson 1.5: 41 bits of milliseconds, then a 10-bit worker number, then a 12-bit counter. The id is also the event’s key in the location store.

One afternoon the delivery map shows a rider jumping two kilometres back, to a road he left a minute ago, then forward again. The phone was fine. The rider was on Karve Road the whole time.

The cause is in server A’s system log. Its clock had drifted a third of a second fast, and at 14:06 the time-sync service corrected it in one step: 300 milliseconds backwards. Before reading on, work out what that does to the ids. The millisecond field now repeats 300 values it has already used, the counter restarts at zero in each of them, and the worker number has not changed. For the next 300 milliseconds server A handed out ids it had already handed out. The location store, keyed by id, did not complain. It overwrote about 150 older locations with newer ones, and the map drew a few riders in the wrong place. Keyed payments would have been overwritten the same way.

Random UUIDs would need no clock at all. They would also lose the property the clock was chosen for: ids that sort by time. A time-ordered id is useful, but it depends on two things nobody had checked: that a server’s clock never goes backwards, and that no two servers share a worker number. The generator needs a guard for each.

Three fields, three assumptions

A Snowflake id is unique only while three things hold: each worker’s (millisecond, sequence) pairs never repeat, no two live workers share an id, and the sequence never runs out inside one millisecond. The original Snowflake README states the first as a rule (it “protects from non-monotonic clocks”, refusing to make ids until time passes the last one it used) and assigns worker ids by configuration.

Clock step versus clock slew

A step sets the clock to the right time at once, which can move it backwards. A slew corrects it gradually by running it slightly fast or slow, so it never goes backwards.

For example: A clock 300 ms fast can be stepped back 300 ms in an instant, or slewed by running slow until the error is gone.

Fix the generator, or change the id?

UUIDv7 removes the worker-id problem completely, and a backwards step costs it only some order within one machine, never uniqueness. Against that, the kitchen already has years of bigint keys in every table and in partners’ systems, and changing a key column everywhere is the hardest kind of migration (lesson 8.1). New tables with no outside readers can start with UUIDv7.

What to remember

1. A Snowflake id is unique only if each worker’s clock never reuses a millisecond, worker ids are never shared, and the 12-bit sequence never overflows within one millisecond.
2. When the clock goes backwards, a generator must wait, refuse or borrow ahead; ignoring it repeats ids. Snowflake refuses.
3. Hand out worker ids from something that can say no (a unique constraint with a lease), never from copied configuration.
4. Time-ordered ids from many machines are only k-sorted: ordered to within the clock difference. UUIDv7 keeps the order and drops worker ids, at twice the size.

Before you number anything by the clock, decide what happens when the clock goes backwards.

In the real world

Real generators add what the simulator leaves out: they save the last millisecond used so a restart cannot repeat it, measure how far behind the clock is before choosing to wait or refuse, and export a metric for every backwards step. RFC 9562 allows a UUIDv7 generator to keep a counter within a millisecond, and tells implementations to check that each new id is larger than the last.