Consistent Hashing | Algorithms You Should Know #1

Key Concepts:

• Consistent Hashing
• Simple Hashing
• Horizontal Scaling
• Hash Ring
• Hash Space
• Virtual Nodes
• Data Partitioning
• Rebalancing

1. Introduction to Data Distribution in Distributed Systems

• In large-scale distributed systems, data is horizontally scaled across multiple machines due to the inability of a single server to hold all the data.
• Even data distribution is crucial for predictable performance.

2. Simple Hashing

• Process:
  1. Hash the object key using a hashing function (e.g., MD5, MurmurHash) to map it to a numerical range.
  2. Apply the modulo operation (hash % number of servers) to determine the server assignment.
• Example: Eight string keys distributed across four servers.
• Limitation: When servers are added or removed, most keys need to be redistributed, leading to a "storm of misses" and significant data movement. This is untenable for systems with frequent server changes. If server 1 goes down, the modulo operation changes from hash % 4 to hash % 3, causing widespread redistribution.

3. Consistent Hashing

• Goal: Minimize object reassignment when the number of servers changes.
• Core Insight: Hash both object keys and server names (or IP addresses) using the same hashing function and range.
• Hash Ring: The range of hash values is visualized as a ring. Servers and objects are placed on this ring based on their hash values.
• Object Location: To find the server for an object, move clockwise from the object's position on the ring until a server is found.
• Example: Four objects and four servers placed on the hash ring. Key 0 is assigned to server 0, and key 1 is assigned to server 1.
• Adding a Server: When a new server (e.g., s4) is added, only the keys that would now be assigned to the new server are moved. In the example, only key k0 needs to be moved from s0 to s4.
• Removing a Server: When a server (e.g., s1) is removed, only the keys assigned to that server need to be remapped to the next server in the ring. In the example, only k1 needs to be remapped to s2.

4. Uneven Distribution and Virtual Nodes

• Problem: Servers may be unevenly distributed on the ring, leading to some servers handling significantly more objects than others. For example, server s2 might store most of the objects, while s1 and s3 store very little.
• Virtual Nodes: Each server is represented by multiple virtual nodes on the ring. This increases the likelihood of even distribution.
• Example: Two servers, each with three virtual nodes (s0_0, s0_1, s0_2 for server 0 and s1_0, s1_1, s1_2 for server 1).
• Trade-off: More virtual nodes lead to better distribution but require more metadata storage. The number of virtual nodes can be tuned based on system requirements.

5. Real-World Applications

• NoSQL Databases (DynamoDB, Cassandra): Used for data partitioning to minimize data movement during rebalancing.
• Content Delivery Networks (Akamai): Used to distribute web content evenly among edge servers.
• Load Balancers (Google Load Balancer): Used to distribute persistent connections evenly across backend servers, limiting the number of connections that need to be re-established when a server goes down.

6. Conclusion

Consistent hashing is a technique used in distributed systems to minimize the impact of adding or removing servers. It involves mapping both servers and objects to a hash ring and using virtual nodes to improve distribution. It is used in various real-world applications, including NoSQL databases, CDNs, and load balancers.