一致性哈希算法

本文主要是介绍一致性哈希算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一致性hash算法是定义一个2^32长度的环，环的顺时针方向依次是0 1 2 ... 2^32-1，服务器节点分布于环上，可以通过一个散列函数对每一个服务器节点求hash值，hash值对应环上的位置，这些服务器节点组成集群，当需要把数据保存到集群时，可以用同一个散列函数对数据求hash值，如果hash值正好对于一台服务器节点，则数据就保存到那个节点上，如果hash值所在环上的位置没有服务器节点，则顺时针查找最近的节点，把数据保存到那个节点上。

一致性hash算法相比普通hash算法有什么优势呢？

 假设有一个KV存储系统有3个节点，总共有60w分布均匀的数据，我们很容易就可以设计出来一个hash算法，把数据映射到3个节点上。每个节点有20w的数据。

但是有这样一个问题，如果集群增加一个节点呢？

数据会重新分布在各节点，但是在生产环境上，会有数据迁移的成本，这样的数据迁移成本有多大呢，我们可以简单的计算一下。结果为需要迁移75%的数据，这样的数据迁移成本是巨大的。

func TestNewServer(t *testing.T) {
    migrated := 0
    for i := 1; i <= 600000; i++ {
        if i%3 != i%4 {
            migrated++
        }
    }
    per := float32(migrated) / float32(600000)
    t.Log(per)
}

相比普通hash算法伸缩性差的缺点，一致性hash算法的迁移成本要小很多。还是以3节点，60w数据为例，每台节点20w数据，当增加节点KVServer4到位于KVServer2和KVServer3的中间时，之前KVServer2到KVServer4之间的数据，现在会映射到KVServer4上，而KVServer4到KVServer3之间的数据还是会映射到KVServer3上面，保持不变。这样只有1/6的数据需要迁移，比之前的75%少得多。实际上，如果节点数越多，需要迁移的数据量越少。

但是一般的情况下生产的数据不一定会均匀分布，这样即使节点均匀分布在hash环上，每台机器上面的数据量也不一定是均衡的。实际上一般采用把节点分成很多个虚拟节点，把虚拟节点映射到环上，当把数据保存到对应的虚拟节点时，实际上是把数据保存到物理节点上。虚拟节点数量越多，增加和减少节点时，需要迁移的数据量越少。还有，这里对一致性hash算法的实现有一定要求，需要hash算法越随机越好，如果不够随机，也会导致数据分布不均衡，一些节点会存储过多的数据，而一些节点会存储过少的数据。

go语言代码实现参考 https://gitee.com/liuanyou/consistenthash 

这篇关于一致性哈希算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！