Designing a Unique ID Generator for Distributed Systems

One database can hand out IDs with AUTO_INCREMENT. Many servers can't share that counter. This post compares four ways to generate unique IDs in a distributed system, and picks one.

Requirements

• 64-bit integers.
• Numeric, unique and sortable by time. They do not need to go up by exactly 1.
• 10,000 IDs per second, or more.

Option 1: Multi-master Replication

Each database still uses AUTO_INCREMENT, but the step is k instead of 1, where k is the number of servers. With k = 2, server A makes 1, 3, 5… and server B makes 2, 4, 6….

• Pros: reuses the database you already have.
• Cons:
  • Hard to run across several datacenters.
  • IDs don't go up with time across servers.
  • Adding or removing a server changes k for everyone.

Option 2: UUID

Each server makes a 128-bit random ID on its own, like 09c93e62-50b4-468d-bf8a-c07e1040bfb2.

• Pros:
  • Simple. No coordination between servers.
  • Scales with no limit.
• Cons:
  • 128 bits, not 64.
  • Not sortable by time (UUID v4 is random).
  • Not numeric.

Option 3: Ticket Server

One central database hands out IDs to everyone, made famous by Flickr.

-- Table "tickets" has one row; the auto-increment id is the counter.
INSERT INTO tickets (stub) VALUES ('a')
  ON DUPLICATE KEY UPDATE id = LAST_INSERT_ID(id + 1);
SELECT LAST_INSERT_ID();

• Pros:
  • Numeric IDs.
  • Easy to build. Good for small and medium apps.
• Cons:
  • Single point of failure. When the ticket server is down, nothing can create records.
  • Adding a second ticket server brings back the sync problems of option 1.

Option 4: Snowflake (Twitter)

Split the 64 bits into fields. Each server fills them in on its own, with no coordination:

Try it. Generate a few IDs, press Burst ×5 to see the sequence count up inside one millisecond, and pick any ID to decode it:

Why it fits:

• 64-bit and numeric: fits a BIGINT column.
• Sortable: the timestamp is the high bits, so a later ID is always a bigger number.
• Fast: 4,096 IDs per ms per machine is about 4 million per second, far above 10,000.
• No single point of failure: each machine generates IDs alone.

What to Watch Out For

• Clock sync. Machines rely on their own clocks. Keep them in sync with NTP.
• Clock going backwards. If the clock jumps back, the machine could repeat an ID. Refuse to generate (or wait) until the clock passes the last timestamp used.
• Tune the bits. Few machines but heavy bursts? Give fewer bits to datacenter and machine and more to the sequence.
• Assign machine IDs safely. Two machines with the same datacenter and machine ID will collide. Hand them out from config or a coordinator like ZooKeeper.

Summary

Snowflake meets every requirement. Its only real cost is that machine clocks must be trusted.