System requirements

Functional:

Generate unique ID

Non-Functional:

High throughput

High consistency - same id cannot be returned twice

5000 Ids per sec (5 servers)

5000 * 60 * 60 *24 = 5k * 86400 = 5k * 100k = 500 B

daily

Capacity estimation

Let's assume one server can handle generation of 1000 ids per sec

5000 Ids per sec (5 servers)

5000 * 60 * 60 *24 = 5k * 86400 = 5k * 100k = 500 B

daily

API design

GET /generate

returns

{

"id":,

"created_at":

}

Database design

We will use database for storing ids for audit purposes

Id Metadata

id

created_at

created_by

server

High-level design

We will have multiple ID Generation Services behind load balancer which will distribute the requests based on round robin algorithm.

Ids and metadata like creation time and server will be stored in database for audit and monitoring purposes

Id generation Service needs to generate ids fast to deal with the throughput.

Request flows

1. User will call an API to generate new Id
2. Request will be redirected to ID generation service by load balancer
3. We will implement rate limiting and if there are too many request coming user will get 429 error
4. else Id generation service will generate new id based on the generation algorithm and publish notification about new ID gerenerated on the queue for database persistence
5. Id generation service will return id to the user

Detailed component design

Id generation

To generate ids we will use the following algorithm based on snowflake twitter algorithm:

1 bit for future

41 bits for time in milliseconds

10 bits for server id

12 bits for counter (rolls over every 4096)

It deals with the fact that time can be desynchronized between different servers

64 bits per identifier

counter will be incremented on the server and rolled every 4096

We will need to store somewhere the server id mapping - we can use zookeeper for this. We need to ensure this will be unique for each server.

this algorithm can handle up to 1024 different servers

Trade offs/Tech choices

In order not to overload database with requests to store ids from ID generation service we can introduce queues. Each Id Generation service can publish a message on the queue. Messages will be picked up in batches by DB write service and we can use batch write to store them in database. This should prevent overloading the database with too many requests as well as slowing down single generation request.

Failure scenarios/bottlenecks

We need to avoid single point of failures that is why we have to have redundancy for each componenent. There will be multiple Id Generation services.

Database will be replicated

Db write service will have another replica in case it fails

If Db write services receives and error while writing to the database it will retry with exponential backoff.

We will also implement healthchecks for each service and alerting mechanism to alert if any is down

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?