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

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

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

http://blog.laofu.online/2020-11-27-redis-01/

作者

付威

发布于

2020-11-27

更新于

2020-11-27

许可协议

评论