SOFA-源码分析-—-负载均衡和一致性-Hash

## 前言

SOFA 内置负载均衡,支持 5 种负载均衡算法,随机(默认算法),本地优先,轮询算法,一致性 hash,按权重负载轮询(不推荐,已被标注废弃)。

一起看看他们的实现(重点还是一致性 hash)。

源码分析

具体源码在 AbstractLoadBalancer 类中,子类需要实现 doSelect 方法:

1
2
3

public abstract ProviderInfo doSelect(SofaRequest invocation, List<ProviderInfo> providerInfos);

随机是默认算法,RandomLoadBalancer 类是具体实现,基本是就是 providerInfos.get(random.nextInt(size)) 的逻辑,但考虑到权重,会按总权重数随机找个数字,然后这个数字会递减直到小于 0 的时候,确定那个节点。好像看起来和权重没什么关系? 有大佬懂的可以指导一下。

本地优先算法,则是找本机的 localhost 进行匹配,优先选择和本机地址相同的服务,然后在这些服务列表进行随机选一个。

轮询就是一个个来。使用取于算法。

然后就是一致性 Hash 了,重点讲讲。 有必要复习一下我们之前写过的一致性 hash 算法 demo: 自己实现一个一致性 Hash 算法

SOFA 具体实现是 ConsistentHashLoadBalancer 类。内部维护一个 Map,每个服务对应一个选择器,这个选择器内部维护着一个 TreeMap,SOFA 会将所有节点均匀的散列在 Map 中,也就是 hash 环上,使用了虚拟节点。当根据服务的 key 获取节点的时候(如果服务列表没变),会通过 hash 值找到比他大的那个节点,相同的请求每次找到的都是同一个节点(根据第一个参数 hash)。

来看看具体实现。

先看看 doSelect 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public ProviderInfo doSelect(SofaRequest request, List<ProviderInfo> providerInfos) {
String interfaceId = request.getInterfaceName();
String method = request.getMethodName();
String key = interfaceId + "#" + method;
int hashcode = providerInfos.hashCode(); // 判断是否同样的服务列表
Selector selector = selectorCache.get(key);
if (selector == null // 原来没有
||
selector.getHashCode() != hashcode) { // 或者服务列表已经变化
selector = new Selector(interfaceId, method, providerInfos, hashcode);
selectorCache.put(key, selector);
}
return selector.select(request);
}

根据接口名和方法名从 map 中找到对应的服务选择器,如果没有,或者服务列表变了,则重新创建一个,这点和缓存的一致性 Hash 设计还是有点不一样。

缓存的一致性 Hash 的目的是:如果服务列表变了,比如节点的增减,那么,缓存的 key 通过相同的 hash 算法依然能够找到对应的缓存节点(最多失效一个节点的数据——如果增减一个节点)。

但 RPC 服务的一致性 hash 的目的是:希望相同的请求总是落在同一个节点上。

而这里无法确定增加的是哪一个节点,索性直接创建一个新的。

然后,调用选择的 select 方法返回一个服务节点。

先看看选择器的构造方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Selector(String interfaceId, String method, List<ProviderInfo> actualNodes, int hashcode) {
this.interfaceId = interfaceId;
this.method = method;
this.hashcode = hashcode;
// 创建虚拟节点环 (默认一个provider共创建128个虚拟节点,较多比较均匀)
this.virtualNodes = new TreeMap<Long, ProviderInfo>();
int num = 128;
for (ProviderInfo providerInfo : actualNodes) {
for (int i = 0; i < num / 4; i++) {
byte[] digest = messageDigest(providerInfo.getHost() + providerInfo.getPort() + i);
for (int h = 0; h < 4; h++) {
long m = hash(digest, h);
virtualNodes.put(m, providerInfo);
}
}
}
}

主要逻辑就是构造虚拟节点,使用 TreeMap,和我们之前实现的一样。那么虚拟节点是如何设计的呢?

SOFA 为每个节点分配了 128 个虚拟节点,保存在 Map 中,也就是 128 个引用指向同一个对象。这里的 hash 算法用来 md5 然后再复杂的 hash 一波,为了更加的均衡吧。

当使用 select 方法的时候,怎么找到相同的节点呢?

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
private ProviderInfo sekectForKey(long hash) {
ProviderInfo providerInfo = virtualNodes.get(hash);
if (providerInfo == null) {
SortedMap<Long, ProviderInfo> tailMap = virtualNodes.tailMap(hash);
if (tailMap.isEmpty()) {
hash = virtualNodes.firstKey();
} else {
hash = tailMap.firstKey();
}
providerInfo = virtualNodes.get(hash);
}
return providerInfo;
}

hash 该方法第一个参数,找到比他的 hash 值大节点集合中的第一个节点,如果没有比他大的,则最小的那个节点(回到原点)。

标准的一致性 hash 算法。保证了每次相同的请求都会落在同一个节点上。

总结

RPC 的一致性 hash 和缓存的一致性 hash 的目的是不同的。
缓存的目的是:当集群中缓存节点增减的时候,服务访问相同 key 依然能够访问到相同的节点(增减造成的失效节点很少)。不会像普通的取于算法那样造成无法访问,进而引起缓存雪崩,甚至 DB 宕机。

而 RPC 的目的是:希望相同的请求(第一个参数相同),每次都会打在相同的节点上。

换个角度想想,其实都是一样的,目的都是为了相同的请求每次都访问到相同的节点。

好啦,关于 SOFA 的负载均衡就到这里啦。

bye!!!


SOFA-源码分析-—-负载均衡和一致性-Hash
http://thinkinjava.cn/2018/05/03/2018/2018-05-03-SOFA-源码分析-—-负载均衡和一致性-Hash/
作者
莫那·鲁道
发布于
2018年5月3日
许可协议