- 什么是一致性哈希
一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对K/n个关键字重新映射，其中K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。
- 一致性哈希的特点
- 平衡性
平衡性是指哈希的结果能够尽可能分布到所有缓冲去，这样可以使得付哦有的缓冲空间都使得 所有的缓冲空间得到利用。
- 单调性
单调性是指如果已经有一些内容通过哈希分派到相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应该能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲或者其他缓冲区。
- 分散性
在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
- 一致性哈希解决了什么问题
- 新增或者减少一台服务器的时候，不会造成大面积的访问错误
- 同一个资源仍然会映射到之前同样的服务器上
- 新增一台服务器时，新的服务器需要尽可能分担存储在其他服务器的资源
- 减少一台服务器时，其他服务器也也可以尽量分担存储它的缓存资源
- 一致性哈希算法
环形空间
通常的哈希算法都是将value映射到一个32位的key值，也即是0 ~ 2^32-1次方的数值空间，如下所示：
把对象映射到环形空间
现在假设有4个对象a，b，c，d，通过hash函数计算出的hash值key在环上的分布如图：
hash(a) = keya
hash(b) = keyb
hash(c) = keyc
hash(d) = keyd
把Cache映射到环形空间
一致性哈希的基本思想就是将对象和Cache都映射到同一个Hash空间中，并且使用相同的Hash 算法。假设当前有A，B，C三台Cache，那么其映射结果将如下图所示，他们在Hash空间中，以对应的哈希值排列：
hash(A) = keyA
hash(B) = keyB
hash(C) = keyC
一般情况下，我们使用Cache 服务器的IP地址或机器名作为Hash函数的输入。
2.1.4 把对象映射到Cache
现在Cache和对象都已经通过同一个Hash算法映射到了Hash数值空间中，接下来要考虑的就是如何将对象映射到Cache上。
在这个环形空间中，如果沿着顺时针方向从对象的Key值出发，直到遇见一个Cache，那么就将该对象存储在这个Cache上，因为对象和Cache的哈希值是固定的，因此这个Cache必然是唯一和确定的。
根据上面的方法，对象a和d将被映射到Cache C上，对象b将被映射到Cache A上，对象C将被映射到Cache B上，如图：
2.1.5 添加或移除Cache
通过Hash求余的方法所带来的最大的问题就在于不能满足单调性，当Cache有所变动时，缓存会失效，进而对后台服务器造成巨大的冲击，接下来分析一下一致性哈希算法如何处理这个问题。
现在假设Cache B被移除了，根据上面的映射方法，这时受影响的仅是那些沿Cache B逆时针遍历到下一个Cache(Cache C)之间的对象，因此这里仅需要移动对象c，将其重新映射到Cache A上即可：
假设再考虑添加一台Cache D的情况，假设在这个环形空间中，Cache D被映射到了对象a和d之间，这时受影响的将仅是那些沿着Cache D逆时针遍历到下一个Cache(Cache A)之间的对象，将这些对象移动到Cache D上即可：
通过添加或移除Cache的分析，一致性哈希算法在保持了单调性的同时，还将数据的迁移量达到了最小，这样的算法对于分布式集群来说时非常合适的，避免了大量的数据迁移，减轻了服务器的压力。
平衡性
平衡性是指哈希的结果能够尽可能分散到所有的Cache中去，这样可以使得所有的缓存空间都能得到充分的利用。
哈希算法并不能保证100%的平衡性，如果Cache较少的话，对象并不能被均匀得映射到Cache上，比如在上面的例子中，仅部署Cache A和Cache B的情况下，在4个对象中，Cache A仅存储了对象b，而Cache B则存储了对象a，d，c，分布很不均匀。为了解决这个问题，一致性哈希算法引入了虚拟节点的概念，定义如下：
虚拟节点是实际节点在Hash空间中的复制品(replica)，实际节点对应了若干个虚拟节点，每个实际节点对应的虚拟节点个数称为复制个数，虚拟节点在Hash空间中以Hash值排列
仍以仅部署A和B的情况为例，现在我们引入虚拟节点，并设置复制个数为2，这就意味着一共会存在4个虚拟节点，Cache A1和Cache A2代表了Cache A，Cache B1和Cache B2代表了Cache B，假设一种比较理想的情况，如下图：
此时映射关系变为：a --> Cache A2；b --> Cache B2；c --> Cache A1；d --> Cache B1，因此对象a和c都被映射到了A上，而b和d都被映射到了B上，平衡性有了很大提高。
引入虚拟节点后，映射关系就从对象 -> 节点变成了对象->虚拟节点，虚拟节点的Hash计算可以采用IP地址加数字后缀的方式。
- 与普通hash的区别
普通hash增加或者减少结点的时候会造成所有数据的重新分配。当其中一个结点发生故障的时候，会造成数据的丢失和数据的不一致性。。。。
- 一致性哈希Go代码实现
import (
"hash/crc32"
"sort"
"strconv"
)
type Hash func(data []byte) uint32
type Map struct {
hash Hash
replicas int // 复制因子
keys uint32 // 已排序的节点哈希切片
hashMap map[uint32]string // 节点哈希和KEY的map，键是哈希值，值是节点Key
}
func New(replicas int, fn Hash) *Map {
m := &Map{
replicas: replicas,
hash: fn,
hashMap: make(map[uint32]string),
}
// 默认使用CRC32算法
if m.hash == nil {
m.hash = crc32.ChecksumIEEE
}
return m
}
func (m *Map) IsEmpty() bool {
return len(m.keys) == 0
}
// Add 方法用来添加缓存节点，参数为节点key，比如使用IP
func (m *Map) Add(keys ...string) {
for _, key := range keys {
// 结合复制因子计算所有虚拟节点的hash值，并存入m.keys中，同时在m.hashMap中保存哈希值和key的映射
for i := 0; i < m.replicas; i++ {
hash := m.hash([]byte(strconv.Itoa(i) + key))
m.keys = append(m.keys, hash)
m.hashMap[hash] = key
}
}
// 对所有虚拟节点的哈希值进行排序，方便之后进行二分查找
sort.Sort(m.keys)
}
// Get 方法根据给定的对象获取最靠近它的那个节点key
func (m *Map) Get(key string) string {
if m.IsEmpty() {
return ""
}
hash := m.hash([]byte(key))
// 通过二分查找获取最优节点，第一个节点hash值大于对象hash值的就是最优节点
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]]
}