CSE Roadmap

Core tier · about 3 hours · 7 parts

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?