极客观点
项目管理
HarmonyOS
在开源系统里涉及到一致性哈希时，有这么两种虚拟节点的生成算法：
一：
如果有如下服务器：
10.10.10.101:port
10.10.10.102:port
10.10.10.103:port
每个节点在md5环上生成N个虚拟节点，那么先生成字符串：
ip1#1, ip1#2, ip1#3, ip1#4....
ip2#1, ip2#2, ip2#3, ip2#4....
然后对每一个字符串执行md5，并将结果指向对应的ip
二：
和第一种思路基本一致，但在生成虚拟节点的哈希值时，使用了一种叫ketama hash的方法：
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);
}
}
}
可能直接看代码比较费劲，我简单说说：
这里也是生成了类似于“一”里的服务器名字，
算出这个服务器的md5值之后，
每一个md5值得有16个字节，然后每4个字节一组，
分别是(0,1,2,3)(4,5,6,7)(8,9,10,11)(12,13,14,15)
用位移得到一个新的哈希值，
并将这四组值指向原来的一个实体节点。
又因为分了每4个虚拟节点一组，所以外层循环就是冗余数/4了。第一种是在google的开源项目groupcache使用的算法。
第二种方法是很多memcached客户端(比如spymemcache)在使用的算法。
两种方法都可以保证在虚拟节点达到一定数值时保证缓存分布均匀。
但第二种看起来只是进行了一些奇特的位处理，并没有什么特别之处啊。
那么第二种方法比第一种好在哪里呢？求指点
另外我想知道这两种算法是否可以从数学上简单证明正确性呢？
好吧，问了很多同学
得到了一种解释：
1.ketama hash算法中以每4个虚拟节点为一组，每组只需要计算一次md5值，所以比每个虚拟节点计算一次省掉了75%的对md5函数的调用，而md5函数本身是需要消耗cpu的，所以次数能少就少
2.因为md5的值有一定的随机性，复用一个md5值中的各位来生成虚拟节点也可以保证这些虚拟节点的随机性，这样和每个节点都去算md5一样，可以保证节点在环上分布均匀
看看sf的巨巨还有没有补充的，没有的话我只能采纳自己了233333