全国服务热线: +86 13177555535
最新公告:
seo培训学习,企业站seo实战培训,培训seo教学课程——实战为主,理论为辅,诚信不变,力保双赢...
SEO培训service
SEO联系Contact us
地址:
中国重庆市九龙区
邮箱:
996934@qq.com
电话:
+86 13177555535
传真:
+86-13177555535
企业seo培训   当前位置:首页 > SEO资讯 > 企业seo培训
谷歌推出有界负载的一致性哈希算法,解决服务器负载均衡问题发布时间:2018-12-06

  雷锋网AI科技评论按:运行大型Web服务需要负载平衡,例如内容托管。通常做法是在多个服务器之间均匀分发客户端,以免任何服务器超负荷运行。此外,谷歌的研究者们期望找到一种分发方式,使得在客户端和服务器可以随时增加或删除的动态环境中,分发也不会随时间波动产生太大变化。谷歌与哥本哈根大学访问研究员Mikkel Thorup合作,开发了一种新的高效分配算法来解决这个问题:即严格控制每个服务器的最大负载,并从理论和经验上进行了研究。紧接着,谷歌研究院与云团队合作,在Google Cloud Pub / Sub(一种可扩展的事件流媒体服务)中实现算法,并在保证一致性和稳定性的同时,对负载分配(分配给服务器的最大负载)的均匀性进行了实质性改进。在2016年8月,谷歌纽约研究院的 Vahab Mirrokni、Mikkel Thorup 及Mikkel Thorup发表了论文"Consistent Hashing with Bounded Loads",并在论文中描述了算法,并分享在ArXiv上,方便更广泛的研究用途。尽管一致性哈希算法早以被应用到动态环境中的负载平衡问题上,但是普遍存在的一个基本问题是,在某些情况下,它们可能导致许多服务器上的负载平衡次优化。此外,客户端和服务器可能会定期添加或删除,但谷歌研究团队不希望因此导致客户端的大量移动。因此,动态分配算法不仅要始终确保适当的负载均衡,还要最小化每次变化后被移动的客户端数量。此外,服务器容量的严格限制使得这种分配问题更具挑战性,也就是, 每台服务器都有一个最大负载容量限制,我们希望容量能接近于平均负载。换句话说,我们希望同时实现分配的均匀性和一致性。有大量的文献讨论了简单场景,即服务器集群是固定的,只有客户端被更新。但在这篇文章中,企业站seo实战培训谷歌研究团队讨论了完全动态的场景,即客户端和服务器可以随时被添加和删除。谷歌研究团队把每个客户端想象成一个球,将服务器想象成进球箱,仔细研究进球的随机过程。为了实现进球箱的均匀性,期望所有箱子的负载尽量接近平均负载(球的数量除以箱子数量)。对于参数ε,谷歌研究团队将每个箱子的容量上下界设置为平均负载的上下(1 ε)倍。这种容量范围允许设计一个同时满足一致性和均匀性的分配算法。想象一下,在一个圆上覆盖了给定范围的数字。谷歌研究团队对球和进球箱分别应用不同的哈希函数,以获得与该圆上的位置对应范围内的数字。然后,我们开始以特定的顺序(假设根据它们的ID)分配球,而不考虑它们的哈希值。然后每个球顺时针移动,并分配到还有剩余容量的第一个箱子。想象一下有6个球和3个箱子,使用2个哈希函数来随机循环地分配球进箱。设每个箱子的容量是2,然后按球的升序依次分配球(根据它们的ID),顺时针移动,1号球进入箱子C,2号球进入箱子A,3号球和4号球进入箱子B,seo培训学习5号球进入箱子C,然后6号球顺时针移动尝试进入箱子B,然而箱子B容量已达限制(箱子容量为2,箱子B已经装了3号球和4号球),所以6号球继续顺时针移动尝试进入箱子C,但是箱子C也已达容量,最后6号球进入了箱子A。红色曲线显示平均移动次数,蓝色线条表示不同ε值的方差。 虚线曲线是基于理论研究建议的负载上界(通过预测实际运动次数能较好地拟合)。除此之外,对于任意值ε,谷歌研究团队知道每个箱子的负载上下界为平均负载的(1 ε)倍。 下图表示不同值ε( 0.1,0.3,0.9)对应的箱子的负载分布。从图中可以看出均匀性和一致性的一个折衷 较小的ε值增强了均匀性,降低了一致性;而较大的ε值增加了一致性而降低了均匀性。较低的ε值能确保许多箱子的负载等于(1 ε)倍的平均负载,其余箱子的负载依次衰减。提供内容托管服务可能会遇到差异很大的各种场景,在这种情况下,谷歌研究院提供的这种一致性哈希算法将是理想的解决方案,即使是面对最坏的情况。作者们对于内部试验的结果感到兴奋,但更加高兴的是,外界发现该算法很有效果且兼具开源特性,允许任何人使用此算法。致谢:感谢Google Cloud Pub / Sub团队的Alex Totok,Matt Gruskin,培训seo教学课程Sergey Kondratyev和Haakon Ringberg,以及Mikkel Thorup对本文的宝贵贡献。开眼数据郑峰搜索引擎提升…最新资讯-SEO专业培训方向说明