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

付威

发布于 2021-01-28 09:55:01

6600

发布于 2021-01-28 09:55:01

文章被收录于专栏：老付的网络博客老付的网络博客

简单的字符串

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 数据结构

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

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

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

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

2.1 优化追加操作

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

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 ，追加后结构体的数据为：

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

3. 双端链表

3.1 实现 Redis 的列表类型

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

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

双端链表
压缩列表

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

双端链表的实现

listNode 节点的数据结构

typedef struct listNode { 
    // 前驱节点
  struct listNode *prev; 
    // 后继节点
  struct listNode *next; 
    // 值
  void *value; 
} listNode;

双端链表本身

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) 清空节点的值，再执行余下的删除操作(比如说，释放节点)

迭代器

typedef struct listIter { 
  // 下一节点
    listNode *next;
// 迭代方向 
    int direction;
  } listIter;

如果值为adlist.h/AL_START_HEAD，那么迭代器执行从表头到表尾的迭代;
如果值为adlist.h/AL_START_TAIL，那么迭代器执行从表尾到表头的迭代;

4. 字典

4.1 字典的结构实现

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

字典;
压缩列表

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

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

数据结构

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

Dicht 的实现

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

dictEntry 数据结构

/*
* 哈希表节点 */
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 采用 hash 算法

redis 采用的 hash 算法有两种：

MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好，具体信息请参考 Mur- murHash 的主页:http://code.google.com/p/smhasher/ 。
基于 djb 算法实现的一个大小写无关散列算法:具体信息请参考

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

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

添加新 key 的过程

4.2 字典的Rehash

为什么要进行 rehash

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

比率在 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 会为假？

当 Redis 使用子进程对数据库执行后台持久化任务时（比如执行 BGSAVE 或 BGREWRITEAOF 时），为了最大化地利用系统的 ==copy_on_write== 机制，程序会暂时将 dict_can_resize 设为假，避免执行自然 rehash ，从而减少程序对内存的触碰（touch）。
当持久化任务完成之后， dict_can_resize 会重新被设为真。另一方面，当字典满足了强制 rehash 的条件时，即使 dict_can_resize 不为真（有 BGSAVE 或 BGREWRITEAOF 正在执行），这个字典一样会被 rehash 。

4.3 Rehash 的步骤

创建一个比 ht[0]->table 更大的 ht[1]->table ；
- 设置字典的 rehashidx 为 0 ，标识着 rehash 的开始；
- 为 ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍；

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

将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；
- 释放 ht[0] 的空间；
- 用 ht[1] 来代替 ht[0] ，使原来的 ht[1] 成为新的 ht[0] ；
- 创建一个新的空哈希表，并将它设置为 ht[1] ；
- 将字典的 rehashidx 属性设置为 -1 ，标识 rehash 已停止；

4.4 渐进式 rehash

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

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

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

渐进式 Rehash 的过程

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

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

_dictRehashStep

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

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

2. dictRehashMilliseconds 步骤

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

字典的收缩

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

创建一个比 ht[0]->table 小的 ht[1]->table ；
将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
将原有 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 基本数据结构

typedef struct zskiplist {
  // 头节点，尾节点
  struct zskiplistNode *header, *tail;
  // 节点数量
  unsigned long length;
  // 目前表内节点的最大层数
  int level;
} zskiplist;

typedef struct zskiplistNode {
  // member 对象
  robj *obj;
   // 分值
  double score;
   // 后退指针
  struct zskiplistNode *backward;
   // 层
  struct zskiplistLevel {
   // 前进指针
  struct zskiplistNode *forward;
    // 这个层跨越的节点数量
   unsigned int span;
  } level[];
} zskiplistNode;

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

允许重复的 score 值：多个不同的 member 的 score 值可以相同。
进行对比操作时，不仅要检查 score 值，还要检查 member ：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。
每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代：当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。