前言

Redis是一个K/V类型的数据库,Key的类型就是字符串,而Value可以支持不同类型,不仅限于简单的字符串,以下将分别介绍五种简单的数据类型中的数据结构:

  • 二进制安全的字符串
  • 列表,基于插入顺序进行排序的元素列表,一般会基于链表实现
  • 哈希,每个字段关联一个value,字段和value都是string类型
  • 集合,保存没有重复值的元素集合,元素中没有顺序
  • 有序集合,与集合类似,但每个元素都与一个 score 的值关联,元素总是按照score字段来进行排序,因此可以获取最大的10个元素或是最小的10个元素等等操作。

字符串

Redis中的每个键值对,其实就是一个 dictEntry 结构,其中保存了key和value的指针,代码如下:

1
2
3
4
5
6
7
8
typedef struct dictEntry {
void *key; /* key */
union {
void *val; uint64_t u64; /* value */
int64_t s64; double d;
} v;
struct dictEntry *next;
} dictEntry;

key的类型就是字符串,其指向的是Redis自定义的SDS类型,Redis基于C语言的字符数组简单实现了一个字符串的类型。

而value的类型并不会直接指向SDS或是其他具体类型,而是一个 redisObject 类型,在这五种常用类型中,都是通过 redisObject 来存储的。

redisObject 的定义代码如下:

1
2
3
4
5
6
7
typedef struct redisObject {
unsigned type:4; /* 对象的类型,例如:OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET */
unsigned encoding:4; /* 数据结构内部编码 */
unsigned lru:LRU_BITS; /* 与内存回收相关 */
int refcount; /* 引用计数。*/
void *ptr; /* 指向对象实际的数据结构 */
} robj;

字符串的内部编码有三种:

  1. int,存储8个字节的整数值
  2. embstr,存储小于44个字节的字符串
  3. raw,存储大于44字节的字符串

当使用 embstr 编码时,只需一次内存分配函数来分配一个连续的内存空间,在这个连续的内存空间中同时包含了 redisObject 和 SDS 两个结构,而 raw 编码需要两次内存分配来分别创建。同理,在释放内存空间时,embstr 仅需要释放一次,而 raw 编码需要调用两次释放函数。

但是对于 embstr 编码的字符串对象来讲,只要这个字符串被修改了,字符串对象就会将编码转为 raw ,也就是说,embstr 编码的字符串对象实际上是只读的。

而对于 int 编码的字符串对象,如果字符串对象被修改后不再是整数值,则编码同样会转为 raw 的字符串对象。

SDS

Redis没有使用C语言的字符数组作为字符串的实现,而是自定义了简单动态字符串(simple dynamic string),简称为SDS,Redis使用SDS作为字符串的实现。

在C语言中,如果使用字符数组实现长度为N的字符串,就需要使用长度N+1的字符数组来表示,且字符数组的最后一个元素必须是空字符 \0

而Redis的SDS结构还是遵循C语言字符串中以空字符 \0 结尾的惯例,但这一字节的空间不会被计算到使用字符串的长度中,SDS的结构如下:

1
2
3
4
5
struct sdshdr { 
int len; /* 记录 buf 数组中已使用字节的数量,也就是字符串的长度 */
int free; /* 记录 buf 数组中未使用字节的数量 */
char buf[]; /* 保存字符串的字节数组 */
};

使用SDS存储字符串的好处有以下几点:

  1. 字符串长度可以直接获取

    在字符数组中,无法记录字符串的长度信息,所以获取字符串的长度需要遍历整个字符数组进行计数,直到遇到空字符串结尾为止,而SDS结构中的len属性记录了长度信息,字符串长度可以直接进行获取。

  2. 不会造成缓冲区溢出

    字符数组的另一个问题则是,如果没有为该字符数组分配足够的空间,直接在数组末尾拼接字符串的话,可能会造成缓冲区溢出的错误。而SDS的空间分配策略会对分配空间进行检查,如果空间不足则会直接进行扩展。

  3. 二进制安全

    字符数组以空字符串结尾,这导致了C语言字符串不能直接保存音频数据,否则第一个被读到的空字符串就将直接被认为是字符串的结尾。而SDS的API都会以处理二进制的方式来处理字符数组中的数据。

  4. 减少内存重分配

    字符数组的空间总是预先分配好的,每次对字符串的增加或减少,都会对这个数组的空间大小进行一次扩展或是释放的操作。在SDS中,字符数组可以预先分配空间,由len字段记录已经使用的空间,由free字段记录未使用的空间。SDS由此实现了空间预分配和惰性空间释放的策略。

    空间预分配

    对SDS进行修改时,如果需要进行空间扩展,除了分配所需的空间,还会对SDS分配额外不使用的空间,由此策略减少了对字符串进行连续增长操作时所需的内存重分配次数。

    惰性空间释放

    当SDS需要缩短字符串长度时,程序不会立刻将这些内存进行回收,而是使用free字段将字节数量记录以便后续使用,且SDS的API也可以直接释放该属性中的未使用空间。

SDS与字符数组对比

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

列表

列表类型存储了一个有序的字符串列表,可以用来充当队列或是栈,关于列表的操作命令可以查看Redis命令参考

Redis 中的列表使用 quicklist 结构来存储, quicklist 存储了一个双向链表,其中的每个节点结构是 ziplist。

quicklist 的结构如下:

1
2
3
4
5
6
7
8
typedef struct quicklist { 
quicklistNode *head; /* 链表头指针 */
quicklistNode *tail; /* 链表尾指针 */
unsigned long count; /* 所有的 ziplist 存储的元素数量 */
unsigned long len; /* 节点数量,也就是链表的长度 */
int fill : 16;
unsigned int compress : 16;
} quicklist;

quicklistNode 的结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct quicklistNode { 
struct quicklistNode *prev; /* 上一个节点 */
struct quicklistNode *next; /* 下一个节点 */
unsigned char *zl; /* 指向 ziplist */
unsigned int sz; /* ziplist 占用了多少字节 */
unsigned int count : 16;
unsigned int encoding : 2;
unsigned int container : 2;
unsigned int recompress : 1;
unsigned int attempted_compress : 1;
unsigned int extra : 10;
} quicklistNode;

quicklistNode 中实际存储的数据是指向了一个 ziplist 结构,列表的存储结构如下图所示:

ziplist

ziplist.c 的文件头部注释中,对ziplist的做出如下解释:

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time.

ziplist 是一个双向链表 ,但 ziplist 为了提高存储效率,是存储在连续的内存空间中的;并且对于值的存储,不同长度的值需要存储的字节数也不同,也就是说,对于大一些的值,就多用一些字节来存储,而对于小一些的值,则就可以少用一些字节来存储;ziplist 中的每个节点通过存储上一个节点的长度和当前节点的长度来实现这种功能。

一个 ziplist 可以包含任意数量的节点 (entry),每个节点都可以保存一个字节数组或整数值。ziplist 的各个组成部分如下:

1
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
属性 说明
zlbytes 记录 ziplist 总使用的内存字节数。
zltail 记录 ziplist 表尾节点距离 ziplist 的起始地址有多少字节,这使得不需要遍历整个 ziplist 就可以确定表尾节点的地址。
zllen 记录 ziplist 的节点数量, 当这个值等于 UINT16_MAX (65535) 时, 节点的真实数量需要遍历整个ziplist 才能得出。
entry ziplist 的节点,节点的长度由节点保存的内容决定。
zlend 特殊值 0xFF(十进制 255 ),用于标记 ziplist 的末端。

哈希

哈希类型存储了无序的散列表,每个字段可以有一个对应的值,但其值只能是字符串类型,存储内容如下:

哈希可以使用两种数据结构来实现,分别是 ziplisthashtable

ziplist

ziplist 在上面存储列表类型时已经有所介绍,但 ziplist 也可以用来作为哈希类型的实现,当有新的键值对加入哈希对象中时,先将键的 ziplist 节点推入到 ziplist 的表尾,然后再将值的 ziplist 节点推入到 ziplist 表尾。

也就是说同一个键值对的两个 ziplist 节点肯定是紧挨在一起的两个节点,键节点在前,值节点在后;且键值对会按照添加顺序依次排在上一个键值对的后面。

只有当哈希对象满足以下两个条件时,哈希对象才会使用 ziplist 编码:

  1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节;
  2. 哈希对象保存的键值对数量小于512 个;

不满足这两个条件时,哈希对象使用 hashtable 编码存储,这两个条件的上限可以通过 redis 的配置文件更改。

hashtable

hashtable 是作为字典保存键值对的数据结构;在字典中,每一个键都可以和一个值进行关联,这些关联的键和值就被成为键值对。

字典中的每个键都是不允许重复的,我们可以根据键来查找与之对应的值进行更新或删除等相关操作。

哈希表的结构如下:

1
2
3
4
5
6
typedef struct dictht {
dictEntry **table; /* 哈希表数组 */
unsigned long size; /* 哈希表大小 */
unsigned long sizemask; /* 掩码大小,用于计算索引值。总是等于 size-1 */
unsigned long used; /* 已有节点数量 */
} dictht;

哈希表节点 dictEntry 结构如下:

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry { 
void *key; /* 键 */
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; /* 值 */
struct dictEntry *next; /* 指向下一个节点 */
} dictEntry;

当发生哈希键冲突时,多个键值对会形成链表,新节点会被添加到表头,然后将 next 指针指向原表头。

字典结构如下:

1
2
3
4
5
6
typedef struct dict { 
dictType *type; /* 类型 */
void *privdata; /* 私有数据 */
dictht ht[2]; /* 哈希表 */
long rehashidx; /* rehash 索引,rehash 不在进行时,值为 -1 */
} dict;

在字典结构中,ht 属性是一个长度为2的数组,其包含了两个哈希表,一般情况下字典只会使用 ht[0] 作为哈希表使用,而 ht[1] 的哈希表只会在对 ht[0] 的哈希表进行 rehash 时使用。

rehashidx 属性记录了 rehash 的进度, 如果当前没有进行 rehash , 那么它的值为 -1 。

也就是说,字典的总体结构如下图所示:

rehash

随着哈希表中保存的键值对逐渐的增多或减少,为了让哈希表的负载因子维持在一个合理的范围内,需要对哈希表进行扩展或收缩;这个过程通过 rehash 完成,rehash的大致步骤如下:

  1. 为字典的 ht[1] 上的哈希表分配空间,空间的大小是2的n次方 。
  2. 将 ht[0] 中的所有键值对 rehash 到 ht[1] 上, rehash 指重新计算键的哈希值和索引值, 然后将键值对放置到 ht[1] 上的哈希表指定位置上。
  3. 当 ht[0] 的所有键值对迁移到 ht[1] 之后,释放 ht[0] , 将 ht[1] 设置为 ht[0] , 并在 ht[1] 新创建一个空白哈希表。

rehash 是分多次进行的,这是为了避免对服务器的性能造成过大的影响,所以 rehash 的详细步骤如下:

  1. 为字典的 ht[1] 上的哈希表分配空间,空间的大小是2的n次方;此时字典还是持有 ht[0] 上的哈希表 。
  2. 将索引计数器变量 rehashidx 的值设置为 0 ,表示 rehash 工作开始。
  3. 在 rehash 期间, 每次对字典执行增删改查操作时, 会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 将 rehashidx 属性的值加一。
  4. 随着字典操作的不断执行,ht[0] 上的所有键值对都会被 rehash 至 ht[1] ,最终将 rehashidx 属性的值设为 -1 , 表示 rehash 操作完成。

这种操作将 rehash 所需要的计算工作量分摊到了每次对字典的增删改查操作中,避免了集中式 rehash 带来的庞大计算量从而影响服务器的性能;在 rehash 过程中,字典会同时使用 ht[0] 和 ht[1] 两个哈希表,新添加的键值对只会被保存到 ht[1] 中,查找键的过程则会同时查找两个哈希表。

集合

集合类型中的元素为 String 类型的字符串,且在集合中不包含重复项;当集合中的元素类型都是整数时,集合类型使用 intset 编码的整数集合来存储元素,否则使用 hashtable 编码的字典来存储元素。

hashtable

使用字典类型来存储集合元素时,字典中的每个键都是一个集合元素,而字典的值被设置为NULL。

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

  1. 集合对象中保存的所有元素都是整数值;
  2. 集合对象中保存的元素数量没有超过 512 个;

没有满足这两个条件的集合对象则使用 hashtable 编码,并且在使用 intset 编码时,有任意一个条件不能满足时,则会执行对象的编码转换操作,将 intset 编码转换为 hashtable 编码 。这两个条件的上限可以通过配置文件更改。

intset

整数集合作为集合中只保存了整数且元素数量不多时的实现,结构如下:

1
2
3
4
5
typedef struct intset {
uint32_t encoding; /* 编码方式 */
uint32_t length; /* 元素数量 */
int8_t contents[]; /* 元素数组 */
} intset;

整数集合的元素实际就存储在了 contents 数组中。

有序集合

有序的集合对象,集合中的元素都有 score 属性作为排序依据,有序集合的编码为 ziplistskiplist

ziplist

使用 ziplist 作为有序集合的实现时,每个集合元素使用两个紧挨的 ziplist 节点保存,第一个节点保存元素信息,第二个节点则保存元素的 score。

在 ziplist 中,根据元素的 score 进行排序,score 越小的节点,则越靠近表头,当有更小的节点插入时,需要移动节点。

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

  1. 有序集合保存的所有元素的长度都小于 64 字节;
  2. 有序集合对象保存的元素数量小于 128 个;

不满足这两个条件时,哈希对象使用 skiplist 编码存储,这两个条件的上限可以通过配置文件更改。

skiplist

skiplist 编码的有序集合对象使用 zset 结构作为底层实现, 一个 zset 结构同时包含一个字典和一个跳跃表:

1
2
3
4
typedef struct zset {
zskiplist *zsl; /* 跳跃表 */
dict *dict; /* 字典 */
} zset;

跳跃表是一种支持平均 O(log N) 最坏 O(N) 复杂度的节点查找的有序数据结构,且在大部分情况下跳跃表的性能可以和平衡树相比较。

在 redis 中,跳跃表的结构由 zskiplistNode 和 zskiplist 组成,其组成如下图:

zskiplist 的结构如下:

1
2
3
4
5
typedef struct zskiplist {
struct zskiplistNode *header, *tail; /* 表头和表尾节点 */
unsigned long length; /* 节点数量 */
int level; /* 最大层数 */
} zskiplist;

zskiplistNode 的结构如下:

1
2
3
4
5
6
7
8
9
10
typedef struct zskiplistNode {
struct zskiplistNode *backward; /* 后退指针 */
double score; /* 分值 */
robj *obj; /* 元素 */

struct zskiplistLevel {
struct zskiplistNode *forward; /* 前进指针*/
unsigned int span; /* 跨越的节点数 */
} level[]; /* 层 */
} zskiplistNode;

除了跳跃表,zset 中的字典结构还保存了每个元素对应 score 的映射;通过字典,在查找元素对应的 score 时就可以直接从字典中返回,虽然元素同时在跳跃表和字典中同时保存,但这两种数据结构通过指针共享了相同元素的对象,因此并不会浪费额外的内存。