一致性哈希算法介绍，及java实现(二)
e D 后的映射关系
虚拟节点
考量 Hash 算法的另一个指标是平衡性 (Balance) ，定义如下：
平衡性
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，比如在上面的例子中，仅部署 cache A 和 cache C 的情况下，在 4 个对象中， cache A 仅存储了 object1 ，而 cache C 则存储了 object2 、 object3 和 object4 ；分布是很不均衡的。
为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念，它可以如下定义：
“虚拟节点”（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。
仍以仅部署 cache A 和 cache C 的情况为例，在图 4 中我们已经看到， cache 分布并不均匀。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假设一种比较理想的情况，参见图 6 。
图 6 引入“虚拟节点”后的映射关系
此时，对象到“虚拟节点”的映射关系为：
objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；
因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。
引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache时的映射关系如图 7 所示。
图 7 查询对象所在 cache
“虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为202.168.14.241 。
引入“虚拟节点”前，计算 cache A 的 hash 值：
Hash(“202.168.14.241”);
引入“虚拟节点”后，计算“虚拟节”点 cache A1 和 cache A2 的 hash 值：
Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2
以下是实现这种算法的java代码：
首先我们实现一个HashFunction，参考net.spy.memcached.DefaultHashAlgorithm中的取hash的算法，KETAMA_HASH算法
复制代码
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class HashFunction {
private MessageDigest md5 = null;
public long hash(String key) {
if (md5 == null) {
try {
md5 = MessageDigest.getInstance("
MD5");
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException("no md5 algorythm found");
}
}
md5.reset();
md5.update(key.getBytes());
byte[] bKey = md5.digest();
long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)
| (long) (bKey[0] & 0xFF);
return res & 0xffffffffL;
}
}
复制代码
然后实现ConsistentHash，参考代码https://weblogs.java.net/blog/2007/11/27/consistent-hashing
复制代码
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash {
private final HashFunction hashFunction;
private final int numberOfReplicas; // 虚拟节点
private final SortedMap circle = new TreeMap(); // 用来存储虚拟节点hash值 到真实node的映射
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
public void add(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunction.hash(node.toString() + i), node);
}
}
public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(hashFunction.hash(node.toString() + i));
}
}
/**
* 获得一个最近的顺时针节点
* @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点
* @return
*/
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
long hash = hashFunction.hash((S