算法 哪位大侠能给解释下 Hash 一致性算法

ptmagic · 2012年04月20日 · 最后由 early 回复于 2018年06月03日 · 6211 次阅读

最近看到 Hash 一致性算法,能解决负载均衡,所以网上搜了一下不大懂,请各位大牛能给解释一下吗?

头像很亮啊

《自己动手写网络爬虫》一书里对 consistent hash 的讲解很不错,推荐看看。

Consistent Hashing 是解决均匀分布问题的。

应用在 数据库分库 等领域:

如果我们采用取余 或者 普通 hash 的话。

再一次增加一台机器的过程中,会导致大面积数据迁移问题。要不然就会出现入库不平均。

consistent hashing 就是为了解决这个问题的。

初始分配:

prepare

将所有机器通过 hash 算法分布在一个 2^32 次方的一个圆环上。

当每一次入库的时候。都会根据 hash 值分配到离自己最近的机器上。

新增机器后的分配策略:

new machine

新增机器只需要移动一台机器的数据就好,不需要影响全局机器。

这样就解决了所谓分库的问题。至于为什么是 2^32.. 其实这个可以是任何数.. 足够大就好。当然相应算法要自己调整。

ps: 本图片链接自我的 iteye blog. 原图扒自一篇翻译的 consistent hashing 的翻译论文。原谅我当时没有做记录是哪一篇。翻译作者可以联系我。

你看看你家的钟,上面有 12 个数字,你可以认为是 12 台服务器,然后闭上眼睛,顺时针转动一根针,忽然停下,然后你看看顺时针方向离指针最近的数字,那就是你可以使用的服务器。

#4 楼 @ch3n 这个解释赞~

#4 楼 @ch3n +1.. 通俗易懂。

#4 楼 @ch3n 假设你顺时针最近的数字的服务器挂掉了,就继续顺时针找下一个服务器。 这样一来,当有一台服务器挂掉的时候只有大约 1/12 的对象受到影响。 添加服务器时受到影响的对象也只有添加服务器逆时针到最近的服务器之间的对象受到影响。 想象一下传统的 Hash 算法如何映射 12 台服务器?

hash(object)%12,那么当添加或删除服务器时,公式就会变成hash(object)%11 或者hash(object)%13,几乎所有的对象都会受影响。

希望楼主家里不是数字时钟 ;D

#3 楼 @Saito 你好,那现在如果我要加一台服务器的话,0~2^32 这个是不会变得对吧?我加了一台不是会把以前节点的数据给冲掉吗?而且需要重新计算全局的 Hash 值呀

#4 楼 @ch3n 你好,那现在如果我要加一台服务器的话,0~12 这个是不会变得对吧?我加了一台不是会把以前节点的数据给冲掉吗?而且需要重新计算全局的 Hash 值呀

#1 楼 @camel 哈哈后 gif 图片罢了哈哈

#9 楼 @ptmagic
Consistent Hash 特点是服务器跟 object 一样,都会被映射到这个环形的空间中,也就是每个服务器跟每个对象都对应了 0~2^32 当中的一个值。加了一台之后只影响这台服务器的 hash 值逆时针到前一台服务器的 hash 值之间的 object

#12 楼 @paranoyang 对呀,用您的假设,假如我有两个服务器在,一个是对应了 0,一个是对于了 2^32,这时候我往 2^16 加一个服务器,那不是有一半的数据访问不到的情况出现?

是的 但是一般不会出现一个对应 0 一个对应 2^32 这种情况。这里涉及到 Hash 算法平衡性的问题,一般 consistent hashing 会通过 Virtual node 来解决。

最近在看一些 emula 相关的东西,涉及到 Chord 算法,刚好也是一种一致性哈希的实现;就是#3 楼 @Saito 说的这个原理, @ptmagic 你可以看看,这有一篇简介:http://blog.csdn.net/chen77716/article/details/6059575

#14 楼 @paranoyang 那如果出现我说的情况,那除了重新计算所有的数据的 Hash 值和对应的服务器的 Hash 值,还有什么别的方法没?

#16 楼 @ptmagic 你说的情况也不需要重新计算 hash 值啊,只有部分对象要变动映射的服务器,hash 值是不变的。 @blackanger 发的链接中有比较详细的解释

需要 登录 后方可回复, 如果你还没有账号请 注册新账号