一致性哈希

我们在使用Redis，Memcached等缓存系统时，当数据量增长到单机内存无法容纳时，我们需要搭建集群，将数据分布式存储到多台服务器。

对于给定的Key，我们如何决定哪台服务器来存储呢？

我们可以采用中心化的方法，使用一个中心节点来存储全局的信息。但如果我们不想维护一个中心节点，还有什么方法吗？

一种简单的解决方法是取模哈希（mod-N hasing)

取模哈希

如上图，集群里有n台服务器，取模哈希的做法是：使用哈希函数计算Key对应的哈希值，然后使用n对哈希值进行取模运算。

server := serverList[hash(key) % n]

取模哈希的优点是容易理解，运行速度快。但存在一个致命的问题：如果更改服务器的数目（增加或者减少），使用上面的公式计算，所有的Key可能都要移动到别的服务器上，缓存雪崩了。

为什么需要一致性哈希

一致性哈希的出现，就是为了解决服务器数目变更后，大部分Key失效的问题，而被提出的。

一致性哈希的优点是：当增加或减少服务器时，只有1/n的Key需要移动。其他的Key都不需要移动。移动的Key会均匀的分布到其他服务器。

举个例子，但我们将服务器数目由9台增加到10台，新的服务器会包含整个集群1/10的Key，
这些Key都是均匀地从9台旧的服务器里迁移过来的。
同样的，当我们减少一台服务器，这台服务器的Key会均匀地迁移到剩余的服务器。

一致性哈希的具体实现

一致性哈希使用一个圆环（hash ring)，环上的每一点都是一个整数值，整个环的值范围是0到2**32-1。

一致性哈希不依赖服务器的数目，算法实现是：使用相同哈希函数对服务器和Key计算，得到对应的哈希值，然后使用2**32对哈希值取模，得到一个整数值，这个整数值对应环山的一个点。

使用哈希函数对服务器进行计算。

使用相同的哈希函数对Key进行计算，然后顺时针，遇到的第一台服务器就是Key存储的服务器。

当其中一台服务器崩溃时，下图可以看到，只会影响少部分的Key。

增加服务器的情况也是一样，只会影响少部分Key。

一致性哈希虚拟节点

当服务器比较少时，Key的分布会很大概率分布不均匀，大部分的Key都存储到其中一台服务器上，负载不均匀。

我们当然希望的是：Key均匀的分布到每台服务器上。

一致性哈希引入了虚拟节点来解决数据分布不均的问题。其实就是加了一层映射关系，当通过圆环，定位到Key要存储到A#2时，我们知道虚拟节点A#2对应实际的服务器A。

虚拟节点的加入，也实现了我们最开始说的一致性哈希的优点，当增加或减少服务器时，只有1/n的Key需要移动。其他的Key都不需要移动。移动部分的Key会均匀地分布到其他服务器。

一致性哈希代码实现

func (m *Map) Add(nodes ...string) {
    for _, n := range nodes {
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + " " + n)))
            m.nodes = append(m.nodes, hash)
            m.hashMap[hash] = n
        }
    }
    sort.Ints(m.nodes)
}

func (m *Map) Get(key string) string {
    hash := int(m.hash([]byte(key)))
    idx := sort.Search(len(m.keys),
        func(i int) bool { return m.keys[i] >= hash }
    )
    if idx == len(m.keys) {
        idx = 0
    }
    return m.hashMap[m.keys[idx]]
}