Design a Unique ID Generator (Snowflake)

1. What is a Unique ID Generator?

In a distributed system, we often need to generate unique identifiers for objects (Tweets, Orders, Chats) without relying on a single central database.

Real-World Examples:

  • Twitter Snowflake: Generates unique Tweet IDs.
  • Instagram: Uses PostgreSQL features to generate IDs.
  • MongoDB ObjectId: 12-byte unique ID.

[!TIP] Why not just use AUTO_INCREMENT? Because it doesn’t scale. If you have 10 database shards, you can’t easily synchronize the counter across them without a single point of failure (SPOF).

2. Requirements & Goals

Functional Requirements

  1. Unique: IDs must be unique across the entire system.
  2. Sortable by Time: If ID_A > ID_B, then A was created after B. This is crucial for feeds/timelines.
  3. Numeric: Preferably 64-bit integer (fits in long). Easier to index than strings.

Non-Functional Requirements

  1. High Availability: We cannot fail to generate an ID.
  2. Low Latency: Generation must be nearly instantaneous.
  3. Scale: Support 10,000+ IDs per second per node.

3. The Approaches

A. Database Auto-Increment

  • Method: Use MySQL AUTO_INCREMENT.
  • Pros: Simple.
  • Cons: Hard to scale. Single Point of Failure. If you use multi-master, it’s hard to keep IDs unique and sequential.

B. UUID (Universally Unique Identifier)

  • Method: Generate 128-bit random string (e.g., a1b2-c3d4...).
  • Pros: No coordination needed. Zero collisions.
  • Cons (The B-Tree Killer):
    1. Too Big: 128 bits is 2x larger than 64-bit int.
    2. Not Sortable: Random strings destroy B-Tree performance.

    Why Random IDs kill Databases: Databases store data in B-Trees on disk. If IDs are sequential (1, 2, 3…), new data is appended to the last page. If IDs are random (UUID), new data is inserted into random pages in the middle of the tree.

    • Page Splits: The DB has to split full pages to make room.
    • Fragmentation: Pages end up half-empty, wasting disk space.
    • Random I/O: The DB must fetch random pages from disk to RAM, killing the Buffer Pool.

C. Twitter Snowflake (The Winner)

  • Method: Construct a 64-bit integer using components (Time, Machine, Sequence). This logic runs on each ID Worker node (as shown in the diagram).
  • Pros: Sortable, Compact (64-bit), Distributed.

4. System Architecture

The generator service is distributed. Each node operates independently but coordinates with ZooKeeper to get a unique Machine ID.

System Architecture: Distributed ID Generator
High Availability | Snowflake Algorithm | Zookeeper Coordination
Request ID (RPC)
Heartbeat (Lease)
App Clients
ID Generator Service
Coordination
Order Svc
Chat Svc
Internal LB
ID Worker 1 Machine ID: 101
Last: 1640995200001
Seq: 124
ID Worker 2 Machine ID: 102
Last: 1640995200005
Seq: 042
ID Worker 3 Machine ID: 103
Last: 1640995200021
Seq: 001
ZooKeeper
• Leader Election
• Machine ID Registry
• Config Management
Acquire ID Lease

5. Component Design: The Snowflake Algorithm

A 64-bit integer is composed of:

  1. Sign Bit (1 bit): Always 0 (to keep ID positive).
  2. Timestamp (41 bits): Milliseconds since a custom Epoch (e.g., Nov 4, 2010).
    • Range: $2^{41} \approx 69$ years.
  3. Machine ID (10 bits): Identifies the server generating the ID.
    • Range: $2^{10} = 1024$ nodes.
  4. Sequence Number (12 bits): Counter for IDs generated in the same millisecond.
    • Range: $2^{12} = 4096$ IDs per ms per node.

Total Capacity: $1024 \text{ nodes} \times 4096 \text{ IDs/ms} \times 1000 \text{ ms/sec} \approx 4 \text{ Billion IDs/sec}$.

6. Data Partitioning (Machine ID)

How do we ensure every server has a unique Machine ID (0-1023)?

Static Configuration

  • Method: Assign MACHINE_ID=1 in env variables.
  • Pros: Simple.
  • Cons: Hard to manage. If a pod dies and restarts, it might conflict or leave gaps.

Dynamic Coordination (ZooKeeper/Etcd)

  • Method: When a server starts, it connects to ZooKeeper.
    • It looks for an available ID in /snowflake/ids.
    • It creates an Ephemeral Node (lock) on that ID.
    • It sends Heartbeats to keep the lock.
  • Benefit: Automatic scaling. If a node dies, the ID is released after the session timeout.

7. Reliability & Fault Tolerance

Sequence Overflow

What if a node generates more than 4096 IDs in 1 millisecond? Solution: Wait for the next millisecond.

if sequence >= 4096:
    while current_timestamp() <= last_timestamp:
        pass # Spin wait
    sequence = 0

Clock Synchronization (NTP)

Servers rely on NTP (Network Time Protocol) to sync clocks. Sometimes, the clock might move backwards (Leap second, or aggressive sync). Danger: If clock moves back, we might generate duplicate IDs (Collision) because the timestamp repeats. Solution:

  1. Refuse to Start: If clock skew is detected on startup, the server should not start.
  2. Wait: If the drift is small (< 5ms), just pause and wait for the clock to catch up.
  3. Error: If the drift is large, return an error to the client (High Availability takes a hit, but consistency is saved).

8. Interactive Decision Visualizer: Snowflake Bit Builder

Adjust the sliders to see how the ID is constructed. Notice how Timestamp has the biggest impact on the final value (Sorting).

0
Timestamp (41 bits)
Machine (10)
Seq (12)
0
1
0
Generated 64-bit ID:
0
0000...

9. System Walkthrough (Dry Run)

  1. Request: App Server needs an ID for a new Tweet.
  2. Worker: ID Generator worker #101 receives request.
  3. Timestamp: Worker reads system clock -> 1640995200000.
  4. Sequence: Checks if ms is same as last ID.
    • If yes, seq++.
    • If seq > 4095, sleep 1ms.
  5. Assembly:
    • Timestamp << 22
    • | MachineID << 12
    • | Sequence
  6. Response: Returns 12345678901234567.

10. Interview Gauntlet

  1. Why not use DB Auto-Increment?
    • Ans: SPOF and Scalability. Writing to a single master is a bottleneck. Multi-master auto-inc is complex to keep unique.
  2. Why is UUID bad for Primary Keys?
    • Ans: Randomness causes Page Splits in B-Trees. New records are inserted in the middle of pages, causing fragmentation and random disk I/O.
  3. What happens during a Leap Second?
    • Ans: The clock might freeze or move back. We must handle this by checking if current < last_timestamp and throwing an error or waiting.
  4. How do you prevent two servers having the same Machine ID?
    • Ans: Use ZooKeeper/Etcd to coordinate. Servers acquire a lock on an ID at startup.
  5. What if you run out of 69 years?
    • Ans: Migrate to a new epoch or a 128-bit ID scheme. 69 years is usually sufficient for the lifespan of most systems.

11. Whiteboard Summary

1. Core Requirements

  • Unique & Sortable (Time)
  • High Throughput (10k/s)
  • 64-bit Integer

2. Key Architecture

  • Worker Nodes: Stateless generators
  • ZooKeeper: Assigns Machine IDs
  • LB: Round Robin

3. Snowflake Bits

  • 1: Sign (Unused)
  • 41: Timestamp (69 years)
  • 10: Machine (1024 nodes)
  • 12: Sequence (4096/ms)

4. Bottlenecks & Fixes

  • Clock Skew: Wait or Error.
  • Sequence Overflow: Sleep 1ms.
  • DB Indexing: Snowflake is Append-Only (Good).