分布式数据存储算法浅析

分布式数据库首先要解决把整个数据集按照分区规则映射到多个节点的问题,即把数据集划分到多个节点上,每个节点负责整体数据的一个子集。需要重点关注的是数据分区算法,通常的分区算法有 hash 算法、一致性 hash 算法、hash slot 算法,下面就这几种常见的数据分区算法进行简单的浅析。

hash 算法

使用特定的数据,如 Redis 的键或用户 ID,再根据节点数量 N 使用公式: hash(key)% N 取模,用来决定数据映射到哪一个节点上。比如,这个时候来了一个 key = hello_world,hash(hello_world) = 11111,这时,集群中一共 3 个节点,11111 % 3 = 2,这个时候,这个 key-value 会打到第 2 个节点上去。 但是这种方案存在一个问题:当节点数量变化时,如扩容或收缩节点,数据节点映射关系需要重新计算,会导致数据的重新迁移

假如其中的某台机器宕机了,就导致 1/3 的数据全部失效,需要重新对两台节点进行取模运算,再分布到其他的节点上去,如果后台逻辑没有处理好,高并发情况下,1/3 的流量可能直接越过缓存,访问数据库,将数据库压垮。

一致性 hash 算法

一致性哈希算法实现思路是为系统中每个节点分配一个 token,范围一般在 0~2^32 ,这些 token 构成一个哈希环。数据读写执行节点查找操作时,先根据 key 计算 hash 值,然后顺时针找到第一个大于等于该哈希值的 token 节点,如图所示:

这种方式相比 hash 算法最大的好处在于加入和删除节点只影响哈希环中相邻的节点,对其他节点无影响。但是也会存在如下的问题:

  • 加减节点会造成哈希环中部分数据无法命中,需要手动处理或者忽略这部分数据。
  • 当使用节点比较少时,节点变化将大范围影响哈希环中数据映射,因此这种方式不适合少量数据节点的分布式方案。
  • 普通的一致性哈希分区在增减节点时需要增加一倍或减去一半节点才能保证数据和负载的均衡。
  • 任何一个 master 宕机,只有之前的在那个master 上的数据会受到影响,因为照这顺时针走,会去找下一个相邻的 master,如果这样一直下去,都没有找到,那就会直接访问数据库,造成数据库流量暴增。

hash slot 算法

hash slot 算法巧妙地使用了哈希空间,使用分散度良好的哈希函数把所有数据映射到一个固定范围的整数集合中,整数定义为槽(slot)。Redis Cluster 就是采用此算法, Redis Cluster 有固定的 16384 个 hash slot,槽是集群内数据管理和迁移的基本单位,采用大范围槽的主要目的是为了方便数据拆分和集群扩展。每个节点会负责一定数量的槽,比如说当前集群有 5 个节点,每个节点平均大约负责 3276 个槽,如下所示:

hash slot 的计算公式:slot = CRC16(key)% 16384 ,对每个 key 计算 CRC16 值,然后对 16384 取模,可以获取 key 对应的hash slot,根据 solt 值就可以该 key 将存放到哪个节点上去。

hash slot 让 node 的增加和移除很简单,增加一个 master,就将其他 master 的 hash slot 移动部分过去,减少一个 master,就将它的 hash slot 移动到其他 master 上去,移动 hash slot 的成本是非常低的。hash slot 的特点总结如下:

  • 解耦数据和节点之间的关系,简化了节点扩容和收缩难度。
  • 节点自身维护槽的映射关系,不需要客户端或者代理服务维护槽分区元数据。
  • 支持节点、槽、键之间的映射查询,用于数据路由、在线伸缩等场景。