Redis底层原理--01. Redis 中的数据结构

发表于 分类于

简单的字符串

1. 设计要点

在 C 语言中，字符串可以用一个 \0 结尾的 char 数组来表示。 比如说，hello world 在 C 语言中就可以表示为 “hello world\0” 。

这种简单的字符串表示在大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和 追加(append)这两种操作:

  • 每次计算字符串长度(strlen(s))的复杂度为 θ(N) 。

  • 对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配(realloc)。

在 Redis 内部，字符串的追加和长度计算并不少见，而 APPEND 和 STRLEN 更是这两种操 作在 Redis 命令中的直接映射，这两个简单的操作不应该成为性能的瓶颈。

另外，Redis 除了处理 C 字符串之外，还需要处理单纯的字节数组，以及服务器协议等内容， 所以为了方便起见，Redis 的字符串表示还应该是二进制安全的:程序不应对字符串里面保存 的数据做任何假设，数据可以是以 \0 结尾的 C 字符串，也可以是单纯的字节数组，或者其他 格式的数据。

考虑到这两个原因，Redis 使用 sds 类型替换了 C 语言的默认字符串表示: sds 既可以高效地 实现追加和长度计算，并且它还是二进制安全的。

2. sds 数据结构

1
2
3
4
5
6
7
8
9
typedef char *sds; 
struct sdshdr {
  // buf 已占用长度 
  int len;
  // buf 剩余可用长度 
  int free;
  // 实际保存字符串数据的地方
  char buf[]; 
};

执行 set msg "hello world" 后的数据结构：

1
2
3
4
5
6
7
struct sdshdr { 
  len = 11; 
  free = 0;
  buf = "hello world\0"; 
  // buf 的实际长度为
  len + 1 
};

通过 len 属性，sdshdr 可以实现复杂度为 θ(1) 的长度计算操作。

2.1 优化追加操作

当再次执行 append msg "again!" 时，对应的数据结构：

1
2
3
4
5
6
struct sdshdr { 
  len = 18;
  free = 18;
// 空白的地方为预分配空间，共 18 + 18 + 1 个字节 
  buf = "hello world again!\0 ";
}

当调用 SET 命令创建 sdshdr 时，sdshdr 的 free 属性为 0 ，Redis 也没有为 buf 创建 额外的空间

当执行 APPEND 命令的时候，Redis 为 bugf 创建了多于一倍的空间大小。

在上面的例子中，”hello world again!\0 “ 一共是 18+1 个字节，但是 Redis 为我们分配了 18+18+1 =37 个字节，这样做的好处是对同一个 sdshdr 进行追加操作，如果追加的长度不超过 free 的长度，则不用再次分配空间。

等到关闭 Redis 之后，再次启动时重新载入的字符串对象将不会再有预分配空间

如果再次执行 APPEND msg " again!" 则不会重新分配 buf 内存，因为追加的长度小于 18 ，追加后结构体的数据为：

1
2
3
4
5
6
struct sdshdr { 
 len = 25;
 free = 11;
 // 空白的地方为预分配空间，共 18 + 18 + 1 个字节 
 buf = "hello world again! again!\0 ";
}

3. 双端链表

3.1 实现 Redis 的列表类型

比如执行 RPUSH 、LPOP 或 LLEN 等命令时，程序在底层操作的可能就是双端链表。

Redis 列表使用两种数据结构作为底层实现:

  1. 双端链表

  2. 压缩列表

使用双端链表的占用的内存比压缩列表要多，所以创建是会优先使用压缩列表，在具体需要场景 转化成双端链表。

双端链表的实现

Redis数据结构

listNode 节点的数据结构

1
2
3
4
5
6
7
8
typedef struct listNode { 
    // 前驱节点
  struct listNode *prev; 
    // 后继节点
  struct listNode *next; 
    // 值
  void *value; 
} listNode;

双端链表本身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct list { 
    // 表头指针
  listNode *head; 
    // 表尾指针
  listNode *tail; 
    // 节点数量
  unsigned long len;
  // 复制函数
  void *(*dup)(void *ptr);
  // 释放函数
  void (*free)(void *ptr);
  // 比对函数
  int (*match)(void *ptr, void *key);
} list;

当删除一个 listNode 时，如果包含这个节点的 list 的 list->free 函数不为空， 那么删除函数就会先调用 list->free(listNode->value) 清空节点的值，再执行余下的删除 操作(比如说，释放节点)

迭代器

1
2
3
4
5
6
typedef struct listIter { 
  // 下一节点
    listNode *next;
// 迭代方向 
    int direction;
  } listIter;
  • 如果值为adlist.h/AL_START_HEAD，那么迭代器执行从表头到表尾的迭代;
  • 如果值为adlist.h/AL_START_TAIL，那么迭代器执行从表尾到表头的迭代;

4. 字典

4.1 字典的结构实现

Redis 的 Hash 类型键使用以下两种数据结构作为底层实现:

  1. 字典;

  2. 压缩列表

因为压缩列表比字典更节省内存，所以程序在创建新 Hash 键时，默认使用压缩列表作为底层

实现，当有需要时，程序才会将底层实现从压缩列表转换到字典

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 字典
*
* 每个字典使用两个哈希表，用于实现渐进式 rehash */
typedef struct dict {
// 特定于类型的处理函数
 dictType *type;
// 类型处理函数的私有数据
 void *privdata; // 哈希表(2 个)
 dictht ht[2];
// 记录 rehash 进度的标志，值为-1 表示 rehash 未进行
 int rehashidx;
// 当前正在运作的安全迭代器数量
 int iterators; 
} dict;

Dicht 的实现

1
2
3
4
5
6
7
8
9
10
/*
* 哈希表 */
typedef struct dictht {
// 哈希表节点指针数组(俗称桶，bucket)
dictEntry **table; // 指针数组的大小
unsigned long size;
// 指针数组的长度掩码，用于计算索引值
unsigned long sizemask; // 哈希表现有的节点数量
unsigned long used; 
} dictht;

dictEntry 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* 哈希表节点 */
typedef struct dictEntry {
// 键
void *key;
 // 值 
union {
  void *val; 
  uint64_t u64; 
  int64_t s64;
} v;
// 链往后继节点
struct dictEntry *next;
} dictEntry;

next 属性指向另一个 dictEntry 结构，多个 dictEntry 可以通过 next 指针串连成链表，从 这里可以看出，dictht 使用 链地址法 来处理键碰撞:当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。

图示哈希表的结构

Redis数据结构

Redis数据结构

Redis 采用 hash 算法

redis 采用的 hash 算法有两种：

  1. MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好，具体信息请参考 Mur-

    murHash 的主页:http://code.google.com/p/smhasher/ 。

  2. 基于 djb 算法实现的一个大小写无关散列算法:具体信息请参考

​ http://www.cse.yorku.ca/~oz/hash.html 。 使用哪种算法取决于具体应用所处理的数据:

  • 命令表以及 Lua 脚本缓存都用到了算法 2 。
  • 算法 1 的应用则更加广泛:数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。

添加新 key 的过程

Redis数据结构

4.2 字典的Rehash

  1. 为什么要进行 rehash

对于使用链地址法来解决碰撞问题的哈希表 dictht 来说，哈希表的性能依赖于它的大小（size
属性）和它所保存的节点的数量（used 属性）之间的比率：

  • 比率在 1:1 时，哈希表的性能最好；
  • 如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表
    本身的性能优势就不再存在；
  1. rehash 条件

dictAdd 在每次向字典添加新键值对之前，都会对哈希表 ht[0] 进行检查，对于 ht[0] 的
size 和 used 属性，如果它们之间的比率 ratio = used / size 满足以下任何一个条件的话，
rehash 过程就会被激活：

  • 自然 rehash ： ratio >= 1 ，且变量 dict_can_resize 为真
  • 强 制 rehash ： ratio 大 于 变 量 dict_force_resize_ratio （目 前 版 本 中，
    dict_force_resize_ratio 的值为 5 ）

Note: 什么时候 dict_can_resize 会为假？

  1. 当 Redis 使用子进程对数据库执行后台持久化任务时（比如执行 BGSAVE
    或 BGREWRITEAOF 时）， 为了最大化地利用系统的 ==copy_on_write== 机制， 程序会暂时将
    dict_can_resize 设为假，避免执行自然 rehash ，从而减少程序对内存的触碰（touch）。

  2. 当持久化任务完成之后， dict_can_resize 会重新被设为真。
    另一方面，当字典满足了强制 rehash 的条件时，即使 dict_can_resize 不为真（有 BGSAVE
    或 BGREWRITEAOF 正在执行），这个字典一样会被 rehash 。

4.3 Rehash 的步骤

  1. 创建一个比 ht[0]->table 更大的 ht[1]->table ；

    • 设置字典的 rehashidx 为 0 ，标识着 rehash 的开始；

    • 为 ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍；

    Screen Shot 2020-11-15 at 22.04.07

  2. 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；

    Redis数据结构

  3. 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；

    • 释放 ht[0] 的空间；

    • 用 ht[1] 来代替 ht[0] ，使原来的 ht[1] 成为新的 ht[0] ；

    • 创建一个新的空哈希表，并将它设置为 ht[1] ；

    • 将字典的 rehashidx 属性设置为 -1 ，标识 rehash 已停止；

    Redis数据结构

4.4 渐进式 rehash

rehash 程序并不是在激活之后就马上执行直到完成的，而是分多次、渐进式地完成的。

假设这样一个场景：在一个有很多键值对的字典里，某个用户在添加新键值对时触发了 rehash
过程，如果这个 rehash 过程必须将所有键值对迁移完毕之后才将结果返回给用户，这样的处理
方式将是非常不友好的。

另一方面，要求服务器必须阻塞直到 rehash 完成，这对于 Redis 服务器本身也是不能接受的。
为了解决这个问题， Redis 使用了渐进式（incremental）的 rehash 方式：通过将 rehash 分散
到多个步骤中进行，从而避免了集中式的计算。

渐进式 Rehash 的过程

渐进式 rehash 主要由 _dictRehashStep 和 dictRehashMilliseconds 两个函数进行：

  • _dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash ；
  • dictRehashMilliseconds 则由 Redis 服务器常规任务程序（server cron job）执行，用
    于对数据库字典进行主动 rehash ；
  1. _dictRehashStep

每次执行 _dictRehashStep ， ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全
部迁移到 ht[1]->table 。

Redis数据结构

因为字典会保持哈希表大小和节点数的比率在一个很小的范围内，所以每个索引上的节点数量
不会很多（从目前版本的 rehash 条件来看，平均只有一个，最多通常也不会超过五个），所以
在执行操作的同时，对单个索引上的节点进行迁移，几乎不会对响应时间造成影响

2. dictRehashMilliseconds 步骤

当 Redis 的服务器常规任务执行时， dictRehashMilliseconds 会被执行，在规定的时间内，
尽可能地对数据库字典中那些需要 rehash 的字典进行 rehash ，从而加速数据库字典的 rehash
进程（progress）

字典的收缩

收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样，它执行以下步骤：

  1. 创建一个比 ht[0]->table 小的 ht[1]->table ；
  2. 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
  3. 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；
    扩展 rehash 和收缩 rehash 执行完全相同的过程，一个 rehash 是扩展还是收缩字典，关键在于
    新分配的 ht[1]->table 的大小：
  • 如果 rehash 是扩展操作，那么 ht[1]->table 比 ht[0]->table 要大；
  • 如果 rehash 是收缩操作，那么 ht[1]->table 比 ht[0]->table 要小；

在默认情况下， REDIS_HT_MINFILL 的值为 10 ，也即是说，当字典的填充率低于 10% 时，程
序就可以对这个字典进行收缩操作了

字典的迭代

字典带有自己的迭代器实现——对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：

  • 迭代器首先迭代字典的第一个哈希表，然后，如果 rehash 正在进行的话，就继续对第二
    个哈希表进行迭代。
  • 当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
  • 当这个索引迭代完了，继续查找下一个不为空的索引，如此循环，一直到整个哈希表都迭
    代完为止

字典的迭代器有两种：

  • 安全迭代器：在迭代进行过程中，可以对字典进行修改。
  • 不安全迭代器：在迭代进行过程中，不对字典进行修改

5. 跳跃表

5.1 基本数据结构

Redis数据结构

1
2
3
4
5
6
7
8
9
10
typedef struct zskiplist {
  // 头节点，尾节点
  struct zskiplistNode *header, *tail;
  // 节点数量
  unsigned long length;
  // 目前表内节点的最大层数
  int level;
} zskiplist;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct zskiplistNode {
  // member 对象
  robj *obj;
   // 分值
  double score;
   // 后退指针
  struct zskiplistNode *backward;
   // 层
  struct zskiplistLevel {
   // 前进指针
  struct zskiplistNode *forward;
    // 这个层跨越的节点数量
   unsigned int span;
  } level[];
} zskiplistNode;

为了适应 Redis 需要，对原生的跳跃表做了修改：

  1. 允许重复的 score 值：多个不同的 member 的 score 值可以相同。

  2. 进行对比操作时，不仅要检查 score 值，还要检查 member ：当 score 值可以重复时，
    单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。

  3. 每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代：当执行
    ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到
    这个属性。

5.2 跳跃表的应用

跳跃表在 Redis 的唯一作用，就是实现有序集数据类型 — sortedset ，其中跳跃表的数据结构如下：

Redis数据结构