2022 年 12 月 14 日，《ACM Queue》第 20 卷第 5 期发表了“Designing an algorithm with reduced connection churn that could replace deterministic subsetting”一文，作者为 Peter Ward、Paul Wankadia 与 Kavita Guliani。

• 背景：Google 的 Autopilot 系统内部用于提高资源利用率，可进行水平和垂直扩展，能有效防止中断，但水平扩展时会导致大量客户端连接短暂断开和重新连接，即连接抖动，这会带来诸多问题，如增加错误或延迟、增加 CPU/内存使用、降低吞吐量、增加连接缓存压力等，经调查发现这是由后端子集选择引起的。Google 十多年来一直使用确定性子集选择算法，虽能平衡每个后端任务的连接数，但连接抖动大，现需设计一种连接抖动减少的算法来替代它。
• Borg 中的后端子集选择：Google 服务运行在 Borg 集群管理软件上，服务所有者配置在多个 Borg 单元中运行的作业以实现地理多样性，一个单元内的作业由一个或多个任务组成，后端子集选择用于连接作业，可减少连接数，使用时需进行复制，前端任务使用负载均衡策略将请求定向到特定后端任务，以实现后端任务的均匀使用。

• 之前的方法：

  • 随机子集选择：最简单的算法是随机选择子集，但与许多负载均衡策略配合不佳，会导致连接分布不均匀，影响负载平衡。
  • 轮询子集选择：通过前端任务的任务编号进行协调，能使连接尽可能均匀，但子集多样性差，可能导致前端任务共享相同的子集，无法进行故障转移。
  • 确定性子集选择：通过引入随机性增加子集多样性，同时保持连接平衡，但会出现后端抖动，即后端规模变化时，前端任务的子集会发生很大变化，导致连接重新建立，增加错误或延迟，还可能出现前端抖动和子集大小抖动。此外，在软件版本更新时，轮询子集选择可能导致大部分前端任务的子集不可用。

• 新算法的探索：

  • 一致子集选择：基于一致哈希，每个前端和后端在单位圆上分配随机位置，前端按顺时针选择前 k 个后端作为子集，添加或删除任务时其他任务位置不受影响，能大幅减少连接抖动，但连接平衡和子集多样性不佳。
  • Ringsteady 子集选择：通过使用低差异序列改善一致子集选择的连接平衡，使后端任务在圆上均匀分布，同时保证良好的子集扩展，在某些情况下利用率低于确定性子集选择，但明显优于随机子集选择。
  • 前端和后端扩展：Ringsteady 子集选择在前端任务数量多于后端任务时连接平衡不足，可通过前端和后端扩展使其位置完全均匀，提高连接平衡，但前端扩展会引入前端抖动，不适合此用例。
  • Rocksteadier 子集选择：为增加子集多样性，将后端任务分组并洗牌，同时解决连接平衡和子集扩展问题，通过使用前端批次号作为 PRNG 的种子来洗牌后端批次，最后通过映射前端/后端批次到 Ringsteady 中的前端/后端任务来解决跨后端批次的平衡问题，较大的 L 值可增加子集多样性，但会增加连接不平衡，相对较小的值（如 10）可在提供足够子集多样性的同时不增加太多连接不平衡。
• 测试和部署：在开发过程中使用生产中的前端、后端和子集大小测试套件比较不同算法的性能，实验表明 Rocksteadier 子集选择减少了连接抖动，在受后端抖动影响最大的服务中进行试点后，该算法被推广为新的默认后端子集选择算法，运行数月无重大事件。
• 结论：Rocksteadier 子集选择在提供良好的连接平衡、高子集多样性、无前端抖动、低后端抖动、低子集大小抖动和良好的子集扩展方面具有创新性，虽这些权衡在 Google 的生产环境中是合适的，但在其他环境中可能并非理想，讨论的这些属性和设计过程在其他环境中可能有用。

作者信息：Peter Ward 是 Google 悉尼站点可靠性工程（SRE）的高级软件工程师，目前从事 Google Maps 工作，曾参与 Autopilot、Chrome 和 Google Photos 等产品；Paul Wankadia 是 Google 悉尼的高级软件工程师，从 SRE 退休后致力于提高软件效率；Kavita Guliani 是 Google 的 SRE 技术作家，与工程师、UX、项目经理和客户合作创建有助于产品或服务采用的文档，业余时间喜欢在大自然中度过、冥想和旅行。