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

对应的存储节点和数组的映射可能如下：

文章插图

那现在用户的图片怎么和存储节点对应呢？因为存储节点已经映射到了数组上, 我们现在可以通过范围区间的方式, 来找到对应的节点, 映射在数组上的图片可以向右查找, 找到了一个节点, 那么这个图片就属于这个节点, 当往右查找到最大值时,再回到最左边从0开始。
我在图中用不同的颜色标记了每个存储服务器的范围区间, 你可以理解一下

文章插图

接下来, 我们就需要对用户的图片进行Hash计算取模,同样的,计算结果一定还是在0-999的范围内, 然后再把这些值映射到数组上, 映射的结果可能如下图:

文章插图

这样就可以通过往右查找的方式, 找到用户的图片相对应的存储节点! 总结下来上面做了几件事情, 首先我们取一个固定的并且比较大的整数进行求模, 然后在对每个节点进行Hash计算求模, 这样可以找出每个节点所对应的范围区间, 最后再把用户的图片进行Hash计算求模, 最后根据范围区间确定图片的所在的存储节点。
那我们看看使用了这种方式, 当存储节点的增加和减少时会有什么影响？
节点增加场景

文章插图

这里我新增了一个存储节点D, 经过Hash计算后映射在数组上, 这样的话, 用户 James 本来是路由到C节点的,现在被路由到了D节点, 不过我们添加了D节点后, 受到影响的也只有C节点, 其实不管D节点映射到数组哪一个位置, 都只会有一个节点会受到影响, 其他的节点可以正常使用。
那么这种情况下, 如何做数据迁移? 我的思路是, 我们需要把C节点全部数据重新进行Hash计算, 然后根据计算结果, 一部分会移动到D节点, 一部分继续保留在C节点。
节点减少场景

文章插图

假如现在 A 节点在晚上20点宕机了, 那么本来应该路由到A节点的数据, 现在就被路由到了节点C, 也就是图中的 Bob的数据, 但是这种情况下, 其他的节点是不会受到节点变动的影响, 等到晚上21点时, A节点又恢复了正常。
这种情况的数据迁移的思路是, 当A节点宕机后, 数据需要全部复制到C节点, 当A节点恢复正常后, 再把C节点20:00至21:00的数据重新Hash计算, 然后根据计算的结果, 一部分会移动到A节点, 一部分继续保留在C节点。
节点分布不均匀
因为节点是随机的散列分布在数组上,所以有的节点的范围比较大, 而有的节点的范围比较小, 这样我们的数据分布就不均匀, 有的节点服务器会有比较大的请求压力。
这种情况有的同学可能会说, 我可以根据数组的长度(1000)和节点(3)的个数, 求出平均值, 然后就可以平均的把节点散列到数组上, 这样每个节点的请求压力都是一样的, 这种方式看起来没什么问题, 但是当添加节点或者移除节点的时候, 每个节点的覆盖范围都需要重新计算, 然后也需要迁移数据, 影响的范围还是挺大的。

文章插图

虚拟节点

文章插图

之前我们用了三个存储节点, 发现有分布不均匀的情况, 上图是我做了一个简单的测试, x 轴是节点的数量, y 轴是标准偏差, 根据这个图的趋势得出的结论是, 节点越多的时候, 标准偏差也就越小, 节点分布的就越均匀。
实际中,服务器节点是有限的, 增加很多节点也肯定是不现实的, 那么就可以在服务器节点不变的情况下, 引入虚拟节点, 也叫做影子节点。

文章插图

还记得我们之前是怎么对节点做hash映射的吗?公式是 hash(node) / 1000, 我们现在可以给A节点创建10个虚拟节点, 分别是 A1, A2,A3..., A10, 对应的虚拟节点的公式就是 hash(A1) / 1000 等等。这些虚拟节点和真实节点存在映射关系, 当图片映射到A节点的任意一个虚拟节点上时, 我们就把这个图片路由到A存储节点, 现在数组上已经有了30个虚拟节点做映射, 分布也比之前更均匀了, 当然你也可以创建更多的虚拟节点, 这些真实节点和虚拟节点的映射关系要保存在内存中或者是数据库中, 现在我们的映射图如下, 这里我给每个真实节点都添加了3个虚拟节点。