Scope and direction

Clarifications:

• do you mean no collisions at all or to implement collisions?
  • no collisions, globally unique IDs
• any preference on the algorithm?
  • ordering should be roughly time-ordered (Snowflake-ish)
• do the IDs need to be ordered or? eg. by timestamp ^
• what scale are throughput are we expecting?
  • 10-100k IDs per system

Problem re-statement:

We need to design a distributed unique ID generator without collisions with time-ordered IDs and high throughput.

Core constraints:

• global unique IDs without collisions
• high throughput across nodes
• minimal synchronisation overhead

Requirements

Functional Requirements:

• generate unique IDs without collisions and timesorted IDs
• support batch requests, batch size is capped to prevent a single request from exhausting per-node capacity

Non-Functional Requirements:

• low latency (p99 < 10 ms per request)
• high throughput (target 10-100k IDs per second
• high availability (target 99.99%)
• minimal synchronisation on the ID generation path

The hardest NFR is guaranteeing global uniqueness at high throughput without bottleneck.

Throughput scales horizontally by adding generator nodes, as ID generation is fully local.

API Design

Request ID(s) endpoint

IDs are returned as strings and the API is stateless.

High-Level Design

Components

• Client - the external clients that are requesting IDs
• Load Balancer - routes the requests between the nodes to split the load and allocates node IDs to them. It uses simple round-robin since generators are stateless.
• ID Generator instances - stateless services which generate the IDs locally

As seen on the diagram, there is no database.

Write path - ID generation

1. Client calls POST /ids
2. Load balancer routes to any generator
3. The generator
   1. reads the current time
   2. increments the local sequence
   3. assembles ID
4. IDs are returned to the client

There are no database calls.

Failure scenarios

1. Generator instance crash
   1. the Load Balancer re-routes the traffic
   2. uniqueness is preserved as no two live instances share the node id
2. Clock goes backwards on a node
   1. generator does not generate IDs until time catches up
   2. alert logged/emitted
   3. throughput impacted locally
3. Generator sequence exhaustion
   1. if the generator exhausts its per ms sequence then it blocks until the next ms
   2. additionally batch size is capped to sequence size and for batch requests the generator will wait until the next ms so that it fits

Data model

The IDs are not stored.

The Load Balancer stores in memory mappings for (instance, node_id).

Capacity estimate

Per node: thousands of IDs/sec easily.

We can scale horizontally by adding generators.

Trade-offs

The IDs are not strictly globally ordered but only time-ordered.

This trades perfect ordering for minimal synchronisation overhead.

Future improvements

We could:

• add logging and metrics
• alternative ID formats
• admin APIs to set up the nodes setings

Detailed Component Design

ID generation algorithm (Twitter Snowflake-like)

Problem

How to generate globally unique IDs without central coordination while keeping the IDs roughly time-ordered.

Solution

We can use a Snowflake-style ID composed of:

• timestamp_ms
• node_id
• sequence

Each generator node:

• keeps locally last_ts and sequence
• receives the allocated node_id from the load balancer
• generates ids using (tempstamp, node, sequence)
• if the clock moves backwards then it waits until it catches up
• resets the sequence per ms

Trade-offs

• the IDs are not strictly globally ordered
• per-node throughput is capped by the sequence size per ms

Node identity allocation

Problem

We need to ensure that two nodes don't generate the same IDs by having the same node_id.

Solution

The Load Balancer:

• assigns mappings of (instane, node_id) to nodes with a TTL
• if a node crashes then the TTL expires
• sends over the node_id to the generator instances and confirms that they use the correct one
• the mappings are stored in memory

Trade-offs

• extra logic in the Load Balancer