Link to the original text
Due to the poor scalability and fault tolerance of cache load balancing realized by ordinary hash algorithm , So we introduce a consistent hash algorithm .
One sentence generalizes the consistency hash ： It is an improved version of the common modular hash algorithm , Hash function calculation method remains unchanged , It's just by building rings Hash Space instead of ordinary linear Hash Space .

operation

• Choose one big enough Hash Space （ It's usually 0 ~ 2^32） Form a hash ring .
• For each storage server node in the cache cluster Hash value , The service node is Hash Position on the ring .
• For every data that needs to be stored key The hash value is also calculated once , The computed hash is also mapped to the ring

advantage ：

• The expansion ability is improved
  When you need to add nodes , Only part of the data of the next node is affected , Migrate the data to a new node .
• Improved fault tolerance
  When a node fails , Only the current node is affected , It will not affect the data of other nodes , Just save the node data to the next node in the clockwise direction .

The problem is ：

• Data skew
  The nodes are unevenly distributed after hashing algorithm , This results in a large amount of data stored on a node
• Node avalanche
  1, Due to data skew, the node request pressure is too high and hangs up
  2, The node is down for some reason , This will cause all the data of this node to be transferred to the next node , The next node hangs up because the request is too large
  3, For the above reasons, after the node hangs up , The data goes to the next node , The next node also hangs up due to excessive pressure ... Cause all nodes to hang up , Cause node avalanche

Solution

How to solve data skew and node avalanche ？

• Virtual node
  It is to virtual a few of its avatar nodes on the hash ring for the original single physical node , These spin off nodes are called 「 Virtual node 」. In fact, the data printed to the sub body node is also mapped to the physical node corresponding to the sub body , Such a physical node can be evenly distributed in all parts of the hash ring through the way of virtual nodes , Solve the problem of data skew .