一致性 hash 算法

作者: fffhJk | 来源:发表于2019-08-13 20:38 被阅读0次

参考列表

理论分析： https://www.cnblogs.com/lpfuture/p/5796398.html
理论分析： https://blog.csdn.net/sparkliang/article/details/5279393
算法实现： https://www.cnblogs.com/xrq730/p/5186728.html
memcache的一致性hash算法使用： https://blog.csdn.net/kongqz/article/details/6695417

基本场景

假设有N个cache服务器，如果将一个object映射到N个cache了？通用的hash算法为，计算对应object的hash值，然后均匀分配到N个cache：
hash(object)%N
一切都运行异常，假设以下两个场景
-1. 一个cache服务器宕机了，这个时候需要对object重新计算分布，那么所有的object都会缓存失效
-2. 由于访问量增加，增加对应的cache数量，那么同样的，所有的对象都需要重新计算。
基于以上两个场景，传统的hash算法无法满足，那么就需要引入一致性hash算法 consistant hashing

hash算法和单调性

Hash 算法的一个衡量指标是单调性（ Monotonicity ），定义如下：

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
容易看到，上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

consistant hashing算法的原理

consistent hashing 是一种 hash 算法，简单的说，在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。

环形hash空间

考虑通常的hash算法都是将value映射到一个32为key的值，也即是0_2^32-1 次方的数值空间。我们将该空间想象成一个首0 尾 2^32 -1相接的圆环。

1AFF1C635E773C2470928AB081B0A2254.jpg

对象映射到hash空间

接下来考虑 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。
hash(object1) = key1;
… …
hash(object4) = key4;

251E42B4FC9EF522F26B789194958CBB0.jpg

把cache映射到hash空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中，并且使用相同的 hash 算法。
假设当前有 A,B 和 C 共 3 台 cache ，那么其映射结果将如图 3 所示，他们在 hash 空间中，以对应的 hash 值排列。
hash(cache A) = key A;
… …
hash(cache C) = key C;

31D6938D7F3A80F60A9B82840193F9B09.jpg

顺便提一下 cache 的 hash 计算，一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 hash 输入。

把对象映射到cache

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，接下来要考虑的就是如何将对象映射到 cache 上面了。
在这个环形空间中，如果沿着顺时针方向从对象的 key 值出发，直到遇见一个 cache ，那么就将该对象存储在这个 cache 上，因为对象和 cache 的 hash 值是固定的，因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗？！
依然继续上面的例子（参见图 3 ），那么根据上面的方法，对象 object1 将被存储到 cache A 上； object2 和 object3 对应到 cache C ； object4 对应到 cache B ；

考察cache的变动

前面讲过，通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时， cache 会失效，进而对后台服务器造成巨大的冲击，现在就来分析分析 consistent hashing 算法。

移除cache

考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象，也即是本来映射到 cache B 上的那些对象。
因此这里仅需要变动对象 object4 ，将其重新映射到 cache C 上即可

4DD041B5688CBABAD7244D42FBC105CC4.jpg

增加cache

再考虑添加一台新的 cache D 的情况，假设在这个环形 hash 空间中， cache D 被映射在对象 object2 和 object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache （ cache B ）之间的对象（它们是也本来映射到 cache C 上对象的一部分），将这些对象重新映射到 cache D 上即可。
因此这里仅需要变动对象 object2 ，将其重新映射到 cache D 上；

5DD9A031CECEC4B8F39549747EC7ABA14.jpg

虚拟节点

考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：

平衡性:平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，比如在上面的例子中，仅部署 cache A 和 cache C 的情况下，在 4 个对象中， cache A 仅存储了 object1 ，而 cache C 则存储了 object2 、 object3 和 object4 ；分布是很不均衡的。
为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念，它可以如下定义：
“虚拟节点”（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。
仍以仅部署 cache A 和 cache C 的情况为例，在图 4 中我们已经看到， cache 分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假设一种比较理想的情况，参见图 6 。

6C70498FFF12D5E58509D8D509385FF8B.jpg

此时，对象到“虚拟节点”的映射关系为：

objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；

因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。
引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。

748FAC097951AB8BB637D0950FB9CBBEB.jpg

“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为 202.168.14.241 。
引入“虚拟节点”前，计算 cache A 的 hash 值：
Hash(“202.168.14.241”);
引入“虚拟节点”后，计算“虚拟节”点 cache A1 和 cache A2 的 hash 值：
Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2

Java实现

Java实现代码主要参考 https://www.cnblogs.com/xrq730/p/5186728.html

不带虚拟节点的一致性hash算法

package consistent.hashing;

import org.apache.commons.collections.MapUtils;

import java.util.Arrays;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 不带虚拟节点的一致性hash算法
 */
public class ConsistantHashingWithoutVirtualNode {
    /**
     * 待添加入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 SortedMap<Integer, String> sortedMap = new TreeMap<>();

    /**
     * 初始化，将所有服务器列表放入sortedMap
     */
    static {

        Arrays.stream(servers).forEach(s -> {
            int hash = getHash(s);
            System.out.println(s + "  init hash:" + hash);
            sortedMap.put(hash, s);
        });
    }


    private static int getHash(String node) {
        int hash = node.hashCode();
        return hash < 0 ? Math.abs(hash) : hash;
    }

    private static String getServer(String node) {
        int hash = getHash(node);
        //得到大于该hash值的所有map
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (MapUtils.isNotEmpty(subMap)) {
            // 第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            return subMap.get(i);
        }
        return sortedMap.get(sortedMap.firstKey());
    }

    public static void main(String[] args) {
        String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
        Arrays.stream(nodes).forEach(node -> System.out.println(node + " hash:" + getHash(node) + " route node:" + getServer(node)));
    }

}

输出结果

192.168.0.0:111  init hash:575774686
192.168.0.1:111  init hash:8518713
192.168.0.2:111  init hash:1361847097
192.168.0.3:111  init hash:1171828661
192.168.0.4:111  init hash:1764547046
127.0.0.1:1111 hash:380278925 route node:192.168.0.0:111
221.226.0.1:2222 hash:1493545632 route node:192.168.0.4:111
10.211.0.1:3333 hash:1393836017 route node:192.168.0.4:111

如上输出结果，很明显看出来hash结果分布不均匀

虚拟节点的一致性hash算法

package consistent.hashing;

import org.apache.commons.collections.MapUtils;

import java.util.*;

/**
 * 带虚拟节点的一致性hash算法
 * 参考 https://www.cnblogs.com/xrq730/p/5186728.html
 */
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<>();

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

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

    static {
        Arrays.stream(servers).forEach(s -> realNodes.add(s));

        for (String s : realNodes) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                String virtualNodeName = s + "&&VN" + i;
                int hash = getHash(virtualNodeName);
                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
    }

    private static int getHash(String node) {
        int hash = node.hashCode();
        return hash < 0 ? Math.abs(hash) : hash;
    }

    /**
     * 得到对应节点的路由
     */
    private static String getServer(String node) {

        int hash = getHash(node);
        String virtualNode = "";
        //得到大于该hash值的所有map
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        if (MapUtils.isNotEmpty(subMap)) {
            // 第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            virtualNode = subMap.get(i);
        } else {
            virtualNode = virtualNodes.get(virtualNodes.firstKey());
        }
        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"};
        Arrays.stream(nodes).forEach(node -> System.out.println(node + " hash:" + getHash(node) + " route node:" + getServer(node)));
    }

}

输出结果

虚拟节点[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 route node:192.168.0.4:111
221.226.0.1:2222 hash:973393028 route node:192.168.0.2:111
10.211.0.1:3333 hash:561068530 route node:192.168.0.4:111

如上结果可以看出，最终的路由节点比较均匀。

memcache的一致性hash算法使用

参考原文 https://blog.csdn.net/kongqz/article/details/6695417
KetamaNodeLocator#setKetamaNodes

  /**
   * Setup the KetamaNodeLocator with the list of nodes it should use.
   *
   * @param nodes a List of MemcachedNodes for this KetamaNodeLocator to use in
   *          its continuum
   */
  protected void setKetamaNodes(List<MemcachedNode> nodes) {
    TreeMap<Long, MemcachedNode> newNodeMap =
        new TreeMap<Long, MemcachedNode>();
    int numReps = config.getNodeRepetitions();
    for (MemcachedNode node : nodes) {
      // Ketama does some special work with md5 where it reuses chunks.
      if (hashAlg == DefaultHashAlgorithm.KETAMA_HASH) {
        for (int i = 0; i < numReps / 4; i++) {
          byte[] digest =
              DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));
          for (int h = 0; h < 4; h++) {
            Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)
                    | ((long) (digest[2 + h * 4] & 0xFF) << 16)
                    | ((long) (digest[1 + h * 4] & 0xFF) << 8)
                    | (digest[h * 4] & 0xFF);
            newNodeMap.put(k, node);
            getLogger().debug("Adding node %s in position %d", node, k);
          }
        }
      } else {
        for (int i = 0; i < numReps; i++) {
          newNodeMap.put(hashAlg.hash(config.getKeyForNode(node, i)), node);
        }
      }
    }
    assert newNodeMap.size() == numReps * nodes.size();
    ketamaNodes = newNodeMap;
  }

获取对应的虚拟节点 int numReps = config.getNodeRepetitions();
以getKeyForNode方法得到这组虚拟节点的name
Md5编码
Md5编码后，每个虚拟结点对应Md5码16个字节中的4个，组成一个long型数值，做为这个虚拟结点在环中的惟一key

KetamaNodeLocator#getNodeForKey

  MemcachedNode getNodeForKey(long hash) {
    final MemcachedNode rv;
    if (!ketamaNodes.containsKey(hash)) {
      // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
      // in a lot of places, so I'm doing this myself.
      SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);
      if (tailMap.isEmpty()) {
        hash = getKetamaNodes().firstKey();
      } else {
        hash = tailMap.firstKey();
      }
    }
    rv = getKetamaNodes().get(hash);
    return rv;
  }

计算出Md5，根据Md5的字节数组，通过Kemata Hash算法得到key在这个环中的位置。

应用场景分析

1、memcache的add方法：通过一致性hash算法确认当前客户端对应的cacheserver的hash值以及要存储数据key的hash进行对应，确认cacheserver，获取connection进行数据存储
2、memcache的get方法：通过一致性hash算法确认当前客户端对应的cacheserver的hash值以及要提取数据的hash值，进而确认存储的cacheserver，获取connection进行数据提取