学界 | 谷歌推出有界负载的一致性哈希算法,解决服务器负载均衡问题

studyinsweden

AI科技评论按:运行大型Web服务需要负载平衡,例如内容托管。通常做法是在多个服务器之间均匀分发客户端,以免任何服务器超负荷运行。此外,谷歌的研究者们期望找到一种分发方式,使得在客户端和服务器可以随时增加或删除的动态环境中,分发也不会随时间波动产生太大变化。

谷歌与哥本哈根大学访问研究员Mikkel Thorup合作,开发了一种新的高效分配算法来解决这个问题:即严格控制每个服务器的最大负载,并从理论和经验上进行了研究。紧接着,谷歌研究院与云团队合作,在Google Cloud Pub / Sub(一种可扩展的事件流媒体服务)中实现算法,并在保证一致性和稳定性的同时,对负载分配(分配给服务器的最大负载)的均匀性进行了实质性改进。在2016年8月,谷歌纽约研究院的 Vahab Mirrokni、Mikkel Thorup 及Mikkel Thorup发表了论文“Consistent Hashing with Bounded Loads”,并在论文中描述了算法,并分享在ArXiv上,方便更广泛的研究用途。

三个月后,Vimeo的Andrew Rodland告诉我们,他发现了这篇论文并在haproxy(一个广泛使用的开源软件)中实现此算法,将其用于Vimeo的负载平衡项目。结果非常惊人:这种算法帮助他们将缓存带宽降低了近8倍,解决了扩大规模的一个瓶颈。他最近在一篇博客文章中详细介绍了此应用。这证明了谷歌研究院的理论研究不仅能应用到实践中,也兼具开源及有效的优点。

以下为AI科技评论编译的论文部分内容,未经许可不得转载。

背景

尽管一致性哈希算法早以被应用到动态环境中的负载平衡问题上,但是普遍存在的一个基本问题是,在某些情况下,它们可能导致许多服务器上的负载平衡次优化。

此外,客户端和服务器可能会定期添加或删除,但谷歌研究团队不希望因此导致客户端的大量移动。因此,动态分配算法不仅要始终确保适当的负载均衡,还要最小化每次变化后被移动的客户端数量。此外,服务器容量的严格限制使得这种分配问题更具挑战性,也就是, 每台服务器都有一个最大负载容量限制,我们希望容量能接近于平均负载。

换句话说,我们希望同时实现分配的均匀性和一致性。有大量的文献讨论了简单场景,即服务器集群是固定的,只有客户端被更新。但在这篇文章中,谷歌研究团队讨论了完全动态的场景,即客户端和服务器可以随时被添加和删除。

算法

谷歌研究团队把每个客户端想象成一个球,将服务器想象成进球箱,仔细研究进球的随机过程。为了实现进球箱的均匀性,期望所有箱子的负载尽量接近平均负载(球的数量除以箱子数量)。对于参数ε,谷歌研究团队将每个箱子的容量上下界设置为平均负载的上下(1 +ε)倍。这种容量范围允许设计一个同时满足一致性和均匀性的分配算法。

想象一下,在一个圆上覆盖了给定范围的数字。谷歌研究团队对球和进球箱分别应用不同的哈希函数,以获得与该圆上的位置对应范围内的数字。然后,我们开始以特定的顺序(假设根据它们的ID)分配球,而不考虑它们的哈希值。然后每个球顺时针移动,并分配到还有剩余容量的第一个箱子。

想象一下有6个球和3个箱子,使用2个哈希函数来随机循环地分配球进箱。设每个箱子的容量是2,然后按球的升序依次分配球(根据它们的ID),顺时针移动,1号球进入箱子C,2号球进入箱子A,3号球和4号球进入箱子B,5号球进入箱子C,然后6号球顺时针移动尝试进入箱子B,然而箱子B容量已达限制(箱子容量为2,箱子B已经装了3号球和4号球),所以6号球继续顺时针移动尝试进入箱子C,但是箱子C也已达容量,最后6号球进入了箱子A。

系统有任何更新(球或箱增加/删除)时,算法需要重新进行计算分配以保证均匀性。算法中巧妙的一点在于,确保小范围的更新(少量球或箱增加/删除)只引起细微的分配变化,以满足一致性。 在论文中,谷歌研究团队表明了增加和删除一个球引起其他球O(1 /ε2)的移动。最重要的一点是负载上界与系统中的球或箱的数量相对独立。 所以即使球或箱的数量加倍,负载的界限也不会改变。这一点增强了分配问题的可扩展性(即使扩大分配规模,也不影响一致性)。下图模拟了球或箱有更新时,移动次数(再分配)随更新的变化情况。

红色曲线显示平均移动次数,蓝色线条表示不同ε值的方差。 虚线曲线是基于理论研究建议的负载上界(通过预测实际运动次数能较好地拟合)。除此之外,对于任意值ε,谷歌研究团队知道每个箱子的负载上下界为平均负载的(1 +ε)倍。 下图表示不同值ε( 0.1,0.3,0.9)对应的箱子的负载分布。

不同ε值的负载分布。 负载分布几乎均匀,覆盖了从0到(1 +ε)倍的平均负载,还有许多箱子的负载等于(1 +ε)倍的平均负载

从图中可以看出均匀性和一致性的一个折衷 - 较小的ε值增强了均匀性,降低了一致性;而较大的ε值增加了一致性而降低了均匀性。较低的ε值能确保许多箱子的负载等于(1 +ε)倍的平均负载,其余箱子的负载依次衰减。

提供内容托管服务可能会遇到差异很大的各种场景,在这种情况下,谷歌研究院提供的这种一致性哈希算法将是理想的解决方案,即使是面对最坏的情况。

作者们对于内部试验的结果感到兴奋,但更加高兴的是,外界发现该算法很有效果且兼具开源特性,允许任何人使用此算法。

致谢:感谢Google Cloud Pub / Sub团队的Alex Totok,Matt Gruskin,Sergey Kondratyev和Haakon Ringberg,以及Mikkel Thorup对本文的宝贵贡献。

原文链接:https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html,AI科技评论编译

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-04-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏顶级程序员

不多掏钱 让数据库快200倍,Really?!

这年头几乎每个人都在这样那样抱怨性能。数据库管理员和程序员不断发现自己处于这种情形:服务器遇到了瓶颈,或者查询起来没完没了,这种情况并不少见。这种郁闷对我们所...

34111
来自专栏技术分享

.NET应用架构设计—面向查询的领域驱动设计实践(调整传统三层架构,外加维护型的业务开关)

阅读目录: 1.背景介绍 2.在业务层中加入核心领域模型(引入DomainModel,让逻辑、数据有家可归,变成一个完整的业务对象) 3.统一协调层Applic...

2047
来自专栏Fish

CUDA C最佳实践-CUDA Best Practices(一)

这文档堪称CUDA官方手册里最有用TOP3了。 ps:全文翻译会累死猿哒,意译意译,各位看官凑合一下啦 前言 文档的作用 这文档能干嘛,是用来帮助开发者从N...

2486

两个有用的数据概念

多年来我一直在反复考虑各种技术解决方案,并且在选择和构建管理数据的技术解决方案时发现它们很有用。它们帮助我构建,并从技术解决方案中向我提供我需要的信息。

1410
来自专栏小狼的世界

[每天五分钟,备战架构师-9]数据库系统

日常数据库使用过程中,离不开SQL语言。Structured Query Language由Boyce和Chamberlin在1974年提出,1975-1979...

872
来自专栏运维一切

ceph容量使用率的优化 原

###背景 随着ceph集群不断的变大和复杂,可能会遇到,整个容量很大,但是真正的数据使用率很低的情况。比如明明有100多TB的空间,但是数据才存了20TB,就...

472
来自专栏吉浦迅科技

DAY62:阅读Glossary

我们正带领大家开始阅读英文的《CUDA C Programming Guide》,今天是第62天,我们正在讲解CUDA C语法,希望在接下来的38天里,您可以学...

793
来自专栏Java架构

刚从阿里面试回来已拿到offer想和大家分享一下(阿里面试经验)

前不久刚从阿里面试回来,做的准备工作也是刷题和不断的充实自己的技术,其实目前阿里的面试题并不是现在流传的那样,不过还算好顺利拿到了offer,下面来跟大家分享一...

1764
来自专栏斑斓

利用聚合概念指导MongoDB的Schema设计

在我们的项目中,为了能够保存分析报表以及用户设置的报表查询条件,我们将这些信息视为报表元数据存储在MongoDB中。要存储的元数据包括:

612
来自专栏恰同学骚年

操作系统核心原理-1.操作系统导论

PS:操作系统原理是大学计算机专业最为重要的一门专业基础课程之一,对于操作系统核心原理的理解对于一个合格的程序员来说十分重要,于是我继续我的“三大原理,两个协议...

782

扫描关注云+社区