Poison

ConsistentHashLoadBalance

之前项目中曾使用一致性 Hash 路由请求至指定的缓存节点,关于 Dubbo 的一致性 Hash 实现可以参考 Dubbo 一致性Hash负载均衡实现剖析,源码参见 ConsistentHashLoadBalance.java at dubbo-3.0.0。其 hash 值与 Invoker 的映射关系采用 TreeMap 作为底层的数据结构,其根据当前调用查询调用者的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private final TreeMap<Long, Invoker<T>> virtualInvokers;

public Invoker<T> select(Invocation invocation) {
String key = toKey(invocation.getArguments());
byte[] digest = Bytes.getMD5(key);
return selectForKey(hash(digest, 0));
}

private String toKey(Object[] args) {
StringBuilder buf = new StringBuilder();
for (int i : argumentIndex) {
if (i >= 0 && i < args.length) {
buf.append(args[i]);
}
}
return buf.toString();
}

private Invoker<T> selectForKey(long hash) {
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash);
if (entry == null) {
entry = virtualInvokers.firstEntry();
}
return entry.getValue();
}

关键点在于 selectForKey 方法中对 TreeMap 实例的 ceilingEntry 调用及 firstEntry 调用,我们知道 TreeMap 底层实现为红黑树,即自平衡的二叉搜索树。ceilingEntry 方法用于使用计算出的 hash 值查找大于等于 hash 值的节点,跟随 ceilingEntry 方法调用至 TreeMap.java at jdk8-b120

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Gets the entry corresponding to the specified key; if no such entry
* exists, returns the entry for the least key greater than the specified
* key; if no such entry exists (i.e., the greatest key in the Tree is less
* than the specified key), returns {@code null}.
*/
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key); // 比较 key 与当前遍历到的节点 p 的 key 值
if (cmp < 0) { // 此时 key < p.key,即当前节点大于要寻找的 key, 但不一定是大于等于 key 的最小值,因为我们需要找大于等于 key 的最小值,所以尝试进入左子树继续搜索
if (p.left != null)
p = p.left; // 当前 p 节点存在左子树,进入左子树继续搜索,对应下方节点示例图一,p 指向 5 时,此时我们寻找的 key 为 1, 尝试进入左子树搜索
else
return p; // 当前 p 节点不存在左子树,对应下方节点示例图一,p 指向 3 时,此时我们寻找的 key 为 1, 返回 3, 即找到了大于等于 key 的最小节点:3
} else if (cmp > 0) { // 此时 key > p.key, 即 p.key < key, 而我们要寻找大于等于 key 的值,所以尝试进入右子树搜索,因为右子树(如果存在)的元素比当前节点大
if (p.right != null) { // 如果存在右子树,则进入右子树搜索
p = p.right;
} else { // 如果不存在右子树,说明当前无法从右子树中尝试寻找更大的值,只能希望向上搜索看是否能找到更大的值
// 当在下方节点示例图一寻找 key 为 10, p 指向 8 时,我们向上搜索,执行下面的代码会在 while 判断时因为 parent 等于 NULL 而跳出 while, 返回 NULL, 即我们未在节点示例图一中找到大于等于 10 的节点
// 当在下方节点示例图二寻找 key 为 10, p 指向 8 时,因 ch 不等于 parent.right 跳出循环,此时 parent 指向的 12 即我们要寻找的节点
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else // 当前节点 p 的 key 值与我们要寻找的值相等,直接返回 p 节点
return p;
}
return null;
}
1
2
3
4
5
6
7
8
9
节点示例图一        节点示例图二

5 12
/ \ /
/ \ /
3 8 5
/ \
/ \
3 8

根据上方 selectForKey 的代码,我们知道,当在 TreeMap 中无法找到大于等于指定 hash 值的节点时,此时我们调用 virtualInvokers.firstEntry() 获取 TreeMap 中的最小节点,firstEntry() 方法将调用至 TreeMap.java at jdk8-b120

1
2
3
4
5
6
7
8
9
10
11
/**
* Returns the first Entry in the TreeMap (according to the TreeMap's
* key-sort function). Returns null if the TreeMap is empty.
*/
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}

即一直向左子树寻找,定位至左下角的节点,即二叉搜索树中的最小值,这样就模拟出了一致性 Hash 的环。