Skip to main content

Design a Unique ID Generator in Distributed Systems

Adapted from: Alex Xu, System Design Interview – An Insider's Guide (2020), Chapter 7 — rewritten and condensed for teaching.

The obvious way to get unique IDs is an AUTO_INCREMENT primary key in a relational database. That stops working once the system is distributed. One database server can't keep up, and handing out IDs from several databases that are unique, ordered, and fast takes coordination. This lesson compares four approaches and builds the one that meets every requirement: Twitter's Snowflake.

Unique IDs come in many shapes. For example:

StyleExample
Auto-increment integer1, 2, 3, …
UUID (128-bit, hex)09c93e62-50b4-468d-bf8a-c07e1040bfb2
Snowflake-style (64-bit, numeric, time-ordered)1724551110456668202

What you'll be able to do after this lesson:

  • Compare multi-master auto-increment, UUIDs, ticket servers, and Snowflake against a set of requirements.
  • Lay out a 64-bit Snowflake ID and compose and decompose IDs with bit shifts.
  • Build a generator that handles several IDs in the same millisecond, sequence overflow, and a clock that moves backwards.
  • Calculate how long a timestamp field lasts and how many IDs per second a machine can produce.

Step 1: Understand the Problem and Establish Scope​

Candidate asksInterviewer answers
What characteristics must IDs have?Unique and sortable
Does each new ID increment by 1?IDs increase with time, but not necessarily by 1. An ID created in the evening is larger than one created that morning
Numeric only?Yes
Length requirement?Must fit in 64 bits
Scale?10,000 IDs per second

Requirements​

  • IDs are unique.
  • IDs are numeric only.
  • IDs fit in 64 bits.
  • IDs are ordered by date.
  • The system can generate more than 10,000 IDs per second.

Step 2: High-Level Design — Four Options​

Option 1: Multi-master replication​

Use each database's auto_increment, but step by k, the number of database servers, instead of 1. With 2 servers, server 1 issues 1, 3, 5, … and server 2 issues 2, 4, 6, … Each server's next ID is its previous ID plus 2.

flowchart LR
  WEB[Web servers] --> DB1["MySQL 1<br/>1, 3, 5, …"]
  WEB --> DB2["MySQL 2<br/>2, 4, 6, …"]

Capacity grows with the number of servers, but the approach has serious drawbacks:

  • Hard to scale across multiple data centers.
  • IDs don't increase with time across servers. A busy server races ahead while a quiet one lags behind.
  • Adding or removing a server is painful, because k changes and every server's step must be reconfigured without collisions.

Practice: multi-master IDs aren't time-ordered​

Implement assign_ids(k, events). events lists which server (0-based) handles each request, in arrival order. Server i starts at i + 1 and steps by k. Return the list of IDs in arrival order. The wrapper then reports whether the IDs came out increasing.

In the "busy server" test, the request that arrives last gets ID 2, which is smaller than three IDs issued before it. Sorting by ID no longer means sorting by time.

Option 2: UUID​

A UUID is a 128-bit identifier designed to be unique without any coordination. Collisions are astronomically unlikely: you would have to generate about a billion per second for roughly a century before the chance of a single duplicate reached 50%. Each web server simply runs its own generator.

flowchart LR
  W1["Web server 1<br/>+ ID generator"]
  W2["Web server 2<br/>+ ID generator"]
  W3["Web server 3<br/>+ ID generator"]
ProsCons
Simple, with no coordination and so no synchronization issues128 bits, but we need 64
Scales trivially: each web server generates the IDs it usesNot ordered by time (random v4 UUIDs)
Usually non-numeric (hex string form)

Newer variants such as UUIDv7 put a timestamp first so they sort by time, but they are still 128 bits.

Option 3: Ticket server​

Flickr built ticket servers to hand out distributed primary keys. The idea is a single, centralized database whose only job is auto_increment. Every web server asks it for the next ID.

flowchart LR
  W1[Web server] --> T[("Ticket server<br/>auto_increment")]
  W2[Web server] --> T
  W3[Web server] --> T
ProsCons
Numeric IDsSingle point of failure: if it goes down, everything that needs IDs stalls
Easy to implement; fine for small and medium scaleSeveral ticket servers remove the SPOF but bring back the synchronization problems of Option 1 (Flickr ran two, one issuing odd numbers and one even)

Option 4: Twitter Snowflake​

None of the above meets every requirement. Snowflake does, by divide and conquer: instead of one counter, split the 64-bit ID into sections that each solve one part of the problem.

 0 | 41 bits: timestamp (ms) | 5 bits: datacenter | 5 bits: machine | 12 bits: sequence
 ^
 sign bit (always 0)
SectionBitsPurpose
Sign1Always 0. Reserved, and keeps IDs positive as signed 64-bit integers
Timestamp41Milliseconds since a custom epoch. Twitter's default is 1288834974657 (Nov 04, 2010, 01:42:54 UTC)
Datacenter ID52⁵ = 32 datacenters
Machine ID52⁵ = 32 machines per datacenter
Sequence12Counts IDs generated in the same millisecond on this machine. Resets to 0 each millisecond

How Snowflake meets the requirements:

  • Unique: no two machines share a (datacenter, machine) pair, and a single machine never repeats a (timestamp, sequence) pair.
  • Numeric and 64-bit: by construction.
  • Time-ordered: the timestamp occupies the most significant bits.
  • Fast: generation is local, with no coordination on the request path.

Check: choosing an approach​

Quiz

Comparing ID schemes

1 / 3

Which requirement rules out standard UUIDs most directly?

Pick an answer to see if you are right.

Step 3: Design Deep Dive​

Datacenter and machine IDs are assigned at startup and rarely change. Change them only with care: if two live machines end up with the same pair, they can mint duplicate IDs. The timestamp and sequence are computed while the generator runs.

Composing and decomposing an ID​

Each section is placed with a left shift and combined with bitwise OR:

id = (timestamp - epoch) << 22    # 22 = 5 + 5 + 12 bits below the timestamp
   | datacenter_id       << 17    # 17 = 5 + 12
   | machine_id          << 12
   | sequence

To read an ID back, shift right and mask with (1 << bits) - 1. For example, (id >> 12) & 0b11111 extracts the machine ID. To recover the time, compute (id >> 22) + epoch, giving milliseconds since the Unix epoch, which converts directly to UTC.

Practice: Snowflake bit layout​

Implement make_id(timestamp_ms, datacenter, machine, sequence) and parse_id(id). parse_id returns a dict with keys timestamp, datacenter, machine, and sequence, where timestamp is the absolute Unix milliseconds. Use the Twitter epoch 1288834974657.

Input is one line: timestamp_ms datacenter machine sequence. The wrapper builds the ID, prints it with its bit length, and then parses it back.

The last test is the largest possible Snowflake ID, 2⁶³ − 1. It fills all 63 bits below the sign bit and fits exactly in a signed 64-bit integer.

Timestamp​

The 41 timestamp bits are the most significant part of the ID, so sorting IDs numerically sorts them by creation time.

How long does 41 bits last?

2⁴¹ − 1 = 2,199,023,255,551 ms. Dividing by 1,000 ms/s, 3,600 s/h, 24 h/day, and 365 days/year gives about 69.7 years.

Starting from Twitter's 2010 epoch, IDs overflow in July 2080. Choosing a custom epoch close to launch day postpones the overflow as long as possible. When the time runs out, you'll need a new epoch or a migration plan.

Sequence number​

12 bits give 2¹² = 4,096 values. The sequence stays 0 unless the same machine generates more than one ID within one millisecond. At most a machine can mint 4,096 IDs per ms, about 4 million per second. That is far more than the 10,000 per second the system needs, and that's for a single machine.

What if a machine needs a 4,097th ID in the same millisecond? The sequence wraps to 0, which would repeat an ID already issued. The generator must instead wait until the next millisecond.

What if the clock moves backwards, for example after an NTP correction? Issuing IDs with an older timestamp could duplicate IDs already issued. The safe choice is to refuse to generate IDs, by raising an error or waiting until the clock catches up.

Practice: a Snowflake generator​

Implement SnowflakeGenerator.next_id(), which returns (timestamp, sequence). The clock is injected as a function, so tests can control time exactly. seq_bits is adjustable so tests can trigger overflow without making 4,096 calls.

Rules:

  1. Read ts = self.clock().
  2. If ts < self.last, raise ValueError('clock moved backwards').
  3. If ts == self.last, increment the sequence modulo 2 ** seq_bits. If it wraps to 0, call self.clock() repeatedly until it returns a value greater than self.last, and use that as ts.
  4. If ts > self.last, reset the sequence to 0.
  5. Set self.last = ts and return (ts, self.sequence).

Input: line 1 is seq_bits num_ids, and line 2 is the clock readings in order.

In the overflow test, all four sequence values for ms 100 are used. The 5th call reads 100 again, so the generator spins: it reads 100 once more, then 101, and only then issues (101, 0). It never reuses (100, 0).

Check: Snowflake internals​

Quiz

Bits, time, and sequences

1 / 4

Why is the timestamp placed in the most significant bits?

Pick an answer to see if you are right.

Step 4: Wrap Up​

We compared multi-master replication, UUIDs, ticket servers, and a Snowflake-like generator, and chose Snowflake because it meets every requirement and scales without coordination. Extra talking points if time allows:

  • Clock synchronization. The design assumes all ID generators share the same clock, which isn't guaranteed across machines, or even across cores. NTP is the usual answer. The Unreliable Clocks lesson explains why clock drift and jumps are a real hazard.
  • Section length tuning. For low-concurrency, long-lived systems, use fewer sequence bits and more timestamp bits, as in the quiz above.
  • High availability. The ID generator is mission-critical: if it stops, nothing can be created. Run generators on many machines (Snowflake needs no coordination, which makes this easy), and monitor clock health.

Key Takeaways​

  • AUTO_INCREMENT doesn't scale out. Multi-master IDs aren't time-ordered, UUIDs are 128-bit and unordered, and a ticket server is a single point of failure.
  • Snowflake splits 64 bits into sign | 41-bit timestamp | 5-bit datacenter | 5-bit machine | 12-bit sequence.
  • Timestamp-first layout makes IDs sortable by time. 41 bits of milliseconds last about 69.7 years from the chosen epoch.
  • The sequence allows 4,096 IDs per ms per machine. On overflow, wait for the next ms. If the clock moves backwards, refuse to issue IDs.

Previous lesson: Design a Key-Value Store.

Next lesson: Design a URL Shortener — unique IDs put to work: 301 vs. 302 redirects, 7-character base-62 codes, hash + collision resolution, and cached redirects.

Reference Materials​

  1. Universally unique identifier — Wikipedia
  2. Ticket Servers: Distributed Unique Primary Keys on the Cheap — Flickr Engineering
  3. Announcing Snowflake — Twitter Engineering
  4. Network Time Protocol — Wikipedia