Distributed ID Generation (Snowflake)

Foundations

In the first lesson, the unique numbers came from somewhere. Now, what if hundreds of servers must each create ids at once, unique across all of them, without asking a central counter?

A Snowflake-style id packs three fields into 64 bits: 41 bits of milliseconds since a chosen epoch, 10 bits of machine number, and 12 bits of sequence within the millisecond. No two machines share a number, and one machine never repeats a sequence within a millisecond, so ids cannot collide, and the timestamp in the high bits makes them sort roughly by time. A machine that uses up 4,096 ids in a millisecond waits for the next.

Take millisecond 1000, machine 5, and sequence 2. The id is (1000 << 22) | (5 << 12) | 2 = 4,194,324,482. The next id on that machine in the same millisecond has sequence 3, and machine 6 in that millisecond produces a different id, because bits 12 to 21 differ.

• Requirements

  Each worked system starts from a scoped list of verbs and numbers.

  Open lesson

Case Scenario

To see how ids can be unique without coordination, consider a unique ID service like Twitter's Snowflake: many app servers need ids that are unique, roughly time-ordered, and cheap to generate, and a URL shortener like bit.ly is one client. Machine 7 combines millisecond 123456789 with sequence 3 into one 64-bit id, with no database round trip.

Links, orders, messages, and log events need ids that never collide, sort roughly by creation time, and remain cheap under many app servers. Sending every create through one counter couples unrelated services to one row and one machine. Generating an id must require no database round trip or distributed lock, while a retried create must still receive the same logical id.