Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

• The system can produce unique identifiers without collisions.
• The system can produce unique ids with high throughput.
• The system should generate IDs that are time-ordered.
• The IDs generated should fit in 64 bit.

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

• The p99 latency for generating unique ids should be less than 100ms.
• The system should be available 99.99% of time. No node failure should halt issuance of new ids.
• The system should be easily scalable to more traffic.

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

Before capacity estimation, we should explain how we can generate a 64-bit unique id.

The breakdown is:

With this estimation, we know that we can have up to 1024 machines.

For each machine, we can generate 4096 IDs per millisecond, the per node throughput per second is:

4096 * 1000 = 4 million IDs per second

The overall max throughput of the system is 4 million per second * 1024 machines = 4.1 billion IDs per second.

On the request side, assuming 100M DAU, and 5 requetss per day:

• 100M DAU × 5 IDs/user/day = 500M IDs/day
• ÷ 86,400 s ≈ 5.8k/s average
• × 2 peak ≈ 11.6k/s

This is below the maximum throughput.

• 4.1B/s ÷ 11.6k/s ≈ 350,000× headroom
• Even at 10× growth (1B DAU), demand is ~116k/s — still ~35,000× under the ceiling.

When the 12-bit counter overflows inside a millisecond, the node spins until the next millisecond.

Also, we can use batching to reduce the RPC count.

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

To retrieve the unique id:

POST v1/issue_unique_ids

To generate the worker id at bootstrap:

POST /v1/workers/lease

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

For this design, we should first understand how we generate the random IDs:

The breakdown is:

This ensures:

1. Each generated ID is unique and doesn't clash with others. Even if 2 IDs are generated by the same machine, at the exact same millisecond, their sequence numbers are different.
2. The IDs are monotonically increasing, since the timestamp and sequence number keeps increasing.

For a request to generate a random unique ID, it first goes to load balancers, which distribute traffic evenly. Then the request gets processed by API gateway, which does rate limiting and authentication.

The request then gets processed by one of the id generator workers, which generates the ID using current timestamp, current machine id, and latest sequence number, and return the generated ID.

How does each machine get its worker ID?

When an ID generator worker starts, it contacts a coordination service backed by etcd, a strongly consistent distributed key-value store using Raft consensus.

1. The coordination service atomically assigns an available worker ID using an etcd transaction.
2. The assignment is associated with a renewable lease (e.g., 30-second TTL).
3. Each worker periodically renews its lease through keepalive requests (e.g., every 5 seconds).
4. If a worker crashes, its lease eventually expires, and etcd automatically removes the worker ID mapping.
5. The worker ID can then be reassigned, subject to safeguards preventing overlap with IDs previously generated by the old worker.

Failure handling:

• If a worker loses its lease, it must stop generating IDs.
• Each worker detects and handles clock rollback. So adjusting time won't lead us to regenerate the same ID.
• Worker IDs are reassigned only when the new worker can safely generate timestamps beyond those used or potentially used by the previous owner. So whenever a worker has a lease, it can only generate ids up to the timestamp dictated by the lease. It can only generate ids beyond that timestamp by extending leases. When another machine node takes over a downed machine's machine node ID, it can only start generating new IDs past the boundary of previous machine's timestamp.

Once initialized, workers generate Snowflake IDs locally without consulting etcd for each request.

How do we handle clock skew?

1. Id generator workers connect to NTP and periodically sync and correct their clocks.
2. Each worker node records a latest timestamp it generated ID with, if current time is ever before that, it waits until past that timestamp to restart generating IDs.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

In this system, the only storage we need is the machine id we assign to each machine node. For this, we should use etcd.

For this storage, we need below features:

1. It should support lease + TTL. If a machine node ever crashes, after TTL passes, the machine node id should be freed for others to use. ETCD inherently supports this.
2. Distributed coordination. It needs to handle assigning machine node ids to different machines, avoiding race conditions. Ectd supports this using Raft.
3. We need strict serializability for assigning and reading machine node ids.

For all writes to the system, they go through the leader node, and need to be acknowledged by a majority of follower nodes.

For all reads to the system, they are handled by the leader node, to avoid stale reads.

In case of leader node crash, one of the follower nodes is guaranteed to have latest values, and can be promoted to the leader node.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

In this system, the only storage we need is the machine id we assign to each machine node. For this, we should use etcd.

For this storage, we need below features:

1. It should support lease + TTL. If a machine node ever crashes, after TTL passes, the machine node id should be freed for others to use. ETCD inherently supports this.
2. Distributed coordination. It needs to handle assigning machine node ids to different machines, avoiding race conditions. Ectd supports this using Raft.
3. We need strict serializability for assigning and reading machine node ids.

For all writes to the system, they go through the leader node, and need to be acknowledged by a majority of follower nodes.

For all reads to the system, they are handled by the leader node, to avoid stale reads.

In case of leader node crash, one of the follower nodes is guaranteed to have latest values, and can be promoted to the leader node.

For this design, we should first understand how we generate the random IDs:

The breakdown is:

This ensures:

1. Each generated ID is unique and doesn't clash with others. Even if 2 IDs are generated by the same machine, at the exact same millisecond, their sequence numbers are different.
2. The IDs are monotonically increasing, since the timestamp and sequence number keeps increasing.

For a request to generate a random unique ID, it first goes to load balancers, which distribute traffic evenly. Then the request gets processed by API gateway, which does rate limiting and authentication.

The request then gets processed by one of the id generator workers, which generates the ID using current timestamp, current machine id, and latest sequence number, and return the generated ID.

How does each machine get its worker ID?

When an ID generator worker starts, it contacts a coordination service backed by etcd, a strongly consistent distributed key-value store using Raft consensus.

1. The coordination service atomically assigns an available worker ID using an etcd transaction.
2. The assignment is associated with a renewable lease (e.g., 30-second TTL).
3. Each worker periodically renews its lease through keepalive requests (e.g., every 5 seconds).
4. If a worker crashes, its lease eventually expires, and etcd automatically removes the worker ID mapping.
5. The worker ID can then be reassigned, subject to safeguards preventing overlap with IDs previously generated by the old worker.

Failure handling:

• If a worker loses its lease, it must stop generating IDs.
• Each worker detects and handles clock rollback. So adjusting time won't lead us to regenerate the same ID.
• Worker IDs are reassigned only when the new worker can safely generate timestamps beyond those used or potentially used by the previous owner. So whenever a worker has a lease, it can only generate ids up to the timestamp dictated by the lease. It can only generate ids beyond that timestamp by extending leases. When another machine node takes over a downed machine's machine node ID, it can only start generating new IDs past the boundary of previous machine's timestamp.

Once initialized, workers generate Snowflake IDs locally without consulting etcd for each request.

How do we handle clock skew?

1. Id generator workers connect to NTP and periodically sync and correct their clocks.
2. Each worker node records a latest timestamp it generated ID with, if current time is ever before that, it waits until past that timestamp to restart generating IDs.