一致性哈希算法之Ketama算法

原文

有关一致性哈希算法原理及其应用讨论的文章已经足够多，如果对一致性哈希算法一点概念都没有的同学可以先参考这篇文章：一致性哈希。

相对来说，一致性哈希算法的原理还是比较容易理解的，但在日常开发过程中发现虽然大部分同事对一致性哈希算法的原理有个大概的认识，然而能知道该算法具体实现的人却寥寥无几。当然一致性哈希算法的实现不同语言有不同的实现方式，其中较为有名的一种实现叫Ketama算法，该算法最初是由Last.fm的程序员实现的并得到了广泛的应用，一些开源框架譬如spymemcached，twemproxy等都内置了该算法的实现。

本文主要从spymemcached的源码出发，分析Ketama算法的具体实现。

在类KetamaNodeLocator.java里有个setKetamaNodes（）方法负责一致性哈希环的初始化工作， 代码如下：

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

下面我们来具体分析下setKetamaNodes函数的实现，首先MemcachedNode这个类对Memcached节点的网络连接参数及方法进行了封装。TreeMap在这里用于模拟一致性哈希环的环状结构。

    int numReps = config.getNodeRepetitions();

getNodeRepetitions()方法负责读取配置信息，返回一个真实的Memcached节点对应的虚拟节点数，默认情况下返回160，也就是说一个Memcached节点在一致性哈希环上对应有160个虚拟节点。

    config.getKeyForNode(node, i)

getKeyForNode()根据传进去的MemcacheNode对象和变量i生成key值，返回值示例：“127.0.0.1:11311-0”

computeMd5()根据key生成16位的MD5摘要， 因此digest数组共16位:

    byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));

将digest数组按每四位一组，通过位操作产生一个最大32位的长整数。之所以是32位是因为一致性哈希环取值范围为0～2^32; 回到上面的例子，对于一个Memcached节点譬如“127.0.0.1:11311”, 将通过for循环产生“127.0.0.1:11311-0”，“127.0.0.1:11311-1”... “127.0.0.1:11311-39”共40个副本，对于每个副本譬如“127.0.0.1:11311-0”, 将会产生4个长整数，对应一致性哈希环上的4个位置，所以默认配置的情况下，一个Memcached节点将在一致性哈希环上占据4×40=160个位置。

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

以k为key将MemcacheNode对象放到TreeMap里：

    newNodeMap.put(k, node);

由于TreeMap中的value是按Key排序的，因此可以通过TreeMap来模拟一致性哈希的环状结构，k值小的排在前，k值大的排在后。

以上就是一致性哈希环初始化过程的的基本分析，下面我们来看看查询的过程， getPrimary()函数传入一个key，譬如"123", 先计算出该key的哈希值。

    public MemcachedNode getPrimary(final String k) {
        MemcachedNode rv = getNodeForKey(hashAlg.hash(k));
        assert rv != null : "Found no node for key " + k;
        return rv;
      }


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

重点在于下面这句, TreeMap的tailMap()方法会返回一个SortedMap对象tailMap, tailMap中包含的所有key值都比传参hash大，这个操作相当于给定一个hash值，从一致性哈希环中按顺时针顺序查找节点，直到查找到第一个key值比传参hash大的节点，该节点就是该hash值所对应的Memcached节点。

    SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);

以上就是对Sypmencached源码中Ketama算法的实现分析。