首页 > 代码库 > 分方式缓存常用的一致性hash是什么原理

分方式缓存常用的一致性hash是什么原理

分方式缓存常用的一致性hash是什么原理

一致性hash是用来解决什么问题的?

先看一个场景

有n个cache服务器,一个对象object映射到哪个cache上呢?

可以采用通用方法计算object的hash值,然后均匀的映射到到n个cache

hash(object) % n

初始阶段运行正常,但当cache服务器发生变动后就会出现问题

例如

(1)一个cache服务器down掉了,这样所有映射到此cache的对象都会失效,需要把此cache移除,这时候映射公式变成了 

hash(object) % (n-1) 

(2)由于访问加重,需要添加cache ,这时候映射公式变成了 

hash(object) % (n+1)

这两种情况几乎会使所有的cache都失效,大量的访问都会直接访问后台服务器,造成极大的压力

一致性hash算法就是为了解决普通hash的不足,把损失降到最低

一致性hash的原理

一致性hash将整个哈希值空间组织成一个虚拟的圆环

假设某哈希函数H的值空间为0-2^32-1(2^32为2的32次方)

整个空间按顺时针方向组织,0和232-1在零点中方向重合

技术分享

把各个cache服务器通过hash计算,根据hash值顺时针排列到圆环上,可以根据服务器的IP或者主机名进行计算

例如有 A B C 三台服务器

技术分享

现在可以映射object了,映射规则为:

将key使用相同的hash计算出值,并确定此数据在环上的位置,从此位置顺时针行走,第一台遇到的cache服务器就是其应该定位到的服务器

例如有4个object需要映射到cache服务器

技术分享

根据映射规则

object 1 -> A
object 2、3 -> B
object 4 -> C

下面看cache服务器的增减情况

(1)移除

例如A出现异常,需要移除

技术分享

object 1 失效,需要映射到B

受影响的只有object 1

(2)添加

cache压力增加,需要添加服务器,新增cache服务器D

技术分享

object 2 需要重新映射到D

受影响的只有object 2

可以看到一致性hash比普通hash高效了很多

分方式缓存常用的一致性hash是什么原理