一致性哈希算法原理以及实现方案

分布式存储方案

我们都知道,当数据量大了的时候,我们都会选择使用多台服务器共存数据,通过 取模方式进行随机分配服务器存储.

例如:  将用户的1亿订单数据分配到3台服务器上,进行分表存储.

我们可以通过订单id,或者用户id,进行取模存储:

$server = [
    '0',
    '1',
    '2'
];
$userId = mt_rand(1,999999);
$mod = $userId%count($server);
echo "用户{$userId}将存储在 服务器{$server[$mod-1]} 中";

这样的话,理论上用户id如果是正常自增,那每台服务器存储的数据都将是平均存储.

哈希算法

在上面我们讲到了可以通过 用户id去进行取模分配服务器

但是实际业务中,没有这么多id取模分配的,数据也可能是不连续,不规律的字符串,这个时候,就需要通过一个好的哈希算法,进行平均分配服务器了.

可以查看文章:http://www.php20.cn/article/sw/hash/253

通过hash算法,将数据尽可能的平均分配到每一台服务器上,

分布式一致性哈希

在上面的存储方案中,我们可以实现对服务器数量进行取模随机分配,保证存储的键尽可能的平均分配到服务器中.

但是,当我们需要扩容服务器,或者进行服务器减配时,就会发现所有的键都需要重新取模分配,那么有什么方法可以尽可能的降低影响吗?

首先,我们需要保证:当取模时,不能使用服务器数量进行取模,否则当服务器数量变动时,所有数据都会变动

这个时候,我们就可以使用分布式一致性哈希算法了.

哈希环

我们首先定义一个0~2^32的数组,同时将数组抽象成一个圆形,0和2^32首尾相连

将服务器节点,通过取模的方式定位到哈希环中:

当需要存储数据时,通过 hash(key)%2^32,定位一个点.同时顺时针开始查找服务器节点,找到的第一个为需要存储数据的节点.

例如: hash(key)%2^32=100,那么哈希环从100位置开始顺时针查找服务器节点,找到第一个节点为服务器0,则该数据存储到服务器0中.

增加服务器节点

当需要增加服务器节点时.首先先服务器通过取模,定位到哈希环的点中.

当定位成功后,意味着 服务器1 的数据需要额外分配,而服务器0,服务器2的数据完全没有变化.

我们只需要将服务器1的数据进行重新分配,将一部分映射的数据重新分配到服务器3即可

删除服务器节点

当服务器2 节点被删除(失效)时, 将会丢失 服务器1->服务器2 之间的映射数据,

这个时候,就需要将服务器2节点的数据迁移到下一台服务器,也就是服务器0中,同时,服务器1,服务器3的数据不受影响.

虚拟节点概念

当服务器2删除之后,剩下的 服务器0,服务器3,服务器2 都映射到了相近位置,这个时候,服务器0的存储数据就变成了 从服务器1->服务0中间所有的映射数据,会导致服务器0压力激增,这个时候就可以使用虚拟节点的概念进行分配.

之前的服务器节点分配,使用的是 hash(ip) %2^32,当服务器数量较少,并且 hash ip 映射值相近时,就会出现服务器节点存储数据分配不均的结果.

这个时候,我们可以采用另一种 hash方案,比如 使用 hash(ip+编号) %2^32,并且一台服务器可以使用多个编号进行分配.例如:

hash (ip+1) %2^32. hash(ip+2)%2^32,一台服务器,映射多个节点:

为了使得服务器节点尽可能平均的存储数据,一个服务器,可以使用更多的虚拟节点,比如10个,100个,将哈希环的服务器节点尽可能的平均分布

redis cluster

redis cluster的一致性哈希算法与本文所说的类似,不同的是redis的哈希环是哈希槽,将key通过hash算法分配到槽位中,同时集群各自管理了多个槽位.