redis 数据分布以及槽信息

发表于 更新于 分类于

在分布式数据库中首先要解决数据集按照分区的规则划分到多个节点，每个节点负责整体数据的一个子集，大致如下图。

dist_database

划分规则

目前常见的划分规则有顺序分区，哈希分区

顺序分区

数据分布于业务相关，可顺序访问，但是离散度易倾斜

哈希分区

数据分布于业务无关，不可顺序访问，离散度较好

哈希分区又可根据算法和规则的不同分为以下几种

  • 节点取余
  • 一致性哈希
  • 虚拟槽

节点取余分区

对于键值 key, 和节点数量 N ，利用公式 计算出一个位于 [0, N - 1] 区间的值用来决定放在哪个节点上

这样做的优点在于简单，但是问题在于节点数量 N 变化时(扩容或者收缩), 数据和节点之间的映射关系需要重新计算，这样的话，就需要进行数据迁移，否则之前的数据就查询不到

一致性哈希分区

在一致性哈希中 ，把所有的数据包括节点数据都放在一个哈希环上，除了需要计算要存储的 key 的 hash 之外，还要计算节点的 hash, 然后在存储是，选择一个与 key 的 hash 最接近的 hash (顺时针找到第一个 >= hash 的节点), 存储进去

优点在于加入和删除节点只影响哈希环中相邻的节点，对其他的节点无影响。
问题在于

  • 加减节点，会造成哈希环中部分数据无法命中，需要手动处理或者忽略这部分数据，因此一致性哈希常用于缓存(redis 的全内存方案)
  • 当使用少量节点时，节点变化将大范围影响哈希环中数据映射，因此不适合少量数据节点的分布式方案
  • 普通的一致性哈希分区在增加节点时需要增加一倍或减去一半节点才能保证数据和负载的均衡

虚拟槽分区

虚拟槽分区为了解决一致性哈希分区的不足而创建的。
虚拟槽分区使用分散度良好的 hash 函数，将 key 映射到固定范围内的整数集合中，整数定义为槽(slot).
这个范围一般远远大于节点数，比如 redis Cluster 槽的范围是 0 - 16383. 一共 16384 个槽

槽概念

redis cluster 中有一个长度为 16384 槽概念，他们的编号为0, 1, 2 ,3 … 16382, 16383. 作为哈希槽使用。槽是集群内数据管理和迁移的基本单位，采用大范围槽的主要目的是为了方便数据拆分和集群扩展。
正常工作的时候，redis cluster 中的每个 master 节点都会负责一部分的槽，当某个 key 映射到某个 Master 负责的槽，那么这个 Master 负责为这个 key 提供服务。
可以有用户指定 Master 节点与槽的对应关系，也可以在初始化时由脚本(redis-trib.rb) 自动生成。
只有 Master 才拥有槽的所有权，如果是某个 Master 才拥有槽的所有权，如果是某个 Master 的 Salve, 这个槽只负责槽的使用，但是没有所有权。

数据分片

在 Redis Cluster 中，拥有 16384 个 slot, 这个数是固定的，存储在 Redis Cluster 中的所有的键都会被映射到这些 slot 中。数据库中的每个键都属于这 16384 个哈希槽中的一个。
集群用公式 CRC16(key) % 16384 计算 key 数于哪个槽。其中 CRC16(key) 语句用于计算 key 的 CRC16 校验。集群中的每个节点负责处理一部分哈希槽。

节点的槽指派信息

clusterNode 结构的 slots 和 numSlots 属性记录了节点负责接待哪些槽

1
2
3
4
struct clusterNode {
    //
    unsigned char slots[16384/8];
};

slots 为一个二进制位数组，共包含 2048 个 byte, 16348 个 bit. 如果拥有哪个槽，那么槽序号对应的 bit 就为 1, 事件复杂度为O(1)

请求重定向

由于每个节点只负责部分 slot, 以及 slot 可能从一个节点迁移到另一个节点，造成客户端有可能会向错误的节点发起请求。
此时需要一种机制对其进行发现和修正，这就是请求重定向，有两种不同的重定向场景

MOVED 错误

  • 请求的 key 对应的槽不在该节点上，节点将查看自身内部所保存的哈希槽到节点 ID 的映射记录，节点回复一个 MOVED 错误.
  • 需要客户端进行再次重试

ASKED 错误

  • 请求的 key 对应的槽目前处于 MIGRATING 状态，并且当前节点找不到这个 key 了，节点回复 ASK 错误。ASK 会把对应槽的 IMPORTING 节点返回，告知客户端到 IMPORTING 的节点查询
  • 客户端进行重试首先发送 ASKING 命令，节点将为客户端设置一个一次性的标志(flag), 使得客户端可以执行一次针对 IMPORTING 状态的槽的命令请求，然后再发送真正的命令请求。
  • 不必更新客户端所记录的槽到节点的映射