Loading...
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.
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.
GenerateUniqueId()
From our capacity estimation we only need to store the counter. Therefore, we can store this information in local memory and use a distributed hash table for maintaining replication and fault-tolerance. See Detail component design section.
We need get a unique ID in a distributed setting while keeping scalability in mind.
Initial thought process:
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:
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.
Our basic request flow will look like this
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 pre-allocation can be store in any DB as long as it's persistent. This is because we need to keep track of which range has been used by which worker.
This also means 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.
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
Cons
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.
If a node crashes, an automated mechanism could allow another node (via the DHT) to take over the unfinished range. This ensures continuity without waiting for the failed node to recover.
While the DHT can provide recovery in the event of a failure, if a worker node crashes and later comes back online, it may not immediately know the last issued ID if this state is only stored in local memory.
If we persist the local counter to disk or a durable store (e.g., periodic checkpoints), the worker node can quickly resume from where it left off after recovering from a crash, instead of starting a new range or relying on the DHT for recovery.
When a worker node fails, neighboring nodes in the DHT may need to transfer the state (last issued ID) from the failed node. Persisting the state locally allows the failed node to recover faster without needing to rely on the DHT to retrieve the exact position within the range.
Persistence ensures that if a node restarts, it can pick up exactly where it left off, reducing the reliance on neighboring nodes in the DHT to maintain this state.
Workers could pre-fetch the next number range before exhausting their current range, reducing the latency of waiting for a new range. This allows continuous ID generation without interruptions.
For example, when the local counter reaches 80% of the current range, the worker node could preemptively request the next range from the Ticket Server.