Design a unique id generator in distributed systems

Table of Contents

  1. Step 1 - Understand the problem and establish design scope
  2. Step 2 - Propose high-level design and get buy-in
    1. Multi-master replication
    2. UUID (Universally Unique Identifier)
    3. Ticket server
    4. Twitter snowflake approach
  3. Step 3 - Design deep dive
    1. Timestamp
    2. Sequence number
  4. Step 4 - Wrap up

auto_increment does not work in a distributed environment

  • a single database is not large enough
  • generating unique IDs across multiple databases with minimal delay is challenging

Step 1 - Understand the problem and establish design scope

  • IDs must be unique.
  • IDs must be sortable.
    • IDs created in the evening are larger than those created in the morning on the same day.
    • The ID increments by time, but not necessarily only increments by 1.
  • IDs only contain numerical values.
  • IDs should fit into 64-bit.
  • The system should be able to generate 10k IDs per second.

Some useful questions to ask

  • “What are the characteristics of unique IDs?”
  • “For each new record, does ID increment by 1?”
  • “Do IDs only contain numerical values?”
  • “What is the ID length requirement?”
  • “What is the scale of the system?”

Step 2 - Propose high-level design and get buy-in

Multi-master replication

  • Uses DBMS’s auto_increment feature.
    • Increase by k, the number of database servers in use.
  • Drawbacks:
    • Hard to scale with multiple data centres.
    • IDs do not go up with time across multiple servers.
    • It does not scale well when a server is added/removed.

UUID (Universally Unique Identifier)

  • 128-bit number, very low probability of getting collision
    • “… after generating 1 billion UUIDs every second for approximately 100 years, would the probability of creating a single duplicate reach 50%.”
  • Pros:
    • Generating UUID is simple. No coordination (synchronisation) between servers is needed.
    • The system is easy to scale; just add/remove servers.
  • Cons:
    • 128 bit is too long (requirement is 66 bit).
    • Do not go up with time.
    • non-numeric

Ticket server

  • Uses a centralised auto_increment feature in a single database server (= the ticket server).
  • Pros:
    • Numeric IDs.
    • Easy to implement.
  • Cons:
    • Single point of failure.

Twitter snowflake approach

Instead of generating an ID directly, it divides an ID into different sections.

1 bit 41 bits 5 bits 5 bits 12 bits
0 timestamp data centre ID machine ID sequence number
  • Sign bit: 1 bit. Always 0. Reserved for future uses.
  • Timestamp: 41 bits. Milliseconds since the epoch or custom epoch.
  • Data centre ID: 5 bits. Up to 32 data centres.
  • Machine ID: 5 bits. Up to 32 machines per data centre.
  • Sequence number: 12 bits. For every ID generated on the machine/process, the sequence number is incremented by 1, and is reset to 0 every millisecond.

Step 3 - Design deep dive

  • Data centre ID and machine ID are chosen at the startup time (fixed).
  • Timestamp and sequence number are generated when the ID generator is running.

Timestamp

  • As timestamps grow with time, IDs are sortable by time.
  • $2^{41}-1$ = 2199023255551 ms, around 69 years.
  • After 69 years, we will need a new epoch time or adopt other techniques to migrate IDs.

Sequence number

  • $2^{12}$ = 4096 combinations.
  • A machine can support a maximum of 4096 new IDs per ms.

Step 4 - Wrap up

Some additional topics.

  • Clock synchronisation.
    • We assumed ID generation servers have the same clock. This assumption might not be true when a server is running on multiple cores. The same challenge exists in multi-machine scenarios. Refer to Network Time Protocol.
  • Section length tuning.
    • Fewer sequence numbers, but more timestamp bits are effective for low concurrency and long-term applications.
  • High availability.