← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 5216.g.1

确定性算法均分子集

理解等级:高级

随机子集负载很不均:300 个客户端、300 个后端、每个连 90 个时,最闲后端只有均值的 63%,最忙达 121%;子集降到 10% 时为 50% 与 150%,要均衡得子集至少 75%,不可行。确定性算法把客户端按“轮”分组,每轮用不同种子重排后端列表并切成子集,同轮客户端各取一个,每个后端每轮恰好分给一个客户端,最终连接数最多差 1。每轮重排不同,避免同一子集后端一起故障时负载堆到剩下几台。发散:均匀不能靠运气。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第20章 数据中心内部的负载均衡系统 · 查看原书依据

      在这种情况下,最低负载的后端只接受平均值的50%(15个连接),而最高负载的后端接受了平均值的150%(45个连接)。 图20-4:300个客户端、300个服务器端和子集大小为10% 的连接分布图 我们最终的结论是,如果使用随机子集分布算法,要相对地平均分配负载,需要至少75%的子集大小。这样大的子集是不可行的:分布如此不均衡的算法在大规模部署情况下是不适用的。 子集选择算法二:确定性算法 Google对随机算法限制的解决方案是:确定性算法,以下这段代码实现了这个算法,详细解释在后文: 我们将客户端任务划分在多“轮”中,每一轮i包含了subset_count个连续的客户端,从客户端subset_count * i开始,同时subset_count是子集的个数(也就是后端数量除以想要的子集大小)。在每一轮计算中,每个后端都会被分配给一个而且仅有一个客户端任务(最后一轮除外,这时可能客户端数量不够,所以有些后端没有被分配)。

    参考来源

    - 位置:《SRE:Google运维解密》第20章《数据中心内部的负载均衡系统》(源文件:`_epub-src/OEBPS/Text/0009_0011.xhtml`) - 结论依据:原文给出随机子集的模拟数据与 75% 的结论,并说明确定性算法按轮重排、分配子集的方法及使用不同重排种子的理由。 - 原始内容:我们最终的结论是,如果使用随机子集分布算法,要相对地平均分配负载,需要至少75%的子集大小。这样大的子集是不可行的:分布如此不均衡的算法在大规模部署情况下是不适用的。