02 Redis 的数据结构

2.3.0 哈希冲突

当往哈希表写入大量数据时，不可避免的就出现多个 key 计算出来的哈希值相同。也就是多个不同的 key 需要放到同一个哈希桶，这就是所谓的哈希冲突。

而 Redis 解决哈希冲突的手段很 Java 一样，都是链式哈希：同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

如图，假设 entry1、entry2、entry3 的哈希值都是 3 ；那么他们将存放在下标为 3 的哈希桶里面，并转换成链表。

PS：没懂哈希冲突的看旧文。旧文：《HashMap 源码解读》有详细例子解析。

当不断发生哈希冲突，链表越来越长，影响查询性能时，Redis 就需要 rehash。

2.3.1 rehash（扩容）

Redis 开始执行 rehash，这个过程分为三步：

• 1、给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
• 2、把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
• 3、释放哈希表 1 的空间。

如此，就可以从哈希表 1 切换到哈希表 2，用增大的哈希表 2 保存更多数据，而原来的哈希表 1 留作下一次 rehash 扩容备用。

你肯定以为这样就完美了？但还有坑，当哈希表 1 数据量很大，如果一次性复制就会造成线程阻塞，无法服务其他请求。Redis 不允许这种事发生，因此使用了渐进式 rehash。

PS：没懂 rehash 的看旧文。旧文：《HashMap 源码解读》有详细例子解析。

2.3.2 渐进式 rehash

啥是渐进式 rehash ？

在第二步拷贝数据时，Redis 仍然正常处理客户端请求，** 每处理一个请求，顺带从哈希表 1 中的第一个索引位置开始，把这个位置上所有的 entry 复制到哈希表 2 中，下个请求就复制位置 2 **；直至全部复制完成。

过程如下图所示：

具体到代码，它的过程是这样的：

• 1、在字典中维持一个索引计数器变量 rehashidx，并将设置为 0，表示 rehash 开始。
• 2、在 rehash 期间，客户端每次对字典进行 CRUD 操作时，会将 ht [0] 中 rehashidx 索引上的值 rehash 到 ht [1]，操作完成后 rehashidx+1。
• 3、字典操作不断执行，最终在某个时间点，所有的键值对完成 rehash，这时将 rehashidx 设置为 - 1，表示 rehash 完成

说到这，你可能还有以下几点疑问？

只有在操作字典的时候才进行复制数据吗？如果客户端只操作一次字段是不是就完不成 rehash 了？

渐进式 rehash 执行时，除了根据针对字典的 CRUD 操作来进行数据迁移，Redis 本身还会有一个定时任务在执行 rehash，如果没有针对字典的请求时，这个定时任务会周期性地（例如每 100ms 一次）搬移一些数据到新的哈希表。

渐进式 rehash，CRUD 究竟在哪个哈希表操作呢？

在渐进式 rehash 过程中，字典会同时使用两个哈希表 ht [0] 和 ht [1]，所有的 CRUD 操作也会在两个哈希表进行。

比如要查找一个键时，服务器会优先查找 ht [0]，如果不存在，再查找 ht [1]。当执行新增操作时，新的键值对一律保存到 ht [1]，不再对 ht [0] 进行任何操作，以保证 ht [0] 的键值对数量只减不增，最后变为空表。

2.4 跳跃表

跳跃表在 Java 中很少接触到，大家对这个知识点也是挺陌生的。之前在学习数据结构是看到过小灰的一篇文章，写得通俗易懂，大家可以看下，建议看完再往下看。

https://mp.weixin.qq.com/s/COBdoHWDhlw4rmG_fGFhSA

跳跃表 (shiplist) 是实现 sortset (有序集合) 的底层数据结构之一；除此以外，在集群节点中也有用到它。

Redis 的跳跃表由 zskiplistNode 和  zskiplist 两个结构定义，源码位于 redis.h 文件中。

其中前者是跳跃表的结构；后者的作用是保存跳跃表的节点数量与头、尾节点的指针等信息。

typeof struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
 struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
  // 跨度
  unsigned int span;
 } level[];
} zskiplistNode;

如下图所示，展示了不同层高的跳跃表节点

typeof struct zskiplist {
    // 表头节点，表尾节点
    struct skiplistNode *header,*tail;
    // 表中节点数量
    unsigned long length;
    // 表中最大层数
    int level;
} zskiplist;

下图展示了一个跳跃表示例：

图片最左边的是 zskiplist 结构，包含：

• header：指向跳跃表的表头节点。
• tail：指向跳跃表的表尾节点。
• level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
• length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

zskiplist 结构右方的是四个 zskiplistNode 结构， 包含：

• 层：比如节点中的 L1、L2、L3 等，包括前进指针和跨度
• 前进指针：用于访问位于表尾方向的其他节点
• 跨度：记录了前进指针所指向节点和当前节点的距离
• 后退指针：指向当前节点的前一个节点，从表尾向表头遍历
• 分值：节点按各自分值从小到大排列
• 成员对象：节点所保存的成员对象

PS：跳跃表这块的内容比较多，比较难说清楚实现细节。具体的看上面的链接，以及《Redis 设计与实现》这本书（说得很好，微信读书网页版就有）

2.5 整数集合

整数集合是 Set（集合）的底层数据结构之一。当 Set 只包含整数值元素，并且这个 Set 的元素数量不多时，Redis 就会使用整数集合作为 Set 的底层实现。

Redis 使用了 intset 用于保存整数值集合，它保证了有序以及不重复。源码如下：

typeof struct intset {
    // 编码方式
    unit32_t encoding;
    // 集合包含的元素数量
    unit32_t lenght;
    // 保存元素的数组
    int8_t contents[];
} intset;

一个保存了 5 个整数的集合如下所示：

length 就不说了，主要说下 contents 和 encoding 的关系；contents 的真正类型取决于 encoding 的值：

• INTSET_ENC_INT16
• INTSET_ENC_INT32
• INTSET_ENC_INT64

这三个值分别对应 16、32、64 编码对应能存放的数字范围是不一样的。16 最小（-32768~32767），32 在中间（-2147483648~2147483647）64 最大（-9223372036854775808~9223372036854775807）。

如下图所示为 INTSET_ENC_INT16 类型集合存放 5 位整数占用的空间：16 * 5

2.5.0 升级操作

如果 contents 本来保存 1、3、5 三个整数值，后面加一个 2147483647456。

那么只有 2147483647456 是真正需要 int64_t 类型来保存的，而其他的 1、3、5 都可以用 int16_t 类型来保存；这时是整体升级，所有元素都会被升级为 int64_t 类型。

也就是说本来是 int16_t 类型的集合，要放入大于本身的整数。就需要升级，步骤如下：

• 1、根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。

• 2、将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。

• 3、将新元素添加到底层数组。

举个栗子：

1、原来是数组是 INTSET_ENC_INT16 类型 3 位，占用 48 位空间；

2、插入整数 65535，超出 INTSET_ENC_INT16 范围；升级为 INTSET_ENC_INT32 。需要的空间也从 48 加到 128 位。如下所示：新分配空间 = 128 - 48 = 80

3、元素 3 排名第三，移动到 contents 索引 2 位置；其他类似，元素 2 移动到索引 1 位置；元素 1 移动到索引 0 位置

4、最后添加新元素 65535 即可完成升级。

注意点：整数集合只支持升级、不支持降级。