TAF 必修课(七):负载均衡

作者:温昂展

前面在过载保护章节中已提及了负载均衡,顾名思义,本节要探究的对象为负载/请求。负载均衡除了起到过载预防的作用,本质上是提高了系统的吞吐量,最小化响应时间,到达资源利用最大化。

一、算法与架构

1. 算法

目前,负载均衡算法不管是在学术研究还是在工程实现上都已比较成熟,算法大体可分以下几种:

  • 随机(random)算法
  • 轮询(round-robin)算法
  • 哈希(hash)算法
  • 一致性哈希算法
  • 静态权重调度算法
  • 动态权重、自适应算法

非自适应类算法不要求从服务节点实时获得负载的更新,而自适应算法通常需要负载均衡器能感知节点的负载变化动态调整分发策略,提高负载平衡的效果。也因此,两类算法在实现上架构设计也有较大的差别。

那么节点的负载如何衡量呢? 根据不同类型的系统应用,通常会定义不同的度量方式,如:CPU资源、内存资源、当前进程数、吞吐量、成功率、响应时间等指标都可以作为负载度量的指标,各个指标的重要程度根据实际情况有所不同。

2. 架构

由于这里探讨的是软负载均衡技术,一些基于硬负载均衡的架构设计不做具体涉及。软负载均衡架构大体可以分为:

  • 基于客户端
  • 基于DNS
  • 基于反向代理
  • 基于第三方应用或系统,如:哈雷、TGW、LVS

除了基于客户端方式,其他架构上实际上都是引入一个均衡服务器做控制或代理,或是返回请求的调度结果,亦或是直接对请求做转发。结合TAF的设计理念和架构做思考,负载均衡器其实可以放到主控侧来实现,但是我认为由于负载均衡策略的复杂性,单是对调度决策数据分析已经非常繁重,因此负载均衡通常还是单独引入一个接入层(统一接入网关)来实现,比如目前在使用的 TGW、哈雷接入、LVS(四层)、GSLB/LB(七层)、L5、CMLB 等都是此类接入层系统的实现方案。

负载均衡器周期性计算出每个被调机器的权重,再使用高效的配额算法分配各个主调机器的访问路由,主调机器上的业务进程通过API来取得这些路由,调用结束时通过API来反馈路由的好与坏。

而TAF的实现,我们把重点放在客户端。

二、TAF实现

根据前面对Client调用的分析可知,客户端会采用选定的负载均衡策略选择一个Invoker,对请求进行路由分发。若采用静态策略,显然在客户端做选择更为直接;若是考虑根据负载调整动态权重,和容错一样,客户端直接统计(成功率、响应时间等)更为精确。

首先根据前面提到的容错策略,初始化服务节点列表如下:

//使用不带权重的hash
List<Invoker<T>> sortedInvokers = sortedInvokersCache;
if (sortedInvokers == null || sortedInvokers.isEmpty()) {
    throw new NoInvokerException("no such active connection invoker");
}

List<Invoker<T>> list = new ArrayList<Invoker<T>>();
for (Invoker<T> invoker : sortedInvokers) {
    if (!invoker.isAvailable()) {
        /**
         * 屏敝后尝试重新调用    
         */
        ServantInvokerAliveStat stat = ServantnvokerAliveChecker.get(invoker.getUrl());
        if (stat.isAlive() || (stat.getLastRetryTime() + (config.getTryTimeInterval() * 1000)) < System.currentTimeMillis()) {
            list.add(invoker);
        }
    } else {
        list.add(invoker);
    }
}
// TODO 如果全死,是否需要随机取一个尝试?
if (list.isEmpty()) {
    throw new NoInvokerException(config.getSimpleObjectName() + " try to select active invoker, size=" + sortedInvokers.size() + ", no such active connection invoker");
}

目前支持的负载均衡策略有Round-Robin轮询、带权重轮询、Hash、带权重Hash、一致性Hash; 默认使用的策略是Round-Robin轮询,若客户端调用时在请求上下文中(JceContext对应的map)有设置对应的hash参数则优先使用相应的hash策略,策略选用的优先级为: 一致性hash > hash > round-robin。其中,

1. Round-Robin轮询

相当于简单随机化,适用于各个节点无差别的情况。

 // 省略服务节点列表初始化
 Invoker<T> invoker = list.get((sequence.getAndIncrement() & Integer.MAX_VALUE) % list.size());

2. hash 均衡

根据请求上下文的hash值对服务节点列表大小取模运行,进行路由分发,在系统正常运行情况下,可以保证相同hash值路由到同一服务节点。

Invoker<T> invoker = list.get((int) (hash % list.size()));

3. 一致性hash均衡

根据一致性hash算法生成一定空间(虚拟节点)大小的调用序列哈希环,整个空间按顺时针方式组织,将对应的服务节点根据哈希映射到环上,在发生移除/添加操作时,它能尽可能小的改变已存在的Key值映射关系。构造算法如下:

public static <T> TreeMap<Long, Invoker<T>> buildConsistentHashCircle(Collection<Invoker<T>> invokers,
                                                                      ServantProxyConfig config) {
    List<Invoker<T>> weightInvokers = new ArrayList<Invoker<T>>();
    for (Invoker<T> invoker : invokers) {
        if (invoker.getUrl().getParameter(Constants.TAF_CLIENT_WEIGHT_TYPE, 0) != 1) {
            weightInvokers.clear();
            break;
        }
        if (invoker.getUrl().getParameter(Constants.TAF_CLIENT_WEIGHT, 0) > 0) weightInvokers.add(invoker);
    }

    TreeMap<Long, Invoker<T>> result = new TreeMap<Long, Invoker<T>>();
    try {
        boolean staticWeight = !weightInvokers.isEmpty();
        Collection<Invoker<T>> srcInvokers = staticWeight ? weightInvokers : invokers;

        for (Invoker<T> invoker : srcInvokers) {
            int replicaNumber = staticWeight ? invoker.getUrl().getParameter(Constants.TAF_CLIENT_WEIGHT, 0) : config.getDefaultConHashVirtualNodes();
            if (replicaNumber > config.getDefaultConHashVirtualNodes())
                replicaNumber = config.getDefaultConHashVirtualNodes();

            replicaNumber = replicaNumber / 4 <= 0 ? 1 : replicaNumber / 4;
            for (int i = 0; i < replicaNumber; i++) {
                byte[] digest = md5(invoker.getUrl().toIdentityString() + i);
                for (int h = 0; h < 4; h++) {
                    long m = hash(digest, h);
                    result.put(m, invoker);
                }
            }
        }

    } catch (Exception e) {
        ClientLogger.getLogger().error("build consistent hash circle err. ", e);
        return null;
    }
    return result;
}

4. 带静态权重策略

上述算法的简单实现都假定每个服务节点都是完全对等的,而实际上每个服务节点的处理能力不尽相同,因此我们可以给每个节点根据处理能力的大小分配对应的权值。权重大的节点处理更多的请求,降低权重小的节点的系统负载。实现上,根据权重序列计算出节点调用序列,权重越大的节点在调用序列中出现的次数越多。生成调用序列算法如下:

public static <T> List<Invoker<T>> buildStaticWeightList(Collection<Invoker<T>> invokers,
                                                         ServantProxyConfig config) {
    List<Invoker<T>> weightInvokers = new ArrayList<Invoker<T>>();
    for (Invoker<T> invoker : invokers) {
        if (invoker.getUrl().getParameter(Constants.TAF_CLIENT_WEIGHT_TYPE, 0) != 1) {
            return null;
        }
        if (invoker.getUrl().getParameter(Constants.TAF_CLIENT_WEIGHT, 0) > 0) weightInvokers.add(invoker);
    }

    if (weightInvokers.isEmpty()) {
        return null;
    }

    if (ClientLogger.getLogger().isDebugEnabled()) {
        ClientLogger.getLogger().debug("[buildStaticWeightList]: weightInvokers size: " + weightInvokers.size());
    }

    int minWeight = Integer.MAX_VALUE;
    int maxWeight = Integer.MIN_VALUE;

    for (Invoker<T> invoker : weightInvokers) {
        int tmpWeight = invoker.getUrl().getParameter(Constants.TAF_CLIENT_WEIGHT, 0);

        if (tmpWeight > maxWeight) maxWeight = tmpWeight;

        if (tmpWeight < minWeight) minWeight = tmpWeight;
    }

    int maxRange = maxWeight / minWeight;
    if (maxRange < config.getMinStaticWeightLimit()) maxRange = config.getMinStaticWeightLimit();

    if (maxRange > config.getMaxStaticWeightLimit()) maxRange = config.getMaxStaticWeightLimit();

    Comparator<Pair<Integer, Invoker<T>>> comparator = new WeightToInvokerComparator<T>();
    TreeSet<Pair<Integer, Invoker<T>>> weightToInvoker = new TreeSet<Pair<Integer, Invoker<T>>>(comparator);
    Map<Invoker<T>, Integer> invokerToWeight = new HashMap<Invoker<T>, Integer>();

    int totalWeight = 0;
    for (Invoker<T> invoker : weightInvokers) {
        int weight = (invoker.getUrl().getParameter(Constants.TAF_CLIENT_WEIGHT, 0) * maxRange) / maxWeight;
        totalWeight += weight;
        weightToInvoker.add(new Pair<Integer, Invoker<T>>(weight, invoker));
        invokerToWeight.put(invoker, weight);
        if (ClientLogger.getLogger().isDebugEnabled()) {
            ClientLogger.getLogger().debug("[buildStaticWeightList]: invoker: " + invoker.hashCode() + ", weight: " + weight + ", host: " + invoker.getUrl().getHost() + ", port: " + invoker.getUrl().getPort());
        }
    }
    List<Invoker<T>> result = new ArrayList<Invoker<T>>();
    for (int i = 0; i < totalWeight; i++) {
        boolean first = true;
        TreeSet<Pair<Integer, Invoker<T>>> weightToInvokerTmp = new TreeSet<Pair<Integer, Invoker<T>>>(comparator);
        Iterator<Pair<Integer, Invoker<T>>> it = weightToInvoker.descendingIterator();
        while (it.hasNext()) {
            Pair<Integer, Invoker<T>> pair = it.next();
            if (first) {
                first = false;
                result.add(pair.second);
                weightToInvokerTmp.add(new Pair<Integer, Invoker<T>>(pair.first - totalWeight + invokerToWeight.get(pair.second), pair.second));
            } else {
                weightToInvokerTmp.add(new Pair<Integer, Invoker<T>>(pair.first + invokerToWeight.get(pair.second), pair.second));
            }
        }
        weightToInvoker = weightToInvokerTmp;
    }
    return result;
}

目前TAF还没有提供基于动态权重的方案实现,但是设计上可扩展性较强,之后可以通过继承LoadBalance接口来做更多策略的实现。

感谢阅读,有错误之处还请不吝赐教。

本系列暂时告一段落,以后有时间再继续补充

再次感谢实习以来Leader和导师的指导,感谢TAF学习上terry浩哥、kahn哥、菠菜哥、jeff哥等小伙伴的热情帮助

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习从入门到成神

计算机系统的层次存储结构详解

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

901
来自专栏Golang语言社区

Go 语言实现 MapReduce 框架

MapReduce 是 Google 提出的一个软件架构,用于大规模数据集(大于1TB)的并行运算。简而言之,就是将任务切分成很小的任务然后一个一个区的执行最后...

3696
来自专栏测试开发架构之路

数据库系统关系模型概念

关系模型简述 关系模型就是处理TABLE,它由三部分组成:  描述DB各种数据的基本结构形式(Table/Relation)  描述Table与Table之...

3604
来自专栏木东居士的专栏

不深入而浅出 Roaring Bitmaps 的基本原理

3644
来自专栏Linyb极客之路

贫血,充血模型的解释以及一些经验

下面用举一个具体的代码来说明,代码来自Hibernate的caveatemptor,但经过我的改写: 一个实体类叫做Item,指的是一个拍卖项目 一个DA...

812
来自专栏灯塔大数据

每周学点大数据 | No.41 join 操作

No.41期 join 操作 Mr. 王:第一个话题就是 join 操作。 join 操作在数据库中还是非常常见的。 小可:这个 join 指的是笛卡儿积操...

3657
来自专栏我的小碗汤

19个很有用的 ElasticSearch 查询语句 篇二

另一个结构化查询的例子是 范围查询。在这个例子中,我们要查找 2015 年出版的书。

1662
来自专栏岑玉海

Hbase 学习(五) 调优

1.垃圾回收器调优 当我们往hbase写入数据,它首先写入memstore当中,当menstore的值大于hbase.hregion.memstore.fl...

36713
来自专栏不会写文章的程序员不是好厨师

伪共享(False Sharing)和缓存行(Cache Line) 大杂烩

在上篇介绍LongAdder的文章中,我们最后留下了一个问题,为什么Cell中要插入很多个实际上并没有使用的Long变量?这个问题就得从False Sharin...

891
来自专栏mukekeheart的iOS之旅

MySQL学习笔记(一)

一、MySQL基础知识 MySQL 是一个真正的多用户、多线程 SQL 数据库服务器。 SQL(结构化查询语言)是世界上最流行的和标准化的数据库语言。MySQL...

2238

扫码关注云+社区