How Consistent Hashing Scales Distributed Systems

Scaling is the process of increasing the system’s capacity to handle growing amount work. It's about designing your application or infrastructure so it can manage more users, data, or requests without failing or becoming slow.

There were two major ways of scaling systems —

1. Vertical Scaling (Scaling Up)

   You might add more power to your system (more cores, more RAM, more storage, faster SSDs). In this case, the ability of the system to handle load is increased. This is also the easiest since it does not require changes to application or its architecture. However, on the flip side, it expensive — as high-end hardware costs more, it is limited — you will soon hit machine’s max capacity. Additionally, upgrades require downtime, and single failure can bring down entire application.

2. Horizontal Scaling (Scaling Out)
   This involves adding more servers to distribute the system load. This could be distributing your database, application or (or its parts) onto separate/multiple machines.
   It is more fault tolerant solution, brings the near unlimited scalability, cheap — you could use multiple standard systems rather than one high-end one, zero downtime during upgrades. However, it is much more complex, as it requires changes to architecture as well as application level code. You need shared state for application to be in sync, load balancers to manage the traffic, etc.

There is also database level scaling (caching, read replicas, and sharding), and application level scaling (asynchronous processing, microservices), which is also used alongside above two techniques.

One of the major problems in horizontal scaling is how to distribute the traffic/load on multiple servers efficiently.

The Rehashing Problem

The simplest way to distribute the load among N servers is using the formula, serverIndex = hash(key) % N .

For example, with 4 servers, we use the modular operation hash(key) % 4 to find the server where a key is stored. This works reasonably well for a fixed number of servers if the data distribution is even, but that is seldom the case in real-world distributed systems.

Now, if a server crashes (say, we go from 4 servers to 3), the formula becomes hash(key) % 3. This change causes a catastrophic remapping. Here is what happens,

1. The result of hash(key) % 3 will be different from hash(key) % 4 for majority of keys — all keys will needed to be remapped, not just the keys on Server 3.

2. Your cache is suddenly empty. Since, keys map to a different server and application cannot find the expected data.

3. All cache misses directly hit your database, overloading it, and likely bringing it to a halt. This is often called, thundering herd problem.

4. You will need to remap almost all K keys in the system, which is an $O(K)$ operation that can grind the system to a halt.

Consistent hashing solves this.

Consistent Hashing

The primary benefit of consistent hashing is that when a server (or slot) is added or removed, only k/n keys need to be remapped on average, where k is the total number of keys and n is the number of servers.

It works by placing servers on a conceptual ring. It then maps a key to the first server it "sees" by moving clockwise around the ring from the key's position. When a server is added or removed, only the keys in its specific arc are affected. The vast majority of keys stay exactly where they are.

Hash Ring

The hash ring represents output space of the hash function in use. For example, If we use SHA-1 as hash function, it’s hash space goes from 0 to 2^160 -1 , lets say x0 … xN.

The hash ring represents the entire output space of the hash function being used. For example, if we use SHA-1 as the hash function, its hash space goes from 0 to 2^160 - 1. In this case x0 will be 0, and xN will be 2^160 - 1.

Hash Servers - We map servers onto the ring using IP or server name, using the same hash function. The hash function used in here is different as there is no modulo operation.

In consistent hashing, we place both the keys and the servers onto this same ring. To determine which server a key is stored on, we travel clockwise from the key's location until a server is found.

For example, in above if we need to find the server for k0, we will go clockwise from k0, until we reach s1. Hence, key k0 is stored on server s1 . Similarly, key k4 and k5 are stored on server s3.

Now, say if we

1. add a server s5 between, k0 and k1. Key k0 will now be found on server s5, while k1 and k2 will be found on server s1. So, only one key was needed to be remapped.

2. If we remove server s3 then only keys k4 and k5 will be needed to be remapped on server s4.

So far it would have become obvious that this issues creates two further problems —

1. It is possible for servers to be clustered unevenly on the ring, creating large gaps. See how, s4, s5, and s1 , s2 only cover half of the ring.

2. It is possible keys are unevenly distributed, where almost all the keys (hotspots) are only assigned to a few servers.

Virtual Nodes

Virtual nodes are used to solve the problem of uneven key distribution in consistent hashing. Instead of mapping a physical server to one point, the server is represented by many virtual nodes at multiple places on the ring. In a real-world system, this number is typically large, which reduces the probability of an uneven distribution of keys. This way, a single server is responsible for many small partitions of the ring.

This large number of virtual nodes helps balance the distribution of keys among the servers on the ring. The standard deviation of the key distribution will be smaller when we increase the number of virtual nodes. However, more space is needed to store the metadata mapping these virtual nodes to their physical servers. This is a tradeoff, and we can tune the number of virtual nodes to fit our system's requirements.

Applications

• Discord Chat Application

• Akamai Content Delivery Network

• Partitioning Component of Amazon’s Dynamo Database.