Requirements

Functional Requirements:

• No two IDs collide across nodes, time, or datacenters.
• Generate at least 10k IDs/sec and scale beyond via more nodes.
• Later IDs are generally larger than earlier IDs; supports chronological sorting.
• Optional API to request multiple IDs per call to amortize latency.

Non-Functional Requirements:

• low latency- the returned Id responses shouldnt take more than 50ms, because the system should be able to handle 10k IDs/sec
• the server should have an up time of at least 99.99%
• scalability, in case of 10k IDs/sec the system must be able to scale up and increase the number of instances.
• also there should be no single point of failure, each server should be responsible for generating it's ids
• the ids should be 64 bits long, 128 bits (UUIDs) might be too large for this scope

API Design

POST /generate body:{timestamp:number, datacenterId:number, machineId:number, sequenceNumber:number}

POST /generate/batch body:{timestamp:number, datacenterId: number, machineId:number, sequenceNumbers:number[]}

machines can be asigned machineIds on startup by leveraging ZooKeeper

High-Level Design

on bootstrap the coordination service eg ZooKeeper is called to assign unique machine IDs and dataCenterIDs. (this is done only once, on startup)

the client then makes a call to request an ID.

the call hits the load balancer which is used to orchestrate over the multiple data centers; and to forward the call to the right machine/server within the data center.

the machine than computes the id and returns the response. the id has the following format:

1 sign bit - always set to 0

41 bits timestamp - this is used to order chronologically the ids;

5 bits - data center id;

5 bits machine/server id;

12 bits sequence number - this incrementally increases and is reset to 0 every second

all the ids are then generated independently locally and they don't rely on other machines or data centers.

the nodes could use the network time protocol (ntp), it would be running on all nodes. perfect sync isnt a must, cause the unicity of ids does NOT depend on the timestamp, BUT on the unique combination of data center, machine ids

Detailed Component Design

each node independently creates ids based on the data center and machine ids. on server start, each machine and data center will be assigned unique ids by leveraging zookeeper. it will prevet id collisions from occuring.

each node will use the network time protocol to check the timestamp which is also saved in the id

every millisecond the sequence number is set to 0 and it start incrementing by one for each id request in order to achieve uniqueness