欢迎光临
中国顶尖人工智能与机器人行业新媒体平台

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

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

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倍,解决了扩大规模的一个瓶颈。他最近在一篇博客文章中详细介绍了此应用。这证明了谷歌研究院的理论研究不仅能应用到实践中,也兼具开源及有效的优点。

以下为雷锋网编译的论文部分内容,未经许可不得转载。

背景

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

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

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

算法

谷歌研究团队把每个客户端想象成一个球,将服务器想象成进球箱,仔细研究进球的随机过程。为了实现进球箱的均匀性,期望所有箱子的负载尽量接近平均负载(球的数量除以箱子数量)。对于参数ε,谷歌研究团队将每个箱子的容量上下界设置为平均负载的上下(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,雷锋网(公众号:雷锋网)编译

赞(0) 关注公众号

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

公众号也精彩

微信扫一扫打赏