题目分析

题目由来 传统的负载均衡场景为单调度器模式，即中心化负载均衡：调度器负责将新到的请求立即转发至多个后端服务器中的一个。随着分布式系统的发展，这种单调度器模式在扩展性、可靠性和性能方面的问题愈发严重。因此，设计和实现去中心化且性能优异的负载均衡是学术和工业界的共同需求。

由此可见，本题的目标是找到一种去中心化且性能优异的负载均衡算法。其中性能优异是本次比赛的评分标准，那么去中心化同样也应是评分的隐藏标准之一，因此我们的答案应该是一种去中心化的负载均衡算法。

整个系统由一个adaptive-loadbalance与3个service所组成，每个service的处理能力各不相同，主要有以下方面的区别：

  • 不同service的硬件资源不一样
  • service处理请求的时间由config中的avg_rtt参数决定，呈负指数分布
  • service含有自己的max_concurrent，即最大并发线程数

其中avg_rtt与max_concurrent将随着时间的推移不断变化。

很自然的，如果我们收集到承载service的硬件资源（CPU与内存）、avg_rtt以及max_concurrent参数，以及函数：EQPS = f(cpu, memory, avg_rtt, max_concurrent)。我们就能计算出每个service在一定时间内处理请求的期望值，按照这个期望值来分配请求即可达到一个比较理想的结果。

方案实现拆解：

  1. load-balance需要能够对每个service做区分：最好的方式为load-balance层发现service注册后，自动为其分配一个ID，并将此ID传递给service，service缓存下来后每次发送请求时必须携带此ID。
  2. service需要能够获取到每个关键的参数值。
  3. service需要在这些参数值变化时及时通知load-balance（边缘触发）。

但是这样的方法没有可扩展性，现实的世界中我们无法得知avg_rtt,max_concurrent等参数，CPU与内存我们能够得知，但是由于实际运行环境的复杂性，其对于程序负载的参考价值也非常有限。因此，个人觉得比较适合的方式是以统计+预测的方式判断程序负载并及时作出反应较为可靠，这也符合大多数程序的实际运行逻辑。

由于每个请求的”处理时间”满足负指数分布，因此在一定时间内请求处理的期望值是固定的。再加上其他各种条件的限制，每个service处理请求的能力应在其期望附近摇摆。

最理想的运算模型为：所有请求将按照当前时刻的承载能力按比例分配给每一个service。

因此，我将设置一小段时间为时间窗口，通过对时间窗口所有请求的统计来预测下一个时间窗口service的载荷。