在上次的一致性哈希讲解中，提到了虚拟结点的生成算法。说得不怎么明白，本文将会对常用的两种虚拟结点生成算法进行一些简单的解析。
我们以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的客户端这么做是有道理的~
