前言
前文回顾，之前介绍了：
今天分析一下最后一个负载均衡器ConsistentHashLoadBalance.
ConsistentHashLoadBalance
一致性Hash负载均衡器. 看一下官方的介绍：
- 一致性 Hash，相同参数的请求总是发到同一提供者。
- 当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
- 算法参见：http://en.wikipedia.org/wiki/Consistent_hashing
- 缺省只对第一个参数 Hash，如果要修改，请配置 <dubbo:parameter key=”hash.arguments” value=”0,1” />
- 缺省用 160 份虚拟节点，如果要修改，请配置 <dubbo:parameter key=”hash.nodes” value=”320” />
一致性hash原理
在理解一致性hash原理之前，先看一看传统的hash算法。
hash算法
hash算法最初的目的是来解决缓存问题。举个例子，分布式场景，假设有3台redis服务器做缓存，我们如何合理分配这3台redis的资源呢？
答案很简单，使用hash算法。hash(userId) % 3来获取到路由的服务器即可。如图： 
但是以上算法看似能解决问题，但是如果其中一台redis挂掉了，或者需要动态增加一台redis服务器，那么原先的hash算法就不适用了！
既然hash算法是无法解决上述问题，那么如何解决呢？一致性hash算法即可。
一致性hash算法
基本原理： $$ \begin{gather} a + b \end{gather} $$
\(a + b\)
将哈希空间 [0, 2^n-1] 看成一个哈希环，每个服务器节点都配置到哈希环上。每个数据对象通过哈希取模得到哈希值之后，存放到哈希环中顺时针方向第一个大于等于该哈希值的节点上。
初始话一个 0 ~ 2^32 -1 的hash环： 
假设初始化有3个节点，根据ip进行hash分配到不同的位置如下： 
hash到服务器算法：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。
假设有数据data1,data2,data3，那么如下数据将会分别落在NodeC,NodeA,NodeB上: 
如果此时动态增加一个节点NodeD,那么如下所示，只会影响到data3数据的，其他数据并未影响： 
这样就是一致性hash算法，只影响一小部分数据。
依然有一个问题，即如果节点数量太小，将会由于数据节点分布不均匀导致数据倾斜问题。如下图所示：落在节点NodeA上的数据远大于NodeB上的数据。 
如何解决这个问题呢，将引入虚拟节点机制： 通过增加虚拟节点，然后将虚拟节点映射到真实节点上。虚拟节点的数量比真实节点来得多，那么虚拟节点在哈希环上分布的均匀性就会比原来的真实节点好，从而使得数据分布也更加均匀。
如下所示：NodeA,NodeB各虚拟出 n 个节点均匀分布在hash环上，这样通过虚拟节点到实际节点的映射来解决数据倾斜问题。 
再看源码
涉及到的配置：
- 缺省只对第一个参数 Hash，如果要修改，请配置 <dubbo:parameter key=”hash.arguments” value=”0,1” />
- 缺省用 160 份虚拟节点，如果要修改，请配置 <dubbo:parameter key=”hash.nodes” value=”320” />
先看doSelect方法：
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName(); // 获取方法调用名
int identityHashCode = System.identityHashCode(invokers); // 生成调用列表hashcode
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key); // 从缓存中获取此方法的一致性哈希选择器
if (selector == null || selector.identityHashCode != identityHashCode) {
// 缓存 key -> selector
selectors.put(key, new ConsistentHashSelector<T>(invokers, invocation.getMethodName(), identityHashCode));
selector = (ConsistentHashSelector<T>) selectors.get(key);
}
return selector.select(invocation); // 选择节点实现由内部类selector完成
}
可以得出结论，核心负载均衡操作都交给了其静态内部类ConsistentHashSelector选择器.
内部选择器的成员与构造器：
private static final class ConsistentHashSelector<T> {
private final TreeMap<Long, Invoker<T>> virtualInvokers; // 虚拟节点
private final int replicaNumber; // 副本数
private final int identityHashCode; // hashcode
private final int[] argumentIndex; // 参数索引数组
ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
// 1.初始化属性
this.virtualInvokers = new TreeMap<Long, Invoker<T>>(); // 虚拟节点用TreeMap结构
this.identityHashCode = identityHashCode; // hashcode取调用列表hashcode
URL url = invokers.get(0).getUrl();
this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160); // 获取 url 上 hash.nodes属性，默认160
String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0")); // 获取 url 上 hash.arguments属性，默认"0"
// 获取 hash.arguments 数组
argumentIndex = new int[index.length];
for (int i = 0; i < index.length; i++) {
argumentIndex[i] = Integer.parseInt(index[i]);
}
// 2.开始创建虚拟结点
// 对每个invoker生成replicaNumber个虚拟结点，并存放于TreeMap中
for (Invoker<T> invoker : invokers) {
String address = invoker.getUrl().getAddress();
for (int i = 0; i < replicaNumber / 4; i++) {
byte[] digest = md5(address + i);
for (int h = 0; h < 4; h++) {
long m = hash(digest, h);
virtualInvokers.put(m, invoker);
}
}
}
}
}
可见，在构造器内主要是
- 初始化属性
- 创建虚拟节点(也算是初始化属性的一部分)
核心方法，ConsistentHashSelector的select方法:
public Invoker<T> select(Invocation invocation) {
String key = toKey(invocation.getArguments()); // 根据调用参数获取 key
byte[] digest = md5(key); // 生成消息摘要
// 将消息摘要转换为hashCode，这里仅取0-31位来生成HashCode
// 调用sekectForKey方法选择结点。
return selectForKey(hash(digest, 0));
}
此方法具体可以拆分为
- md5() 生成消息摘要
- hash() 获取hash值
- selectForKey() 根据hash值寻址
md5和hash方法就不说了，hash方法的位操作先不深究，主要的方法还是ConsistentHashSelector的selectForKey方法:
private Invoker<T> selectForKey(long hash) {
// 1.找到一个该hash值得尾节点，然后获取其上一个节点
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
// 2.如果该节点不存在，即表示落在环上最后一个和第一个之间的位置，那么直接返回最小值(第一个点)，这样就形成了逻辑环
if (entry == null) {
entry = virtualInvokers.firstEntry();
}
return entry.getValue();
}
这里解释下，如图所示，
- 如果hash值落在了
【2】的位置，那么就直接返回NodeA#1即可。 - 如果hash值落在
【1】的位置，由于【1】后面已经没有虚拟节点，因此返回TreeMap的最小值，即首节点NodeB#3，这样就形成了一个逻辑环。
结束语
参考:
这样LoadBalance基本完成，最后再回到最初的起点Cluster接口。
