确定性光圈：分布式负载均衡算法

在此博客文章中，我们将介绍我们已在Twitter上广泛开发和部署的新客户端负载平衡技术，该技术使我们的微服务架构可以将集群有效地扩展到数千个实例。我们称这种新技术为确定性孔径，可在Twitter的协议无关远程过程调用（RPC）框架Finagle中使用。

我们的微服务架构包括许多不同的服务，这些服务具有不同的容量要求。随着Twitter应用程序部分的增长，我们可以通过向相应的服务群集添加更多实例或副本来扩展容量需求（即水平扩展）。为了正确利用服务群集的所有副本，Finagle在每个Finagle客户端中都嵌入了一个客户端负载均衡器。这使我们可以使用更少的物理基础架构层进行操作。在现代服务系统中，这些负载均衡器通常被称为应用程序负载均衡器，它们具有两个主要功能：

它们允许后端服务的调用者通过在后端副本之间划分工作来安全地利用聚合容量。

由于对各个服务的所有请求现在都流经负载平衡器，因此可以很好地在副本不可避免发生故障时绕着副本进行路由。

那么，这些负载平衡器到底能平衡什么呢？它们在会话（OSI L5）和请求（OSI L7）上保持平衡。由于请求通常是资源利用的更准确代理，因此我们主要根据结果请求分配来衡量负载均衡器实施的有效性。但是，由于会话是请求的媒介，因此会话分配是重要的考虑因素。让我们深入探讨两者。

为了平衡请求，我们使用一种称为“两种选择的力量（P2C）”的分发策略。这是一个两步过程：

对于平衡器需要路由的每个请求，它会随机选择两个唯一的实例。

如果您希望在代码中看到算法，则可以在此处找到Finagle的Scala实现。该策略基于Michael Mitzenmacher论文背后的思想，即两种选择在随机负载均衡中的作用。 Mitzenmacher的工作的主要结果是，比较两个随机选择的实例上的负载会收敛于指数分布优于随机分布的负载分布，同时减少了负载平衡器所需的状态量（例如，有争议的数据结构）管理。

而且，由于P2C算法使我们可以将选择和评估过程分为不同的阶段，因此我们可以对负载进行复杂的定义。但是，对于常见用例，在本地负载均衡器中选择最少数量的未完成请求既简单又有效。实际上，只要会话平均分配，我们对P2C的实施就会导致统一的请求分配。

那么我们如何平衡会议？最简单的方法是使用网状拓扑。

服务A是服务B的客户端，并且A的每个实例都有一个嵌入式负载平衡器。依次地，每个负载平衡器打开与服务B的所有副本的会话，从而实现均匀的会话分配。

但是，当我们将服务扩展到数千个实例时，全网格拓扑会带来各种负面影响。对于初学者来说，会话​​的固有成本，例如分配套接字，缓冲区等。最重要的是，我们需要确保平衡器不会通过使用陈旧或不健康的会话来损害成功率。为此，我们必须在每个会话中实施相对昂贵的运行状况检查和断路器，但由于每个连接收集的数据很少，因此这些检查和断路器可能无效。更糟糕的是，因为负载均衡器是分布式的，所以每个均衡器必须独立地发现相同的故障-没有隔离。

考虑到这些问题，我们着手减少负载均衡器管理的会话数，而无需大幅度更改我们的体系结构或在负载均衡器之间引入昂贵的协调。

我们在此空间中寻求解决方案的首次尝试是所谓的随机孔径。这基于一个非常明显的想法：不要从所有后端中进行选择，而是选择一个随机子集。好主意，但这提出了一个新问题：我们应该选择多少个实例？事实证明，这不是一个简单的答案，并且会根据相应客户端的请求并发性而有所不同。因此，我们在随机孔径内安装了一个反馈控制器，该控制器根据客户提供的负载确定子集的大小。

让我们看一下假设的随机光圈拓扑在光圈大小为3时的外观：

我们已经可以看到一些有趣的事情。首先，我们实现了减少会话总数的目标，同时在负载均衡器中仍保持3的冗余度。这将减少与会话数量快速增长相关的开销，并使我们继续水平扩展两个集群。但是，我们在后端产生了不平衡：实例1有三个会话，实例5没有会话！直方图形式可以更好地说明这一点：

我们可以看到负载大致呈二项式分布：大多数后端实例将具有1或2个连接，但有些实例的连接数可能更少，甚至更差。这绝对不是理想的选择，但这只是一个小小的假设示例-在实践中这是一个真正的问题吗？此数据显示了当我们部署配置为从P2C更改为随机孔径的生产集群时，对每个后端每秒请求（RPS）的影响：

在部署之前，我们会看到一个很好的痕迹集合，它们整齐地堆叠在一起。部署后：pandemonium！虽然我们成功地将总连接数大大减少了99％以上，但我们的请求分配却一团糟。有趣的是，我们可以看到一些不同的负载带的形成：一些负载几乎没有请求，而另一些负载则接近400 rps！这是实际的二项式分布！

生成有趣的图表很有趣，但是这种情况对于服务所有者来说显然是不可接受的。这种分散的请求分发使服务所有者几乎不可能进行容量规划。这是死路一条，还是我们可以解决？幸运的是，我们有数学工具可以用来推断统计数据。我们采取的一种方法是建议服务所有者通过将系统建模为二项分布来计算其连接数。也就是说，服务所有者必须插入客户端和服务器计数以及候选连接计数，直到模型收敛到可接受的方差。

该过程有点疯狂，因为它需要为服务所有者进行大量的前期工作，但它确实有效。通过上述策略优化了随机光圈参数后，该仪表板就是同一面板：

好多了，但还不完美。我们看到不连续的步骤已经消失了，但是我们仍然拥有比使用随机光圈之前更大的请求速率分布。但是，这是一个可以接受的价差，而减少它的唯一方法是增加连接数，这正是我们试图避免的情况。换句话说，我们在此集群中的此服务的connections-vs-load方差曲线中找到了最佳位置。问题在于，该值不适用于请求速率和大小不同的其他集群，并且如果要调整其集群大小或后端，甚至不一定保持最新状态。这现在可以正常工作，并会引起一些麻烦，但这并不是我们可以在Twitter的所有服务上启用的功能。

随机光圈是“前进两步，后退一步”的成就。我们可以继续扩展集群，但现在除了浪费掉属于请求分发较低端的实例的容量之外，还迫使服务所有者进行复杂的配置。我们如何对此进行改进？收益来自子集，问题来自于随机执行。接下来，我们开始确定性地使子集公平。

为了确定子集，我们需要一种新的方式来考虑或建模拓扑。这种新的表示形式需要具有一些核心属性：

轻度的协调-表示形式不需要任何重量级的分布式共识，客户即可选择后端子集。

最小的中断-更改客户端或后端的数量不应引起重大的改组，以免造成不适当的连接中断。

在此表示中，我们将客户端和后端以相等的间隔放置在环上，分别称为对等环和目标环。这类似于一致性哈希，不同之处在于我们可以保证为相应的服务在整个环域中实现节点的完美分配，因为我们提前知道了每个环的成员身份-仅仅是客户机或服务器的集合！

通过构建对等和目标环，我们现在可以组合或覆盖它们，以得出各个服务之间的关系。客户将按照顺时针旋转戒指的顺序选择后端：

在此模型中，我们不再具有具有零个或三个会话的实例！但是，我们并不完美：我们仍然有两个后端和两个会话。不幸的是，就像随机光圈一样，如果我们有多个服务在与服务B对话，我们可以预期此问题会变得更加复杂：

立刻，您可以看到视觉环表示上拥挤。当我们计算分配给服务B的每个实例的会话数时，我们看到实例1只有两个会话，而实例5多达四个！我们再次重新引入了随机光圈的条带效应，尽管规模明显减小。

环形模型是对随机光圈的显着改进，但是我们可以做得更好吗？在三个客户端和七个后端的情况下，如果我们尝试通过再次操纵会话数来缓解此问题，我们看到达到此目的的唯一方法是将每个客户端的会话数提高到七个，从而有效地恢复到完整状态。网格拓扑。我们可以尝试在客户数量和后端数量之间建立某种关系，但是很明显，该解决方案不够灵活，无法很好地扩展。

我们再一次调整了表示方式，将客户和后端表示为环的连续切片，而不是环上的离散点。我们将它们之间的关系定义为它们各自切片的重叠，更重要的是，该重叠可以是分数。我们称其为连续坐标模型。在此模型中，我们可以看到后端实例2在服务A的实例0和实例1之间不对称地共享。这转化为一个额外的会话，但是如果权衡这些会话以尊重环表示，我们可以得到均匀的请求负载到所有服务B。

使用连续环坐标模型，我们可以将客户端均匀地映射到后端子集。平衡请求时，我们如何尊重代表？一种方法是利用P2C中的随机选择过程！每个平衡器在其范围内选取两个坐标，并将它们映射到目标环上的离散实例。因为我们在负载均衡器的范围内随机且均匀地进行选择，所以我们固有地尊重分数边界。换句话说，我们只需要确保“选择两个”过程遵守对等点和目标环之间的范围交集，其余部分就位。

通过突出显示服务A的实例1的选择过程，让我们看一下它的工作方式示例：

它的范围与服务B的实例4和2的所有实例3和2 / 3rds重叠。这意味着我们希望实例4和2接收与实例3一样大的2 / 3rds负载。在P2C上下文中接收较少的负载意味着不必经常选择它。因此，我们的选择过程如下：

对于每个请求，在[offset，offset + width）内选取两个点，并将这些点映射到目标环上的离散实例。

在这两个离散实例中，选择一个在环模型中具有最小负载权重的负载（按其相交度加权）。

步骤2包括一个细微但重要的修改。由于某些实例的相交切片较小，因此它们的拾取频率将比其他实例低，因此其负载将比具有较大相交切片的实例低。为了避免在比较负载时偏向较小的相交切片，我们需要将其与交集的大小成反比地标准化。

在此处可以找到Finagle中P2C的修改版本。除了计算环之间的交点的数学运算外，此代码还严格遵循原始的P2C算法。

我们没有在此模型中明确提及光圈大小，但是如果您已经注意到它自然不属于该表示形式。至少为1 / N，其中N是对等环中的实例数。但是不必将其固定为最小值。只要我们围绕目标环进行整个旋转，就可以增大或缩小它。例如，仍然可以根据请求负载动态调整其大小（只要对等环的所有成员都同意相同的大小，这将需要更积极的协调形式）。在Twitter上，默认情况下，根据经验，我们发现大小至少为10可以在弹性和连接数之间取得良好的平衡。

确定性孔径是Twitter上实现负载平衡的一项重大飞跃。在过去的几年中，我们已经能够在大多数Twitter服务上成功运行它，并取得了不错的成绩。以下是服务拓扑已从配置良好的随机孔径升级到确定性孔径的典型案例的一些要点：

我们看到请求分配有了显着改善，负载的相对标准偏差降低了78％：

同时大大减少了连接数。在升级过程中，相同的服务拓扑连接数下降了91％（从〜280K降至〜25K）：

请记住，这种随机光圈配置已经使会话数最小化，并且我们仍然能够减少91％的连接。使用P2C的大多数服务（这是大多数情况！）看到了更好的结果。

确定性孔径的灵活性和性能已经获得成功，并且具有足够的通用性，足以巩固其在Twitter上作为默认负载均衡器算法的地位。大多数服务已迁移到新的负载均衡器，只有少数例外。随之而来的是一些小的操作更改和需要考虑的限制。

将独立实例或少量实例集设置为金丝雀时，连接数量通常会比生产规模的集群高很多。这是因为需要完全覆盖目标环：只有很少的对等点可以分担负载，您可以期望有更多的连接。在1个对等节点的极限情况下，我们看到P2C行为，对于2个对等节点，我们大约得到P2C的连接的一半，依此类推。

即使协调要求宽松，我们仍然要求命名更新相对较快地传播到同位体，否则我们将失去均匀的分布。在实践中，当命名更新的一致性时间达到10秒左右时，我们看到了积极的结果。

像所有子集算法一样，确定性孔径模型基于单个客户端平均产生的负载。这意味着使用此算法的每个服务层都将接收均匀的负载。在此约束之外，不均匀性将传播到目标群集，从而再次导致不平衡。最简单的解决方案是使用RPC堆栈顶部具有全网状拓扑结构的完美平衡器，确保负载在进入系统时被均匀分散（即消除热点）。

突发流量也可能是确定孔径的问题。发生这种情况的常见情况是，对于每隔一定时间刷新本地缓存的服务。缓存刷新后，客户端可能会立即看到负载的急剧增加，这可能对其客户端的光圈成员不利，而目标环的其余部分可能处于空闲状态。在这种情况下，全网状拓扑通常是更好的选择，因此在缓存刷新后，所有后端都可以吸收脉冲负载。

如果您到目前为止已经做到了，那么还有最后一个好消息：使用几段元数据，您可以在基于Finagle的服务中使用确定性孔径。

Twitter上的许多人为负载平衡的发展做出了贡献。 我们会不遗余力而无法接受：Billy Becker，Marius Eriksen，Daniel Furse，Steve Gury，Eugene Ma，Nick Matheson，Moses Nakamura，Kevin Oliver，Brian Rutkin和Daniel Schobel的贡献！ 我们还要感谢Rebecca Isaacs，Steve Hetland，Ryan O＆Neill和Elif Dede对本博客文章的反馈和贡献！