Redis设计与实现-数据结构

虽然说之前也使用过Redis这个久负盛名的NoSQL数据库,但是也仅仅停留在用得阶段,并没有对其的设计原理和实现进行深究,对Redis的印象也只是停留在它是一个基于内存的k-v键值存储数据库,经常被用来做系统的缓存方案。但是知道这些对我来说并不够,便找了本书结合网上的源码一起看,本文是基于《Redis设计与实现》书籍第一部分的mini版阅读笔记,方便以后回顾。

概述

Redis数据库里面的键值对都是由对象组成的,其中:

  • 数据库键总是一个字符串对象。
  • 数据库键的值value则可以是:字符串对象、列表对象、哈希对象、集合对象、有序集合对象这五种对象中的任意一种。

第一部分主要是介绍实现五种对象的最底层数据结构,以及每种对象分别对应有哪些数据结构实现方式。

数据结构

难怪数据结构在计算机的基础学科中占据那么重要的地位,无论是数据库领域的存储还是要寻找合适的算法实现,都是跟数据结构密不可分。Redis中最底层设计的数据结构主要有:简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。下面逐一说明:

简单动态字符串(sds)

简称SDS(simple dynamic string),sds没有采用C语言中的字符串,而是自己定义了sds,在sds.h中定义的数据结构为:

1
2
3
4
5
6
7
8
9
10
struct sdshdr {
// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度
int len;
// 记录 buf 数组中未使用字节的数量
int free;
// 字节数组,用于保存字符串
char buf[];
};

c字符串与SDS字符串之间的区别如下:

c字符串 SDS
获取字符串长度的复杂度为O(N)。 获取字符串长度的复杂度为 O(1) 。
API 是不安全的,可能会造成缓冲区溢出。 API是安全的,不会造成缓冲区溢出。
修改字符串长度N次必然需要执行N次内存重分配。 修改字符串长度N次最多需要执行N次内存重分配。
只能保存文本数据。 可以保存文本或者二进制数据。
可以使用所有 string.h 库中的函数。 可以使用一部分 string.h 库中的函数。

链表(list)

链表被广泛用于实现 Redis 的各种功能, 比如列表键, 发布与订阅, 慢查询, 监视器等等。链表由链表节点组成,在adlist.h/listNode中定义了节点的数据结构,如下:

1
2
3
4
5
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;

一个链表会有许多的节点,所以只定义节点数据结构当然不行,Redis在adlist.h/list 中定义了持有链表的数据结构,这样操作链表会更加方便,代码如下:

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结构来表示,每个节点都有一个指向前置节点和后置节点的指针, 所以 Redis 的链表实现是双端链表。
  • 每个链表使用一个list结构来表示,这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL , 所以 Redis 的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数, Redis 的链表可以用于保存各种不同类型的值。

字典(dict)

字典是一种用于保存键值对的抽象数据结构,在Redis中的应用相当广泛,比如Redis的数据库就是使用字典作为底层实现的,对数据库的增删改查也是构建在对字典的操作之上的。
Redis的字典主要有哈希表实现而成,而哈希表中又有若干个哈希表节点,在dict.h/dictht 中定义了哈希表的结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;

table属性是个数组,数组每个元素都是一个指向dictEntry节点的指针,每个dictEntry保存的是一个键值对。而在dict.h/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;

当然有这些数据结构还不够,还需要对哈希表和哈希表节点进行管理,于是有字典结构,在dict.h/dict中定义了字典结构,这就如同adlist.h/list中定义了链表结构一样,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表,字典只使用ht[0],ht[1]则是在rehash的时候使用
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

如图所示为一个普通状态下的字典:

字典小结:

  • Redis 中的字典使用哈希表作为底层实现, 每个字典带有两个哈希表, 一个用于平时使用, 另一个仅在进行 rehash 时使用。
  • 当字典被用作数据库的底层实现, 或者哈希键的底层实现时, Redis 使用 MurmurHash2 算法来计算键的哈希值。
  • 哈希表使用链地址法来解决键冲突, 被分配到同一个索引上的多个键值对会连接成一个单向链表。
  • 在对哈希表进行扩展或者收缩操作时, 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面, 并且这个 rehash 过程并不是一次性地完成的, 而是渐进式地完成的。

跳表(zskiplist)

记得之前在看levelDB源码的时候,想起levelDB在内存中的memtable的核心结构就是用到了跳表,现在再看Redis的时候发现Redis的底层数据结构也用到了跳表,这里不回顾跳表算法了,只谈Redis中跳表的实现方式。
Redis中跳表的实现是由redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义, 其中 zskiplistNode 结构用于表示跳跃表节点, 而 zskiplist 结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针, 等等。
redis.h/zskiplistNode中定义的节点数据结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
// 层,每个跳表节点都会有若干层
struct zskiplistLevel {
// 指向表尾方向的前进指针
struct zskiplistNode *forward;
// 跨度,两个节点之间的距离
unsigned int span;
} level[];
} zskiplistNode;

redis.h/zskiplist中定义的跳表结构如下:

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

跳表小结:

  • 跳跃表是有序集合的底层实现之一, 除此之外它在 Redis 中没有其他应用。
  • Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成, 其中 zskiplist 用于保存跳跃表信息(比如表头节点、表尾节点、长度), 而 zskiplistNode 则用于表示跳跃表节点。
  • 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
  • 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。
  • 跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。

整数集合(instet)

当一个集合只包含整数值元素,并且这个集合元素数量不多时,redis就会使用整数集合作为集合建的底层实现。
在 intset.h/intset 中定义了一个整数集合的数据结构:

1
2
3
4
5
6
7
8
9
10
11
typedef struct intset {
// 编码方式,根据不同的编码方式来确定contents中元素的类型
uint32_t encoding;
// 集合包含的元素数量,即使contents数组的长度
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;

每当要在整数集合中添加一个整数,这个整数的类型的长度比现有的所有元素的类型长度都长时,整数集合就要进行升级(upgrade),然后才能将新元素添加到整数集合中。
整数集合小结:

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组, 这个数组以有序、无重复的方式保存集合元素,在有需要时,程序会根据新添加元素的类型, 改变这个数组的类型。
  • 升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存,因为只会在需要的时候进行升级。
  • 整数集合只支持升级操作, 不支持降级操作。

压缩列表(ziplist)

当一个列表键只包含少量列表项,而且每个列表项要么是小整数值要么就是长度比较短的字符串,那么Redis就会用压缩列表来做列表键的底层实现。
压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。
下图是压缩列表的构成部分:

zlbytes:记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配, 或者计算 zlend 的位置时使用。
zltail:记录压缩列表表尾节点距离压缩列表的起始地址有多少字节: 通过这个偏移量,程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen:当这个属性的值小于 UINT16_MAX (65535)时, 这个属性的值就是压缩列表包含节点的数量; 当这个值等于 UINT16_MAX 时, 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX:压缩列表包含的各个节点,节点的长度由节点保存的内容决定。
zlend:(十进制 255 ),用于标记压缩列表的末端。

其中,压缩列表节点的构成如下图:

previous_entry_length:以字节为单位, 记录了压缩列表中前一个节点的长度。
encoding:记录了节点的 content 属性所保存数据的类型以及长度.
content:负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的 encoding 属性决定。

压缩列表小结:

  • 压缩列表是一种为节约内存而开发的顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表, 或者从压缩列表中删除节点, 可能会引发连锁更新操作, 但这种操作出现的几率并不高。

对象

Redis 并没有直接使用上述数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象,每种对象都用到了至少一种我们前面所介绍的数据结构。
Redis 使用对象来表示数据库中的键和值,每次当我们在Redis的数据库中新创建一个键值对时, 我们至少会创建两个对象,一个对象用作键值对的键(键对象),另一个对象用作键值对的值(值对象)。Redis 中的每个对象都由一个redisObject结构表示,该结构中和保存数据有关的三个属性分别是 type 属性、 encoding 属性和 ptr 属性:

1
2
3
4
5
6
7
8
9
typedef struct redisObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 指向底层实现数据结构的指针
void *ptr;
// ...
} robj;

字符串对象

字符串对象的编码可以是 int 、 raw 或者 embstr 。其中对于int编码的字符串对象的一些操作可以int编码转换为raw编码,比如APPEND命令,embstr也是如此。
说一下三种字符串编码方式的区别:如果一个字符串对象保存的是整数值,则直接用int编码;如果一个字符串对象保存的是字符串值,但是长度大于等于39,则用raw编码;否则长度小于39就用embstr编码。

列表对象

列表对象的编码可以是 ziplist(压缩列表) 或者 linkedlist(链表) 。
当列表对象可以同时满足以下两个条件时, 列表对象使用 ziplist 编码:

  1. 列表对象保存的所有字符串元素的长度都小于 64 字节;
  2. 列表对象保存的元素数量小于 512 个;
    不能满足这两个条件的列表对象需要使用 linkedlist 编码。

    哈希对象

    哈希对象的编码可以是 ziplist 或者 hashtable 。
    ziplist 编码的哈希对象使用压缩列表作为底层实现, 每当有新的键值对要加入到哈希对象时,程序会先将保存了键的压缩列表节点推入到压缩列表表尾,然后再将保存了值的压缩列表节点推入到压缩列表表尾。如下图所示:

    hashtable 编码的哈希对象使用字典作为底层实现,哈希对象中的每个键值对都使用一个字典键值对来保存,如下图所示:

当哈希对象可以同时满足以下两个条件时, 哈希对象使用 ziplist 编码:

  1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节;
  2. 哈希对象保存的键值对数量小于 512 个;
    不能满足这两个条件的哈希对象需要使用 hashtable 编码。

集合对象

集合对象的编码可以是 intset 或者 hashtable 。
intset 编码的集合对象使用整数集合作为底层实现,集合对象包含的所有元素都被保存在整数集合里面。
另一方面, hashtable 编码的集合对象使用字典作为底层实现, 字典的每个键都是一个字符串对象, 每个字符串对象包含了一个集合元素, 而字典的值则全部被设置为 NULL ,意思就是只保留key而不需要value。

当集合对象可以同时满足以下两个条件时, 对象使用 intset 编码:

  1. 集合对象保存的所有元素都是整数值;
  2. 集合对象保存的元素数量不超过 512 个;
    不能满足这两个条件的集合对象需要使用 hashtable 编码。

有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist 。
ziplist 编码的有序集合对象使用压缩列表作为底层实现,每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),而第二个元素则保存元素的分值(score)。
压缩列表内的集合元素按分值从小到大进行排序,分值较小的元素被放置在靠近表头的方向,而分值较大的元素则被放置在靠近表尾的方向。
skiplist 编码的有序集合对象使用zset结构作为底层实现,一个zset结构同时包含一个字典和一个跳跃表:

1
2
3
4
5
6
typedef struct zset {
zskiplist *zsl;//保证有序性
dict *dict;//保证获取某个对象以O(1)的时间复杂度
} zset;

使用跳表和dict字典两种数据结构的有序集合对象,兼具了跳表和字典两种数据结构的优点特性,由于会共享元素的成分和分值,所以也不会出现内存浪费。

当有序集合对象可以同时满足以下两个条件时, 对象使用 ziplist 编码:

  1. 有序集合保存的元素数量小于 128 个;
  2. 有序集合保存的所有元素成员的长度都小于 64 字节;
    不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

内存回收

C语言本身不具备内存回收,Redis 在自己的对象系统中构建了一个引用计数(reference counting)技术实现的内存回收机制,通过这一机制,程序可以通过跟踪对象的引用计数信息,在适当的时候自动释放对象并进行内存回收。redis通过redisObject中的refcount属性维护这一特性:

1
2
3
4
5
typedef struct redisObject {
// ...
// 引用计数
int refcount;
} robj;

当创建对象时,refcount等于1,当对象被另外一个新对象用时,加1,不再被新对象用时减1,引用值为0时,对象占用的内存会被释放。

对象共享

除了用于实现引用计数内存回收机制之外, 对象的引用计数属性还带有对象共享的作用。
在 Redis 中, 让多个键共享同一个值对象需要执行以下两个步骤:

  1. 将数据库键的值指针指向一个现有的值对象;
  2. 将被共享的值对象的引用计数增一。

共享对象机制对于节约内存非常有帮助,数据库中保存的相同值对象越多,对象共享机制就能节约越多的内存。
共享对象和目标对象完全相同的情况下,程序才会将共享对象用作键的值对象,而一个共享对象保存的值越复杂,验证共享对象和目标对象是否相同所需的复杂度就会越高,消耗的 CPU 时间也会越多,因此尽管共享更复杂的对象可以节约更多的内存,Redis 只对包含整数值的字符串对象进行共享。

最后

本文大部分内容来自于原书籍的节选,所以如果想知道更详细内容可以直接阅读书籍。

-EOF-