Loading...
IDs should be 64 bits
IDs should be roughly time sortable
Users should not be able to guess the IDs
Generate 1M/sec IDs
Availability: 99.99% availability
Latency: p99 of under 10ms
IDs should not collide with each other
Throughput scales linearly by adding generator nodes without redising
No SPOF
Total IDs = 10^6 / sec
Peak QPS = 2 * 10^6 IDs / sec
Bandwidth = 10^6 * 8 bytes = 8MB/sec which is under the standard network bandwidth (1GB/sec)
GET /unique_id
Response:
{
ID: string,
success: True
}
We return ID as string, as Javascript Int is limited to 2^53 - 1, which will break if we pass 64bit int.
Clients will simply call the API without passing any additional params.
The call goes through a load balancer and then to a server. The server id is generated when a server was initially booted and is fixed for the server.
Clients call the API service, which goes through Load balancer.
Load Balancer routes the request to the healthy server, based on the load on each server. In our case, the work done by each server and each task is similar, so a simple Round Robbin system will work.
Each Server stores the metadata (server_id required for generating the unique id).
We have 64 bits, out of which 1st bit is a sign bit and always 0.
Next 41 bits would be timestamp bits (time spent since the epoch), 10 bits for worker ids (resulting in 1024 servers in a cluster) and then 12 bits for counting. Each server can have their counter in memory.
Nodes run NTP; on detected clock rollback, a node pauses generation until its clock catches up
There is no database in our design as our system only generates the IDs and returns it to the clients, without storing them
Load Balancer distributes the load in Round Robin fashion and checks the health of the servers.
Servers keep the server id in memory and the sequential counter as well. The clocks needs to be in sync.
If the clocks get behind, they can be synced to the current time. We lose some of the ids there, which is fine.
If the clocks move ahead, we pause the id generation and let the clocks sync. In this situation, we do not want to sync the clock to a previous time, bcz of ID duplication
Each server has 12 bits for counting each ms. So if 4096 ids are generated, the server stops for that ms.
On start of new milliseconds, the counter is reset to 0.
Counting will be serialized via atomic increment
At restart of worker, the time stamp would have moved ahead, so the IDs generated would be unique, as long as each server live gets a unique ids