Share

负载均衡算法的重新理解
最近在Netflex 博客上看到了他们的一篇关于负载均衡的技术文档（原文），觉得很有收获，自己做个总结并分享。

背景

  1. Netflex 的服务器集群请求量非常巨大， 达到 1M QPS。 目前Netflex 是使用 Zuul 作为他们的服务网关，Zuul实现了负载均衡算法，解决了业务后端的流量分配问题。<br />但由于请求量大， 业务后端集群的服务器数量非常多，所以当集群出现故障或异常的时候，请求的错误数量就会快速增高，影响服务质量。
  3. 在继续进行这个话题之前，我先补充一些个人的看法: 很多后端工程师在实际的场景中，其实不太关心LB 的弹性设计(包括我自己)， 因为弹性设计是非常困难的事情（后面会解释）。 在日常情况下， 如果某台业务服务器出现故障，工程师通常都会人工摘掉故障的服务器，半夜的时候，还需要爬起来处理。 在某些自动化程度高一些的公司，可能会配置一些故障熔断策略来降低请求的错误率，但通常这种熔断策略都是根据简单的维度进行判断，所以还是需要人工根据网络和服务器的状态做调整处理。  <br />    在集群规模不大的时候，这种处理方法是比较有效的，毕竟机器数量不多，机器，网络出现故障的几率不算太高， 而且人工介入，大家的内心还是比较踏实。<br />    但在Netflex， 情况就完全不一样了。 首先： Nexflex 的机器集群数量很大，达到以万为级别，因此故障的几率大大提高，几乎每隔十几个小时就会出现故障。 另外： 他们的集群是部署在aws 上， 云上的机器经常会出现“漂移"和无计划重新启动，如果缺乏"完善"的故障自动转移机制， 那么他们工程师的工作压力将会非常大。

负载均衡服务的核心功能与设计难点

  1. 要有效地降低错误数量，我们需要先了解下负载均衡服务需要解决什么问题。<br />    负载均衡服务（LB）主要解决了两大问题： 1. 流量分配，保证集群的吞吐量与利用率。 2. 保持弹性, 当集群出现故障，可以自动转移流量，确保服务可用性。<br />    因此，当LB进行流量分配的时候，**它需要知道集群的健康和吞吐量情况**，才能进行做出最优的分配策略。这也就是LB 设计的难点，LB 要如何了解集群的状态呢？

解决方案

”主动” 和 ”被动” 机制：

要获取集群的状态， 要么“主动”去拉去，但这种做法需要消耗的资源比较高，尤其是网络带宽消耗， 而且更重要得是，需要解决“状态”一致性的问题， 因为，LB本身也是一套集群，集群的状态同步需要引入额外的同步机制才能实现，文中的作者也不建议这种机制，因为他们采取了“被动”机制。
“被动”机制就是在LB 分发的请求中带上特定的”header”, 让上游的业务服务器返回自身健康情况。

“choice-two” 算法：

  1. 当LB 获取到集群的状态后，最直观的做法是直接将请求路由到状态”健康“，并且”延时“最低的服务。但其实这种做法还不够周全，因为服务器的状态都是瞬息万变的，LB 获取到的集群永远是”过时“ 的信息，所以直接将请求路由很容易将请求路由到负载很高机器上。 引用文章的说法，这个时候机器有可能陷入  "空闲" --> "繁忙” --> "空闲"的重复轮转状态。<br />   在这里，你可能会觉得这是小概率事件，但实际上这是完全有可能出现的，尤其在集群规模庞大的时候，需要充分考虑每一个细节。<br />   为了解决这个问题，作者采取了 "choice-two" 算法，原因是这种方法简单，可靠。这个算法的原理也很简单，它不是直接取延时最低的服务节点，而是使用两次随机算法，获取到两个节点，然后再比较和两个节点的延时，再进行路由。 这种做法在概率上避免”重复轮转“ 的问题，具体的证明推论，可以参考 [论文](http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf)
  1. node1 = servers.randomChoice()
  2. node2 = servers.randomChoice()
  4. nodex = node1.latency < node2.latency? node1: node2
  5. route_traffic(nodex)

Review:

基于之前看的Medium 文章， 扩展阅读了 “choice-two” 算法。反思了之前自己做HSF RTSLB插件的时候没有考虑到惊群问题。
原文

Tips:

  1. 为了方便在Mac 的iterms 上显示Git 的分支， 我安装了oh-my-zsh.  可以提升shell 使用体验

https://github.com/zsh-users/zsh-autosuggestions/blob/master/INSTALL.md#oh-my-zsh

Algorithm:

[56]MergeInterval
第一步，先使用interval 的第一个元素排序，第二步，使用merge 数组，不断归并interval 

  1. from typing import List
  4. class Solution:
  5.     def merge(self, intervals: List[List[int]]) -> List[List[int]]:
  6.         intervals.sort(key=lambda x: x[0])
  7.         merged = []
  8.         for interval in intervals:
  9.             if not merged or merged[-1][1] < interval[0]:
  10.                 merged.append(interval)
  11.             else:
  12.                 merged[-1][1] = max(merged[-1][1], interval[1])
  13.         return merged
  17. intervals = [[1,3],[2,6],[8,10],[15,18]]