consistent hashing

consistent hashing 算法思想是：首先求出服务器（节点）的哈希值，并将其配置到0～2^32的圆上。然后用同样的方法求出 存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过2^32仍然找不到服务器，就 会保存到第一台服务器上。下面有一张比较经典的图，直接用过来，不修改了。

    

        图一  Consistent Hashing原理示意图

     这里有四台服务器，我们假设增加一台服务器Node5，可以看到，它影响的数据只是在增加Node5逆时针方向的数据会受到影响。同样，删除其中一台服务器，例如删除服务器node4，那么影响的数据也只是node4上缓存的数据。

   

   图二 Consistent Hashing添加服务器

   Consistent Hashing最大限度地抑制了hash键的重新分布。另外要取得比较好的负载均衡的效果，往往在服务器数量比较少的时候需要增加虚拟节点来保证服务器能 均匀的分布在圆环上。因为使用一般的hash方法，服务器的映射地点的分布非常不均匀。使用虚拟节点的思想，为每个物理节点（服务器）在圆上分配 100～200个点。这样就能抑制分布不均匀，最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上，就表示用户数据真正存储位置是在该 虚拟节点代表的实际物理服务器上。
下面有一个图描述了需要为每台物理服务器增加的虚拟节点。

 

  图三 虚拟节点倍数- 物理节点数关系图

      x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数(scale)，y轴是实际物理服务器数，可以看出，当物理服务器的数量很小时，需要更大的虚拟节 点，反之则需要更少的节点，从图上可以看出，在物理服务器有10台时，差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。

下面是一个简单的java参考实现：

 

import
 java.util.Collection;
import
 java.util.SortedMap;
import
 java.util.TreeMap;

public
 
class
 ConsistentHash<T> {

 private
 
final
 HashFunction hashFunction;
 private
 
final
 
int
 numberOfReplicas;
 private
 
final
 SortedMap<Integer, T> circle = 
new
 TreeMap<Integer, T>();

 public
 ConsistentHash(
      HashFunction hashFunction, //hash算法
      int
 numberOfReplicas,
//虚拟节点数
      Collection<T> nodes//物理节点
   ) {
   this
.hashFunction = hashFunction;
   this
.numberOfReplicas = numberOfReplicas;

   for
 (T node : nodes) {
     add(node);
   }
 }

 public
 
void
 add(T node) {
   for
 (
int
 i = 
0
; i < numberOfReplicas; i++) {
     circle.put(hashFunction.hash(node.toString() + i), node);
   }
 }

 public
 
void
 remove(T node) {
   for
 (
int
 i = 
0
; i < numberOfReplicas; i++) {
     circle.remove(hashFunction.hash(node.toString() + i));
   }
 }

//关键算法
 public
 T get(Object key) {
   if
 (circle.isEmpty()) {
     return
 
null
;
   }
   int
 hash = hashFunction.hash(key);
   if
 (!circle.containsKey(hash)) {
     SortedMap<Integer, T> tailMap = circle.tailMap(hash);
     hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
   }
   return
 circle.get(hash);
 }

}