一致性hash

分布式缓存问题

​ 分布式系统中，当服务增长到一定规模时，惯常的做法是集群化，引入负载均衡，这样做的好处是：1. 高可用。2. 解耦。从外部看，透明化了集群的内部细节（外部都通过负载均衡服务器通信，然后由负载均衡服务器分发请求）。

假设一个简单的场景：有4个cache服务器组成的集群，当一个对象传入集群时，这个对象应该存储在哪一个cache里呢？一种简单的方法是使用映射公式：

Hash(object) % 4

这个算法的问题在于容错性和扩展性不好。所谓容错性是指当系统中某一个或几个服务器变得不可用时，整个系统是否可以正确高效运行；而扩展性是指当加入新的服务器后，整个系统是否可以正确高效运行。

假设一下情况：

• 由于流量增大，需要增加一台cache，共5个cache。这时，映射公式就变成Hash(object) % 5。
• 有一个cache服务器down掉，变成3个cache。这时，映射公式就变成Hash(object) % 3。

因此系统中一旦有服务器变更，大量的key会被重定位到不同的服务器从而造成大量的缓存不命中，这意味着一时间所有的缓存全部失效。而这种情况在分布式系统中是非常糟糕的。

一个设计良好的分布式哈希方案应该具有良好的单调性，即服务节点的增减不会造成大量哈希重定位。一致性哈希算法就是这样一种哈希方案。

一致性哈希算法

1. 简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为${2}^{32}$-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：

整个空间按顺时针方向组织。0和${2}^{32}$-1在零点中方向重合。

1. 下一步将各个服务器使用hash函数进行一次哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将三台服务器使用ip地址哈希后在环空间的位置如下：

1. 接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的hash函数计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

例如我们有A、B、C、D四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据一致性哈希算法，数据A会被定为到Server 1上，D被定为到Server 3上，而B、C分别被定为到Server 2上。

容错性与可扩展性分析

新的一致性hash算法成功解决了cache服务器增减时key的失效问题。现在，无论增减cache，只有部分key失效。

现假设Server 3宕机了：

可以看到此时A、C、B不会受到影响，只有D节点被重定位到Server 2。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

下面考虑另外一种情况，如果我们在系统中增加一台服务器Memcached Server 4：

此时A、D、C不受影响，只有B需要重定位到新的Server 4。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

虚拟节点

对于一个object来说，它落在环上的任何位置的概率都是一样的，那么落在一个cache的概率就和圆弧的长度成正比。于是，我们希望每个cache所占的圆弧长度更接近。

理论上，只要cache足够多，每个cache在圆环上就会足够分散。但是在真实场景里，cache服务器只会有很少，所以，引入了“虚拟节点”的概念。

一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如我们的系统中有两台服务器，其环分布如下：

此时必然造成大量数据集中到Server 1上，而只有极少量会定位到Server 2上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，将一个物理节点拆分为多个虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。具体做法可以在服务器ip或主机名的后面增加编号来实现。

实现一致性哈希(java)

• 一致性Hash算法实现版本1：不带虚拟节点

package com.zsr.test.ConsistentHash;

import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * 一致性Hash算法实现版本1：不带虚拟节点
 * 
 * @author David
 */
public class ConsistentHashingWithoutVirtualNode {
  /**
   * 待添加入Hash环的服务器列表
   */
  private static String[] servers = { "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111",
      "192.168.0.4:111" };

  /**
   * key表示服务器的hash值，value表示服务器的名称
   */
  private static TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();

  /**
   * 程序初始化，将所有的服务器放入sortedMap中
   */
  static {
    for (int i = 0; i < servers.length; i++) {
      int hash = getHash(servers[i]);
      System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
      treeMap.put(hash, servers[i]);
    }
    System.out.println();
  }

  /**
   * 简单起见，复用String的hashCode算法;实际hash算法可以采用MurmurHash
   */
  private static int getHash(String str) {
    int hash = str.hashCode();
    // String的hashCode()方法却会产生负数，取绝对值
    return Math.abs(hash);
  }

  /**
   * 得到应当路由到的结点
   */
  private static String getServer(String node) {
    // 得到带路由的结点的Hash值
    int hash = getHash(node);
    // 获取大于或等于指定key的最小map键相关联的map键值对
    Entry<Integer, String> entry = treeMap.ceilingEntry(hash);

    if (entry == null) {
      return treeMap.firstEntry().getValue();
    }
    return entry.getValue();
  }

  public static void main(String[] args) {
    String[] nodes = { "127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333" };
    for (int i = 0; i < nodes.length; i++)
      System.out.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
  }
}

测试结果:

[192.168.0.0:111]加入集合中, 其Hash值为771739798
[192.168.0.1:111]加入集合中, 其Hash值为770816277
[192.168.0.2:111]加入集合中, 其Hash值为769892756
[192.168.0.3:111]加入集合中, 其Hash值为768969235
[192.168.0.4:111]加入集合中, 其Hash值为768045714

[127.0.0.1:1111]的hash值为35944419, 被路由到结点[192.168.0.4:111]
[221.226.0.1:2222]的hash值为973393028, 被路由到结点[192.168.0.4:111]
[10.211.0.1:3333]的hash值为561068530, 被路由到结点[192.168.0.4:111]

从运行结果来看，也没有问题，三个点路由到的都是顺时针离他们Hash值最近的那台服务器上。

• 一致性Hash算法实现版本2：带虚拟节点

编程方面需要考虑的问题是：

1. 一个真实结点如何对应成为多个虚拟节点？
2. 虚拟节点找到后如何还原为真实结点？

这两个问题其实有很多解决办法，这里使用了一种简单的办法，给每个真实结点后面根据虚拟节点加上后缀再取Hash值，比如”192.168.0.0:111”就把它变成”192.168.0.0:111&&VN0”到”192.168.0.0:111&&VN4”，VN就是Virtual Node的缩写，还原的时候只需要从头截取字符串到”&&”的位置就可以了。

package com.zsr.test.ConsistentHash;

import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * 带虚拟节点的一致性Hash算法
 * 
 * @author David
 */
public class ConsistentHashingWithVirtualNode {
  /**
   * 待添加入Hash环的服务器列表
   */
  private static String[] servers = { "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111",
      "192.168.0.4:111" };

  /**
   * 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
   */
  private static List<String> realNodes = new LinkedList<String>();

  /**
   * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
   */
  private static TreeMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();

  /**
   * 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
   */
  private static final int VIRTUAL_NODES = 5;

  static {
    // 先把原始的服务器添加到真实结点列表中
    for (int i = 0; i < servers.length; i++)
      realNodes.add(servers[i]);

    // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
    for (String str : realNodes) {
      for (int i = 0; i < VIRTUAL_NODES; i++) {
        String virtualNodeName = str + "&&VN" + String.valueOf(i);
        int hash = getHash(virtualNodeName);
        System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
        virtualNodes.put(hash, virtualNodeName);
      }
    }
    System.out.println();
  }

  /**
   * 简单起见，复用String的hashCode算法;实际hash算法可以采用MurmurHash
   */
  private static int getHash(String str) {
    int hash = str.hashCode();
    // String的hashCode()方法却会产生负数，取绝对值
    return Math.abs(hash);
  }

  /**
   * 得到应当路由到的结点
   */
  private static String getServer(String node) {
    // 得到带路由的结点的Hash值
    int hash = getHash(node);
    // 获取大于或等于指定key的最小map键相关联的map键值对
    Entry<Integer, String> entry = virtualNodes.ceilingEntry(hash);

    String virtualNode = null;
    if (entry == null) {
      virtualNode = virtualNodes.firstEntry().getValue();
    }
    virtualNode = entry.getValue();
    return virtualNode.substring(0, virtualNode.indexOf("&&"));
  }

  public static void main(String[] args) {
    String[] nodes = { "127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333" };
    for (int i = 0; i < nodes.length; i++)
      System.out.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
  }
}

测试结果:

虚拟节点[192.168.0.0:111&&VN0]被添加, hash值为1490088590
虚拟节点[192.168.0.0:111&&VN1]被添加, hash值为1490088591
虚拟节点[192.168.0.0:111&&VN2]被添加, hash值为1490088592
虚拟节点[192.168.0.0:111&&VN3]被添加, hash值为1490088593
虚拟节点[192.168.0.0:111&&VN4]被添加, hash值为1490088594
虚拟节点[192.168.0.1:111&&VN0]被添加, hash值为1293575085
虚拟节点[192.168.0.1:111&&VN1]被添加, hash值为1293575086
虚拟节点[192.168.0.1:111&&VN2]被添加, hash值为1293575087
虚拟节点[192.168.0.1:111&&VN3]被添加, hash值为1293575088
虚拟节点[192.168.0.1:111&&VN4]被添加, hash值为1293575089
虚拟节点[192.168.0.2:111&&VN0]被添加, hash值为1097061580
虚拟节点[192.168.0.2:111&&VN1]被添加, hash值为1097061581
虚拟节点[192.168.0.2:111&&VN2]被添加, hash值为1097061582
虚拟节点[192.168.0.2:111&&VN3]被添加, hash值为1097061583
虚拟节点[192.168.0.2:111&&VN4]被添加, hash值为1097061584
虚拟节点[192.168.0.3:111&&VN0]被添加, hash值为900548075
虚拟节点[192.168.0.3:111&&VN1]被添加, hash值为900548076
虚拟节点[192.168.0.3:111&&VN2]被添加, hash值为900548077
虚拟节点[192.168.0.3:111&&VN3]被添加, hash值为900548078
虚拟节点[192.168.0.3:111&&VN4]被添加, hash值为900548079
虚拟节点[192.168.0.4:111&&VN0]被添加, hash值为704034570
虚拟节点[192.168.0.4:111&&VN1]被添加, hash值为704034571
虚拟节点[192.168.0.4:111&&VN2]被添加, hash值为704034572
虚拟节点[192.168.0.4:111&&VN3]被添加, hash值为704034573
虚拟节点[192.168.0.4:111&&VN4]被添加, hash值为704034574

[127.0.0.1:1111]的hash值为35944419, 被路由到结点[192.168.0.4:111]
[221.226.0.1:2222]的hash值为973393028, 被路由到结点[192.168.0.2:111]
[10.211.0.1:3333]的hash值为561068530, 被路由到结点[192.168.0.4:111]

从运行结果看，每个点路由到的服务器都是Hash值顺时针离它最近的那个服务器节点，没有任何问题。

通过采取虚拟节点的方法，一个真实结点不再固定在Hash换上的某个点，而是大量地分布在整个Hash环上，这样即使上线、下线服务器，也不会造成整体的负载不均衡。

参考

一致性哈希算法及其在分布式系统中的应用

对一致性Hash算法，Java代码实现的深入研究

实现一致性哈希java版本

陌生但默默一统江湖的MurmurHash