Section 1.1: The Concept of the Hashing Ring

To illustrate how consistent hashing works, consider a scenario where we need to manage the data of all employees in an organization. We could use a hashing algorithm, like UUIDv4 (Universally Unique Identifier), to assign a unique identifier to each user across four different nodes.

For example, a user might be represented as follows:

{

"userId": "51376fb9-de87-4d5c-b78e-ecaeb8058f28",

"firstName": "Norbert",

"lastName": "Takacs"

}

At this stage, it's crucial to identify which node will store this record, which is determined by the node's position on the hashing ring. Each node is assigned a random position based on the output of a hashing function.

To construct the hashing ring, we need to establish the minimum and maximum values for the hashing algorithm. In the case of UUIDv4, these are represented as follows:

• The "nil" UUID: 00000000-0000-0000-0000-000000000000 (all bits set to zero).
• The "max" UUID: FFFFFFFF-FFFF-FFFF-FFFF-FFFFFFFFFFFF (all bits set to one).

By converting these UUIDs to their numeric representations, we can derive the minimum and maximum hash values:

{

"minHash": "00000000-0000-0000-0000-000000000000",

"minHashValue": 0,

"maxHash": "FFFFFFFF-FFFF-FFFF-FFFF-FFFFFFFFFFFF",

"maxHashValue": 340282366920938463463374607431768211455

}

For our example user record, the corresponding numeric value would be 107955310059342914197630047461575069480, positioning it at approximately 31.7% on the hashing ring. To simplify, we can use a range of 0 to 100.

With four nodes initially placed on this ring, they receive random values when added. For instance, our nodes might have the following positions: 7, 33, 60, and 75.

When a record is written, the application hashes the userId, identifies the nearest node, and stores the record as follows:

• Node N4: handles hashes from 7% to 32%
• Node N1: handles hashes from 33% to 60%
• Node N2: handles hashes from 60% to 74%
• Node N3: handles hashes from 75% to 100%

This method allows for efficient record storage without the need to worry about which node is responsible for each record, while also minimizing reorganization during node addition or removal.

Section 1.2: Addressing Load Distribution Challenges

One potential issue with this distribution method is uneven load balancing, as nodes may end up storing a disproportionate amount of data. For instance, if nodes were assigned values of 10, 70, 80, and 87, the first node could end up managing more than half of the records.

To mitigate this skewed distribution, virtual nodes (vNodes) can be introduced. Each physical node is assigned multiple unique hashes from various hashing functions, thus allowing for improved load balancing across the system. In this scenario, each node could utilize four hashes from different algorithms, resulting in multiple random points on the hashing ring.

Known implementations of consistent hashing include various systems, such as:

• Couchbase's automated data partitioning
• OpenStack's Object Storage Service (Swift)
• Amazon's Dynamo storage system
• Data partitioning in Apache Cassandra
• Akka's consistent hashing router
• Riak, a distributed key-value database
• Gluster, a network-attached storage file system
• Akamai content delivery network
• Discord chat application
• Load balancing gRPC requests to a distributed cache in SpiceDB