Unique ID generator

01 · CONTEXT

Why generating unique IDs stops being trivial

In a single database, auto-increment solves it: each new row gets the next number. The problem appears when data spreads across several machines and each one needs to create identifiers without waiting for the others. As in any interview, start with gathering requirements: does the ID need to be numeric? Does it need to fit in a few bytes? Does it need to follow creation order? What is the expected throughput per second?

Twitter's case shows the practical reason. When moving from MySQL to Cassandra, the team lost the sequential generator that used to come for free: the project itself said there is no facility for sequential ID generation in this kind of storage. The choice of database changed what the ID layer needed to offer, and that is where Snowflake was born.

Snowflake's requirements are a good set of questions to ask. The machines that generate IDs should not need to coordinate with each other, to keep high availability. IDs should be roughly time-ordered, that is, k-sortable within a reasonable bound, and not strictly in order. And they should be compact: the team discarded solutions that required 128-bit numbers and wanted to keep IDs below 64 bits.

02 · TICKET SERVERS

Flickr's path: databases dedicated to issuing IDs

Flickr discarded GUIDs mainly because they are large and index poorly in MySQL, and the team depends on indexes to keep queries fast. The alternative was the ticket server: a dedicated database server, with a single database, where each new ID comes from a REPLACE INTO command followed by reading the last inserted ID, taking advantage of auto-increment.

1. Before storing a new object, the application service asks for an ID instead of letting each database invent its own.

2. Requests alternate between the two ticket servers, which splits the load and tolerates the failure of one of them.

3. The ID space is split in half: one server issues only odd numbers and the other only even, with no need to replicate or lock between them.

4. If one ticket server goes down, the other keeps issuing, but only from its side of the space; that is why a single server would be a single point of failure.

This design solves uniqueness and compactness, but leaves one more central service to operate. Flickr observed that provisioning IDs as a single point of failure is unacceptable and therefore runs two ticket servers, and that replicating between them would be problematic and locking would hurt performance.

03 · SNOWFLAKE

IDs that carry time inside

Snowflake builds the 64-bit ID in three parts: 41 bits of time in milliseconds from a custom epoch, which gives 69 years; 10 bits of machine identifier, up to 1024 machines; and 12 bits of sequence number, which resets every 4096 IDs per machine, with protection against resetting within the same millisecond. Since time occupies the highest bits, sorting by ID is roughly equivalent to sorting by creation.

1. Each generator serves its applications on its own: none asks the other before issuing, and this preserves availability.

2. Each issued ID combines the current instant, the machine's configured identity, and a local counter; different machines never produce the same value.

3. Applications write to the partitioned storage using these IDs, which sort roughly by creation without querying the objects.

Note the effect on data partitioning: since the ID is already unique from birth on any generator, any partition can receive it without consulting a central coordinator. The cost is that the order is only approximate, not total.

04 · CLOCK

The clock dependency

Since time is part of the ID, the clock becomes a critical dependency. Snowflake's documentation recommends using NTP to keep the clock accurate and says the service protects itself from non-monotonic clocks, that is, ones that move backward. If NTP makes the clock repeat a few milliseconds, the service refuses to generate IDs until it reaches an instant later than that of the last ID issued.

1. A generator's clock moves backward after a synchronization adjustment; issuing now could repeat an instant already used.

2. The generator refuses to issue until the time passes that of the last ID; the application tied to it waits, while the other generator continues normally.

05 · COMPARISON

Which approach to choose