System requirements

Many distributed services now require unique global identifiers. Social security numbers, personal account numbers, bank account numbers, tweet IDs, picture IDs, and file IDs are examples of unique identifiers in a service.

Functional:

• They can't be any length. Let's assume we limit ourselves to 64 bits.
• The date is used to increase the ID. This provides a lot of versatility to the system; for example, you may arrange people by ID, which is the same as sorting by registration date.

Non-Functional:

• The solution must be scalable as the number of requests increases.
• The solution must be able to withstand component failure.

Capacity estimation

Typically for generate unique IDs we don't need to store the generated IDs. Instead we would store the counter and this would serve to ensure uniqueness when generating the next ID.

API design

GenerateUniqueId()

• Input: N/A
• Output: a 64 bit unique ID

Database design

From our capacity estimation we only need to store the counter. Therefore, we can store this information in local memory. See Detail component design section.

High-level design

We need get a unique ID in a distributed setting while keeping scalability in mind.

Initial thought process:

• Probabilistic methods are ruled out since the ID must be assumed to be globally unique.
• The client will utilize the issued ID for an indefinite length of time, which implies that once assigned, the ID will be lost forever and will not be reused for future assignments.
• Because the ID is short, say 64 bits, compared to the machine's unique identifier, the idea of creating a unique ID using a combination of MAC address + Process id + Thread id + Timestamp is ruled out.
• Given that the requirement is to generate 64 bit unique ID we will not consider UUIDs (128 bits) or MongoDB Object IDs (96-bit).

We can use the twitter snowflake unique ID generation

This is a network service devoted to creating 64-bit unique IDs at a large scale. Twitter made it to create unique identifiers for tweets, direct messages, lists, etc. These unique identifiers are 64-bit unsigned numbers that are time-based rather than sequential. It is made up of the following components:

The Twitter Snowflake algorithm generates a 64-bit unique ID, and these 64 bits are divided into several components:

• 41 bits for the timestamp
• 10 bits for the machine ID
• 12 bits for the sequence number
• 1 reserved bit (which is currently unused and set to 0)

This division of bits allows the Snowflake algorithm to generate IDs that are unique, time-ordered, and can scale across multiple machines.

This is the best option that satisfies all of our needs. This allows our microservices to generate IDs on their own.

Request flows

Our basic request flow will look like this

1. Client sends a request to the Load Balancer for a unique ID.
2. The Load Balancer forwards the request to a Worker Node.
3. The Worker Node requests a Number Range from the Ticket Server (Bookkeeper).
4. The Ticket Server assigns a Number Range to the Worker Node.
5. The Worker Node generates the unique ID using Snowflake ID Generation (combining Machine ID, Sequence Number, and Timestamp).
6. The Worker Node returns the generated 64-bit Unique ID to the Client.
7. The DHT Network ensures data replication and fault tolerance, allowing neighboring nodes to take over if any worker node fails.

Detailed component design

We can use multiple worker nodes which are responsible for generating IDs.

We also need a way to store the counter in order to generate the sequence number portion.

We can create a ticket server responsible for this. However simply storing the counter via database is not scalable (see Trade Offs Section) given if there are concurrent request, there might be scalability issue due to db locking. Not to mention this also imposes a single point of failure.

A better approach would be to be pre-allocate a range of values to each worker and let each worker handle the counter within that given range.

This way the worker would not need to request for the counter on every request. This counter can be stored in the local memory of each worker.

In case of failure, each worker node constructs a DHT node and joins a DHT ring. A DHT ring is a decentralized structure used in distributed systems that assigns data (in this case, number ranges, counter) to different nodes based on their node ID. This allows the system to use key-based routing to distribute the number ranges across multiple worker nodes, ensuring scalability and fault tolerance.

Lastly, the twitter snowflake unique ID generation process also requires a zookeeper to maintain the mapping of Nodes and Machine IDs. So we are also adding a ZooKeeper to do this maintenance.

if a worker exhausts it's current number range it would request additional number range by making a request to the ticket server.

Trade offs/Tech choices

An alternative implementation is to use a centralized server for incrementing ID.

The centralized method involves keeping a table with the last generated ID. When a node requests a new ID, the system retrieves the current ID, increases it, and assigns the new value to the node. While this approach is reliable, it has a single point of failure because all nodes depend on this one table for new IDs. If the service goes down, ID generation stops. To make it more resilient, MySQL shards are set up with master-replica pairs to ensure availability. To prevent ID conflicts within shards, the system ensures IDs are unique for each shard. This setup uses a centralized database that tracks and increments the ID for each request.

Pros

• It performs well in a sharded database and at scale.
• Short length, good indexing, and does not degrade query speed while dealing with massive datasets.

Cons

• Because all nodes rely on this table for the next ID, there is a single point of failure.
• Ticketing servers can become a write bottleneck at scale because they may not be adequate when the number of writes per second is enormous, causing the ticketing server to overload and decrease performance.
• Extra computers are required for ticketing servers.
• There is a single point of failure if we use a single database, and we can't ensure that IDs will be sortable over time if we use many databases.

The centralized approach is still used in many system today however, as the system grows and needs to handle more requests, the approach discussed in Detailed component design section becomes more practical because it reduces the frequency of interaction with the Ticket Server and minimizes contention for the database lock.

Failure scenarios/bottlenecks

See Detailed component design on DHT.

Future improvements

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