一致性哈希
一致性哈希在哈希算法基础上, 适用于动态变化的Cache环境中
场景
如果我们有4台Cache服务器来存放一些对象, 可以用简单的办法来分配:object.hashCode() % 4.
- Cache0:
object.hashCode() % 4 == 0 - Cache1:
object.hashCode() % 4 == 1 - Cache2:
object.hashCode() % 4 == 2 - Cache3:
object.hashCode() % 4 == 3
动态变化体现在, 如果因为某些原因Cache服务器少了一台或者多了一台, 我们怎么处理对象与服务器的关系呢?
少了一台应该%3, 多了一台应该%5, 这样服务器上原来存放的对象与服务器的对应关系就全乱了
使用一致性哈希解决上述场景
算法步骤
一致性哈希算法采用一种新的方式来解决问题，不再仅仅依赖object.hashCode()本身，而且将Cache的配置也进行哈希运算。具体步骤如下:
- 先求出每个Cache的哈希值, 并将其配置到一个0~2^32的圆环区间上(为啥是32?哈希值一般不超过32位)
- 求出需要存储对象的哈希值, 也将其配置到这个圆环上
- 从对象所映射到的位置顺时针开始找, 把对象保存在第一个找到的Cache节点上
新增Cache服务器的情景
假设在这个环形哈希空间中, Cache5被映射在Cache3和Cache4之间, 那么受影响的将仅是沿Cache5逆时针遍历, 直到下一个Cache(Cache3)之间的对象. 只对这些对象进行转移即可.
Cache3~Cache5之间部分原来映射到Cache4, 现在应该映射到Cache5;
Cache5~Cache4之间部分原来映射到Cache4, 现在还是映射到Cache4, 不受影响;
删除Cache服务器的情景
假设在这个环形哈希空间中, Cache3被移除, 那么受影响的将仅是沿Cache3逆时针遍历直到下一个Cache(Cache2)之间的对象
原来Cache2~Cache3之间部分原来映射到Cache3, 现在应该映射到Cache4;
原来Cache3~Cache4之间部分原来映射到Cache4, 现在还是映射到Cache4, 不受影响;
虚拟Cache服务器
考虑到哈希算法并不是保证绝对的平衡, 尤其Cache较少的话, 对象并不能被均匀的映射到Cache上. 为了解决这种情况引入了”虚拟节点”的概念.
虚拟节点是实际节点在环形空间的复制品, 一个实际节点对应了若干个”虚拟节点”, 这个对应个数也称为”复制个数”, “虚拟节点”在哈希空间中以哈希值排列.
仍以4台Cache服务器为例,设置”复制个数”为2后, 共有8个“虚拟节点”分部在环形区域上, 会如下图一样:
引入了”虚拟节点”后，映射关系就从对象-->Cache服务器转换成了对象-->虚拟节点-->Cache服务器. 当然虚拟节点与真正的服务器之间也有对应关系. 查询对象所在Cache服务器的映射关系整个流程如下图所示:
