分布式系统之一致性哈希算法

作者就职于京东,在稳定性保障、敏捷开发、高级JAVA、微服务架构有深入的理解

一致性哈希是用来解决缓存节点删除增加或者微服务架构中的粘性负载均衡后端节点删除增加时，避免大部分节点缓存失效的一种算法。原理是将对象和节点都进行相同hash算法( MurmurHash, MetroHash or SipHash1–3,SHA-1 or MD5)处理后映射到一个圆环中(This should be familiar to every Java programmer – the hashCode method on Object returns an int, which lies in the range -231 to 231-1. Imagine mapping this range into a circle so the values wrap around)，顺时针查找对象映射位置的下一个节点，则是命中的节点，如果没有找到则返回圆环的第一个节点(To find which cache an object goes in, we move clockwise round the circle until we find a cache point)，这种情况当新增和删除节点时并不会改变原来所有的命中规则

1和4会命中A、2会命中B、3会命中C

当C节点crash和新增D节点时，只会影响3和4的object缓存失效

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,
    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);
  } 

}
复制代码

但是当节点个数比较少时，往往会出现数据倾向现象(With a small number of vnodes, different servers could be assigned wildly different numbers of keys.)，所以需要引入虚拟节点(virtual nodes),一般是主机名加编号,数据定位方式不变，只不过命中后要将虚拟节点转换成真实节点(To add the list of nodes to the ring hash, each one is hashed m.replicas times with slightly different names ( 0 node1, 1 node1, 2 node1, …))，Dubbo服务框架中的ketama算法也是采用的这种思想

然而环哈希算法依旧会导致节点不平衡(the load distribution across the nodes can still be uneven),重复hash也会导致内存开销增大。于是Google公司于2014年提出Jump Hash，设计思路是当桶的数量变化时，只需要把一些对象从旧桶移动到新桶，不需要做其它移动

func Hash(key uint64, numBuckets int) int32 {
  var b int64 = -1
  var j int64
  for j < int64(numBuckets) {
    b = j
    key = key*2862933555777941757 + 1
    j = int64(float64(b+1) *
      (float64(int64(1)<<31) / float64((key>>33)+1)))
  }
  return int32(b)
}
复制代码

然而依旧是不足的，输入是节点数量，输出是对应的序列号(The main limitation is that it only returns an integer in the range 0..numBuckets-1. It doesn’t support arbitrary bucket names),另外只能增加或者删除最后的节点，不支持任意节点删除，也就是说中间节点失效时，失效节点的数据并不会重新平均分配(you can only properly add and remove nodes at the upper end of the range)，所以它适用于分布式主备存储类系统中(These combined make Jump Hash better suited for data storage applications where you can use replication to mitigate node failure)

当然还有其他杰出的算法如Multi-Probe Consistent Hashing、Rendezvous Hashing、Maglev Hashing，具体的大家网上查阅吧

文章来源：www.liangsonghua.me

作者介绍：京东资深工程师-梁松华，在稳定性保障、敏捷开发、JAVA高级、微服务架构方面有深入的理解