自适应负载均衡(20%)

发表于 更新于 分类于

云环境下自适应负载均衡算法的设计。
题目描述 -> 阿里巴巴 2019 中间件性能挑战赛-自适应负载均衡（初赛）赛题

抽不出时间，中途放弃了。

云计算

云计算定义

提供海量、方便、按需分配的共享计算资源池。

和传统意义上的服务器之间的差别

  1. Internet-based.
  2. dynamic scalability.
  3. virtual resource-based information technology services, according to the demand, to share networking, storage, applications, services, modules and other resources.

负载均衡 + 云服务 = LBaaS(Load Balancer as a Service)

许多云服务厂商提供了负载均衡服务，它可以看作 SaaS 的一类，但仍然处于比较初步的阶段、有许多问题亟待解决，其主要需求和挑战包括：

  • 容错能力
  • 弹性扩容
  • 网络拓扑独立：因为算法的实现和服务器的网络拓扑结构是密切相关的。

负载均衡（LB）

LB 在系统资源之间调整工作负载（workload），从而提高系统性能和资源利用率。

负载均衡算法的应用

TODO

负载均衡考虑的协议

根据负载均衡所处的协议层次，可以分为：

  • 七层负载均衡：根据端口号和应用层协议如 HTTP 协议的主机名、URL，转发报文到上游服务器（不同的 IP 地址+端口），如 HaProxy、Nginx。
  • 四级负载均衡：根据端口将报文转发到上游服务器（不同的 IP 地址+端口），如 LVS NAT 模式、F5、HaProxy。

    现在 Nginx 也已经支持 TCP 四层负载均衡了，一般场景下可以作为 HaProxy 的替代品。

  • 二级负载均衡：通过改写报文的目标 MAC 地址为上游服务器 MAC 地址，源 IP 地址和目标 IP 地址是没有变的，负载均衡服务器和真实服务器共享同一个 VIP，上游服务器直接响应报文到客户端，不经过 LVS，从而可以提升性能，如 LVS DR 工作模式。

    LVS 和上游服务器必须在同一个子网，为了解决跨子网问题而又不影响负载性能，可以选择在 LVS 后边挂 HaProxy，通过四到七层负载均衡器 HaProxy 集群来解决跨网和性能问题。

除了这些之外，还有 DNS 也可以实现简单的负载均衡，但是它有缓存且无失败重试机制。
一些大型网站架构所需的负载均衡一般如下图所示：

下层的其实担当了上层的负载均衡，这是为了解决上层的单点，但是这样的话一定会有一层成为单点，解决方法主要有以下两点：

  • 另准备一个高可用的 monitor 系统去心跳检测 LB 的健康，宕机时自动控制重启，并通知运维。
  • 去中心化，去掉了 LB 的单点特性，但对技术能力要求较高。

负载均衡器所处的平台类型

  1. Hardware-based
    负载均衡的目标是物理资源。
    TODO：
  2. Software-based

负载均衡系统的关注点

  • 服务器规模：显然如果上游服务器只有一个的情况下负载均衡是没有意义的。
  • 负载均衡算法：决定请求被转发到哪台上游服务器上。
  • 失败重试机制：上游服务器出现故障（Fault）时，是否需要重试。

    超时、Bug、崩溃等都可以归类到 Fault 内，但是 Fault 并不意味着失效（Failure）——即不再提供服务，当然是在一定的容错（Fault-Tolarance）保证机制下。

  • 服务器心跳检查：通过定时的 ping 来发现失效的上游服务器，并将它们剔除出可用服务器的列表。

Static load balancing

static policy 是为系统的平均状态而设计的，它忽略了系统真实运行时的状态。

TODO：

Dynamic(adaptive) load balancing

Dynamic policy 会根据服务器的真实运行状况来调整其决定。

TODO：

架构

目标：高吞吐量、低响应时间、高资源利用率
负载均衡算法可以被分为 5 大组件：

  • Transfer Policy：将任务从一个节点转移到另一个节点；
  • Selection Policy：选择负载转移的方式（选择哪个节点来处理任务）；
  • Location Policy：决定提供服务所必须使用的资源数量，及资源所处位置；
  • Information Policy：获取工作负载相关的系统属性（工作负载属性、平均系统负载）；
  • Load Estimation Policy：决定一个节点的总工作负载。

负载均衡算法生效的大致流程如下：

  1. 从客户端接收请求；
  2. 根据请求计算所需的负载量，并构建请求队列；
  3. 使用一个 monitor daemon 阶段性检查服务器池的负载状况；
  4. 利用一个负载策略（算法）选择一个合适的服务器；

实现

负载统计

下面按我的尝试顺序列出：

一般我都是有点想法就实现一下，所以导致很多方案其实并没有太多可推敲余地。

1. 利用系统调用统计负载

provider 直接查询 /proc/stat 文件的方式计算，但是这种方式没有考虑多个 provider 共用一个 OS 的情况（provider 在容器内），而且没有可移植性。

2. 吞吐量

2.1 一般的容量规划方法都是基于压测算出的，没法动态化，我感觉运行时比较 consumer 单位时间发出去请求数和 provider 单位时间实际处理的请求数比较一下、然后动态修改发给每个 provider 请求的概率，可以试一下。
2.2 但是这种方法有个难点是如何计算吞吐量，一次请求大致需要经过下面的链路：
一次请求的流程
其中 request 和 response 属于 dubbo 框架的职责，而 hash 则是一个示例计算服务，它本身没有多少计算量，所以我们实际上均衡的目标是 request 和 response 这两个部分的负载，而这两个部分几乎又是对称的，所以可以直接用”单位时间内请求到达量”来表示“单位时间内吞吐量”。
2.3 观察实现结果，发现 provider 反馈的速率过慢导致 consumer 根本来不及修改负载均衡配置（框架代码每隔一段时间会修改 provider 线程池大小，产生动态变化的效果）。

3. 回压（未实现）

有点类似消息队列的实现方式，在 consumer 端使用一个队列来解耦请求处理和请求的发送过程。

参考

基础

  1. Java 8
    Lambda 表达式和 Java 集合框架
    Java8 新特性学习-Stream 的 Reduce 及 Collect 方法详解
  2. JMX
    关注这两个包下的 MXBean：javax.management、java.lang.management。
    其实自己看代码调接口就可以，不用看太多教程了，jdk 中也已经有很多注释。
    Java Management Extensions (JMX) Technology
    什么是 JMX？
    JMX 是 Java 官方提供的监控框架，不过是偏 JVM 层，而我们这次的方案主要是框架层的（出题人在 Dubbo 框架之上加了限流，用于模拟）。
    Java cpu 监控 分析
    how to control system load of a particular process? eg. Java
    Java 为了控制系统负载可能会用到一些系统调用。
    How do I monitor the computer’s CPU, memory, and disk usage in Java?
    使用 JMX 是更简单的、可移植性更高的做法。

负载均衡

  1. 负载均衡
    How does a load balancer distribute client traffic across servers?
    Load Balancing Algorithms and Techniques
  2. 云环境下的负载均衡
    Load balancing in cloud computing: A big picture
    An adaptive load balancing strategy in cloud computing based on Map reduce
    An Efficient Adaptive Load Balancing Algorithm for Cloud Computing Under Bursty Workloads
    DC（DataCenter）：包含多个虚拟机
    LB（LoadBalancing）：包含两种负载均衡策略，负载较低时使用 Random，负载较高时用 RR（RoundRobin）
    Fuzzifier：相当于一个负载收集器，从 DC 上收集负载情况，更新到 LB；需要收集的负载属性包括 CPU 速度、内存占用情况、磁盘占用情况、网络带宽等；用 jFuzzyLogic 写模糊判断逻辑（感觉比较鸡肋），比如负载超过 80%就切到 RR；
    The Adaptive Load Balancing Algorithm in Cloud Computing
    Adaptive Load Balancing Algorithm Based on Prediction Model in Cloud Computing
    Adaptive Resource Allocation for Load Balancing in Cloud
  3. 去中心化负载均衡
    A Decentralized System for Load Balancing of Containerized Microservices in the Cloud