ConsistentHashLoadBalance

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

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:

/**
 * 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;
                // parent 为 null 说明已经经过 root 节点，无法找到大于等于 p 的节点，跳出 while 循环直接返回 null
                // ch == parent.right 说明此时从右子节点回退，此时的 parent 小于 ch, 不满足条件，所以继续执行直到 ch != parent.right, 即从左子节点回退，此时 parent 大于 ch, 找到满足条件的 parent，跳出 while 循环返回 parent
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else // 当前节点 p 的 key 值与我们要寻找的值相等，直接返回 p 节点
            return p;
    }
    return null;
}

节点示例图一        节点示例图二

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

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

/**
 * 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 的环。

Reference

Fix wrong interpretation by tianshuang · Pull Request #1686 · apache/dubbo-website · GitHub