一致性哈希-虚拟结点生成

在上次的一致性哈希讲解中，提到了虚拟结点的生成算法。说得不怎么明白，本文将会对常用的两种虚拟结点生成算法进行一些简单的解析。

我们以Google的groupcache和经典应用memcached来做例子进行说明。

首先是groupcache，在groupcache中生成虚拟结点的算法代码如下：

func (m *Map) Add(keys ...string) {
    for _, key := range keys {
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
            m.keys = append(m.keys, hash)
            m.hashMap[hash] = key
        }
    }
    sort.Ints(m.keys)
}

对每个实体机器生成replicas个虚拟结点，每个虚拟结点生成一个#编号+名字的字符串，例如10.10.10.107这个结点有4个虚拟结点的话：

110.10.10.107
210.10.10.107
310.10.10.107
410.10.10.107

就是其4个虚拟结点的名字，对四个字符串进行hash，生成4个key，groupcache里的Hash方法是可以覆盖的，如果传入nil，那么会用默认的crc32.ChecksumIEEE，来看一下Map和New的定义：

type Map struct {
    hash     Hash
    replicas int
    keys     []int // Sorted
    hashMap  map[int]string
}

func New(replicas int, fn Hash) *Map {
    m := &Map{
        replicas: replicas,
        hash:     fn,
        hashMap:  make(map[int]string),
    }
    if m.hash == nil {
        m.hash = crc32.ChecksumIEEE
    }
    return m
}

比如容易懂，keys里存的是虚拟结点hash后的结果，然后这些key在hashMap里都可以找到对应的实体结点。

查找结点的时候可以用keys来做二分查找，所以时间复杂度是O(logn)。

下面来看看memcached。

memcached里的一致性哈希其实和groupcache差不多，主要的区别在于哈希算法，又因为一致性哈希是客户端侧的负载均衡，所以我们要看的是memcached客户端的代码，比如spymemcached里的算法：

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

默认使用的哈希算法是ketama hash，这种哈希算法的特殊之处是会把虚拟结点每4个分成一组，每一组计算一次md5值，然后这个md5值的16个字节会被分成4组：

(0, 1, 2, 3)
(4, 5, 6, 7)
(8, 9, 10, 11)
(12, 13, 14, 15)

之后每个字节分别被左移24位、16位、8位，生成新的对应虚拟结点的新的md5值(其实不是md5值)。

举例，如果原来有一组值：

10, 5, 14, 9

那么计算出的该虚拟结点对应的值就是：

(10<<24) + (5<<16) + (14<<8) + 9

很诡异的一个算法。这种方法比前文的直接计算所有虚拟结点的md5值好在什么地方呢？

看这一句：

// Ketama does some special work with md5 where it reuses chunks.

其实就是说，这个算法会重复利用md5值的各个位。我们知道md5值计算是比较消耗cpu的一项工作，而按虚拟结点每4个一组，可以减少75%的md5计算次数。

当然了，也有人会反驳说，这项工作消耗cpu，但我的web应用启动时只需要计算一次，之后全局的数组可以重复利用，所以75%的节省根本没有什么意义。

这个就要看网站的具体架构了，由于memcached的一致性哈希负载均衡是客户端的负载均衡，如果我们用java或者golang做web开发，那么在服务端应用启动时进行一次计算确实没有什么问题。

但如果使用php来做web应用，做过php开发的应该明白，php是没有什么可以全局复用的全局变量的(redis或者memcached的pconnect所能得到的持久化连接不算)。所以每次web请求从nginx到cgi都会重新走各种web框架的index.php，然后重新去计算每一个服务器虚拟结点的md5，那么这个问题可能就会变成比较严重的性能问题。

所以memcached的客户端这么做是有道理的~