Что такое Consistent Hashing

• Hash both keys and nodes на common space (e.g. SHA-1 → 0..2^160)
• Each key → closest node clockwise on ring
• Adding node: only keys between previous node и new одно reshuffle
• Virtual nodes: 1 physical node = 100-200 virtual points on ring → better balance
• Alternative: Rendezvous Hashing (simpler, comparable properties)

// Pseudocode
function nodeForKey(key, ring):
  h = hash(key)
  for node in ring sorted by hash:
    if hash(node) >= h: return node
  return ring[0]  // wrap around

• Bloom Filter
• Load Balancer
• CDN

Consistent Hashing offers several advantages over traditional hashing methods:

• Minimized Data Redistribution: When a node is added or removed from the cluster, only a small fraction of the data (approximately 1/N) needs to be redistributed, which reduces downtime and improves system efficiency.
• Load Balancing: By distributing keys across multiple nodes in a circular manner, consistent hashing ensures that the load is evenly distributed among the nodes.
• Scalability: Adding or removing nodes from the cluster can be done dynamically without disrupting the entire system. This makes it easier to scale the system up or down as needed.
• Fault Tolerance: The distributed nature of consistent hashing makes the system more fault-tolerant. If one node fails, the data can be seamlessly redirected to other nodes.

These advantages make consistent hashing a popular choice for distributed systems that require high availability and scalability.

Implementing consistent hashing involves several steps:

• Define the Hash Function: Choose a hash function that generates a consistent output for the same input. This ensures that keys are distributed in a predictable manner.
• Create Virtual Nodes: Instead of assigning a single key to a node, create multiple virtual nodes for each physical node. This helps in balancing the load more evenly.
• Distribute Keys: Use the hash function to distribute keys across the virtual nodes in a circular manner. The key is assigned to the node that is closest to it in the circular arrangement.
• Handle Node Changes: When a node is added or removed, update the virtual node assignments and redistribute the keys accordingly. This ensures that the system remains balanced even as nodes are added or removed.

Here is a simple example of how to implement consistent hashing in Python:

Consistent hashing is just one of many load balancing techniques used in distributed systems. Here are some other popular techniques and how they compare to consistent hashing:

• Round-Robin: In round-robin load balancing, requests are distributed in a sequential manner. This can lead to uneven load distribution if the nodes have different capacities. Consistent hashing, on the other hand, ensures that the load is distributed more evenly.
• Random Load Balancing: In random load balancing, requests are distributed randomly among the nodes. This can result in some nodes being overloaded while others are underutilized. Consistent hashing provides a more predictable and balanced distribution.
• Weighted Round-Robin: In weighted round-robin load balancing, nodes are assigned weights based on their capacity. Requests are then distributed in a round-robin manner based on these weights. While this can improve load balancing, it does not provide the same level of consistency as consistent hashing.

Consistent hashing is particularly useful in scenarios where the system needs to be highly available and scalable, such as in distributed caches, CDNs, and database sharding.