本文简单介绍 Dubbo 中的负载均衡策略:一致性哈希策略。
1
一致性哈希策略
一致性哈希策略:指的是相同参数的请求总是发到同一个提供者实例。
简单描述一下一致性哈希,如下图所示。假设有 8 ,组成下面 A - H 的 8 个虚拟节点,A - H 哈希值分别是递增的,当有一个请求进来,通过计算参数的哈希值,比如该值刚好是 1 的位置,那么选中比 1 的值大的最小的那个实例,则结果该请求选中 C 虚拟节点;假如请求的参数的哈希值是在 2 的位置,那么找不到比 2 的值大的最小的实例,则选中所有实例中最小的一个,也就是 A。
2
Dubbo 实现方式
Dubbo 在使用一致性哈希的时候,会用到如下配置:
配置对哪些参数做哈希计算,默认是只对第一个参数:
配置需要多少份虚拟节点,也就是一个提供服务的实例需要冗余多少份,默认是160份虚拟节点
Dubbo 在实现一致性哈希策略的时候使用了虚拟节点的概念,就是扩大实例个数,当然不是真的有那么多个实例,比如有 5 个实例,默认是 160 个备份,则真实的虚拟节点有 5 * 160 = 800 个。
为什么要采取虚拟节点?
假如不使用虚拟节点,只有 5 个节点,当移除掉 1 个节点的时候,会导致将改移除节点的请求分配到另外 4 个节点的时候不平衡,哈希计算并不保证平衡。当使用虚拟节点的时候,有更多个节点可分配,会更加均匀的分配到其他节点上。
3
一致性哈希策略的优点
优点:在一些需要将同一个请求参数对应到同个服务的场景下很适合;当对实例进行增加或者删除的时候,能避免引起很大的变动。
4
ConsistentHashLoadBalance 源码
public classConsistentHashLoadBalanceextendsAbstractLoadBalance {
public static finalStringNAME="consistenthash";
// 记录所有
private finalConcurrentMap>selectors=newConcurrentHashMap>();
@SuppressWarnings("unchecked")
@Override
protected InvokerdoSelect(List> invokers,URL url,Invocation invocation) {
String methodName = RpcUtils.getMethodName(invocation);
String key = invokers.get().getUrl().getServiceKey() +"."+ methodName;
// 计算哈希值 key,通过这个字段来识别出调用实例是否有变化,有变化则重新创建 ConsistentHashSelector
intidentityHashCode = System.identityHashCode(invokers);
ConsistentHashSelector selector = (ConsistentHashSelector)selectors.get(key);
if(selector ==null|| selector.identityHashCode!= identityHashCode) {
// 没有存在 selector 或者 invokers 实例有变化,重新创建
selectors.put(key, newConsistentHashSelector(invokers,methodName,identityHashCode));
selector = (ConsistentHashSelector)selectors.get(key);
}
returnselector.select(invocation);
}
private static final classConsistentHashSelector {
private finalTreeMap>virtualInvokers;
private final intreplicaNumber;
private final intidentityHashCode;
private final int[]argumentIndex;
ConsistentHashSelector(List> invokers,String methodName, intidentityHashCode) {
// 虚拟节点
this.virtualInvokers=newTreeMap>();
this.identityHashCode= identityHashCode;
URL url = invokers.get().getUrl();
// 虚拟节点数量
this.replicaNumber= url.getMethodParameter(methodName,"hash.nodes",160);
// 需要哈希的参数,默认是第一个参数
String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName,"hash.arguments","0"));
// 记录需要哈希的参数的下标
argumentIndex=new int[index.length];
for(inti =;i
argumentIndex[i] = Integer.parseInt(index[i]);
}
for(Invoker invoker : invokers) {
String address = invoker.getUrl().getAddress();
// 每一个实例存 replicaNumber 份虚拟节点
for(inti =;i
// 先将虚拟节点分为 (replicaNumber/4) 份,先做 MD5
byte[] digest = md5(address + i);
for(inth =;h
//再做哈希计算,得到 m,作为 Key
longm = hash(digest,h);
// 存到虚拟节点
virtualInvokers.put(m,invoker);
}
}
}
}
publicInvokerselect(Invocation invocation) {
// 得出要进行哈希的字符串
String key = toKey(invocation.getArguments());
// 进行 MD5
byte[] digest = md5(key);
returnselectForKey(hash(digest,));
}
// 根据 hash.arguments 配置的对多少个参数进行哈希,得出拼接后的字符串
privateStringtoKey(Object[] args) {
StringBuilder buf =newStringBuilder();
for(inti :argumentIndex) {
if(i >=&& i
buf.append(args[i]);
}
}
returnbuf.toString();
}
// 选择实例
privateInvokerselectForKey(longhash) {
// 找出大于或等于 hash 中最小的键值对
Map.Entry> entry =virtualInvokers.ceilingEntry(hash);
if(entry ==null) {
// 找出最小的键值对
entry =virtualInvokers.firstEntry();
}
returnentry.getValue();
}
// 计算哈希值
private longhash(byte[] digest, intnumber) {
return(((long) (digest[3+ number *4] &0xFF)
| ((long) (digest[2+ number *4] &0xFF)
| ((long) (digest[1+ number *4] &0xFF)
| (digest[number *4] &0xFF))
&0xFFFFFFFFL;
}
// MD5 加密
private byte[]md5(String value) {
MessageDigest md5;
try{
md5 = MessageDigest.getInstance("MD5");
}catch(NoSuchAlgorithmException e) {
throw newIllegalStateException(e.getMessage(),e);
}
md5.reset();
byte[] bytes;
try{
bytes = value.getBytes("UTF-8");
}catch(UnsupportedEncodingException e) {
throw newIllegalStateException(e.getMessage(),e);
}
md5.update(bytes);
returnmd5.digest();
}
}
}
参考文章:
https://web.archive.org/web/20120605030524/http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html
http://www.zsythink.net/archives/1182
做个有梦想的程序猿
领取专属 10元无门槛券
私享最新 技术干货