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

我们以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的客户端这么做是有道理的~