html5 公司网站,杭州seo,站长工具是干嘛的,建设通网站会员共享密码子集算法有助于优化服务间连接利用率#xff0c;降低资源使用。但随机或轮询子集算法在动态拓扑环境中会造成较高的连接扰动。本文介绍了谷歌在解决连接扰动方面所做的思考和实践#xff0c;并介绍了当前最新的Rocksteadier子集算法。原文: Reinventing Backend Subsetting a… 子集算法有助于优化服务间连接利用率降低资源使用。但随机或轮询子集算法在动态拓扑环境中会造成较高的连接扰动。本文介绍了谷歌在解决连接扰动方面所做的思考和实践并介绍了当前最新的Rocksteadier子集算法。原文: Reinventing Backend Subsetting at Google 近年来由于有利于提高资源利用率Autopilot系统在谷歌内部越来越受欢迎。Autopilot可以做很多事情可以配置为执行水平扩展调整服务正在运行的任务数量以满足需求可以配置为执行垂直扩展调整每个任务分配的CPU/内存资源。Autopilot在防止停机方面也很有效相对人工运维来说可以实现服务规模的更快扩容来响应不断增长的需求。 随着Autopilot的广泛使用服务所有者发现了一个有趣的问题: 每当横向扩容的服务调整大小时许多客户端连接(通常是长连接)都会短暂断开并重新连接这种连接扰动会导致如下后果: 增加了当前请求的错误或延迟 增加了连接握手消耗的CPU/内存使用率 TCP慢启动建立新连接的过程降低了吞吐量 增加了连接缓存的压力 这些影响的严重程度因服务而异但在某些情况下错误或延迟的增加会使服务水平目标面临风险并阻碍Autopilot的采用。最终研究发现这种连接扰动问题是由后端子集引起的。 后端子集(Backend subsetting)是一种将服务连接在一起时减少连接数量的技术对于降低成本非常有用甚至可能是在系统限制条件下进行运维所必需的。十多年来Google使用确定性子集(deterministic subsetting)[1]作为默认后端子集算法尽管该算法平衡了每个后端任务的连接数量但会造成较高水平的连接扰动(connection churn)。 我们的目标是设计一种减少连接扰动的算法用以取代确定性子集作为默认后端子集算法。该目标雄心勃勃如海鲁姆定律(Hyrums 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)并且(因为我们为负载最多的后端任务预留资源)总容量将基于具有最多连接的后端任务( 其中 是到第n个后端任务的连接数)。从而获得以下指标: 然而该度量并没有考虑到连接的离散性。如果M×k不能被N整除理想的子集算法必须为每个后端任务分配 或 个连接因此 并且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选4210个可能子集但该算法只能分配5个不同的子集。一般情况下应该有 个子集。 这有什么问题想象一下一个前端任务正在执行某个更改该更改会在其子集中的后端任务中触发不良行为(例如高延迟或崩溃)而这将影响其他前端任务这些任务应该能够在其他后端任务上重试请求。但是如果其他前端任务所分配的子集和金丝雀前端任务完全相同那它们将共享相同的命运并且无法实现故障转移或者只能将故障转移到相同的后端任务从而造成这些后端任务过载。 确定性子集(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) 如何改善一致性子集的连接平衡性后端任务的连接数与后端任务在环上的空闲空间成正比因此连接平衡性取决于后端任务在环周围的均匀间隔程度。有了这种认识就可以通过有利于均匀分布的位置序列来改进随机选择的位置即构造低差异序列[2]。 仅仅因为后端任务是连续编号的所以低差异序列中的第n个元素可以与第n个后端任务相关联。 我们在谷歌选择的序列是二进制的van der Corput序列[3](将0作为第0个元素)它表示为0 。这些分数决定了每个节点在圆上的位置如图4b所示第一个任务被放置在圆的顶部第二个任务被放置在圆的中间以此类推。 选择这个序列的原因之一是它在计算元素位置时很方便。例如要获得第5个元素的位置(字长为8位)只需要将5的二进制00000101反转为10100000(十进制为160)然后将其作为位置的定点数得到 。 到目前为止本文只讨论了后端任务但是前端任务的需求是一样的。如果后端任务比前端任务多得多那么前端任务应该均匀分布以便选择的子集尽可能均匀避免重叠。对前端和后端任务使用相同的顺序会获得另一个方便的属性: 当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是 )作为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并设个星标吧如果能一键三连(转发、点赞、在看)则能给我带来更多的支持和动力激励我持续写下去和大家共同成长进步 参考资料 [1] A subset selection algorithm deterministic subsetting: https://sre.google/sre-book/load-balancing-datacenter/#a-subset-selection-algorithm-deterministic-subsetting-eKsdcaUm [2] Low discrepancy sequence: https://en.wikipedia.org/wiki/Low-discrepancy_sequence [3] van der Corput sequence: https://en.wikipedia.org/wiki/Van_der_Corput_sequence - END - 本文由 mdnice 多平台发布
