Consistent hashing

Hash partitioning is the most common strategy for distributing data across servers in practice.

To implement it, three elements must be defined: boundaries for each data range, which server holds each range, and how to rebalance when servers change.

Among many possible implementations, consistent hashing stands out for its simplicity and efficiency.

Consistent hashing begins with a hash function that maps keys to integers.

This function must be fast because it is used for every request.

Cryptographic hash functions, such as those in the SHA family, distribute keys well but are computationally expensive.

Non-cryptographic hash functions are better suited for general lookup operations.

For example, MurmurHash is a widely used non-cryptographic hash function.

Assume the hash function outputs an integer in the range from 0 to 2³¹.

The algorithm maps each key to a point on a circle.

An arbitrary point on the circle is assigned the value 0.

Moving clockwise, each value is assigned a position on the circle.

A list of servers is processed, and each server’s identifier—such as an IP address or hostname—is hashed.

The resulting hash value determines where on the circle the server is located.

Each server owns all hash values between itself and its nearest clockwise neighbor.

This creates a single hash range per server.

The direction (clockwise or counterclockwise) does not affect the outcome.

To find which server stores a key:

1. Compute the hash value of the key.
2. Move clockwise from the hash value until reaching a server.
3. The server at the first point encountered owns that key.

This ensures each key is assigned to exactly one server.

1. Hash each server’s identifier to determine its position on the circle.
2. Store the resulting hash ranges in sorted order.
3. Share this sorted list with all clients.

Clients use binary search to locate the correct hash range.

Once the range is found, the client knows which server owns it.

Each server has only one assigned range.

The client then forwards the request to that server.

Simplicity and speed are key strengths.

The algorithm efficiently solves two core problems:

• How to divide the hash value space into ranges.
• How to assign ranges to servers.

When a new server is added:

1. Hash its identifier to find its position on the circle.
2. The new server takes ownership of its own range.
3. The previous clockwise neighbor now owns a smaller range.

This adjustment ensures minimal disruption to existing key assignments.

When a server leaves:

• Its range is split among remaining servers.
• The redistribution happens smoothly due to the circular structure.

The algorithm maintains consistency with minimal data movement.

When a new server joins the cluster, it takes ownership of one or more shards previously owned by another server. No other servers experience changes in their data ranges.

When a server is removed, its range is transferred to the counterclockwise neighbor. Again, all other servers remain unaffected.

This behavior ensures minimal data movement during rebalancing—exactly what is desired in dynamic clusters.

In this model, the cluster uses a fixed number of equally sized shards.

Each server is assigned a hash value. The algorithm moves clockwise from that value to locate the range border.

The server is placed at that border, taking ownership of the range.

When a new server joins, it claims one or more shards from another server.

Shards are never split in this approach.

Data is replicated within the cluster. This ensures no data loss if a server crashes.

Replicas are stored on the next one or two clockwise neighbors of the original server.

The algorithm has two major flaws:

• The domino effect: If a heavily loaded server crashes, all its data shifts to the next server. This may overload that server, causing it to fail and triggering a chain reaction.

• Uneven distribution: Servers are placed randomly on the cycle. This leads to some servers being close together, others far apart, creating data hotspots.

To address these issues, virtual nodes (v-nodes) are introduced.

Each physical server is hashed multiple times, creating multiple points on the cycle.

For example, a server’s name is modified by appending an index to its IP address.

The index is incremented to generate the next virtual node’s position.

Each server now owns multiple ranges, not just one.

With two servers, each owns multiple ranges, resulting in more even data distribution.

With three servers, each is assigned three virtual nodes.

Each server owns three distinct ranges.

When a server fails, its load is distributed across the remaining available servers.

Without virtual nodes, all load from a failed server shifts to a single neighbor.

More virtual nodes lead to more uniform data distribution.

The trade-off is increased memory usage to store v-node lists.

Each lookup requires more binary search iterations to identify the correct server.

Virtual nodes improve load balancing and fault tolerance.

The algorithm remains efficient under dynamic changes.

This design supports real-world cluster operations with minimal data movement during failures or additions.

The use of virtual nodes is a widely adopted modification in production systems.

Several databases use consistent hashing, including Cassandra, Couchbase, and Voldemort.

Consistent hashing helps assign shards to servers and enables efficient rebalancing by minimizing data movement.

It is used for data partitioning in distributed caches and content delivery networks.

Consistent hashing evenly distributes cache data—such as web content—among CDN cache servers.

Consistent hashing helps load balancers distribute persistent connections evenly across backend servers.

When a backend server fails, only connections to that server are reshuffled. All other connections remain unchanged.

Chat systems must reestablish user connections to remaining servers after a failure.

Consistent hashing helps distribute these connections evenly among available servers.

Consistent in hashing can distribute messages across multiple queue partitions in messaging systems.

For example, RabbitMQ implements such a feature.

Most messaging systems use simpler mechanisms, such as a modulo function, to distribute messages among partitions.

If data is short-lived and does not require movement during rebalancing, basic partitioning—like modulo or random selection—may suffice.

If rebalancing is needed and data movement must be minimized, consistent hashing is appropriate.