System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• generate unique ids without collision
• distributed, i.e., multiple nodes can generate an id concurrently
• numerical ids (easy to generate and sortable per node)

Non-Functional:

List non-functional requirements for the system...

• high throughput (10k ids generated per second by a node)
• minimal concurrency management/overhead
• long lived system (ids must not repeat for a long time)
• high available, consistent
• Authenticate a user to prevent DDoS attack on the system

Capacity estimation

Estimate the scale of the system you are going to design...

10K ids generated per node per second.

Num seconds in a day = 100k

Num seconds in a year = 100k * 365 = 4 * 10^7 approx

Num ids generated in a year per node = 4 * 10^11

Assuming 5 id generator nodes globally, num ids generated in a year globally = 2 * 10^12

If system must be usable for 50 years, num unique ids to be generated = 10^14 = 2^40.

So 40 bits will be required to represent an id.

3 additional bits for representing the machine address.

Total 43 bits

• 10K reads and writes per second. System is both read and write-heavy.
• Amount of data read and written is very low.

API design

Define what APIs are expected from the system...

1. Get a unique id

GET https:///id

Returns a unique 43 bit id

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

An id will be represented as follows:

3 bits machine/cluster address + 40 bits id

Id is incremented for every request, updated in persistent cache and returned the user. Redis can be used a persistent cache.

1. Increment id in-memory
2. Update persistent Redis cache
3. Return the new id

Steps 1 and 2 should be atomic.

A Key-value store DB can be used. 2 pieces of information can be stored as follows.

Key: lastIdGenerated. value: id

Key: clusterAddress value: mac or unique address to identify this cluster. It is part of the id.

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Load Balancer: Used to regulate the number of incoming requests

Auth: Authenticate the user to prevent DDoS attacks

Id incrementor: Increments the 40-bit id part of the id

Redis Cache: Used for fast read/write access of the last generated id. Cache is backed by a key-value store.

KV Store: Stores the lastGeneratedId and clusterAddress persistently.

Zookeeper: Used for monitoring for failed nodes in the cluster and discovering newly added ones.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

1. User makes a request to get a unique id
2. Request goes through the LB and Auth Servers
3. Unique id is generated and updated in the cache and DB
4. Generated id is returned to the user.

Startup:

On startup, the system reads its clusterAddress and lastGeneratedId from the DB and serves new incoming requests using this info.

Failure Scenario:

1. Cluster is deployed in Active-Standby mode. A single leader generates the id
2. Leader node crashes
3. Zookeeper identifies this and elects a new leader.
4. New leader can pickup from where the old leader left by reading lastGeneratedId and clusterAddress from the DB.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Nginx server can be used for serving API requests as it is known for fast response time.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Generate auto-incremented vs random ids

It is possible to design a system which generates a random id. But with that approach, a set of already-generated ids must be kept in DB so that the same id is not repeated. This increases the storage requirement and throughput suffers due to the additional step to validate newly generated id against existing ones.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

This is a stateless system. So node failures can be recovered easily by reading lastGeneratedId and clusterAddress from the DB.

1. Cluster is deployed in Active-Standby mode. A single leader generates the id
2. Leader node crashes
3. Zookeeper identifies this and elects a new leader.
4. New leader can pickup from where the old leader left by reading lastGeneratedId and clusterAddress from the DB.

Future improvements

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

• The current system provides sortability within a cluster only. Global sortability across ids generated from all clusters is not provided. This can be an enhancement.

• Ability to release and id if no longer in use so that it can be reused.