Part 5 of 7 · 2 min read
Dangers
Clocks, sequence limits and machine numbers.
The generator on each machine is a small loop. In outline:
next_id():
now = current time in ms
if now < last: # the clock moved back
refuse, or wait until it catches up
if now == last:
sequence = (sequence + 1) mod 4096
if sequence == 0: # used all 4096 in this ms
wait until the next ms
else:
sequence = 0
last = now
return (now - epoch) << 22 | datacentre << 17 | machine << 12 | sequence
The numbers 22, 17 and 12 are the shifts: sequence takes the lowest 12 bits, machine the next 5, data centre the next 5, and the time starts above that (12 + 5 + 5 = 22). The method must be run by one thread at a time per generator, or protected by a lock or atomic counter (Level 5 in the low-level track).
Danger 1: the clock moves backwards. The book assumes all servers agree on the time and says this may not be true, since a server with several cores or many machines can have clocks that differ. A machine whose clock jumps back by 5 milliseconds would make IDs with an old timestamp and could repeat an earlier sequence. The check in the code above catches this: if the time is below the last time used, the generator refuses or waits. The usual cure for drifting clocks is the Network Time Protocol (NTP), which the book names. This links to the clock problems of Level 5, page 4.
Danger 2: the sequence runs out. More than 4,096 IDs in one millisecond on one machine is rare, but possible. The generator must wait for the next millisecond, never wrap and repeat.
Danger 3: two machines with the same number. If two machines run with the same data centre and machine values, their IDs collide. Machine numbers need a safe way to be handed out, such as a small coordination service at startup, or fixed configuration reviewed by hand.
Danger 4: running out of years. At the end of the 69 years, IDs would overflow. Plan a new epoch or a migration well before that.
Check yourself: 1. What does the generator do when the clock goes backwards? 2. Why is a lock or an atomic step needed? 3. How can two machines end up making the same IDs?