聊聊一致性哈希算法
一.一致性哈希算法要解决什么问题
假设我们有N个缓存空间，我们现在要把对象存储到到这个N个缓存空间中，我们可以定义这样的哈希函数
hash(object) mod N
每次存储对象的时候，计算一下这个哈希函数的值，这个值在[0,N)之间，这样我们就可以知道当前这个对象需要存储在那个缓存空间中了。
基于上面的解决方案，我们考虑如果缓存空间增加1个的话，我们该怎么处理，此时我们的哈希函数就变成了
hash(object) mod (N + 1)
哈希函数的变动意味着什么呢？意味着所有的对象需要重新哈希，这个代价太高了，会导致系统不可用的时间大大增加。
我们再考虑如果缓存空间有一个不可用啦，此时我们的哈希函数就变成了
hash(object) mod (N - 1)
哈希函数同样发生了变化，哈希函数的变化就意味着你之前存储的所有对象都要进行再次哈希。
上面这两种情况都是在实际生产环境中经常发生的，要是我们采用上面的解决方案，我们就没法把系统的稳定性保持在4个9。因此一致性哈希算法出现了，该算法能够保证缓存空间增加和减少的时候把再哈希的范围缩到最小。
二.哈希空间
这里的哈希空间是指哈希函数值域形成的取值空间，一般情况下哈希函数的值域在[0,2^32)，我们把这个值域想象成一个环形的空间，这个环形的空间就是我们这里一致性哈希算法的对应的哈希空间。至于为什么这里需要把它想象成一个环，就是为了后面对象和存储空间的映射。关于哈希空间如下图所示
接下来对象和对象的存储空间都是需要向这个哈希空间来映射的。
三.把对象映射到哈希空间
假设这里有四个对象，object1,object2,object3,object4,我们现在需要通过哈希函数把这个四个对象映射到我们前面提到的哈希空间中。
hash(object1) mod N = key1
hash(object2) mod N = key2
hash(object3) mod N = key3
hash(object4) mod N = key4
如下图所示，我们把四个对象映射到我们上面提到的哈希空间中
这样我们的对象就在哈希空间中找到了自己的位置。
四.把缓存空间映射到哈希空间
假设我们有三个缓存空间，cacheA,cacheB,cacheC,现在我们把这个三个缓存空间映射到哈希空间中
hash(cacheA) mod N = keyA
hash(cacheB) mod N = keyB
hash(cacheC) mod N = keyC
这样我们的缓存空间在哈希空间中也找到了自己的位置。
五.把对象映射到缓存空间
我们的目的不是映射到哈希空间，而是把对象映射到缓存空间，目前对象和缓存空间都映射到了哈希空间，现在我们需要把对象映射到缓存空间，如何处理呢？我们可以把哈希空间顺时针绕一圈，遍历哈希空间中的object,找到离object最近的cache，然后把这个object放在这个cache上面，这样即可完成object到cache的映射。如下图所示：
此时此刻，我们的对象已经和缓存空间之间建立了关系，并且对象已经找到自己应该前往那个缓存空间了。
六.增加一个缓存空间
现在我们考虑增加一个缓存空间cacheD
我们看到增加一个缓存空间cacheD后，我们需要重新映射的对象只有object2,其他三个对象都不需要重新映射。
七.删除一个缓存空间
现在我们考虑删除一个缓存空间cacheB
删除缓存空间cacheB后，我们只需要把object4做重新映射即可。
八.解决负载均衡的问题
要是我们的缓存空间数目不多，但是哈希空间很大，这会导致object不均衡地存储到缓存空间中，因此我们引入虚拟节点来解决这个问题，针对每个缓存空间，我们可以引入多个虚拟节点，v1…vn,所有映射到这几个虚拟节点的对象都会存储到同一个物理节点上。
这里的cacheA引入了两个虚拟节点vA1和vA2
这里的cacheB引入了两个虚拟节点vB1和vB2
这里的cacheC引入了两个虚拟节点vC1和vC2
虚拟节点不会存储对象，正真存储对象的是物理节点。
九.为什么叫一致性哈希算法
- 存储对象和存储空间使用相同的哈希空间
- 存储空间的数目变化不会导致哈希函数的变化