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

前言

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

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

源码分析

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

public abstract ProviderInfo doSelect(SofaRequest invocation, List
    
      providerInfos);复制代码

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

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

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

然后就是一致性 Hash 了，重点讲讲。有必要复习一下我们之前写过的一致性 hash 算法 demo：。

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

来看看具体实现。

先看看 doSelect 方法：

@Overridepublic ProviderInfo doSelect(SofaRequest request, List
    
      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
    
      actualNodes, int hashcode) {    this.interfaceId = interfaceId;    this.method = method;    this.hashcode = hashcode;    // 创建虚拟节点环 （默认一个provider共创建128个虚拟节点，较多比较均匀）    this.virtualNodes = new TreeMap
     
      ();    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
    
      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！！！