《Redis设计与实现》笔记

第二章 简单动态字符串

在Redis中，C字符串只会作用字符串字面量用在一些无需对字符串值进行修改的地方，当需要修改的时候，Redis会使用自己构建的一种名为简单动态字符串的抽象类型SDS来表示。SDS还会用在AOF模块和客户端状态中的缓冲区里。p8

SDS的定义

//sds.h
struct sdshdr{
    //记录buf数组中已使用字节的数量，等于SDS所保存字符串的长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组，保存字符串
    char buf[];
};

使用该结构比直接使用C字符串有以下好处：

1. 获取字符串长度的复杂度从O（n）降低到O（1）；
2. 杜绝缓冲区溢出，SDS在进行字符串操作时会先检查是否有足够的空间p11；
3. 减少修改字符串时带来的内存重分配次数，通过free字段，SDS实现了空间预分配和惰性空间释放两种优化策略。对于空间预分配策略而言，如果对SDS修改后len小于1MB，则将分配和len相同长度的未使用空间，如果修改后len大于1MB，则分配1MB的未使用空间；对于惰性空间释放，则是说缩短字符串长度时，并没有真正释放空间，而是将free值增大而已，便于将来可能有的增长操作。另外SDS也提供了相应的API用来真正释放未使用空间。
4. C字符串中不能包含空字符，所以也不能保存像图片、音频等二进制数据，但SDS可以，它是二进制安全的。
5. 兼容部分C字符串函数，如strcasecamp、strcat。

主要API见p17。

第三章 链表

当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。除此以外，发布与订阅、慢查询、监视器等功能也用到了链表。

链表和链表节点的实现

//adlist.h
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;

特点：

• 双端
• 无环
• 有头尾节点
• 有链表长度计数器
• 多态，链表节点使用void*指针保存节点值，所以可以保存各种不同类型的值

API见p21

第四章 字典

Redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查也是构建在对字典的操作之上的。当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。

字典的实现

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

哈希表

//dict.h/dictht
typedef struct dictht{
    //哈希表数组
    dictEntry **table;//dictEntry定义也在dict.h中，每个dictEntry保存一个键值对
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值，总是等于size-1
    unsigned long sizemask;
    //已有节点的数量
    unsigned long used;
}dictht;

哈希表节点

typedef struct dictEntry{
    //键
    void *key;
    //值
    union{
        void* val;
        uint64_t u64;
        int64_t s64;
    }v;
    //指向下个hash表节点，形成链表，解决哈希冲突
    struct dictEntry *next;
}distEntry;

字典

//dict.h
typedef struct dict{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash索引，当rehash不在进行时，值为-1
    int rehashidx;
}dict;

typedef struct dictType{
    //计算哈希值的函数
    unsigned int(*hashFunction)(const void * key);
    //复制键的函数
    void* (*keyDup)(void * privdata,const void *key);
    //复制值的函数
    void* (*valDup)(void privdata,const void *obj);
    //对比键的函数
    int (*keyCompare)(void *privdata,const void* key1,const void* key2);
    //销毁键的函数
    void (*keyDestructor)(void* privdata,void *key);
    //销毁值的函数
    void (*valDestructor)(void* privdata,void *obj);
}dictType;

一般情况下，字典只使用ht[0]哈希表，ht[1]只会在对ht[0]进行rehash时使用。

hash算法

Redis计算哈希值和索引值的方法如下：

//使用字典设置的哈希函数计算键key的哈希值
hash=dict->type->hashFunction(key);
//使用哈希表的sizemask属性和哈希值计算出索引值，根据情况不同，ht[x]可以是ht[0] 或 //ht[1]
index=hash&dict->ht[x].sizemask;

因为dictEntry节点组成的链表没有指向链表尾部的指针，所以在哈希冲突的时候为了速度考虑，程序总是将新节点添加到链表的表头位置（O（1）），排在已有元素前面。

当字典呗用作数据库或哈希键的底层实现时，Redis使用MurmurHash2算法来计算哈希值。

rehash

随着操作的不断执行，哈希表保存的键值对会增多或减少，为了保证负载因子在一个合理的范围内，则需要对哈希表的大小进行相应的扩展或者收缩，这可以通过rehash来完成。

步骤如下：

1. 为ht[1]分配空间，如果是扩展操作，则大小等于第一个大于等于ht[0].used*2的2^n，如果是收缩操作，则大小等于第一个大于等于ht[0].used的2^n；
2. 将ht[0]中的所有键值对重新计算哈希值和索引值放入ht[1]中；
3. 释放ht[0]，并将ht[1]置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次做准备。

当以下条件之一满足时，会开始扩展：

1. 服务器没有执行BGSAVE或BGREWRITEAOF命令，且负载因子大于等于1；
2. 服务器在执行BGSAVE或BGREWRITEAOF命令，且负载因子大于等于5；

当负载因子小于0.1时，或进行收缩操作。

渐进式rehash

为了避免一次性rehash对服务器性能造成影响，服务器分多次、渐进地将ht[0]慢慢rehash到ht[1]。

步骤如下：

1. 为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]上进行。

主要API见p36.

第五章 跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

查找效率平均水平O（logN），最坏O（N），大部分情况下，跳跃表的效率可以和平衡树媲美，所以有些程序可以用跳跃表来代替平衡树。

Redis使用跳跃表来作为有序集合键的底层实现之一，也被用在集群节点中，其余地方没有再用。

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

跳跃表实现

//跳跃表节点 redis.h/zskiplistNode
typedef struct zskiplistNode{
    //层，程序可以通过层来加快访问其他节点的速度，一般来说
    //层越多，访问其他节点的速度就越快
    struct zskiplistLevel{
        //前进指针，用于从表头向表尾方向访问节点
        struct zskiplistNode *forward;
        //跨度，跨度越大，相距越远，与遍历操作无关，是用来计算排位的，排位就是在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来的值
        unsigned int span;
    }level[];
    //后退指针
    struct zskiplistNode *backward;
    //分值，可相同
    double score;
    //成员对象，不可相同
    robj* obj;
}zskiplistNode;

多个跳跃表节点就可以组成一个跳跃表

typedef struct zskiplist{
    //表头节点和表尾节点
    struct zskiplistNode *header,*tail;
    //表中节点的数量，不算表头节点
    unsigned longn length;
    //表中层数最大的节点的层数，每个层高都是1至32之间的随机数
    int level;
}zskiplist;

API见p45

第六章 整数集合

整数集合（intset）时候集合键的底层实现之一，当一个集合只包含整数值元素，并且集合元素数量不多时，Redis就会使用整数集合来作为集合键的底层实现。

整数集合的实现

整数集合是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t、int64_t的整数值，并保证不会重复。

//intset.h
typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组，各个项在数组中升序排列，虽然声明写的是int8_t，但真正保存的类型取决于encoding属性的值，分别能存16/32/64位的整数
    int8_t contents[];
}intset;

升级

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

升级分三步：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间；
2. 将原来的所有元素都转换成新类型，注意这里扩展空间后原来的元素是从后往前被重新放到正确的位置上的
3. 添加新元素

向整数集合中添加新元素的时间复杂度是O（n）

升级的好处：

1. 提升灵活性
2. 节约内存

降级

要注意的是，整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

API见p51

第七章 压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一，当一个列表键只包含少量列表项，并且每个列表项要么是小整数要么是长度比较短的字符串，Redis就会使用压缩列表来做列表键的底层实现。哈希键同理。

压缩列表构成

压缩列表各个组成部分以及书名

属性	类型	长度（字节）	用途
zlbytes	uint32_t	4	整个压缩表占用的内存字节数
zltail	uint32_t	4	压缩表表尾节点距离起始地址有多少字节
zllen	uint16_t	2	压缩列表包含的节点数量，当该值等于UINT16_MAX时，节点真实数量需要遍历整个压缩列表得出
entryX	列表节点	不定	各个节点长度由保存的内容决定
zlend	uint8_t	1	0xFF，标志末尾

每个压缩列表节点可以保存一个字节数组或者一个整数值，其中字节数组可以是以下三种长度中的一种：

1. 长度小于（2^6-1）
2. 长度小于2^14-1
3. 长度小于2^32-1

而整数值可以是六种长度中的一种：

1. 4位长，介于0至12之间的无符号整数；
2. 1字节长有符号整数
3. 3字节长有符号整数
4. int16_t
5. int32_t
6. int64_t

每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成。

previous_entry_length可以是1字节或5字节长，如果前一节点的长度小于254字节，则previous_entry_length是1字节，保存前一个节点的长度，如果前一节点的长度大于等于254字节，则previous_entry_length长度是五字节，其中第一字节被置为0xFE，而后四个字节用来保存前一节点的长度。这个属性可以用来逆序遍历节点。

encoding属性记录节点的conten属性所存数据的类型和长度，具体可以看p56，简单来说以11开头表示整数编码，content存的是整数，而以00/01/10开头则表示content存的是字节数组，后面几位存的是长度。

连锁更新

添加和删除节点都可能导致连锁更新的现象，所谓连锁更新，简单来说就是原来e1…eN存的都是250~253字节的数据，那么它们的previous_entry_length只需要1字节，但如果这时在e1之前插入一个大于等于254长度的数据，那么e1的previous_entry_length就不够了，就要从1字节扩充成5字节，但这就导致e1长度超过253字节，导致后续所有节点都要重新分配内存，这就是连锁更新，最坏时间复杂度将达到O（n^2）。

但要注意的是，连锁更新真正造成性能问题的几率是很低的，因为O（n^2）的时间复杂度是在很极端的情况下达到的，所以平均复杂度只是线性的。

具体API见p59

第八章 对象

前面介绍了Redis用到的主要数据结构，但Redis并没有直接使用这些数据结构，而是基于这些数据结构创建了一个对象系统。

Redis对象系统实现了基于引用计数的内存回收机制，还通过引用计数实现了对象共享机制，最后对象带有访问时间记录信息。

对象的类型和编码

每当在Redis数据中新创建一个键值对时，都至少会创建两个对象，每个对象都由一个redisObject表示。

typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    //...
}redisObject;

类型

对象的type属性记录了对象的类型，type属性对应REDIS_STRING/REDIS_LIST/REDIS_HASH/REDIS_SET/REDIS_ZSET五中类型中的一种。

编码和底层实现

对象的ptr指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定，一共有八种。。

使用OBJECT ENCODING命令可以查看一个数据库键的值对象的编码。

字符串对象

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，则字符串对象会将字符串对象的编码设置为int。

如果一个字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，则用一个SDS来保存，编码设置为raw。

如果一个字符串对象保存的是一个字符串值，并且长度小于等于32字节，则使用embstr编码的方式来保存。

int和embstr编码的字符串对象会在某些情况下转换为raw编码，比较特殊的一点是embstr编码的字符串对象实际上时只读的，当修改值的时候就会变成raw。

列表对象

列表对象的编码可以是ziplist或者linkedlist。

当列表对象同时满足以下两个条件的时候，使用ziplist编码：

1. 列表对象保存的所有字符串元素的长度都小于64字节；
2. 列表对象保存的元素数量小于512个；

否则使用linkedlist编码。

哈希对象

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

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

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

否则使用hashtable编码。

集合对象

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

当集合对象同时满足以下两个对象时，使用intset编码：

1. 集合对象保存的所有元素都是整数；
2. 集合对象保存的元素数量不超过512个。

否则使用hashtable编码。

有序集合对象

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

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

typedef struct zset{
    zskiplist* zsl;//按分值从小到大保存了所有集合元素
    dict* dict;//创建了一个从成员到分值的映射
}zset;

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

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

否则使用skiplist编码。

类型检查与命令多态

在Redis中，有些命令可以在多种类型上执行，但有些则不行。

为了确保只有指定类型的键可以执行某些特定的命令，在执行一个类型特定的命令之前，Redis会先检查输入建的类型是否正确，然后再决定是否执行该命令。

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

内存回收

每个对象的引用计数信息由redisObject结构的refcount属性记录，即是基于引用计数的内存回收机制。

对象共享

除了用于实现内存回收机制之外，对象的引用计数属性还带有对象共享的作用。

目前来说，Redis会在初始化服务器时创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当需要用到的时候，服务器就会使用这些共享对象。

对象的空转时长

Redis中的RedisObject结构包含的最后一个属性为lru属性，该属性记录了对象最后一次被命令程序访问的时间。

利用OBJECT IDLETIME命令可以打印出给定键的空转时长，即当前时间减去lru时间算出的值。

第九章 数据库

服务器中的数据库

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

struct redisServer{
    //...
    //一个数组，保存着服务器中所有数据库
    redisDb* db;
    //...
    //服务器的数据库数量，默认16
    int dbnum;
    //...
};

切换数据库

默认情况下，客户端的目标数据库为0号数据库，但可以通过SELECT命令切换。

typedef struct redisClient{
    //...
    //记录客户端当前正在使用的数据库库
    redisDb* db;
    //...
}redisClient;

目前Redis没有可以返回客户端目标数据库的命令。

数据库键空间

typedef struct redisDb{
    //...
    //数据库建空间，保存着数据库中的所有键值对
    dict* dict;
    //...
}redisDb;

在读取一个键之后，服务器会根据键是否存在来更新键的hit次数和miss次数，这两个值可以在INFO stats命令的keyspace_hits和keyspace_misses属性中查看。

设置生存时间或过期时间

通过EXPIRE命令或者PEXPIRE命令，客户端可以以秒或者毫秒精度为数据库中的某个键设置生存时间，过期后就会自动删除生存时间为0的键。

而EXPIREAT或PEXPIREAT命令则以秒或毫秒给数据库中的某个键设置过期时间，过期时间是一个UNIX时间戳，当该时间来临时服务器自动删除该键。

其中EXPIRE、PEXPIRE、EXPIREAT三个命令最后都是转换成PEXPIREAT一样。

redisDb结构中会有一个名为expires的字典，该字典中保存了数据库中所有键的过期时间，这个字典也被称作过期字典。

过期字典的键是一个指针，这个指针指向键空间中的某个键对象，值是一个longlong类型的整数。

PERSIST命令可以移除一个键的过期时间，即将该键值对从过期字典中移除。

过期键删除策略

有三种不同的删除策略：

• 定时删除：在设置键的过期时间的同时，创建一个定时器，让定时器在键的过期时间来临时，立即执行对键的删除操作。【对CPU不友好，内存友好】
• 惰性删除：放任键过期不管，但是每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话就删除该键，如果没有过期就返回该键。【CPU友好，内存不友好】
• 定期删除：每隔一段时间，程序就对数据库进行一次检查，删除里面的过期键。【结合】

Redis的过期键删除策略

使用的是惰性删除和定期删除两种策略。

惰性删除在db.c/expireIfNeeded方法中。

定期删除策略在redis.c/activeExpireCycle方法中。周期性执行，每次执行的时候，则在规定时间内分多次遍历服务器中的各个数据库，随机检查一部分键的过期时间并删除过期的。

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

生成RDB文件

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

载入RDB文件

如果服务器以主服务器模式运行，那么在载入RDB文件时会进行检查，过期键会被忽略。

如果以从服务器模式运行，那么不会检查，所有键都被载入。但因为主从服务器在进行数据同步的时候，从服务器的数据库会被清空，所以一般也不会有影响。

AOF写入

如果数据库中的某个键已经过期但还没有被惰性删除或定期删除，那么AOF文件不会因此而有任何影响，但当过期键被惰性删除或者定期删除之后，程序就会向AOF文件追加一条DEL命令，显示记录该键被删除。

AOF重写和RDB类似，不会管已过期的键。

复制

• 主服务器删除一个键后，会向所有从服务器发送一个del命令，通知从服务器删除该键；
• 从服务器本身不会删除键，即使该键已经过期，也仍然按未过期处理，该get还是能get到，只有在收到主服务器的del命令时才进行删除。

数据库通知

该功能可以让客户端通过订阅给定的频道或者模式，来获取数据库中键的变化，以及数据库中命令的执行情况。

分为两种：

• 键空间通知：某个键执行了什么命令
• 键事件通知：某个命令被什么键执行了

服务器配置的notify-keyspace-events选项决定了服务器所发送通知的类型。

发送通知

发送数据库通知的功能是由notify.c/notifyKeyspaceEvent函数实现，具体实现见p120.

第十章 RDB持久化

RDB文件的创建与载入

Save和BGSAVE两个命令都可以生成RDB文件，但又有不同，save是阻塞的，而BGSAVE则是生成一个子进程创建RDB文件，父进程继续处理命令请求。

实际工作由rdb.c/rdbSave函数完成，上述两个命令都是调用该函数的，载入时实际调用的函数是rdb.c/rdbLoad函数。

在执行BGSAVE命令期间，客户端发送的SAVE和GBSAVE命令会被服务器拒绝，而对于BGREWRITEAOF则会等到BGSAVE写完后再调用。

如果BGREWRITEAOF执行期间调用了BGSAVE，则BGSAVE会被拒绝。

载入RDB文件期间，服务器会一直处于阻塞状态。

自动间隔性保存

Redis会定期使用BGSAVE命令，当Redis服务器启动时，用户可以指定配置文件或传入启动参数设置save选项，若用户没有指定则使用默认的。

save 900 1

save 300 10

save 60 10000

接着设置服务器状态redisServer结构的saveparams属性：

struct redisServer{
    //...
    //记录保存条件的数组
    struct saveparam* saveparams;
    //...
    //修改计数器
    long long dirty;
    //上一次执行bgsave的时间
    time_t lastsave;
};

struct saveparam{
    //秒数
    time_t seconds;
    //修改数
    int changes
};

服务器会以100ms为周期周期性执行函数serverCron，该函数用于对正在运行的服务器进行维护，它会检查save属性中设置的条件是否已经满足，满足就执行BGSAVE。

RDB文件结构

Redis文件所包含的各个部分：

REDIS	db_version	databases	EOF	check_num

RDB文件的最开头是REDIS部分，长度5字节，保存“REDIS”五个字符，用来判断文件是否是RDB文件。

db_version长度为4字节，记录RDB文件的版本号。

databases包含着另个或多个数据库，以及各个数据库中的键值对数据。

EOF长度为1字节，标志着RDB文件正文内容的结束。

check_num是一个8字节的无符号整数，保存一个检验和。

database部分

database部分可以保存任意多个非空数据库，每个非空数据库在RDb文件中可以保存为SELECTDB、db_number、key_value_pairs三个部分。

SELECTDB常量的长度为1字节，当读入程序遇到这个值的时候，它知道接下来要读的是一个数据库号码。

db_number保存一个数据库号码，根据号码大小不同，长度可以是1字节、2字节或5字节。

当程序读入该部分后，服务器会调用SELECT命令切换到对应数据库。

key_value_pairs部分保存该数据库中所有键值对数据。

key_value_pairs部分

不带过期时间的键值对在RDB文件中由TYPE、key、value三部分组成。

带有过期时间的键值对的结构由五部分组成：EXPIRETIME_MS、ms、TYPE、key以及value。

根据TYPE不同，不同类型的值对象在RDB文件中的保存结构都不相同，详细见p128起的叙述，这里只简单记录一下。

• 字符串对象，有两种编码：REDIS_ENCODING_INT或者REDIS_ENCODING_RAW，如果是前者则按照ENCODING和integer两部分保存，若是后者，则又有压缩或不压缩两种方式保存。
• 列表对象，TYPE的值为REDIS_RDB_TYPE_LIST，则表示value存的是REDIS_ENCODING_LINKEDLIST编码对象，RDB中保存结构分为list_length、item1、item2…itemN。
• 集合对象，编码REDIS_ENCODING_HT，也是分为长度和元素集合存储。
• 哈希表对象，也是长度，后面跟各个kv对。
• 有序集合对象，也一样，长度跟上分值和成员本身值。
• INTSET编码的集合，存的时候整数转换成字符串存，取的时候再转换回整数。
• ZIPLIST编码的列表、哈希表或者有序集合，存的时候是把压缩列表转换成了一个字符串对象。

分析RDB文件

od命令可以打印RDB文件

od -c dump.rdb

具体可看这一节书中的例子。

Redis本身带有RDB检查工具redis-check-dump。

od命令加上-c参数和-x参数可以同时以ASCII编码和十六进制显示，便于查看检验和。

第十一章 AOF持久化

AOF(Append Only File)

与RDB持久化通过保存数据库中的键值对来记录数据库状态不同，AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态的。

是纯文本格式。

AOF持久化的实现

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

服务器配置的appendfsync选项有三个值：always、everysec和no。

appendfsync的值	flushAppendOnlyFile的行为
always	将aof_buf缓冲区的所有内容写入并同步到AOF文件
everysec	将aof_buf缓冲区的所有内容写入到AOF文件，但每隔一秒才同步一次
no	只写，不同步，什么时候同步由操作系统控制

AOF文件的载入与数据还原

1. 创建一个不带网络连接的微客户端；
2. 从AOF文件中分析并读取一条写命令；
3. 使用伪客户端执行读出的写命令；
4. 重复步骤2和3，直到AOF文件中所有写命令都被处理完毕。

AOF重写

随着时间流逝，AOF文件内容会越来越多，为了解决AOF文件体积膨胀的问题，Redis提供了AOF重写功能，新AOF文件中不会包含任何浪费空间的冗余命令，所以体积要小很多。

虽然功能命名为AOF文件重写，但实际上，AOF文件重写并不需要对现有的AOF文件进行任何读写操作，真正操作时读取服务器当前的数据库状态来实现的。

在实际中，为了避免在执行命令时造成客户端输入缓冲区溢出，重写时会先检查元素数量，如果超过redis.h/REDIS_AOF_REWRITE_ITEMS_PER_CMD值时，就分成多条命令来写，所以并不是简单的一个键值对数据用一条命令来代替，具体见p147。

为了避免AOF操作重写造成线程长时间阻塞，会让子进程执行重写，这就是AOF后台重写，但这样又会导致子进程在重写的时候父进程执行了新的写操作，使得子进程重写后的AOF文件并不一致。

为了解决这个问题，Redis设置了一个AOF重写缓冲区，这个缓冲区在子进程被创建之后开始使用，当Redis执行完一个写命令之后，它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区。当子进程完成AOF重写工作之后，它会向父进程发送一个信号，父进程接收到该信号之后会调用一个信号处理函数，并执行以下两步：

1. 将AOF重写缓冲区的所有内容写入到新AOF文件中；
2. 对新的AOF文件进行改命，原子地覆盖原有的AOF文件。

完成这两步后，父进程就可以正常接收命令请求了。

整个步骤里，父进程只有在最后调用信号处理函数的时候会阻塞。

这就是AOF后台重写，也是命令BGREWRITEAOF命令的实现原理。

第十二章 事件

Redis服务器是一个事件驱动程序，需要处理以下两类事件：

1. 文件事件（file event）：服务器通过套接字与客户端连接，文件事件就是服务器对套接字操作的抽象，完成一系列网络通信操作。
2. 时间事件（time event）：Redis服务器中的一些操作需要在给定的时间点执行，时间事件就是对这类定时操作的抽象。

文件事件

使用I/O多路复用来同时监听多个套接字。

是基于Reactor模式实现的网络通信程序。

文件事件处理器有四个组成部分：套接字、I/O多路复用程序、文件时间分派器（dispatcher）以及事件处理器。

尽管多个文件事件可能会并发出现，但I/O多路复用程序总是将所有产生事件的套接字都放在一个队列里，然后通过这个队列以有序地、同步地、每次一个套接字的方式向文件事件分派器传送套接字。当上一个套接字产生的事件被处理完毕之后，再进行下一个。

I/O多路复用程序的实现中包装了常见的select、epoll、evport和kqueue。

有两类事件：AE_READABLE和AE_WRITABLE。

如果一个套接字同时产生了这两种事件，那么文件事件分派器优先处理AE_READABLE事件。

文件事件有多个处理器，最常用的是连接应答处理器、命令请求处理器和命令回复处理器。

具体看p156.

时间事件

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

• 定时事件
• 周期性事件

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

• id，全局唯一，新的比旧的大
• when：毫秒精度unix时间戳，记录时间事件的到达时间
• timeProc：时间事件处理器，一个函数。如果该函数返回值为AE_NOMORE，则为定时事件，否则是周期性事件。

书上说目前版本的Redis只使用了周期事件。

在实现方面，服务器将所有时间事件都放在一个无序链表中，每当时间事件执行器运行时，它就遍历整个链表找到所有已到达的时间事件，并调用相应的事件处理器。

【注】在目前的版本中，正常模式下的Redis服务器只使用serverCron一个时间事件，在benchmark模式下也只有两个时间事件，所以用无序链表不会影响性能。

事件的调度与执行

事件的调度和执行由ae.c/aeProcessEvents函数负责，大致逻辑如下：

1. 获取到达时间离当前时间最近的时间事件，最计算出距离还有多少毫秒赋值给remaind_ms
2. 如果剩余时间小于0，则将remaind_ms更新为0
3. 根据remaind_ms创建一个timeval结构
4. 根据timeval结构阻塞并等待文件事件产生，如果remaind_ms==0，则不阻塞
5. 处理所有产生的文件事件
6. 处理所有已到达的时间事件

将aeProcessEvents函数置于一个循环里面，加上初始化和清理函数，这就构成了Redis服务器的主函数。

第十三章 客户端

Redis服务器是典型的一对多服务器程序。

对于每个与服务器进行连接的客户端，服务器都会其建立了相应的redis.h/redisClient结构，该结构保存了客户端当前的状态信息以及相关数据结构。

Redis服务器状态结构的clients属性是一个链表，保存了所有与服务器相连的客户端的状态结构。

客户端属性

客户端属性可以分为两类：

1. 一类是比较通用的属性；
2. 另一类是和特定功能相关的属性，比如操作数据库时用到的db属性等等。

套接字描述符

fd属性的值是-1或者大于-1的整数，-1表示伪客户端，其他表示普通客户端。

名字

name属性一般是空，但可以使用CLIENT setname设置一个，使得客户端更好区分。

标志

flags属性记录了客户端的角色以及目前所处的状态，具体各个标志可看书p165或redis.h源码。

输入缓冲区

客户端状态的输入缓冲区用于保存客户端发送的命令请求。

命令与命令参数

在服务器将客户端发送的命令请求保存到客户端的输入缓冲区之后，服务器会解析得到命令参数以及参数个数，并把这两个值分别保存到argv属性和argc属性。

命令的实现函数

服务器之后会到命令表（一个字典）中根据argv[0]的值查找命令实现的一个数据结构redisCommand，argv[0]不区分大小写，找到后将客户端状态的cmd属性指向该结构。

输出缓冲区

执行命令所得的命令回复会被保存在客户端状态的输出缓冲区中，每个客户端都有两个输出缓冲区可用，一个大小固定，一个大小可变。

• 大小固定的缓冲区用于保存长度比较小的回复
• 大小可变的缓冲区用于保存长度比较大的回复

大小固定的缓冲区由buf和bufpos两个属性组成，buf是一个大小为REDIS_REPLY_CHUNK_BYTES字节的字节数组，而bufpos属性则记录buf数组已使用的字节数量，数组长度默认16KB。

可变大小缓冲区由reply链表和一个或多个字符串对象组成。

身份验证

authenticated属性用于记录客户端是否通过了身份验证，仅在服务器启用了身份验证功能时使用。

时间

c_time：记录创建客户端的时间，CLIENT list命令的age域记录了这个秒数。

lastinteraction属性记录客户端与服务器最后一次互动的时间，idle域记录该秒数。

obuf_soft_limit_reached_time属性记录了输出缓冲区第一次到达软性限制的时间。

客户端的创建与关闭

普通客户端

创建普通客户端时，就把新的客户端状态添加到服务器状态结构clients链表的末尾。

普通客户端被关闭的原因有多种：

• 客户端进程退出或者被杀死；
• 客户端向服务器发送了带有不符合协议格式的命令请求；
• 客户端成了CLIENT KILL命令的目标；
• 客户端空转时间超过了timeout配置选项（有一些例外情况见书上p173）
• 客户端发送的命令请求大小超过输入缓冲区限制大小；
• 要发送给客户端的命令回复大小超过了输出缓冲区的限制。服务器使用两种模式来限制客户端输出缓冲区的大小：硬性限制和软性限制。

Lua脚本的伪客户端

服务器会在初始化时创建负责执行Lua脚本中包含的Redis命令的伪客户端，并将这个伪客户端关联在服务器状态结构的lua_client属性中；

lua_client伪客户端在服务器运行的整个生命期中会一直存在，只有服务器被关闭时，这个客户端才会被关闭。

AOF文件的伪客户端

服务器在载入AOF文件时，会创建用于执行AOF文件包含的Redis命令的伪客户端，并在载入完成之后关闭该伪客户端。

第十四章 服务器

Redis服务器负责与多个客户端建立网络连接，处理客户端发送的命令请求，在数据库中保存客户端执行命令所产生的数据，并通过资源管理来维持服务器自身的运转。

命令请求的执行过程

1. 客户端向服务器发送命令请求，命令请求会转换成协议格式发送
2. 服务器接受命令请求并存入客户端状态的输入缓冲区中，然后处理，在数据库中进行设置操作，并产生命令回复
3. 服务器将命令回复发送给客户端
4. 客户端接受服务器返回的命令回复并将命令回复打印给用户观看

serverCron函数

serverCron函数默认每隔100ms执行一次，这个函数负责管理服务器的资源，并保持服务器自身的良好运转。

更新服务器时间缓存

为了减少对当前时间系统调用的执行次数，服务器状态中的unixtime属性和mstime属性被用作当前时间的缓存：

struct redisServer{
    //...
    //保存了秒级精度的系统当前unix时间戳
    time_t unixtime;
    //保存了毫秒级精度的系统当前unix时间戳
    long long mstime;
    //...
};

这两个属性记录的时间精确度并不高，当需要执行高精度时间的功能来说，服务器还是会再次执行系统调用。

更新LRU时钟

服务器状态中的lruclock属性保存了服务器的LRU时钟，也是服务器时间缓存的一种：

struct redisServer{
    //...
    //默认每十秒更新一次，用于计算键的空转时长
    unsigned lruclock:22;
    //...
};

每个redis对象都会有一个lru属性，这个lru属性保存了对象最后一次被命令访问的时间

typedef struct redisObject{
    //...
    unsigned lru:22;
    //...
};

空转时间就是lruclock-lru的值，当然只是一个模糊估计值。

更新服务器每秒执行命令次数

serverCron函数中的trackOperationsPerSecond函数会以抽样计算的方式估算并记录最近一秒钟处理的命令请求数量，可通过INFO status命令中的instantaneous_ops_per_sec查看。

struct redisServer{
    //...
    //上一次抽样的时间
    long long ops_sec_last_sample_time;
    //上一次抽样时服务器已执行命令的数量
    long long ops_sec_last_sample_ops;
    //数组中的每一项记录了一次抽象结果
    long long ops_sec_samples[REDIS_OPS_SEC_SAMPLES];
    //数组索引，每次抽样后加1，索引到最后一格则变成0，形成环形数组
    int ops_sec_idx;
};

数组中记录的值是根据服务器平均每一毫秒处理了多少个命令请求乘以1000估算出来的。

instantaneous_ops_per_sec的值则是根据环形数组里的值求平均数得到的估算值。

更新服务器内存峰值记录

服务器状态中的stat_peak_memory属性记录该值。

处理SIGTERM信号

收到该信号后悔调用sigtermHandler函数，会打开服务器状态的shutdown_asap标志，用于关闭服务器。

管理客户端资源

serverCron函数中每次都会调用clientsCron函数，该函数会对一些客户端进行一些检查。

管理数据库资源

serverCron函数每次都会调用databasesCron函数，会对一部分数据库进行检查。

执行被延迟的BGREWRITEAOF命令

服务器状态的aof_rewrite_scheduled标志记录是否延迟。

检查持久化操作的运行状态

服务器状态使用rdb_child_pid属性和aof_child_pid属性记录执行BGSAVE命令和BGREWRITEAOF命令的子进程的ID，也可以用来查询这两个命令是否在执行。

将AOF缓冲区中的内容写入AOF文件

关闭异步客户端

增加cronloops计数器的值

该值记录serverCron函数执行的次数。

初始化服务器

服务器从刚启动到能够接受客户端命令请求，需要经过一系列的初始化和设置过程，比如初始化服务器状态，接受用户指定的服务器配置，创建相应的数据结构和网络连接等等。

初始化服务器状态结构

初始化服务器的第一步就是创建一个struct redisServer类型的实例变量server作为服务器的状态，并为各个属性设置默认值。

主要函数是initServerConfig，会做以下工作：

• 设置服务器的运行ID
• 设置服务器的默认运行频率。
• 设置服务器的默认配置文件路径
• 设置服务器的运行架构
• 设置服务器的默认端口号
• 设置服务器的默认RDB和AOF持久化条件
• 初始化LRU时钟
• 创建命令表

载入配置选项

初始化服务器数据结构

在initServerConfig函数中只初始化了命令表一个数据结构，不过除了命令表之外，服务器状态还包含其他数据结构，这里列两个比较熟悉的，更多数据结构见书：

• server.clients链表
• server.db数组

主要函数是initServer函数，除了初始化数据结构外，该函数还做了一些其他重要的操作设置：

• 为服务器设置进程信号处理器
• 创建共享对象
• 打开服务器监听端口
• 为serverCron函数创建时间事件
• 检查AOF
• 初始化后台I/O模块

还原数据库状态

执行事件循环

第十五章 复制

在Redis中，用户可以通过SLAVEOF命令或者设置slaveof选项，让一个服务器去复制另一个服务器，则被复制的服务器为主服务器，进行复制的称作从服务器。

旧版复制功能的实现（2.8版本以前）

Redis的复制功能分为同步（sync）和命令传播两个操作。

同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。

命令传播操作则用于在主服务器的数据库状态被修改，导致主从服务器的数据库状态不一致时，让主从服务器数据重新回到一致的状态。

同步

当客户端向从服务器发送SLAVEOF命令时，要求从服务器复制主服务器，从服务器需要执行同步操作。

1. 从服务器向主服务器发送SYNC命令。
2. 主服务器执行BGSAVE命令，在后台生成一个RDB文件，并使用缓冲区来记录从现在开始执行的所有写命令
3. 当主服务器的BGSAVE命令执行完毕时，主服务器会将BGSAVE命令生成的RDB文件发送给从服务器
4. 主服务器将缓冲区里的所有写命令发送给从服务器。

命令传播

同步操作执行完之后，主从服务器两者的数据库将达到一致状态，但这种一致并不是永远的，每当主服务器执行客户端发送的写命令时，主服务器的数据库就可能被修改并导致主从服务器状态不再一致，这时就需要主服务器将运行的写命令传播给从服务器，使两者数据库保持一致。

旧版复制功能的缺陷

简单来说，同步完成之后主从服务器之间是通过命令传播来保持一致的，但如果在命令传播阶段主从服务器断开连接了，等到从服务器重新连上来的时候，它会重新发送SYNC同步命令将自上次同步之后的所有命令都重新生成RDB文件同步一遍，但这RDB文件中可能有很多操作是在掉线之前的命令传播阶段就做了的，所以会很低效，而且SYNC是一个非常耗费资源的资源。

新版复制功能的实现

为了解决上述缺陷，Redis从2.8版本开始使用PSYNC命令代替SYNC命令来执行复制时的同步操作。

PSYNC命令具有完整重同步和部分重同步两种模式：

• 完整重同步用于处理初次复制情况，和SYNC命令执行步骤基本一样。
• 部分重同步则用于处理断线后重复制情况：当从服务器在断线后重新连接主服务器时，如果条件允许，主服务器可以将主从服务器连接断开期间执行的写命令发送给从服务器，从服务器只处理这些写命令。

部分重同步的实现

部分重同步功能由以下三个部分构成：

• 主服务器的复制偏移量（replication offset）和从服务器的复制偏移量。个人感觉可以和TCP连接中收发端的滑动窗口以及序号类比，主服务器发了N字节，就把主服务器的偏移量加上N，从服务器接收到N字节就把自己的偏移量加上N，主从一致时，主从服务器的偏移量应该是一样的。
• 主服务器的复制积压缓冲区（replication backlog），主服务器每次往从服务器命令传播时也会往一个叫做复制积压缓冲区的定长先进先出队列中写入相同命令，当主从服务器断开连接，这时主从服务器的偏移量就不一样了，当从服务器重新连上来时会检查主从偏移量之间的差距，如果相差的数据大小没有超过复制积压缓冲区大小，则可从积压缓冲区中将没接收到的数据重新发送，即PSYNC，否则只能完整重同步；
• 服务器的运行ID（run ID），实现部分重同步还需要用到服务器运行ID，是40个随机十六进制，当从服务器初次对主服务器进行复制时，主服务器会将自己的运行ID传送给从服务器，掉线重连后从服务器会向主服务器发送该ID，如果相同则说明连上的就是之前的主服务器，就执行PSYNC，否则只能完整重同步。

PSYNC命令实现流程

复制的实现

通过向从服务器发送SLAVEOF命令，可以让一个从服务器去复制一个主服务器（2.8版本以上）。

SALVEOF <mater_ip> <master_port>

本节是一个具体例子，可以看p211，这里简单列出步骤：

1. 设置主服务器的地址和端口；
2. 建立套接字连接；
3. 发送ping命令；
4. 身份验证；
5. 发送端口信息；
6. 同步，从服务器向主服务器发送PSYNC命令，值得一提的是在同步操作之前只有从服务器时主服务器的客户端，但是在执行同步操作之后，主服务器也是从服务器的客户端；
7. 命令传播。

心跳检测

在命令传播阶段，从服务器会默认以每秒一次的频率向主服务器发送命令REPLCONF ACK <replication_offset>，主要有三个作用：检测主从服务器的网络连接状态、辅助实现min-slaves选项、检测命令丢失。

2.8版本之前没有这个命令，所以尽量使用2.8版本以上的Redis。

第十六章 Sentinel

Sentinel（哨兵）是Redis的高可用性解决方案：由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器以及这些主服务器下的所有从服务器，当被监视的主服务器下线时，Sentinel系统会自动将下线主服务器属下的某个从服务器升级为新的主服务器，然后由新的主服务器代替已下线的主服务器继续执行命令请求。

启动并初始化Sentinel

启动一个Sentinel可以使用命令：redis-sentinel /path/to/your/sentinel.conf或者命令redis-server /path/to/your/sentinel.conf --sentinel.

启动步骤如下：

1. 初始化一个服务器
2. 将普通Redis服务器使用的代码替换城Sentinel专用代码
3. 初始化Sentinel状态
4. 根据给定的配置文件，初始化Sentinel的监视主服务器列表
5. 创建连上主服务器的网络连接，对于每个被Sentinel监视的主服务器来说，Sentinel会创建两个连向主服务器的异步网络连接：一个是命令连接，一个是订阅连接。

获取主服务器信息

Sentinel默认会以每十秒一次的频率向被监视的主服务器发送INFO命令，从命令返回的结果中可以看出该主服务器的信息以及其属下的从服务器信息，并进行更新。

获取从服务器信息

当Sentinel发现主服务器有新的从服务器出现时，Sentinel除了会为这个新的从服务器创建新的实例之外，还会创建连接到从服务器的命令连接和订阅连接。

Sentinel也会默认每十秒一次向从服务器发送INFO命令。

向主服务器和从服务器发送信息

默认下，Sentinel会以每两秒一次的频率向所有被监视的主从服务器发送以下格式的命令：

PUBLISH \__sentine__:hello "<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_name>,<m_pi>,<m_port>,<m_epoch>"

s_开头的是Sentinel本身的信息，m_表示的是当前监视的主或从服务器的信息。

接收来自主服务器和从服务器的频道信息

当Sentinel与一个主服务器或从服务器建立起订阅连接之后，Sentinel就会通过订阅连接，向服务器发送以下命令：SUBSCRIBE \__sentinel__: hello，对该频道的订阅会一直持续到连接断开为止。

对于监视同一个服务器的多个Sentinel来说，一个Sentinel发送的信息会被其他Sentinel接收到并处理。

Sentinel和Sentinel之间不会创建订阅连接，只有命令连接。

检测主观下线状态

默认下，Sentinel会以每秒一次的频率向所有与它建立了命令接连的实例发送ping命令，并通过返回的结果判断实例是否在线。

Sentinel配置文件中的down-after-milliseconds选项指定了Sentinel判断实例进入主观下线所需的时间长度：如果一个实例在down-after-milliseconds毫秒内，连续向Sentinel返回无效回复，那么Sentinel会修改这个实例所对应的实例结构，在结构的flags属性中打开SRI_S_DOWN标识，以此来表示这个实例已经进入主观下线状态。

检查客观下线状态

当Sentinel将一个主服务器判断为主观下线之后，为了确认这个主服务器是否真的下线了，它会向同样监视这一主服务器的其他Sentinel进行询问，当Sentinel从其他Sentinel那接收到足够数量的已下线判断之后，Sentinel就会将从服务器判定为客观下线，打开主服务器实例结构flags属性的SRI_O_DOWN标识，并对主服务器执行故障转移操作。

选举领头Sentinel

当一个主服务器被判断为客观下线时，监视这个下线主服务器的各个Sentinel会进行协商，选举出一个领头Sentinel，由它对下线主服务器进行故障转移操作。

选举规则还比较复杂，详细看p239.

故障转移

在选举产生出领头Sentinel之后，领头Sentinel将对已下线的主服务器执行故障转移擦操作，该操作包含以下三个步骤：

1. 在已下线主服务器属下的所有从服务器中挑选出一个转换成主服务器；
2. 让已下线主服务器属下的所有从服务器改为复制新的主服务器；
3. 将已下线主服务器设置为新的主服务器的从服务器。

第十七章 集群

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

节点

连接各个节点的工作可以使用CLUSTER MEET命令来完成，Redis服务器会在启动时根据cluster-enabled配置选项是否是yes来决定是否开启服务器的集群模式。

集群数据结构

clusterNode结构保存了一个节点的当前状态：

struct clusterNode{
    //创建节点的时间
    mstime_t ctime;
    //节点名字，由40个十六进制组成
    char name[REDIS_CLUSTER_NAMELEN];
    //节点标识
    int flags;
    //节点当前的配置纪元
    uint64_t configEpoch;
    //节点ip
    char ip[REDIS_IP_STR_LEN];
    //节点端口
    int port;
    //保持连接节点所需的有关信息
    clusterLink* link;
    //...
};

typedef struct clustereLink{
    //连接的创建时间
    mstime_t ctime;
    //TCP套接字描述符
    int fd;
    //输出缓冲区，保存着等待发送给其他节点的消息
    sds sndbuf;
    //输入缓冲区，保存着从其他节点接收到的消息
    sds rcvbuf;
    //与这个连接相关联的节点，如果没有就为NULL
    struct clusterNode* node;
} clusterLink;

//每个节点都保存一个clusterState结构，记录在当前节点的视角下集群目前所处的状态
typedef struct clusterState{
    //指向当前节点的指针
    clusterNode* myself;
    //配置纪元
    uint64_t currentEpoch;
    //集群当前的状态，在线还是下线
    int state;
    //集群中至少处理着一个槽的节点的数量
    int size;
    //集群节点名单
    dict* nodes;
    //...
} clusterState;

CLUSTER MEET命令的实现

槽指派

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

当所有16384个槽都有节点在处理时，集群处于上线状态，否则处于下线状态。

可以利用CLUSTER ADDSLOTS命令将一个或多个槽指派给节点负责。

记录节点的槽指派信息

struct clusterNode{
    //...
    unsigned char slots[16384/8];
    int numslots;
    //...
};

slots属性是一个二进制位数组，每一位用来表示该节点是否负责处理该槽，1表示处理。

传播节点的槽指派信息

一个节点除了会将自己负责处理的槽记录在clusterNode结构的slots属性和numslots之外，还会将自己的slots数组通过消息发送给集群中的其他节点。

记录集群所有槽的指派信息

typedef struct clusterState{
    //...
    clusterNode* slots[16384];
    //...
}clusterState;

CLUSTER ADDSLOTS命令的实现

1. 遍历所有输入的槽，如果有哪怕一个槽已经指派给了某个节点，则返回错误
2. 若所有输入槽都是未指派槽，则再次遍历所有输入槽，指派给当前节点，修改clusterState.slots数组和clusterNode.slots数组

在集群中执行命令

集群上线后，当客户端向节点发送命令时，接收命令的节点会计算出命令要处理的数据库属于哪个槽，如果是自己则直接执行，如果不是自己则向客户端返回MOVED错误，指引客户端转向正确的节点。

计算键属于哪个槽

def slot_number(key):
	return CRC16(key) & 16383

节点数据库的实现

节点和单机服务器在数据库方面的一个区别是，节点只能使用0号数据库，而单机Redis没有这个限制，其他地方则相同。

重新分片

Redis集群的重新分片操作可以将任意数量已经指派给某个节点的槽改为指派给另一个节点。

重新分片可以在线进行。

Redis集群的重新分片操作时由Redis的集群管理软件redis-trib负责执行的，具体步骤如下：

1. redis-trib向目标节点发送CLUSTER SETSLOT <slot> IMPORTING <source_id>命令，让目标节点准备好从源节点导入属于槽slot的键值对
2. redis-trib对源节点发送CLUSTER SETSLOT <slot> MIGRATING <target_id>，让源节点准备好将属于槽slot的键值对迁移到目标节点
3. redis-trib向源节点发送CLUSTER GETKEYSINSLOT <slot> <count>命令，获得最多count个属于槽slot的键值对的键名
4. 对于3中获得的每个键名，redis-trib都向源节点发送一个MIGRATE <target_ip> <target_port> <key_name> 0 <timeout>命令，将被选中的键值对原子地迁移
5. 重复3和4直到所有节点都完成迁移
6. redis-trib向集群中的任意一个节点发送CLUSTER SETSLOT <slot> NODE <target_id>命令，将槽slot指派给目标节点，这一指派信息会通过消息发送至整个集群，最终集群中的所有节点都会知道槽slot已经指派给了目标节点。

ASK错误

CLUSTER SETSLOT IMPORTING命令的实现

typedef struct clusterState{
    //...
    clusterNode* importing_slots_from[16384];
    //...
}clusterState;

如果importing_slots_from[i]的值不是NULL，而是指向一个clusterNode节点，那么表示当前节点正在从clusterNode所代表的节点导入槽i。

在对集群进行重新分片的时候，向目标节点发送命令：

CLUSTER SETSLOT <i> IMPORTING <source_id>可以将目标节点的importing_slots_from[i]的值设置为source_id所代表的节点的clusterNode结构。

CLUSTER SETSLOT MIGRATING命令的实现

typedef struct clusterState{
    //...
    clusterNode* migrating_slots_to[16384];
    //...
}clusterState;

同理，如果migrating_slots_to[i]的值不为NULL，则表示正在向所指的clusterNode节点迁移。

命令：CLUSTER SETSLOT <i> MIGRATING <target_id>

ASK错误

如果节点收到一个键key的请求，但并没有在自己的数据库里找到键key，那么节点会检查自己的clusterState.migrating_slots_to[i]，如果正在迁移，则会向客户端发送一个ASK错误，引导客户端到正在导入槽i的节点去查找key。

ASKING命令

ASKING命令唯一要做的就是打开发送该命令的客户端的REDIS_ASKING标识。

当客户端接受到ASK错误时会先向转向节点发一个ASKING命令，然后才再次发送命令。

客户端的REDIS_ASKING标识是一个一次性标识，当节点执行了一个带有REDIS_ASKING标识的客户端发送的命令之后，该客户端的REDIS_ASKING标识就会被移除。

ASK错误和MOVED错误的区别

MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点；

ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施。

复制与故障转移

Redis集群中的节点分为主节点和从节点，其中主节点用于处理槽，从节点用于复制某个主节点，并在被复制的主节点下线时代替下线主节点继续处理命令请求。

设置从节点

向一个节点发送命令：CLUSTER REPLICATE <node_id>可以让接收命令的节点成为noid_id所指定节点的从节点并开始复制。

struct clusterNode{
    //...
    //如果这时一个从节点，那么指向主节点
    struct clusterNode* slaveof;
    //...
};

集群中的所有节点都会在代表主节点的clusterNode结构的slaves属性和numslaves属性中记录正在复制这个主节点的从节点名单。

struct clusterNode{
    //...
    //正在复制这个主节点的从节点数量
    int numslaves;
    //一个数组，每个项指向一个正在复制这个主节点的从节点的clusterNode结构
    struct clusterNode** slaves;
    //...
};

故障检测

集群中的每个节点都会定期向集群中的其他节点发送ping消息，如果接受ping消息的节点没有在规定的时间内返回pong消息，则会被标记为疑似下线（probable fail，PFAIL）。

当一个主节点A通过消息得知主节点B认为主节点C进入了PFAIL，主节点A会在自己的clusterState.nodes字典里找到主节点C，并将B的下线报告添加到fail_reports链表中。

struct clusterNode{
    //...
    //一个链表，记录了所有其他节点对该节点的下线报告
    list* fail_reports;
    //...
};
struct clusterNodeFailReport{
    //报告目标节点已经下线的节点
    struct clusterNode* node;
    //最后一次从node节点收到下线报告的时间
    mstime_t time;
}typedef clusterNodeFailReport;

如果在一个集群里面，半数以上负责处理槽的主节点都将某个主节点X报告为疑似下线，那么这个主节点X将被标记为已下线，将X标记为已下线的节点会向集群广播此消息，所有收到该消息的节点都会立刻将X标记为已下线。

故障转移

当一个从节点发现自己正在复制的主节点进入了已下线状态，则会开始进行故障转移。

1. 从所有从节点中选中一个节点，选举方法和16章中选举零头Sentinel的方法非常相似，因为两者都是基于Raft算法的领头选举方法来实现的；
2. 被选中的从节点执行SLAVEOF no one命令，成为新的主节点；
3. 新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己；
4. 新的主节点广播PONG消息；
5. 新的主节点开始接受命令请求。

消息

节点发送的消息主要有以下五种：

1. MEET消息
2. PING消息
3. PONG消息，以上三种消息都是用相同的消息正文，所以是通过消息头的type属性来判断的，每次发送这三种消息的时候，发送者都从自己的已知节点列表中随机选出两个节点保存到clusterMsgDataGossip结构中发送出去。
4. FAIL消息，当主节点A将主节点B标记为FAIl时，A会向集群广播关于B的FAIL消息，FAIL消息的正文里只包含nodename属性。
5. PUBLISH消息，当客户端向集群中的某个节点发送命令PUBLISH <channel> <message>命令，接收到PUBLISH命令的节点不仅会向channel频道发送消息message，还会向集群广播一条PUBLISH消息，所有接受到这条PUBLISH消息的节点都会向channel发送message。

一条消息由消息头和消息正文组成。

消息头的主要字段见p282，由clusterMsg结构表示。

第十八章 发布与订阅

Redis的发布与订阅功能由PUBLISH、SUBSCRIBE、PSUBSCRIBE等命令组成。

频道的订阅与退订

当一个客户端执行SUBSCRIBE命令订阅某个或某些频道的时候，这个客户端与被订阅频道之间就建立起了一种订阅关系。

Redis将所有频道的订阅关系都保存在服务器状态的pubsub_channels字典里面，这个字典的键是某个被订阅的频道，而键的值则是一个链表。

struct redisServer{
    //...
    //保存所有频道的订阅关系
    dict* pubsub_channels;
    //...
};

订阅和退订就是在字典上进行操作，p294。

模式的订阅与退订

PSUBSCRIBE命令用来订阅模式，与频道类似，服务器也将所有模式的订阅关系都保存在一个属性里：

struct redisServer{
    //...
    //保存所有模式订阅关系
    list *pubsub_patterns;
    //...
};

该属性是一个链表，链表中的每个节点都包含着一个pubsubPattern结构，这个结构如下：

typedef struct pubsubPattern{
    //订阅模式的客户端
    redisClient * client;
    //被订阅的模式
    robj* pattern;
}pubsubPattern;

模式的订阅与退订也就是在list上进行操作，p296.

发送消息

当一个Redis客户端执行PUBLISH <channel> <message>命令将消息message发送给频道channel的时候，服务器需要执行以下两个动作：

1. 将消息message发送给channel频道的所有订阅者；
2. 如果有一个或多个模式和channel频道匹配，那么将message发送给pattern模式的订阅者。

查看订阅信息

PUBSUB命令是Redis2.8新增加的命令之一，客户端可以通过这个命令来查看频道或模式的相关信息。

PUBSUB CHANNELS [pattern]用于返回服务器当前被订阅的频道

PUBSUB NUMSUB [channel-1 channel-2 ...]接受任意多个频道作为输入参数，并返回这些频道的订阅者数量。

PUBSUB NUMPAT命令用于返回服务器当前被订阅模式的数量，即返回pubsub_patterns链表的长度。

第十九章 事务

Redis通过MULTI、EXEC、WATCH等命令来实现事务功能。

事务的实现

一个事务从开始到结束通常会经历三个阶段：

• 事务开始，MULTI命令的执行标志着事务的开始，打开了客户端状态的flags属性中的REDIS_MULTI标识。

• 命令入队

  

• 事务执行，每个客户端都有自己的事务状态，这个事务状态保存在客户端状态的mstate属性里，该属性是一个multiState结构：

typedef struct multiState{
    //事务队列，fifo顺序
    multiCmd* commands;
    //已入队命令计数
    int count;
} multiState;

typedef struct multiCmd{
    //参数
    robj **argv;
    //参数数量
    int argc;
    //命令指针
    struct redisCommand *cmd;
} multiCmd;

当一个处于事务状态的客户端向服务器发送EXEC命令时，这个EXEC命令将立即被服务器执行，服务器会遍历该客户端的事务队列，执行队列中保存的所有命令，最后将执行命令所得的结果全部返回给客户端。

WATCH命令的实现

WATCH命令是一个乐观锁，它可以在EXEC命令执行之前监视任意数量的数据库键，并在EXEC命令执行时检查被监视的键是否至少有一个已经被修改过，如果是，服务器将拒绝执行事务并返回代表执行失败的空回复。

每个Redis数据库都保存着一个watched_keys字典，这个字典的键是某个被WATCH命令监视的数据库键，而字典的值则是一个链表，链表中记录了所有监视相应数据库键的客户端。

typedef struct redisDb{
    //...
    //正在被WATCH命令监视的键
    dict* watched_keys;
    //...
};

所有对数据库进行修改的命令在执行之后都会调用multi.c/touchWatchKey函数对该字典进行检查，查看是否有客户端正在监视刚刚被修改过的键，如果有则打开该客户端的REDIS_DIRTY_CAS标识，标识客户端的事务安全性已经被破坏。

当服务器接收到某客户端的EXEC命令时会检查该客户端是否打开了REDIS_DIRTY_CAS标识，如果打开了则拒绝执行。

事务的ACID性质

原子性（Atomicity）、一致性（Consistency）、隔离性（isolation）以及持久性（durability），前三者总是有的，当Redis运行在某种特定的持久化模式下时，事务也具有持久性。

Redis没有事务回滚机制。

Redis事务中三个可能出错的地方：

1. 入队错误
2. 执行错误
3. 服务器停机

Redis事务只有当服务器运行在AOF持久化模式下，并且appendfsync选项的值为always时才具有持久性（同时还需要no-appendfsync-on-rewrite配置选项没有被打开）。

其实不管Redis在什么模式下运作，在一个事务的最后加上SAVE命令总可以保证事物的耐久性，但这种做法效率太低，所以不具有实用性。

第二十章 Lua脚本

Redis从2.6版本开始引入对Lua脚本的支持，客户端可以通过使用Lua脚本，直接在服务器端原子地执行多个Redis命令。

创建并修改Lua环境

• 创建一个基础的Lua环境
• 载入函数库
• 创建redis全局表格
• 使用redis自制的随机函数来替换Lua原有的随机函数
• 创建排序辅助函数
• 创建redis.pcall函数的错误报告辅助函数
• 保护lua的全局环境
• 将lua环境保存到服务器状态的lua属性中

lua环境协作组件

一个是负责执行Lua脚本中的redis命令的伪客户端，一个是用于保存Lua脚本的lua_scripts字典，该字典有两个作用：实现SCRIPT EXISTS命令和实现脚本复制功能。

EVAL命令的实现

1. 根据客户端给定的Lua脚本，在Lua环境中定义一个Lua函数
2. 将客户端给定的脚本保存到lua_srcipts字典，等待将来进一步使用
3. 执行刚刚在Lua环境中定义的函数

EVALSHA命令的实现

只要脚本对应的函数曾经在Lua环境里面定义过，那么即使不知道脚本的内容本身，客户端也可以根据脚本的SHA1校验和来调用脚本对应的函数，从而达到执行脚本的目的。

脚本管理命令的实现

SCRIPT FLUSH：用于清除服务器中所有和Lua脚本有关的命令，这个命令会释放并重建lua_scripts字典，关闭现有的lua环境并重新创建一个新的Lua环境。

SCRIPT EXISTS：根据输入的SHA1校验和，检查校验和对应的脚本是否存在于服务器中。

SCRIPT LOAD：和EVAL命令执行脚本所做的前两步完全一样：命令首先在Lua环境中为脚本创建相对应的函数，然后再将脚本保存到lua_scripts字典中。

SCRIPT KILL：如果超时运行的脚本未执行过任何写入操作，那么客户端可以通过SCRIPT KILL命令来指示服务器停止执行这个脚本，并向执行该脚本的客户端发送一个错误回复。

脚本复制

复制EVAL、SCRIPT FLUSH和SCRIPT LOAD命令时，主服务器会直接向所有从服务器发送该命令。

而在传播EVALSHA命令的时候，必须确保EVALSHA命令要执行的脚本已经被所有从服务器载入过，否则主服务器会将EVALSHA命令转换成一个等价的EVAL命令进行传播。

主服务器使用服务器状态的repl_scriptcache_dict字典记录自己已经将哪些脚本传播给了所有从服务器，键是SHA1校验和，而值都是NULL。

每当主服务器添加一个新的从服务器时，主服务器都会清空自己的repl_scriptcache_dict字典。

第二十一章 排序

Redis的SORT命令可以对列表键、集合键或者有序集合键的值进行排序。

用的是快排。

SORT 命令的实现

该命令可以对一个包含数字值的键key进行排序，详细步骤如下：

1. 创建一个和numbers列表长度相同的数组，数组每一项都是一个RedisSortObject结构；
2. 遍历该数组，将各个数组项的obj指针分别指向numbers列表的各个项，并将obj指针所指的列表项转换成一个double类型浮点数存在相应数组项的u.score属性里面；
3. 根据u.score的值对数组排序；
4. 遍历数组，顺序输出obj所指的列表项。

ALPHA、ASC以及DESC选项的实现都是在对数组排序的时候有所不同，具体看p347开始的几页。

LIMIT选项的实现

在默认情况下，SORT命令总会将排序后的所有元素都返回给客户端，但是通过LIMIT选项可以只返回其中一部分。

LIMIT <offset> <count>

GET选项的实现

通过GET选项，我们可以让SORT命令在对键进行排序之后，根据被排序的元素，以及GET选项所指定的模式，查找并返回某些键的值。

STORE选项的实现

默认情况下，SORT命令只向客户端返回排序结果，而不保存排序结果。

通过STORE选项，可以将排序结果保存到指定的键里面，并在又需要的时候重用这个排序结果。

SORT key ALPHA STORE key2

多个选项的执行顺序

1. 排序：在这一步命令会使用ALPHA、ASC或DESC、BY这几个选项；
2. 限制排序结果集的长度，会使用LIMIT选项；
3. 获取外部键，会使用GET选项
4. 保存排序结果集：使用STORE选项
5. 向客户端返回排序结果集

选项的摆放顺序

除了GET选项之外，改变选项的摆放顺序并不会影响SORT命令执行这些选项的顺序。

第二十二章 二进制位数组

Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组。

BITOP命令既可以对多个位数组进行按位与、按位或、按位异或运算，也可以对给定的数组进行取反运算。

位数组的表示

Redis使用SDS结构来保存位数组，并使用SDS结构的操作函数来处理位数组。

【注意】buf数组保存位数组的顺序和我们平时书写位数组的顺序是完全相反的，比如buf[0]字节中各个位分别是1/0/1/1/0/0/1/0，表示的其实是01001101。这样来保存可以简化SETBIT命令的实现。

GETBIT命令的实现

GETBIT <bitarray> <offset>

1. 计算byte=offset/8
2. 计算bit=（offset mod 8）+1
3. 根据byte和bit去取值。

时间复杂度O（1）。

SETBIT命令的实现

SETBIT <bitarray> <offset> <value>

1. 计算len=offset/8+1
2. 检查bitarray键保存的位数组的长度是否小于len，如果是则扩展为len个字节，并将新扩展的二进制位都设置为0；
3. 计算byte=offset/8
4. 计算bit=（offset mod 8）+1
5. 根据byte和bit定位offset偏移量指定的二进制位，首先将该位上的值保存在oldvalue中，然后将新值value设置为这个二进制的值
6. 向客户端返回oldvalue的值

时间复杂度O(1)。

【注意】因为buf数组使用逆序来保存位数组，所以当程序需要对buf数组进行扩展时，写入操作可以直接在新扩展的二进制位中完成，而不必改动位数组原来已有的二进制位。如果buf数组使用和书写一样的顺序来保存位数组，那么每次扩展buf数组后都需要将已有的位进行移动，然后才能执行写操作，影响执行速度。

BITCOUNT命令的实现

几种可能的实现方式：

1. 遍历
2. 查表，即映射hash，以空间换时间
3. variable-precison SWAR算法

前两种有明显缺陷，主要看下第三种。

统计一个数组中非0二进制位的数量，在数学上被称为“计算汉明重量”，对于普通处理器来说，目前已知效率最好的通用算法就是variable-precison SWAR算法，该算法通过一系列位移和位运算操作，可以在常数时间内计算多个字节的汉明重量，并且不需要任何额外内存。

具体例子和算法见p372，看下来主要逻辑就是利用移位和位运算先算每两位有多少个1，然后算每四位有多少个1，接着是每八位有多少个1，依次类推，最后算出总的，但这个总数是在最高位的，所以需要再进行一个移位操作把值移到最低字节便于查看。

Redis中的实现

BITCOUNT命令的实现用到了查表和SWAR两种算法：

• 查表算法使用键长8位的表，表中记录从0000 0000到1111 1111在内的所有二进制位的汉明重量；
• 而SWAR算法方面，BITCOUNT命令在每次循环中载入128个二进制位，然后调用四次32位variable-precision SWAR算法来计算这128个二进制位的汉明重量。

在执行命令时，会根据未处理的二进制位的数量来决定具体使用哪种算法，大于等于128就用SWAR，否则用查表法。

时间复杂度O(n)。

BITOP命令的实现

因为C语言直接支持对字节执行逻辑与或非以及异或操作，所有BITOP命令的AND、OR、XOR和NOT四个操作都是直接基于这些逻辑操作实现的。

NOT复杂度O(n)，其他的O(n^2)。

第二十三章 慢查询日志

Redis的慢查询日志功能用于记录执行时间超过给定时长的命令请求，用户可以通过这个功能产生的日志来监视和优化查询速度。

服务器配置中有两个和慢查询日至相关的选项：

• showlog-log-slower-than选项指定执行时间超过多少微妙的命令请求会被记录到日志上；
• showlog-max-len选项指定服务器最多保存多少条查询日志。

服务器使用先进先出的方式保存慢查询日志。

SLOWLOG GET命令查看服务器所保存的慢查询日志。

struct redisServer{
    //...
    //下一条慢查询日志的ID
    long long slowlog_entry_id;
    //保存了所有慢查询日志的链表
    list* slowlog;
    //服务器配置slowlog-log-slower-than选项的值
    long long slowlog_log_slower_than;
    //
    unsigned long slowlog_max_len;
    //...
};
//slowlog链表中每个节点都是一个slowlogEntry结构，新的节点插入在表头
typedef struct slowlogEntrt{
    //唯一标识符
    long long id;
    //命令执行时的时间，格式为UNIX时间戳
    time_t time;
    //执行命令消耗的时间，以微妙为单位
    long long duration;
    //命令与命令参数
    robj **argv;
    //命令与命令参数的数量
    int argc;
}slowlogEntry;

在每次执行命令的前后，程序都会记录微秒格式的当前UNIX时间戳，这两个时间戳之间的差就是服务器执行命令所耗费的时长，这个时长会传给slowlogPushEntryIfNeeded函数，会根据情况检查是否需要为自己执行的命令创建慢查询日志。

slowlogPushEntryIfNeeded函数作用有两个：检查命令的执行时长是否超过阈值、检查慢查询日志的长度是否超过最大长度。

第二十四章 监视器

执行MONITOR命令，客户端可以将自己变为一个监视器，实时地接收并打印出服务器当前处理的命令请求的相关信息。

每当一个客户端向服务器发送一条命令请求时，服务器除了会处理这条命令外，还会将关于这条命令请求的信息发送给所有监视器。

MONITOR执行步骤如下：

1. 打开客户端监视器标志REDIS_MONITOR
2. 将客户端添加到服务器状态的monitors链表的末尾
3. 向客户端返回OK

服务器每次处理命令之前，都会调用replicationFeedMonitors函数，由该函数将被处理的命令请求的相关信息发送给各个监视器，该函数步骤如下：

1. 根据执行命令的客户端、当前数据库的号码、命令参数、命令参数个数等参数创建要发送给各个监视器的信息
2. 遍历所有监视器，发送信息

举个例子，若服务器在时间1378822257，根据IP为127.0.0.1、端口56604的客户端发送的命令请求，对0号数据库执行命令KEYS *，那么服务器创建的信息如下：

1378822257 [0 127.0.0.1:56604] "KEYS" "*"

【END】