一文读懂哈希和一致性哈希算法( 三 ) _哈希算法

文章插图

引入了虚拟节点后, 在数组的映射看起来平均很多了, 现在我们每个真实节点的请求压力都是一样的了, 接下来, 我们还要看下这个方案在节点的变动情况下应该怎么处理。
增加节点
现在增加了一个节点D,按照上面的规则, 实际上是要添加 D 的虚拟节点, D1,D2,D3,然后散列映射到数组上,如下图所示:

文章插图

先看最左边, D1 插入到了 C2 和 A1 之间, 而A1和A节点对应, D1节点和D节点对应, 也就是说A节点的一部分数据要迁移到D节点, 这里我的思路是, 当在节点写入数据时, 同时把虚拟节点的信息也记录下来,这样就很方便做数据迁移了, 我们可以在A节点中只找出A1虚拟节点的数据, 而不是全部, 然后Hash计算映射后, 根据计算结果,一部分同步到D节点, 一部分保持不变。后边的数据也可以按照这个思路进行数据迁移。
节点减少

文章插图

当C节点下线的时候, 我们同时要移除和C节点对应的虚拟节点,C1,C2,C3, 然后就是数据迁移的工作了, 根据图中的表示, 可以直接把 C节点中的C2节点的数据迁移到A1节点, C1迁移到B3,C3迁移到B1中, 完成！
总结本文介绍了哈希和一致性哈希算法, 以及提供了一些数据迁移的思路, 回顾下这个方案, 首先需要定义一个比较大的固定值用于取模, 然后创建和真实节点对应的虚拟节点, 最后再把虚拟节点映射到数组上, 通过范围区间的方法, 来确定图片属于哪一个存储节点。
可能还有同学会说, 一致性hash也有缓存失效的时候,也需要手动迁移数据。是的, 维基百科对一致性Hash的定义是, 当节点的数量变动时,可以允许少部分的数据进行迁移, 而大部分的数据还是不变的。
上面的一致性Hash算法其实是经典的哈希环算法, 当然还有其他的算法, 比如跳跃一致性哈希法, 有兴趣也可以看一下, 以上内容均为个人理解, 如果错误, 可以指出, 希望对您有用！

【一文读懂哈希和一致性哈希算法】