1. 数据结构与对象

1.1 简单动态字符串(SDS)

Redis没有使用C语言传统的字符串表示,而是构建了一种简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。Redis只会使用C字符串作为字面量。
除了用来保存数据库中的字符串值之外,SDS还被用做缓冲区(buffer): AOF模块中的AOF缓冲区,以及客户端状态中的输入缓冲区,都是SDS实现的。

在计算机科学中,字面量(literal)是用于表达源代码中一个固定值的表示法(notation)。

1.1.1 SDS的定义

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

SDS示例

SDS遵循C字符串以空字符结尾的惯例,保存空字符的1字节空间不计算在SDS的len属性里面。

1.1.2 与C字符串的区别

  1. 获取字符串长度复杂度:C字符串不记录长度信息,所以获取字符串长度复杂度为O(N),SDS为O(1)。
  2. 杜绝缓冲区溢出:strcat函数可以将src字符串中的内容拼接到dest字符串的末尾:
    char *strcat(char *dest, const char *src)
    因为C字符创不记录自身的长度,所以strcat假定用户在执行这个函数时,已经为dest分配了足够多的内存,可以容纳src字符串中的所有内容,而一旦这个假定不成立,就会产生缓冲区溢出。SDS在执行拼接操作之前检查s的长度是否足够,在发现s目前的空间不足以拼接时,sdscat就会扩展s的空间,然后执行拼接操作。
  3. 减少修改字符串时带来的内存重分配次数:b中说道每次拼接字符串时,C字符串都要对C字符串进行一次内存重分配操作(即:在拼接操作,需要扩展空间大小,否则缓冲区溢出;在截断操作,需要释放多余空间,否则内存泄漏),因为重分配是比较耗时的操作,所以为了避免频繁修改字符串对性能造成的影响,SDS通过未使用空间接触了字符串长度和底层数组长度之间的关联:SDS中,buf的长度不一定是字符数量+1,数组里面可以包含未使用的字节,而这些字节的数量就由SDS的free属性记录。通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

  • 如果对SDS进行修改之后,SDS的长度小于1MB,那么程序分配和len属性同样大小的未使用空间,这时SDS len属性的值将和free属性的值相同。
  • 如果对SDS修改之后,SDS的长度大于1MB,那么程序会分配1MB的未使用空间。

惰性空间释放

  • 当 SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录下来,并等待将来使用。同时SDS提供了相应的API,在有需要时,释放SDS未使用的空间,这样就可以避免惰性空间释放策略会造成内存浪费。

1.1.3 二进制安全

C语言字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符串,所以C字符串只能保存文本数据,不能保存二进制数据。
SDS的API都是二进制安全(binary-safe)的。

1.1.4 兼容部分C字符串的函数

虽然SDS的API都是二进制安全的,但是API总会将SDS保存的数据的末尾设置为空字符串,这是为了让那些保存文本数据的SDS可以重用一部分<string.h>库定义的函数。

1.2 链表

当一个列表键包含数量比较多的元素,又或者包含的元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现。除了链表键之外,发布与订阅、慢查询、监视器等功能也用到了链表,Redis服务器本身还是用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区(output buffer)。

Redis的链表实现的特性可以总结如下:

  • 双端:链表节点带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)。
  • 无环:表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点。
  • 带表头指针和表尾指针:通过list结构的head指针和tail指针,程序获取链表的表头节点和表尾节点的复杂度为O(1)。
  • 带链表长度的计数器:程序使用list结构的len属性来对list持有的链表节点进行计数,程序获取链表中节点数量的复杂度为O(1)。
  • 多态:链表节点使用void*指针来保存节点值,并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

1.3 字典

1.3.1 结构

字典,又称为符号表(symbol table)、关联数组(associative array)或映射(map),是一种用于保存键值对(key-value pair)的抽象数据结构。

Redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。

字典结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dict{
// 类型特定函数
dicType *type;

// 私有数据
void *privdata;

// 哈希表
dictht ht[2];

// rehash索引
// 当rehash不在进行时,值为-1
in threhash; /* rehashing not in progress if rehashidx == -1 */

} dict;

type属性是一个指向dictType结构的指针,每个dictType结构保存了一簇用于特定类型键值对的函数,Redis会为用途不同的字典设置不同的类型特定函数。
pridata属性则保存了需要传给那些类型特定函数的可选参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct dicType{

// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);

// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);

// 对比键的函数
int (*keyCompare)(void *privdata,const void *key1,const void *key);

// 销毁键
(*keyDestructor)(void *privdata,void *key);

// 复制值
void(*valDup)(void *privdata, const void *obj);

// 销毁值
void(*valDestructor)(void *privdata,void *obj);
}

ht属性是一个包含两个项的数组,数组的每项都是dictht哈希表,一般情况下只是用ht[0],ht[1]只会在对ht[0]哈希表进行rehash时使用。
除ht[1]之外,另一个和rehash有关的属性就是rehashidx,它记录了rehash目前的进度,如果目前没有进行rehash,那么它的值为-1。
dic

1.3.2 哈希算法

Redis使用的是MurmurHash2算法。

  1. 算出hash值:hash=dict->type->hashFunction(key);
  2. 根据hash值计算索引值:index = hash & dict->ht[x].sizemask;//x是0或1

1.3.4 键冲突

Redis的哈希表使用链地址法(separate chaining)来解决冲突,每个哈希表节点都有一个next指针,多个哈希表节点就可以用next指针构成一个单项链表。速度考虑,最新节点添加到表头位置,复杂度O(1)。

1.3.5 rehash

为什么无论是HashMap还是Redis,扩容/收缩时容量大小都是2的幂?

  • 减少碰撞次数,比如1111&1110=1110,1110&1110=1110;
  • 容量*2不至于分配空间过大造成浪费;

Redis对字典的rehash步骤如下:

  1. 为字典的ht[1]哈希表分配空间,这个哈希表的空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量:
  • 如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n;
  • 如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2^2;
  1. 将保存在ht[0]中的所有键值对rehash到ht[1]上:rehash指的是重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。
  2. 当ht[0]包含的所有键值对都迁移到了ht[1]之后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备。

哈希表的扩展与收缩

当以下条件中的任意一个被满足时,程序会自动开始对哈希表执行扩展操作:

  • 服务器目前没有执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表负载因子大于等于1。
  • 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于5。
1
2
# 负载因子=哈希表已保存节点数量/哈希表大小
load_factor = ht[0].used/ht[0].size

执行BGSAVE或BGREWRITEAOF命令的过程中,Redis需要创建当前服务器进程的子进程,大多数操作系统都采用写时复制(copy-on-write)技术优化子进程的使用效率,所以在子进程存在期间,服务器会提高执行扩展操作所需的负载因子。
当哈希表的负载因子小于0.1时,程序自动开始执行收缩操作。

1.3.6 渐进式rehash

rehash动作不是一次性、集中式的完成,而是分多次、渐进式的完成。
渐进式rehash步骤:

  1. 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。
  2. 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始。
  3. 在rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成后,程序将rehashidx属性的值增一。
  4. 随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash值ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作完成。

在渐进式rehash期间,字典的删除、查找、更新等操作会在两个哈希表上进行。如果新加到字典的键值对一律被保存到ht[1]里面。

1.4 跳跃表

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。

Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时,Redis就会使用跳跃表来作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构。

1.4.1 结构

skiplist
上图展示了一个跳跃表示例,左边是zskiplist结构:

  • header: 指向跳跃表的表头节点
  • tail: 指向跳跃表的结尾节点
  • level: 记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)
  • length: 记录跳跃表的长度,跳跃表目前包含节点的数量(表头节点不计算在内)

右侧是zskiplistNode结构:

  • level: 节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,以此类推。每层两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,跨度则记录了前进指针所指向节点和当前节点的距离。
  • backward: 节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
  • score: 各个节点中的1.0、2.0、和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排序。
  • obj: 各个节点中的o1、o2和o3时节点所保存的成员对象。

1.5 整数集合

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。
整数集合是Redis用于保存整数值的集合抽象数据结构,他可以保存集合类型为int16_t、int32_t或者int64_t的整数值,并且保证集合中不会出现重复元素。

1
2
3
4
5
6
7
8
typedef struct intset{
// 编码方式
uint32_t encoding;
// 集合包含的元素
uint32_t length;
// 保存元素的数据
int8_t contents[];
}

contents数组是整数集合的底层实现:整数集合的每个元素都是contents数组的一个数组项(item),各个项在数组中按值的大小从小打到有序的排列,并且数组中不包含任何重复项。

1.5.1 整数集合升级

每当我们将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,整数集合先进行升级,然后添加到整数集合里面。

升级步骤:

  1. 根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,放置元素过程中,需要维持底层数组的有序性质不变。
  3. 将新元素添加到底层数组里面。

1.6 压缩列表

当一个列表键只包含少量的列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。

压缩列表是为了节约内存开发的,是由一系列特殊编码的连续内存块组织的顺序(sequential)数据结构。

ziplist
ziplistintroduce

节点content属性负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的encoding属性决定。

1.6.1 连锁更新

连锁更新最坏情况下需要对压缩列表执行N次空间重分配操作,而每次空间重分配的最快复杂度为O(N),所以更新的最快复杂度为O(N^2)。

1.7 快速列表(quicklist)

quicklist是一个ziplist的双向链表(双向链表是由多个节点Node组成的)。也就是说quicklist的每个节点都是一个ziplist。ziplist本身也是一个能维持数据项先后顺序的列表(按插入位置),而且是一个各个数据项在内存上前后相邻的列表。
结构如下:

quicklist
图片来自三石雨-Redis结构之quicklist

quicklist基于空间和时间的考虑,结合双向链表和ziplist的优点。

双向链表linkedlist便于在表的两端进行push和pop操作,在插入节点上复杂度很低,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。
ziplist存储在一段连续的内存上,所以存储效率很高。但是,它不利于修改操作,插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝。
摘自harleylau Redis源码剖析–quicklist

1.8 对象

Redis并没有 直接使用SDS、双端链表、字典、压缩列表、整数集合这些数据结构实现键值对数据库,而是基于这些数据结构创建了一个对象系统。对象系统包含:字符串对象、列表对象、哈希对象、集合对象和有序集合对象。
Redis的对象系统实现了基于引用计数计数的内存回收机制,当程序 不再使用某个对象的时候,这个对象所占用的内存就会被自动释放;另外Redis还通过引用计数技术实现了对象共享机制,这种机制在适当情况下,通过让多个数据库键共享同一个对象来节约内存。
Redis对象带有访问时间记录信息,该信息可以用于计算数据库键的空转时长,在服务器启用了maxmemory功能情况下,空转时长较大的那些键可能会优先被服务器删除。

1.8.1 对象的类型与编码

Redis使用对象来表示数据库中的键和值,每次当我们在Redis的数据库中新建一个键值对时,我们至少会创建两个对象,一个对象用作键值对的键,一个对象用作键值对的值。

Redis中的每个对象都由一个RedisObject结构表示,该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性:

1
2
3
4
5
6
7
8
9
10
typedef struct redisObject{
// 类型
unsigned type:4;

// 编码
unsigned encoding:4;

// 指向底层实现数据结构的指针
void *ptr;
}

type记录了对象的类型:

  • REDIS_STRING:字符串对象
  • REDIS_LIST:列表对象
  • REDIS_HASH:哈希对象
  • REDIS_SET:集合对象
  • REDIS_ZSET:有序集合对象

字符串键指的是这个数据库键所对应的值得字符串对象
列表键指的是数据库键所对应的值为列表对象

ptr指针指向对象的底层实现数据结构,这些数据结构由对象的encoding属性决定。encoding记录对象使用的编码:

encoding
除上述列表外,还有一个是REDIS_ENCODING_QUICKLIST编码,快速列表。

每种类型的对象都至少使用了两种不同编码,下表列出了每种类型的对象可以使用的编码。

type-encoding

除上述列表外,还有一个是REDIS_LIST对应REDIS_ENCODING_QUICKLIST。

1.8.2 字符串对象

字符串对象的编码可以是int、raw或者embstr。
如果字符串对象保存的是整数值,将字符串对象的编码设置为int。
如果字符串对象保存的是一个字符串值,并且这个字符串值长度大于32字节,字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值,并将对象的编码设置为raw。
raw结构:
raw
如果字符串对象保存的是一个字符串值,并且这个字符串值长度小于32字节,字符串对象将使用embstr编码的方式保存这个字符串值。
embstr内存块结构:
embstr
raw和embstr区别:

  • embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次。
  • 释放embstr编码的字符串对象只需要调用一次内存释放函数,而释放raw编码的字符串对象需要调用两次内存释放函数。
  • embstr编码的字符串对象的所有数据都保存在一块连续的内存里面,所以这种编码的字符串对象比起raw编码字符串对象比起来raw编码的字符串能够更好地利用缓存带来的优势。

字符串对象保存各类型值得编码方式:

string

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下,会被转换为raw编码的字符串对象。
Redis没有为embstr编码的字符串对象编写任何响应的修改程序,所以embstr编码的字符串对象实际上是只读的。

string

1.8.3 列表对象

列表对象的编码可以使ziplist或者linkedlist。
ziplist结构如下:
ziplist

linkedlist结构如下:

linkedlist

StringObject结构:

string-object

当列表对象满足如下条件时,使用ziplist编码:
列表对象保存的所有字符串元素的长度都小于64字节;
列表对象保存的元素数量小于512个;

列表命令的实现:
list-order

1.8.4 哈希对象

哈希对象的编码可以是ziplist或者hashtable。

ziplist编码的哈希对象使用压缩列表作为底层实现,每当有新的键值对要加入到哈希对象时,程序会先将保存了键的压缩列表节点推入到压缩列表表尾,然后再将保存了值得压缩列表节点推入到压缩列表表尾:

  • 因此保存了同一键值对的两个节点总是紧挨在一起,保存键的节点在前,保存值的节点在后;
  • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向,而后添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

例如:

1
2
3
>HSET profile name "Tom"
>HSET profile age 25
>HSET profile career "Programmer"

哈希对象的压缩列表底层实现:

hash-ziplist-implement

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

  • 字典的每个键都是一个字符串对象,对象中保存了键值对的键;
  • 字典的每个值都是一个字符串对象,对象中保存了键值对的值。

如果上述例子不是ziplist而是hashtable,则结构如下:

hashtable-implement

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

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

hash命令:

hash-order

1.8.5 集合对象

集合对象编码可以是intset或者hashtable。

集合命令:

set-order
set-order

1.8.6 有序集合对象

有序集合的编码可以是ziplist或者skiplist。

ziplist的的存储结构:

sorted-set-ziplist
sorted-set-ziplist

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

1
2
3
4
typedef struct zset{
zskiplist *zsl;
dict *dict;
} zset;

zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素,每个跳跃表节点保存了一个集合元素:跳跃表节点的Object属性保存了元素的成员,而跳跃表的score属性则保存了元素的分值。通过这个跳跃表,程序可以对有序集合进行范围型操作,如ZRANKZRANGE等命令就是基于跳跃表API来实现的。

除此之外,zset结构中的dict字典为有序集合创建了一个从成员的分值的映射,字典中的每个键值对都保存了一个集合元素:字典的键保存了元素的成员,而字典的值保存了元素的分值。通过这个字典,程序可以O(1)复杂度查找给定成员的分值,ZSCORE命令就是根据这一特性实现的。

虽然zset结构同时使用跳跃表和字典来保存有序集合元素,而这两种数据机构都会通过指针来共享相同元素的成员和分值,所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或分值,也不会浪费额外内存。

为什么有序集合需要同时使用跳跃表和字典来实现?
如果我们只是用字典来实现有序集合,那么虽然已O(1)复杂度查找成员的分值这一特性被保留,但是字典以无序的方式保存集合元素,所以每次在执行范围操作时,都需要对字典保存的所有元素进行排序,完成这种排序至少需要O(NlogN)时间复杂度,以及额外的O(N)内存空间。同样如果只是用跳跃表,根据成员查找分值操作复杂度将为O(logN)。

skiplist结构:

sorted-set-skiplist

注意:字典和跳跃表会共享元素的成员和分值,并不会造成数据重复。

命令实现:

sorted-set-order

1.8.7 类型检查与命令多态

Redis中用于操作键的命令基本上可以分为两种类型。
一种可以对任何类型键执行;另一种只能对特定类型的键执行。

Redis在执行一个类型特定的命令之前,会先检查输入键的类型是否正确,然后再决定是否执行给定的命令。
类型特定命令所进行的类型检查是通过redisObject结构的type属性来实现的:

  • 在执行一个类型特定命令之前,服务器会先检查输入数据库键的值对象是否为执行命令所需类型,如果是的话执行。
  • 否则,拒绝执行,返回类型错误。

Redis除了会根据值对象的类型来判断键是否能够执行指定命令之外,还会根据值对象的编码方式,选择正确的命令实现代码来执行命令。如llen:

llen-order

1.8.8 内存回收

因为C不具备自动内存回收功能,所以Redis在自己的对象系统中构建了一个引用计数(reference counting)技术实现的内存回收机制。

1.8.9 对象共享

Redis对象的引用计数属性还带有对象共享的作用(多个键共享同一个值对象)。
这些共享对象不单单只有字符串键可以使用,那些数据结构中嵌套了字符串对象的对象都可以使用这些共享对象。

Redis只对包含整数值的字符串对象进行共享。

1.8.10 对象的空转时长

除了type、encoding、ptr和refcount四个属性外,redisObject结构包含的最后一个属性为lru属性:

1
2
3
typedef struct redisObject{
unsigned lru:22;
} robj;

OBJECT IDLETIME命令可以打印出键的空转时长,计算方式:当前时间-lru。

2. 单机数据库实现

Redis服务器将所有数据库都保存在服务器状态redis.h/redisServer结构的db数组中,db数组的每个项都是一个redis.h/redisDb结构,每个redisDb结构代表一个数据库。

数据库结构示例:
db

redisDb结构的dict字典保存了数据库中的所有键值对,我们将这个字典成为键空间:

数据库键空间示例:
db

键空间的键也就是数据库的键,每个键都是一个字符串对象。
键空间的值也就是数据库的值,每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的任意一种Redis对象。
数据库的键空间是一个字典。

读写空间时的维护操作

  • 读取一个键后,服务器会根据键是否存在来更新服务器的键空间命中次数或键空间不命中次数,这两个值可以在INFO stats命令的keyspace_hits属性和keyspace_misses属性中查看。
  • 读取一个键后,服务器会更新键的LRU时间,可以使用OBJECT idletime 命令查看键key的闲置时间。
  • 如果服务器在读取一个键时发现该键过期,服务器会先删除这个过期键,然后才执行余下的其他操作。
  • 如果客户端使用watch命令监视了某个键,那么服务器在对被监视的键进行修改后,会将这个键标记为脏(dirty)。
  • 服务器每次修改一个键后,都会对(dirty)键计数器的值增1,这个计数器会触发服务器的持久化及复制操作。
  • 如果服务器开启了数据库通知功能,那么对键进行修改之后,服务器将按配置发送响应的数据库通知。

2.1 过期时间

Redis有四种不同的命令可以用于设置键的生存时间或过期时间:

  • EXPIRE<key><ttl>命令用于将键key的生存时间设置为ttl秒。
  • PEXPIRE<key><ttl>命令用于将键key的生存时间设置为ttl毫秒。
  • EXPIREAT<key><timestamp>命令用于将键key的生存时间设置为timestamp秒数时间戳。
  • PEXPIRE<key><timestamp>命令用于将键key的生存时间设置为timestamp毫秒数时间戳。

redisDb结构的expires字典保存了数据库中所有键的过期时间,我们称这个字典为过期字典:

  • 过期字典的键是一个指针,这个指针指向键空间中的某个键对象。
  • 过期字典的值是一个long long类型的整数,这个整数保存了键所指向的数据库键的过期时间——一个毫秒精度的UNIX时间戳。

PERSIST命令可以移除一个键的过期时间。

TTL命令以秒级单位返回键的剩余生存时间,PTTL命令以毫秒为单位返回键的剩余生存时间。

2.2 过期键删除策略

定时删除: 在设置键的过期时间的同时,创建一个定时器(timer),让定时器在键的过期时间来临时,立即执行对键的删除操作。
惰性删除: 放任键过期不管,但是每次从键空间中获取键时,都检查取得的键是否过期,如果过期的话,就删除该键;如果没有过期,就返回该键。
定期删除: 每隔一段时间,程序就对数据库进行一次检查,删除里面的过期键。至于要删除多少过期键,以及要检查多少个数据库,则由算法决定。

2.2.1 定时删除

定时删除对内存友好,对CPU时间不友好,在过期键比较多的情况下,删除过期键这一行为可能会占用相同一部分CPU时间。

2.2.2 惰性删除

惰性删除策略对CPU友好,对内存不友好。有内存泄漏的风险。

2.2.3 定期删除

定期删除操作的难点在于如果确定删除操作的时长和频率。

2.2.4 Redis的过期删除策略

Redis服务器实际使用的是惰性删除和定期删除两种策略。

2.2.5 AOF、RDB和复制功能对过期键的处理

在执行SAVE命令或者BGSAVE命令创建一个新的RDB文件是,程序会对数据库中的键进行检查,已过期的键不会保存到新建的RDB文件中。

RDB文件载入:

  • 如果服务器以主服务器模式运行,那么在载入RDB文件时,程序会对文件中保存的键进行检查,未过期的键会被载入到数据库中,而过期键则会被忽略,所以过期键对载入RDB文件的主服务器不会造成影响。
  • 如果服务器以从服务器模型运行,那么载入RDB文件时,文件中保存的所有键,不论是否过期,都会被载入到数据库中。不过主从服务器在进行数据同步时,从服务器的数据库会被清空。

AOF重写的过程中,会对数据库中的键进行检查,已过期的键不会被保存到重写后的AOF文件中。

当服务器在复制模式下时,从服务器的过期键删除动作有主服务器控制:

  • 主服务器在删除一个过期键后,会显式地向所有从服务器发送一个DEL命令,告诉从服务器删除这个过期键。
  • 从服务器在执行客户端发送的读命令时,及时碰到过期键也不会将过期键删除,而继续像处理未过期的键一样处理过期键。
  • 从服务器只有在接到主服务器发来的DEL命令后,才会删除过期键。

2.2.6 数据库通知

数据库通知时Redis 2.8版本新增加的功能,这个功能可以让客户端通过订阅给定的频道或者模式,获知数据库中键的变化,以及数据库中命令的执行情况。

监听索引为0的键空间key为message所有操作。

1
> SUBSCRIBE [email protected]__:message

2.3 RDB持久化

2.3.1 RDB文件的创建与载入

Redis命令可用于生成RDB文件,一个是SAVE,另一个是BGSAVE。
SAVE会阻塞Redis服务进程,知道RDB文件创建完毕,阻塞期间,服务器不能处理任何命令请求。
BGSAVE命令会派生除一个子进程,然后由子进程负责创建RDB文件,服务器进程继续处理命令请求。
BGSAVE命令正在执行,客户端发送的BGREWRITEAOF命令会被延迟到BGSAVE命令执行完毕后执行。
BGREWRITEAOF正在执行,那么客户端发送的BGSAVE命令会被服务器拒绝。

如果开启了AOF持久化功能,服务器会优先使用AOF文件还原数据库状态。
只有AOF持久化功能处于关闭状态时,服务器才会使用RDB文件来还原数据库状态。

2.3.2 自动间隔性保存

2.3.3 RDB文件结构

rdb

REDIS部分用来校验是否为RDB文件。
db_version长度为4字节,记录RDB文件的版本号。
databases部分包含着两个或者任意多个数据库,以及各个数据库中的键值对数据。
EOF标志着RDB文件的正文结束。
check_sum保存着一个校验和,由REDIS、db_version、databases、EOF计算得出。校验RDB文件是否出错或者损坏。

database部分保存任意多个非空数据库,如下图所示,每个非空数据库可以保存SELECTDB、db_number、key_value_pairs:

rdb
rdb

SELEECT表示数据库号码。
db_number保存一个数据库号码。
key_value_pairs保存数据库中的所有键值对数据。

rdb

key_values_pairs保存了一个以上的键值对,如果键值对带有过期时间的话,那么键值对的过期时间也会被保存在内。
不过期时间的键值对由TYPE、key、value组成。
TYPE:

  • REDIS_RDB_TYPE_STRING
  • REDIS_RDB_TYPE_LIST
  • REDIS_RDB_TYPE_SET
  • REDIS_RDB_TYPE_ZSET
  • REDIS_RDB_TYPE_HASH
  • REDIS_RDB_TYPE_LIST_ZIPLIST
  • REDIS_RDB_TYPE_SET_INTSET
  • REDIS_RDB_TYPE_ZSET_ZIPLIST
  • REDIS_RDB_TYPE_ZIPLIST

过期时间的键值对在RDB文件中结构:
rdb

2.4 AOF持久化

AOF持久化功能的实现可以分为命令追加、文件写入、文件同步三个步骤。

2.4.1 命令追加

当AOF持久化功能处于打开状态时,服务器在执行完一个写命令后,会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区末尾:

1
2
3
struct redisServer{
sds aof_buf;
}

2.4.2 文件写入与同步

Redis的服务器进程就是一个事件循环,这个循环中的文件事件负责接收客户端的命令请求,以及向客户端发送命令回复,而时间事件则负责执行像serverCron函数这样需要定时运行的函数。

1
2
3
4
5
6
7
8
9
10
11
def eventLoop():
while True:
# 处理文件事件,接收命令请求以及发送命令回复
# 处理命令请求时可能会有新内容被追加到aof_buf缓冲区中
processFileEvents()

# 处理时间事件
processTimeEvents()

# 考虑是否将aof_buf中的内容写入和保存到AOF文件里面
flushAppendOnlyFile()

flushAppendOnlyFile函数的行为由服务器配置的appendfsync选项的值来决定,各个不同值产生的行为如表:
appendfsync

2.4.3 AOF重写

因为AOF通过保存执行的写命令来记录数据库状态,所以可能造成AOF文件过大。为了解决这个问题,Redis提供了AOF文件重写功能。通过创建一个新的AOF文件替代现有的AOF文件,新旧两个AOF文件所保存的数据库状态相同,但新AOF文件不会包含任何浪费空间的冗余命令,所以新AOF通常比旧AOF小得多。
重写功能通过读取服务器当前的数据状态来实现的。因为aof——rewirte函数生成的新的AOF只包含还原当前数据库状态所必需的的命令,所以新AOF文件不会浪费任何硬盘空间。

注意:
在实际中,为了避免执行命令时造成客户端输入缓冲区溢出,重写程序在处理列表、哈希表、集合、有序集合这四种可能会带有多个元素的键时,会先检查所包含的元素数量,如果元素数量超过了redis.h/REDIS_AOF_REWRITE_ITEMS_PER_CMD常量的值,那么重写程序将使用多条命令来记录键的值。

aof_rewrite会长时间阻塞,所以Redis将AOF重写程序放到子进程里执行:

  • 子进程进行AOF重写期间,服务器进程可以继续处理命令请求。
  • 子进程带有服务器进程的数据副本,使用子进程而不是线程,可以在避免使用锁的情况下,保证数据的安全性。

AOF重写期间,客户端命令可能对现有数据库状态修改,造成当前数据库状态和AOF文件不一致的情况。

为了解决不一致的情况,Redis服务器设置了一个AOF重写缓冲区,这个缓冲区在服务器创建子进程之后开始使用,当Redis服务器执行完一个写命令后,它同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区。

AOF完成重写后,它会向父进程发送一个信号,父进程在接到该信号之后,会调用一个信号处理函数,并执行以下工作:

  • 将AOF重写缓冲区中的所有内容写入到新AOF文件中,这时新AOF文件所保存的数据库状态将和服务器当前的数据库状态一致。
  • 对新的AOF文件进行改名,原子的覆盖现有的AOF文件,完成新旧两个AOF文件的替换。

AOF后台重写过程中,只有信号处理函数执行时会对服务器进程造成阻塞,其他时候,AOF不会阻塞父进程。

2.5 事件

Redis服务器是一个事件驱动程序:

  • 文件事件: Redis服务器通过套接字与客户端进行连接,而文件事件就是服务器对套接字操作的抽象。服务器与客户端的通信产生响应的文件事件,而服务器则通过监听并处理这些事件来完成一系列网络通信操作。
  • 时间事件: Redis服务器中的一些操作需要在给定的时间点执行,而时间事件就是服务器对这类定时操作的抽象。

2.5.1 文件事件

Redis基于Reactor模式开发了自己的网络事件处理器: 这个处理器被称为文件事件处理器:

  • 文件事件处理器使用I/O多路复用程序来同时监听多个套接字,并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
  • 当被监听的套接字准备好执行连接应答、读取、写入、关闭等操作时,与操作对应的文件事件就会产生,这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

2.5.2 时间事件

Redis的时间事件分为以下两类:

  • 定时事件: 让一段程序在指定的时间之后执行一次。
  • 周期性时间: 让一段程序每隔指定时间执行一次。

一个时间事件主要由以下三个属性组成:

  • id: 服务器为时间事件创建的全局唯一ID。从小到大递增。
  • when: 毫秒级精度的UNIX时间戳,记录了时间事件的到达时间。
  • timeProc: 时间事件处理器,一个函数。当时间事件到达时,服务器就会调用相应的处理器来处理事件。

一个时间事件是定时事件还是周期性事件取决于时间事件处理器的返回值:

  • 如果事件处理器返回ae.h/AE_NOMORE,那么这个事件为定时事件: 该事件在达到一次之后就会被删除,之后不再到达。
  • 如果事件处理器返回一个非AE_NOMORE的整数值,那么这个事件为周期性事件: 当一个时间事件到达之后,服务器会根据事件处理器返回的值,对事件事件的when属性进行更新,这个事件在一段时间之后再次到达,并以这种方式一致更新并运行下去。

持续运行的Redis服务器需要定期对自身的资源和状态进行检查和调整,从而确保服务器可以长期、稳定的运行,这些定期操作由redis.c/serverCron函数负责执行,主要工作包括:

  • 更新服务器的各类统计信息,比如时间、内存占用、数据库占用情况。
  • 清理数据库中的过期键值对。
  • 关闭和清理连接失效的客户端。
  • 尝试进行AOF和RDB持久化操作。
  • 如果服务器是主服务器,那么对从服务器进行定期同步。
  • 如果处于集群模式,对集群进行定期同步和连接测试。

2.5.3 事件调度与执行

事件调度和执行由ae.c/aeProcessEvents函数负责。

processFileEvent这个函数并不存在,在实际中,处理已产生文件事件的代码是直接写在aeProcessEvents函数里面。

事件调度和执行规则:

  1. aeApiPoll函数的最大阻塞时间由到达时间最近当前时间的时间事件决定,这个方法既可以避免服务器对事件事件进行频繁的轮询,也可以确保aeApiPoll函数不会阻塞过长时间。
  2. 因为文件事件是随机出现的,如果等待并处理完一次文件事件之后,仍未有任何事件事件到达,那么服务器将再次等待处理文件事件。随着文件事件的不断执行,时间会逐渐向时间事件所设置的到达时间逼近,并最终来到到达时间,这时服务器就可以开始处理到达的时间事件。
  3. 对文件事件和时间事件的处理都是同步、有序、原子的执行的,服务器不会中途中断事件处理,也不会对事件进行抢占,因此不管是文件事件的处理器,还是时间事件的处理器,也不会对事件进行抢占,一次不管是文件事件的处理器,还是时间事件的处理器,它们都会尽可的减少程序阻塞时间,并在有需要时主动让出执行权,从而降低造成时间饥饿的可能性。另外,时间事件也会将非常耗时的持久化操作放到子线程或者子进程执行。
  4. 因为时间事件在文件事件之后执行,并且事件之间不会出现抢占,所以时间事件的实际处理时间,通常会比时间事件设定的到达时间晚一些。

3. 多机数据库实现

3.1 复制

在Redis中,用户可以通过执行SLAVEOF命令或者设置slaveof选项,让一个服务器去复制(replicate)另一个服务器。

Redis复制功能分为同步和命令传播两个操作:

  • 同步操作用于将服务器的数据库状态更新至主服务器当前所处的数据库状态。
  • 命令传播操作则用于在主服务器的数据库状态被修改,导致主从服务器的数据库状态出现不一致时,让主从服务器的数据库重新回到一致的状态。

Redis复制实现:

  1. 客户端发送命令(此命令是异步的):>SLAVEOF master-ip master-port
  2. 1命令在从服务上完成masterhost和masterport属性的设置之后,从服务器返回OK。
  3. 从服务器根据masterhost和masterport建立socket连接。
  4. 发送PING命令,检查socket连接的读写状态,检查主服务器的命令处理,如果主服务器返回非PONG,则断开并重连主服务器。
  5. 从服务器发送身份验证信息。
  6. 发送从服务器的端口信息。
  7. 同步PSYNC。
  8. 最后命令传播。

Redis复制流程图:

redis-replicate

从Redis 2.8版本开始,Redis使用PSYNC代替SYNC命令执行复制操作。
PSYNC命令执行:

PSYNC

PSYNC与SYNC最显著的区别是PSYNC支持部分重同步。

3.2 Sentinel

Sentinel是Redis的高可用解决方案。

启动Sentinel时,执行redis-server /path/sentinel.conf --sentinel或者redis-sentinel /path/sentinel.conf命令即可。

Sentinel启动时,需要执行以下步骤:

  1. 初始化服务器
  2. 将普通Redis服务器使用的代码替换成Sentinel专用代码
  3. 初始化Sentinel状态
  4. 根据给定配置文件,初始化Sentinel的监视主服务器列表
  5. 创建连向主服务器的网络连接

Sentinel状态图:
redis-sentinel-state

3.2.1 获取主从、Sentinel的信息

初始化Sentinel最后一步是创建连向主服务器的网络连接,Sentinel将成为主服务器的客户端。

对于每个被Sentinel监视的主服务器来说,Sentinel会创建两个连向主服务器的异步网络:

  • 命令连接,这个连接专门向主服务器发送命令,并接收命令回复。
  • 订阅连接,这个连接专门用于订阅主服务器的__sentinel__:hello频道。

Sentinel默认以每十秒一次的频率,通过命令连接向被监视的主服务器发送INFO命令,通过INFO获取主服务器的当前信息。
Sentinel通过主服务器发现从服务器时,也会建立上述的两个连接,每10秒发送INFO命令,获取从服务器的当前信息。
默认情况下,Sentinel每2秒通过命令连接向所有主从服务器发送如下命令:
PUBLISH __sentinel__:hello "<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_name>,<m_id>,<m_port>,<m_epoch>

s开头的是sentinel的信息,m开头的是主服务器的信息,如果发送的是从服务器,则m为从服务器正在复制的主服务器的信息。
Sentinel与一个主或从服务器建立订阅连接后,Sentinel就会通过订阅连接,向服务器发送以下命令:
SUBSCRIBE __sentinel__:hello

Sentinel通过频道信息发现一个新的Sentinel时,不仅会为新的Sentinel创建相应的实例结构,还会创建一个连向新Sentinel的命令连接。

3.2.1 下线状态

Sentinel每1秒一次的频率向所有与它建立命令连接的实例发送PING命令,判断是否在线。
实例在down-after-milliseconds内返回+PONG、-LOADING、-MASTERDOWN以外的回复,Sentinel将修改该实例的flags属性:SRI_S_DOWN标识,标识进入主观下线状态。
超时也会被置为主观下线状态。

当主服务器被判定为主观下线后,为确认是否真的下线了,Sentinel会询问监视此服务器的其他Sentinel,如果从其他Sentinel得到足够数量的已下线判断后,Sentinel将此服务器置为客观下线。

Redis下线状态及Sentinel领头选举:
redis-down
上图中,1. master代表一个主服务器,2. 监视master的sentinel代表其中一个监视master的sentinel(所有监视master的sentinel都会这样去操作,这个地方只是列出来一个作为示例),3. 监视master的sentinel代表监视master的sentinel的集合。

3.2.2 故障转移

故障转移步骤:

    1. 在已下线的主服务器的从服务器中,选一个作为主服务器。
    1. 让其他没有作为主服务器的从服务器复制新的主服务器。
    1. 将已下线的主服务器置为新主服务器的从服务器,当下线的主服务器再上线时,它就会成为新主服务器的从服务器。

3.3 集群

Redis集群是Redis提供的分布式数据库方案,集群通过分片(sharding)来进行数据共享,并提供复制和故障转移功能。

3.3.1 节点

当一个节点node发送CLUSTER MEET <IP> <PORT>命令,可以让node节点与ip和port所指定的节点进行握手(handshake),当握手成功后,node节点就会将ip和port所指定的节点添加到node节点当前所在的集群中。
集群数据结构示例:
cluster

3.3.2 槽

Redis集群通过分片的方式来保存数据库中的键值对:集群的整个数据库被分为16384个槽(slot),数据库中的每个键都属于这16384个槽的其中一个,集群中的每个节点都可以处理0个或者最多16384个槽。

如果16384个槽都有节点在处理时,集群处于上线状态(ok),相反如果数据库中有任何一个槽没有得到处理,那么集群处于下线状态(fail)。

槽分配命令CLUSTER ADSLOTS <slot> [slot ...],例如127.0.0.1:6379>cluster addslots 0 1 2 ... 1000将0到1000的槽分配给本地的6379节点负责。

槽分配后节点的ClusterState结构:

clusterstate

集群节点数据库存储结构:

clusterstate

集群节点保存key对应槽的跳跃表:

clusterstate

3.3.3 分片

Redis集群的重新分片操作可以将任意数量已经指派给某个节点的槽改为指派给另一个节点,并且相关槽所属的减值对也会从源节点被移动到目标节点。

Redis集群的重新分片操作是由Redis的集群管理软件redis-trib负责执行的,Redis提供了进行重分配分片所需要的所有命令。

Redis重分片迁移过程:

migrate

迁移过程中,查询key的命令过程如下:

redis-ask

redis-asking

3.3.4 故障检测

集群中的每个节点都会定期的向集群中的其他节点发送PING消息,以此来检测对方是否在线。

3.3.5 消息

集群中的各个节点通过发送和接收消息(message)来进行通信。消息主要以下五种:

  • MEET消息:当发送者接收客户端发送的CLUSTER MEET命令时,发送者会向接收者发送MEET消息,请求接收者加入到发送者当前所处的集群里面。
  • PING消息:集群里的每个节点默认每隔一秒钟就会从已知节点列表中随机选出五个节点,然后对五个节点中最长时间没有发送过PING消息的节点发送PING消息。
  • PONG消息:当接收者收到发送者发来的MEET消息或者PING消息时,为了向发送者确认这条MEET消息或者PING消息已到达,接收者会向发送者返回一条PONG消息。
  • FAIL消息:当一个主节点A判断另一个主节点B进入FAIL状态时,节点A会向集群广播一条关于B的FAIL消息,所有接收到这条消息的节点都会立即将B标记为已下线。
  • PUBLISH消息:当节点接收到一个PUBLISH命令时,节点会执行这个命令,并向集群广播一条PUBLISH消息,所有接收者都会执行相同的PUBLISH命令。

Redis集群中的各个节点通过Gossip协议来交换各自关于不同节点的状态信息,其中Gossip协议由MEET、PING、PONG是三种消息实现。三种消息使用相同的消息正文,通过消息头type区分消息。

4. 独立功能的实现

4.1 事务

Redis 通过MULTI、EXEC、WATCH等命令来说实现事务。
事务在执行期间,服务器不会中断事务处理其他请求。

4.1.1 事务的实现

一个事务从开始时到结束通常经历3个阶段:

  1. 事务开始: MULTI
  2. 命令入队:
  3. 事务执行: EXEC

4.1.2 WATCH 命令的实现

WATCH命令是一个乐观锁(optimistic locking),它可以在EXEC命令执行之前,监视任意数量的数据库键,并在EXEC命令执行时,检查被监视的键是否至少少有一个已经被修改过了,如果是,则拒绝执行事务,并向客户端返回代表事务执行失败的空回复。
每个Redis数据库都保存着一个watched_keys字典,这个字典的键时某个被WATCH命令监视的数据库键,而字典的值则是一个链表,链表中记录了所有监视相应数据库键的客户端。
如果有修改命令对数据库键修改过,那么touchWatchKey函数将监视被修改键的客户端的REDIS_DIRTY_CAS标识打开,标识该客户端的事务安全性被破坏。

watch

4.1.3 事务的ACID性质

Redis的事务和传统的关系型数据库事务的最大区别在于,Redis不支持事务回滚机制,即使事务队列中的某个命令在执行期间出现了错误,整个事务也会继续执行下去,直到将事务队列中的所有命令都执行完毕。

Redis 通过谨慎的错误检测和简单的设计来保证事务的一致性,从而确保事务的一致性。以下介绍Redis事务可能出错的地方,并说明Redis是如何妥善处理这些错误。

  1. 入队错误:服务器会拒绝执行入队过程中出现错误的事务,所以Redis事务的一致性不会被带有入队错误的事务影响。
  2. 执行错误:
  • 执行过程中发生的错误都是一些不能在入队时被服务器发现的错误,这些错误只会在命令实际执行时触发。
  • 即使在事务的执行过程中发生错误,服务器也不会中断事务的执行,它会继续执行事务中余下的其他命令,并且已执行的命令不会被出错的命令影响。
  1. 服务器停机:
  • 如果Redis服务器运行在无持久化的内存模式下,那么重启之后的数据库将是空白的,因此数据总是一致的。
  • 如果服务器运行在RDB模式下,那么在事务中途停机不会导致不一致性,因为服务器可以根据现有的RDB文件来恢复数据,从而将数据库还原到一个一致的状态。如果找不到可供使用的RDB文件,那么重启之后的数据库将是空白的,空白的总是一致的。
  • 如果服务器运行在AOF模式下,那么事务中途停机不会导致不一致性,因为服务器可以根据现有的AOF文件来恢复数据,从而将数据还原到一个一致的状态。如果找不到可供使用的AOF文件,那么重启之后的数据库将是空白的,而空白数据库总是一致的。

FAQ

  1. BGSAVE 是否会存执行BGSAVE命令后客户端请求的命令?
  2. 假如说每秒执行一次AOF持久化,那么Redis从aof缓冲区写入AOF文件时,服务端处理的命令是否会存入缓冲区,是否会进入AOF文件?

引用

文中的列表和图片大都引用自Redis 设计与实现(第二版)

Redis 设计与实现(第二版)
harleylau-Redis源码解析-quicklist
三石雨-Redis结构之quicklist