最近看到 Hash 一致性算法,能解决负载均衡,所以网上搜了一下不大懂,请各位大牛能给解释一下吗?
Consistent Hashing 是解决均匀分布问题的。
应用在 数据库分库 等领域:
如果我们采用取余 或者 普通 hash 的话。
再一次增加一台机器的过程中,会导致大面积数据迁移问题。要不然就会出现入库不平均。
consistent hashing 就是为了解决这个问题的。
初始分配:
将所有机器通过 hash 算法分布在一个 2^32 次方的一个圆环上。
当每一次入库的时候。都会根据 hash 值分配到离自己最近的机器上。
新增机器后的分配策略:
新增机器只需要移动一台机器的数据就好,不需要影响全局机器。
这样就解决了所谓分库的问题。至于为什么是 2^32.. 其实这个可以是任何数.. 足够大就好。当然相应算法要自己调整。
ps: 本图片链接自我的 iteye blog. 原图扒自一篇翻译的 consistent hashing 的翻译论文。原谅我当时没有做记录是哪一篇。翻译作者可以联系我。
你看看你家的钟,上面有 12 个数字,你可以认为是 12 台服务器,然后闭上眼睛,顺时针转动一根针,忽然停下,然后你看看顺时针方向离指针最近的数字,那就是你可以使用的服务器。
#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
#16 楼 @ptmagic 你说的情况也不需要重新计算 hash 值啊,只有部分对象要变动映射的服务器,hash 值是不变的。 @blackanger 发的链接中有比较详细的解释