相关文章:
一致性哈希算在 1997 年由麻省理工学院提出,是一种特殊的哈希算法,目的是解决分布式缓存的问题
一致性哈希算法将哈希值空间组织成一个虚拟的圆环
假设将某个哈希函数 H 的值空间为 0-2^32-1 (因为哈希值通常是一个 32 位的无符号整形)
我们将这个由 2^32 个点组成的圆环称为哈希环
接着对 key 进行哈希运算得到哈希值 (可以选择服务器的 IP 或主机名作为关键值进行哈希运算),这样每台服务器就可以确定其在哈希环上的位置
然后使用以下算法来定位数据的目标存储服务器:即对数据 key 使用相同的哈希函数进行运算后得到哈希值,并确定此数据在环上的位置,然后沿环顺时针方向寻找,第一台遇到的服务器就是数据的目标存储服务器
假设有 ObjectA、ObjectB、ObjectC、ObjectD 四个数据对象,对其进行哈希运算后,在环空间的位置如上所示
根据一致性哈希算法,ObjectA 会被定位到 NodeA 上,ObjectB 会被定位到 NodeB 上,ObjectC 会被定位到 NodeC 上,ObjectD 会被定位到 NodeD 上
四个数据 ObjectA、ObjectB、ObjectC、ObjectD 在环空间的位置已确定,假设此时 NodeC 宕机,则 ObjectA、ObjectB、ObjectD 都不会受到影响,只有 ObjectC 会被重新定位到 NodeD 上
假设在 NodeB 和 NodeC 之间新加一台服务器 NodeX,则 ObjectA、ObjectB、ObjectD 都不会受到影响,只有 ObjectC 会被重新定位到 NodeN 上
一致性哈希算法并不是完美的,它会遇到一个叫做哈希环数据倾斜的问题
为了解决哈希环数据倾斜问题,一致性哈希算法引入了虚拟节点的机制,即对每一个服务器节点计算多个哈希,每个计算结果为止都放置一个子服务器节点,即虚拟节点,具体做法可以由在服务器 IP 或主机名的后面增加编号来实现
如上所示,我们为每台服务器计算三个虚拟节点,NodeA --> NodeA#1、NodeA#2、NodeA#3,NodeB --> NodeB#1、NodeB#2、NodeB#3,将它们均匀地分布在哈希环上,于是这样就形成了六个虚拟节点
同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如当数据定位到 NodeA#1 或 NodeA#2 时,两个虚拟节点的数据均需要再次定位到 NodeA 上,这样子就解决了服务器节点少时的数据倾斜问题
在实际应用中,通常将虚拟节点设置为 32 或更大,因此即使服务器节点很少,也能够做到相对均匀的数据分布