Unique ID generation across shards

A single database hands out auto-increment IDs without any trouble. With many shards, each shard's counter starts at the same place and collides with the others. You need IDs that are unique without a central counter for every insert, and ideally ones that sort by creation time.

The big idea

Give each branch office its own serial prefix, then count inside the branch. Branch 7 can never collide with branch 3, and no head-office call is needed for each new serial.

The picture breaks in two places. Each prefix must be unique, and the clock must never run backwards.

The options

Walking through Snowflake

Snowflake, created at Twitter in 2010, packs three fields into 64 bits:

[ 41 bits: milliseconds since a custom epoch ][ 10 bits: worker ID ][ 12 bits: sequence ]

The 41-bit timestamp covers about 69 years. The 10-bit worker ID allows 1,024 workers. The 12-bit sequence gives 4,096 IDs per millisecond per worker, which is about 4 million per second per worker.

Packing and unpacking are just bit shifts and masks:

const EPOCH = 1_700_000_000_000n

function snowflake(ms: bigint, worker: bigint, seq: bigint): bigint {
  return ((ms - EPOCH) << 22n) | (worker << 12n) | seq
}

const id = snowflake(EPOCH + 5_000n, 7n, 42n)
console.log(id, id >> 22n, (id >> 12n) & 0x3ffn, id & 0xfffn)

Output:

20971548714n 5000n 7n 42n

The timestamp occupies the top bits, so the IDs sort by creation time. The last line decodes the same three fields back out.

A real generator also needs a loop that waits when a millisecond's 4,096 sequence numbers run out, and a check that the clock has not moved backwards.

Common mistakes

• Letting the clock move backwards. A generator that trusts a backward clock can issue an ID it already gave out. Refuse to issue IDs until the clock catches up.
• Picking worker IDs by hand or at random. Two workers with the same ID can collide. Assign IDs through a registry.
• Using random UUIDv4 as a B-tree key. New rows land at random places, so the index is rewritten all over. UUIDv7 keeps inserts together.
• Assuming IDs reveal nothing. Time-based IDs show when a row was created, and some schemes also reveal the shard.

Check yourself

1. A Snowflake worker's clock jumps back two seconds. What is the risk?

Answer: The generator can produce IDs it already issued, so it must refuse to issue new IDs until the clock passes the last one.

2. Why are UUIDv7 keys friendlier to a B-tree than UUIDv4?

Answer: Their leading bits follow time, so new rows land near each other instead of at random positions.

Key takeaways

• Unique IDs across shards avoid a central counter for every insert.
• Snowflake-style IDs are 64-bit and sort by creation time.
• UUIDv7 gives a 128-bit, time-sortable ID with no coordination.
• Guard the clock: a backward jump makes time-based IDs unsafe.

Further learning

Clocks are the weak point of time-based IDs. Read clocks and ordering for why they can drift.

Twitter Snowflake ID generator (archived)Snowflake is a network service for generating unique ID numbers at high scale with some simple guarantees. - twitter-archive/snowflakeGitHub