与哈希算法的关系

一致性哈希算法是基于哈希算法提出的,在分布式环境中,一致性哈希算法满足以下几个条件:

平衡性:数据对象应该平均分配到各个节点,这样能够解决负载均衡的问题;

单调性:增删节点时,不影响系统正常运行

分散性:数据对象分散存储与集群的各个节点(节点自身可以有其他节点的冗余数据),每个节点不必存储所有数据

实现原理

一致性哈希算法将整个哈希空间抽象为一个拥有2^32个节点的虚拟的圆环,起点为0,终点为2^32-1

使用服务器某项或多项唯一标识进行HASH运算即可得到该服务器在圆环中的位置,假定我们有4台服务器A,B,C,D,理想分布如下图所示:

假定有4个数据对象O1,O2,O3,O4,经HASH运算后,在圆环中的分布如下图所示:

确定位置后,让数据对象以顺时针的方向流动,达到最近的一台服务器,该服务器即为该数据对象的存储节点:

节点故障

假设服务器A故障,那么数据对象O1将流转至服务器B,其他数据对象不受影响

新增节点

假设新增服务器E,E位于数据对象O1与服务器A之间

数据倾斜问题

假设数据对象O1,O2,O3,O4经过取模运算后都位于服务器A~B之间,那么他们都会流转至服务器B,造成数据倾斜问题

为了解决该问题,一致性哈希算法引入了虚拟节点机制,即对同一台服务器进行多次HASH运算,在虚拟环上建立多个节点,缓解数据倾斜问题