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

前言

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

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

源码分析

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

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 方法：

@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 方法返回一个服务节点。

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

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 方法的时候，怎么找到相同的节点呢？

代码：

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！！！