子集算法有助于优化服务间连接利用率，降低资源使用。但随机或轮询子集算法在动态拓扑环境中会造成较高的连接扰动。本文介绍了谷歌在解决连接扰动方面所做的思考和实践，并介绍了当前最新的 Rocksteadier 子集算法。原文: Reinventing Backend Subsetting at Google
近年来，由于有利于提高资源利用率，Autopilot系统在谷歌内部越来越受欢迎。Autopilot 可以做很多事情：可以配置为执行水平扩展，调整服务正在运行的任务数量以满足需求；可以配置为执行垂直扩展，调整每个任务分配的 CPU/内存资源。Autopilot 在防止停机方面也很有效，相对人工运维来说，可以实现服务规模的更快扩容来响应不断增长的需求。
随着 Autopilot 的广泛使用，服务所有者发现了一个有趣的问题: 每当横向扩容的服务调整大小时，许多客户端连接(通常是长连接)都会短暂断开并重新连接，这种连接扰动会导致如下后果:
- 增加了当前请求的错误或延迟
- 增加了连接握手消耗的 CPU/内存使用率
- TCP慢启动建立新连接的过程降低了吞吐量
- 增加了连接缓存的压力
这些影响的严重程度因服务而异，但在某些情况下，错误或延迟的增加会使服务水平目标面临风险，并阻碍 Autopilot 的采用。最终研究发现，这种连接扰动问题是由后端子集引起的。
后端子集(Backend subsetting)是一种将服务连接在一起时减少连接数量的技术，对于降低成本非常有用，甚至可能是在系统限制条件下进行运维所必需的。十多年来，Google 使用确定性子集(deterministic subsetting)作为默认后端子集算法，尽管该算法平衡了每个后端任务的连接数量，但会造成较高水平的连接扰动(connection churn)。
我们的目标是设计一种减少连接扰动的算法，用以取代确定性子集作为默认后端子集算法。该目标雄心勃勃，如海鲁姆定律(Hyrum's Law)所说，"系统所有可观察到的行为都将依赖于某个人。"我们需要了解确定性子集的所有行为，避免犯同样的错误。
Borg 的后端子集
谷歌的服务运行在内部集群管理软件 Borg 上。服务所有者配置可以在多个 Borg 单元(cell) 中运行的作业(job) ，以实现地理分区。在计算单元中，作业由一个或多个任务组成，每个任务在数据中心的某些机器上运行，任务从 0 开始连续编号。
利用后端子集将作业连接在一起，如果由 M 个任务组成的前端作业连接到由 N 个任务组成的后端作业，则通常会有 M×N 个连接，当作业有数千个任务时，连接数可能会相当大。相反，如果每个前端任务都连接到 k 个后端任务，可以将连接数减少到 M×k。为 k 选择合适的值取决于使用者，但通常比 M 或 N 小得多。
要使用后端子集，必须服务必须是可重复的(replicated): 如果将相同请求发送给不同任务，它们应该执行相同的工作并返回相同的响应。
前端任务的负载均衡策略用于将请求定向到特定的后端任务，目标是在后端任务之间实现统一使用。每个后端任务分配相同资源，为了避免过载，需要为负载最多的后端任务预备资源。
以前的方法
后端子集算法选择的子集对生产有各种影响: 连接均衡、子集多样性、连接扰动和子集扩容。为了描述这些行为并解释新算法是如何开发的，我们从一个简单的算法开始，并对其进行迭代改进。
随机子集
最简单的可行算法之一是选择随机子集: 每个前端任务将后端任务列表(由任务编号 0 到 N-1 标识)打乱，并选择前 k 个任务。
不幸的是，这与许多负载均衡策略的交互效果很差。假设有一个 CPU 密集型服务，所有请求都消耗相同的成本，并且每个前端任务都用循环负载均衡来均匀的分发请求。因此，每个后端任务的负载将与其连接的数量直接相关。然而，随机子集的连接分布远非均匀，如图 1 所示。
轮循是一种简单的负载均衡策略，但并不是唯一受连接分布影响的策略。考虑到谷歌服务的多样性及其不同的负载均衡需求，要求与连接无关的负载均衡策略是不切实际的。因此，子集算法应努力平衡连接分布。
属性: 连接平衡(Connection Balance)
假设负载均衡策略受连接分布影响，目标是度量子集算法造成的负载不均衡的数量。为此，假设每个前端任务在其子集中的每个后端任务上生成等量负载，这并不一定完全符合实际情况，但对于当前目标已经足够了。
利用率是衡量负载均衡的一个有用指标: 用总使用率除以总容量得到正在使用的资源比例。可以应用于连接分布: 总使用量将是连接总数(M×k)，并且(因为我们为负载最多的后端任务预留资源)总容量将基于具有最多连接的后端任务(max(Cn)×N，其中 Cn 是到第 n 个后端任务的连接数)。从而获得以下指标:
然而，该度量并没有考虑到连接的离散性。如果 M×k 不能被 N 整除，理想的子集算法必须为每个后端任务分配 $\left\lfloor Mk\over N \right\rfloor或\left\lceil Mk\over N \right\rceil个连接，因此max(C_n) = \left\lceil M*k\over N \right\rceil$ 并且 Utilization < 1。在这种情况下，要实现 Utilization = 1，必须调整度量以给出可实现的利用率:
这个指标可以比较不同场景下子集算法的连接平衡性。注意，实现高利用率有两种简单的方法。首先，增加 k 自然会提高利用率，因为降低了子集对负载均衡的影响，将子集大小增加到 N 意味着完全禁用子集设置。其次，随着前端任务与后端任务比例的增加，每个后端任务的子集算法有更多选择，因此即使随机选择，连接平衡性也会自然改善。如图 2 所示，对于最多有 256 个任务的作业(k = 20, 1≤ M ≤ 256, k ≤ N ≤ 256, M × k > N)，图中绘制了利用率与前后端任务的比率，虽然不完全是现实场景，但足以证明算法的行为。
轮询子集
随机子集可以基于前端任务编号(0 到 M-1)引入协调来改进。轮询子集将后端任务连续分配给第一个前端任务子集，然后是第二个任务子集，依此类推，如表 1 所示。每个前端任务 m 可以通过后端任务号有效生成自己的子集。
很容易看出，这样做可以尽可能统一的平衡连接，一旦后端任务 n 被分配了一个连接，在所有其他后端任务都被分配连接之前，不会被分配另一个连接。虽然该算法具有良好的连接平衡性，但其其他性能并不理想。
属性: 子集多样性(Subset Diversity)
想象一下，如果表 1 中有更多前端任务会发生什么。前端任务 5 将被分配给后续的 4 个后端任务，即{0,1,2,3}，但这与前端任务 0 的子集相同。这 10 个后端任务的每个子集有 4 个任务，总共有 10 选 4=210 个可能子集，但该算法只能分配 5 个不同的子集。一般情况下，应该有 N/gcd(k,N) 个子集。
这有什么问题？想象一下，一个前端任务正在执行某个更改，该更改会在其子集中的后端任务中触发不良行为(例如，高延迟或崩溃)，而这将影响其他前端任务，这些任务应该能够在其他后端任务上重试请求。但是，如果其他前端任务所分配的子集和金丝雀前端任务完全相同，那它们将共享相同的命运，并且无法实现故障转移或者只能将故障转移到相同的后端任务，从而造成这些后端任务过载。
确定性子集(Deterministic subsetting)
可以通过引入随机性来增加子集多样性，但必须以保持连接平衡的方式进行。这就产生了这样一种解决方案: 打乱所有后端任务，将它们分配给前几个前端，然后重复这一步骤。
例如，对于表 1 中的场景，可以将后端任务排列为[9,1,3,0,8,6,5,7,2,4]，并将子集{9,1,3,0}和{8,6,5,7}分配给前两个前端任务。然而，这带来了一个问题，因为后端任务 2 和 4 没有分配。然后到下一个前端任务子集，洗牌后的后端任务列表可能是[7,2,0,8,9,1,4,5,3,6]，但不能将后端任务 2 分配给相同的前端任务。尝试跳过后端任务 2(使用后端任务 0)也有问题，因为这样就引入了一种依赖关系，在这种依赖关系中，前端任务需要计算之前每一组打乱的后端任务，而不仅只考虑分配了的后端任务。
该问题可以通过忽略多余的任务来解决，这样只会导致少量的连接不平衡。在这个例子中，前端任务 2 将使用子集{7,2,0,8}。
这是之前在《站点可靠性工程:谷歌如何运行生产系统》(第20章)中描述的算法，但可以通过平衡每个组中的剩余任务来进行改进，最简单的实现方法是(在洗牌之前)选择哪些任务在轮询过程中遗留下来。例如，第一组前端任务选择留下{0,1}，然后对剩下的任务进行洗牌，得到子集{8,3,9,2}和{4,6,5,7}，第二组前端任务选择留下{2,3}，然后对剩下的任务进行洗牌，得到子集{9,7,1,6}和{0,5,4,8}。这种额外的平衡确保所有后端任务都被均匀的留下，从而产生更好的分布。
该算法提供了良好的连接平衡性和子集多样性，并在生产中取得了十多年的良好效果。在 Autopilot 更频繁的调整横向大小之前，其唯一的主要问题在于特别小的子集大小。
属性: 连接扰动(Connection Churn)
考虑一下当后端任务从 10 个增加到 11 个时，前端任务的子集会发生什么变化，如图 3 所示，其中的变化用红色突出显示。
尽管集群大小变化不大，但子集发生了很多变化，前端任务 3 尤为不幸，其被分配了完全不同的子集。当后端大小发生变化时，每个前端任务将和不再属于其子集的后端断开连接，并连接到新添加的后端。重新建立连接需要多次网络交互，在此期间可能发生以下情况:
- 后端过载，因为前端任务只能通过更少的已连接的后端任务来平衡负载，并且连接分布不均衡。
- 如果没有既定后端任务可用于给定的前端任务，将发生更多错误和延迟。
这种连接扰动是由于改变后端大小引起的，因此称为后端扰动。子集算法也可能因为前端扰动(改变前端大小)和子集大小扰动(改变子集大小)而造成问题。
理想情况下，后端扰动数量应该与后端大小的变化成正比。例如，如果后端大小翻倍，则每个前端任务的子集更改一半是合理的。这种后端变动应该均匀分布在各个子集中: 每个前端子集中的一半后端发生变化是可接受的，但如果有一半前端子集中的所有后端都发生了变化，那就不行了。
到目前为止，所有算法都没有考虑前端扰动，这在子集算法中尤其不可取。假设某个前端作业过载，并且添加了额外任务来增加容量。前端扰动将导致现有前端任务重新连接到后端任务，在添加的任务能够开始服务之前容量将显著减小。
如果子集大小是动态调整的，比如基于前端大小、后端大小和/或流量级别，那么子集大小的变动就很重要。很容易看出，随机子集具有最小的扰动: 只有洗牌后列表的一部分被用作子集。另一方面，轮循和确定性子集都依赖于子集大小，从而导致较高的子集大小扰动。
属性: 子集分布(Subset Spread)
另一个需要考虑的有趣问题是如何将新版本软件部署到 Borg 作业中。作业通常通过从任务 0 开始进行滚动重启来完成更新，并限制正在运行的任务重启次数。除了重启缓慢的异常任务外，这意味着在更新期间，某个连续编号的任务组将不可用。
考虑对轮询子集的影响: 在表 1 中，第一个前端任务的子集{0,1,2,3}也是该过程将重新启动的前四个任务，如果正在运行的任务数量与子集大小相似，则大多数前端任务的子集在更新期间的某个时刻将完全不可用。随机子集和确定性子集的性能更好，因为任何单个子集都不太可能具有相对接近的任务数，但是如果有足够数量的前端任务，则很可能会遇到这一问题。
我们在实践中观察到这一问题，可以通过减少运行中的任务数量(减慢更新速度)或增加子集大小(增加成本)来缓解这种情况。理想情况下，子集算法将在每个子集中分散后端任务数，以便更新对前端任务具有一致且最小的影响。子集多样性和子集扩展之间存在矛盾: 前者需要许多不同的子集，但后者需要限制可接受的子集。
寻找新算法
这些是后端子集算法的期望属性:
- 良好的连接平衡性
- 较高的子集多样性
- 没有前端扰动
- 较低的后端扰动
- 较低的子集大小扰动
- 良好的子集分布
除了前端扰动，其他都不需要最优性能，只需要满足避免不良行为即可。
一致性子集(Consistent subsetting)
出发点基于一致性哈希: 每个前端和后端在单位环上随机分配一个位置，每个前端通过选择沿圆周顺时针移动找到的前 k 个后端来确定其子集。图 4a 显示了前端任务(蓝色方块)和后端任务(黄色圆圈)随机位置的一致性子集。前端任务 0 顺时针移动并选择看到的前两个后端，获得子集{3,2}。
当任务被添加到环或从环中移除时，其他任务位置不受影响，从而极大减少了连接扰动。当添加后端任务时，每个前端任务的子集最多只有一个更改。
不幸的是，该算法在连接平衡性或子集多样性方面做得不太好。由于前端任务在选择其子集时没有协调，因此连接平衡性并不比随机子集更好。因为前端任务选择的第一个后端任务决定了子集的其余部分，所以最多可能有 N 个不同的子集，从而影响到了子集多样性。
稳定环子集(Ringsteady subsetting)
如何改善一致性子集的连接平衡性？后端任务的连接数与后端任务在环上的"空闲空间"成正比，因此连接平衡性取决于后端任务在环周围的均匀间隔程度。有了这种认识，就可以通过有利于均匀分布的位置序列来改进随机选择的位置，即构造低差异序列。
仅仅因为后端任务是连续编号的，所以低差异序列中的第 n 个元素可以与第 n 个后端任务相关联。
我们在谷歌选择的序列是二进制的van der Corput序列(将 0 作为第 0 个元素)，它表示为 0，1/2，1/4，3/4，1/8，5/8，3/8，7/8。这些分数决定了每个节点在圆上的位置，如图 4b 所示，第一个任务被放置在圆的顶部，第二个任务被放置在圆的中间，以此类推。
选择这个序列的原因之一是它在计算元素位置时很方便。例如，要获得第 5 个元素的位置(字长为 8 位)，只需要将 5 的二进制 00000101 反转为 10100000(十进制为 160)，然后将其作为位置的定点数，得到 160/28=5/8。
到目前为止，本文只讨论了后端任务，但是前端任务的需求是一样的。如果后端任务比前端任务多得多，那么前端任务应该均匀分布，以便选择的子集尽可能均匀，避免重叠。对前端和后端任务使用相同的顺序会获得另一个方便的属性: 当 M = N 时，每个前端任务都有不同的子集(从相同编号的后端任务开始)，并实现理想的连接平衡性。图 4b 显示了实际的算法，我们称之为稳定环子集(Ringsteady Subsetting)。
与随机和确定性子集(子集的分布取决于运气)不同，稳定环子集保证了良好的子集分布性，连续编号的后端任务在圆上彼此相距很远，因此圆周围连续任务的子集将具有均匀分布的任务编号。
图 2c 显示，算法在某些情况下的利用率低于确定性子集(见图 2b)，但明显优于随机子集(见图 2a)。
前端和后端扩容
不幸的是，稳定环子集的连接平衡性有缺陷，如图 2c 右侧所示，前端任务数量超过后端任务，但利用率并没有向理想状态收敛，这与图 2b 中的确定性子集不同。低差异序列导致前端和后端任务的位置接近但并不完全均匀间隔。不过这种不平衡性只存在于有多余任务的场景中。
那为什么不让它们完全均匀间隔呢？这就需要稍微做一点移动了(比较图 4b 和图 4c)，而这会引入少量连接扰动，但应该能改善连接平衡性。当应用于前端任务时，我们称之为前端扩容，当应用于后端任务时，我们称之为后端扩容。
对于前后端扩容，算法将始终实现理想的连接平衡性。不幸的是，前端扩容使得前端任务的位置依赖于前端大小，这就引入了前端扰动，使得它不适合这个用例。
图 2d 显示了结果。与图 2c 相比，当 M > N 时，后端扩容达到了改善连接平衡性的目标，而当 M < N 时，仅出现了较小的退化。虽然在某些情况下，仍然比确定性子集(见图 2b)的利用率低，但足够了。
Rocksteadier 子集
支持后端扩容的稳定环子集几乎拥有我们想要的所有属性。它继承自一致性子集，所以在子集多样性上有缺陷，可能只有 N 个不同的子集。我们研究了Rendezvous Hashing作为增加子集多样性的替代方案，但除了随机性并不能改善连接平衡性。相反，我们设计了一种结合稳定环的算法来增加子集多样性，而且不会显著降低任何其他属性。
之前我们通过打乱后端任务来实现子集多样性，但这使得顺序依赖于后端大小，因此导致后端扰动。相反，通常前端大小 M 明显小于可能的子集数量。因此，并非每个后端都必须进行洗牌(即，产生所有可能的排列)以实现足够的子集多样性。
解决问题的方法是形成 L 个后端任务组(称为 lot)，并对任务进行洗牌。参数 L 必须是常量，如果其依赖于前端大小、后端大小或子集大小就会导致连接扰动。最后一个后端 lot 必须由 L 个任务组成，所以如果后端大小不是 L 的倍数，则添加填充任务(不是真正的后端任务，在选择子集时将被跳过)。此外还要构造 L 个前端任务组。在每个前端批次中，尝试将后端任务均匀分布在前端任务上，类似于轮循或确定性子集。
表 2 显示了这个过程的第一步: 基于 L = 10 将前端和后端任务分组。为了便于说明，这里显示了第二个前端 lot(任务 10-19)。由于后端大小不是 L 的倍数，填充任务 55-59(用灰色文本表示)被添加到最后一个后端 lot。
表 3 显示了这个过程的第二步: 对每个后端批进行洗牌。该表显示了从左到右对每个后端 lot 进行洗牌后，前端任务 13(红色)和 19(蓝色)的潜在子集分配。
这个过程的要求是:
- 前端 lot 中的每个前端任务需要对后端任务使用相同的洗牌顺序。
- 后端 lot 应该在不同的前端 lot 中进行不同的洗牌。
- 添加新的后端 lot 不能影响先前洗牌后端 lot 的顺序。
这些需求可以通过使用前端 lot 号(对于前端任务 m，是 ⌊Lm⌋)作为 PRNG(伪随机数生成器，pseudorandom number generator)的种子，然后使用该 PRNG 按顺序对每个后端批号进行洗牌来实现。
我们仍然需要想出一种将子集分配给前端任务的方法。可以从考虑一些简单但不太好用的方法开始。第 i 个前端任务可以遍历第 i 行，并从每个 lot 中获取后端任务。如果到达该行的最后一个后端 lot，绕行读取表中的下一行。例如，在表 3 中，前端任务 13 将选择以{4,14,21,39,46,52,7,18，…}开头的子集。此外还要跳过填充后端任务，并从最后一个后端 lot 绕到第一个 lot，因此前端任务 19 将选择以{6,10,20,30,44,8,13,22，…}开头的子集。
这种分配子集的方法在两个方面造成了连接不平衡: 它无法在后端 lot(即跨列)之间实现平衡，并且无法在后端 lot(即多行)内保持平衡。
为了在后端 lot 之间进行平衡，请考虑表 3 中描述的场景，其中子集大小较小，例如 k = 3。前端任务 10-19 的子集将只从前三列中选择后端任务，后端任务 0-29 每个都有一个连接。请注意，对于每个前端 lot 都是如此，虽然每个后端 lot 中的顺序因前端 lot 而异，但第一个后端 lot 始终包含任务 0-9，第二个 10-19，以此类推。
不同的前端 lot 需要以均匀分布的方式访问不同的后端 lot，并且不会引入扰动。这部分问题可以通过将 Rocksteadier 算法中的前端/后端 lot 映射到 Ringsteady 中的前端/后端任务来解决。例如，在图 4c 中，前端任务 1 看到后端任务的顺序为[1,5,3,0,4,2]，在表 4 中，列被重新排序，以便前端 lot 1 中的任务以相同顺序从选择后端任务。Rocksteadier 前端任务 1 使用与 Ringsteady 前端任务 1 相对应的顺序。
剩余的(相对较小的)平衡问题发生在最后一个前端 lot 不完整的时候。例如，考虑表 4，如果只有前端任务 10、11 和 12，那就存在一个相对较大的子集大小。因为子集都从连续行开始，之间会有一些重叠，从而导致某些后端任务(例如，第三行上的任务，5,45,26，…有多个连接，甚至可能有来自所有三个前端任务的连接)，而位于较低行的后端任务将没有连接。这种不平衡可以通过调整前端任务到起始行的不同映射来缓解: 这是大小为 L 的固定排列，可以任意选择稳定环顺序[0,8,2,4,6,1,9,5,3,7]将连续的前端任务分散到各行中。表 5 显示了最终的子集分配过程，对前端任务进行了排列，并显示了前端任务 10(红色)、11(蓝色)和 12(绿色)的子集分配(k = 10)。
较大的 L 值提高了子集多样性，但代价是连接不平衡。幸运的是，相对较小的值(例如 10)能够为典型的 Borg 作业提供足够的子集多样性，而且不会增加连接不平衡。
测试及部署
我们在开发期间基于生产环境收集的前端、后端和子集大小的测试套件来比较不同算法的属性，表明 Rocksteadier 子集减少了连接扰动率，不过我们想要验证是否也能减少二阶效应。
为此，我们在非生产环境中的一个服务上运行实验。两个前端作业(一个使用确定性子集，另一个使用 Rocksteadier 子集)不断向后端作业发送请求，后端作业在实验期间逐渐调整大小(使用不同步长)。图 5 显示了结果，每次后端大小发生变化时，使用确定性子集的前端作业都会出现错误峰值，而使用 Rocksteadier 子集的前端作业则基本不受影响。
我们在最受后端扰动影响的服务中试用了 Rocksteadier 子集，消除了这一服务采用 Autopilot 的障碍，大大节省了资源，降低了生产事故率。
经过几个月运行，没有发生任何重大事故，Rocksteadier 子集作为新的默认后端子集算法在全公司推出并获得了成功，基本上没有引起服务所有者的注意。
结论
本文介绍了谷歌寻求的一种算法，能够提供良好的连接平衡性、较高的子集多样性、无前端扰动、较低的后端扰动、较低的子集大小扰动和良好的子集传播性。大多数子集算法能够提供其中的几个属性，但据我们所知，只有 Rocksteadier 子集能够提供所有这些属性。
最后，虽然这些折衷适用于谷歌的生产环境，但在其他环境中可能并不理想。无论如何，对这些属性的讨论和对设计过程的理解也有可能对其他环境有所帮助。
你好，我是俞凡，在 Motorola 做过研发，现在在 Mavenir 做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI 等技术始终保持着浓厚的兴趣，平时喜欢阅读、思考，相信持续学习、终身成长，欢迎一起交流学习。为了方便大家以后能第一时间看到文章，请朋友们关注公众号"DeepNoMind"，并设个星标吧，如果能一键三连(转发、点赞、在看)，则能给我带来更多的支持和动力，激励我持续写下去，和大家共同成长进步！
