Shellbye.github.io
Shellbye.github.io copied to clipboard
Published
20 hours ago •
Shellbye
Shellbye
《Redis设计与实现》读书笔记
redis设计与实现
第2章 简单动态字符串
2.1 SDS的定义
SDS(Simple Dynamic String)
无法修改的才用C string，所有可能修改的地方，都用的SDS
struct sdshdr {
int len; // SDS中已使用的字符串长度
int free; // 可用
char buf[]; // 保存字符串，遵循C字符串结尾'\0'不计入len
}
2.2 SDS与C字符串的区别
2.2.1 常数复杂度获取字符串长度
Redis的SDS，因为有len字段，获取字符串长度的执行时间是O(1)的
2.2.2 杜绝缓冲区溢出
2.2.3 减少修改字符串时带来的内存重分配次数
1.空间预分配
2.惰性空间释放
2.2.4 二进制安全
SDS的buf是【字节】数组，它用来保存二进制数据
2.2.5 兼容部分C字符串函数
2.2.6 总结
2.3 SDS API
第3章 链表
3.1 链表和链表节点的实现
typedef struct listNode {
struct listNode * prev;
struct listNode * next;
void * value;
}
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;
3.2 链表和链表节点的API
第4章 字典
4.1 字典的实现
Redis的字典使用哈希表作为底层实现
4.1.1 哈希表
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引
// 总是等于size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
4.1.2 哈希表节点
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_tu64;
} v;
// 指向下个哈希表节点，形成链表（解决冲突）
struct dictEntry *next;
} dictEntry;
4.1.3 字典
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当rehash不在进行时，值为-1
int rehashidx;
} dict;
4.2 哈希算法
计算key的哈希值
hash = dict->type->hashFunction(key);
计算索引值
index = hash & dict->ht[x].sizemask; // 根据情况不同（是否rehash）,x为0或者1
哈希算法
MurmurHash
4.3 解决键冲突
Redis的哈希表使用链地址法来解决冲突
因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，
程序总是将新节点添加到链表的表头位置
4.4 rehash
重新散列（rehash）是为了让负载因子（load factor）维持在一个合理的范围之内
rehash的时候，ht[1]就派上了用场，它会根据是扩展还是收缩，
将自己的大小设置为第一个大于ht[0].used*2或者小于ht[0].used的2^n
哈希表的扩展与收缩
load_factor = ht[0].used / ht[0].size
load_factor > 1 (或者BGSAVE\BGREWRITEAOF执行时为 5)时
扩展
load_factor < 0.1 时
收缩
4.5 渐进式rehash
依赖 rehashinx，它指向下一个需要rehash的索引
4.6 字典API
第5章 跳跃表
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，
从而达到快速访问节点的目的
跳跃表是有序集合的底层实现之一
5.1 跳跃表的实现
5.1.1 跳跃表节点
typedef struct zskiplistNode {
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
} zskiplistNode;
5.1.2 跳跃表
typedef struct zskiplist {
// 表头节点和表尾节点
struct skiplistNode *header, *tail;
// 表中节点数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
}
5.2 跳跃表的API
第6章 整数集合
整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素且数量不多时，
Redis就会使用整数集合作为集合键的底层实现
6.1 整数集合的实现
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
}
contents中的内容，取决于encoding的值
6.2 升级
每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，
整数集合需要先进行升级（upgrade）,然后才能加入新元素
因为如此，所以向整数集合中添加新元素的时间复杂度是O(N)
6.3 升级的好处
6.3.1 提示灵活性
6.3.2 节约内存
6.4 降级
是不支持的
6.5 整数集合API
第7章 压缩列表
压缩列表（ziplist）是列表键和哈希键的底层实现之一。
7.1 压缩列表的构成
压缩列表是Redis为了节约内存而开发的，
是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。
一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值
zlbytes | zltail | zllen | entry1 | entry2 | ... entryN | zlend
7.2 压缩列表节点的构成
7.2.1 previous_entry_length
7.2.2 encoding
7.2.3 content
7.3 连锁更新
最坏的复杂度是O(N^2)
7.4 压缩列表API
第8章 对象
Redis对象系统包含：字符串对象，列表对象，哈希对象，集合对象，有序集合对象
8.1 对象的类型与编码
typedef struct redisObject {
// 类型
unsigned type;
// 编码
unsigned encoding;
// 指向底层实现数据结构的指针
void *ptr;
...
} robj;
8.1.1 类型
对象的类型
REDIS_STRING
REDIS_LIST
REDIS_HASH
REDIS_SET
REDIS_ZSET
使用 TYPE 命令，返回的结果就是对象的类型
8.1.2 编码和底层实现
对象的编码
REDIS_ENCODING_INT
REDIS_ENCODING_INT
REDIS_ENCODING_RAW
REDIS_ENCODING_HT
REDIS_ENCODING_LINKEDLIST
REDIS_ENCODING_ZIPLIST
REDIS_ENCODING_INTSET
REDIS_ENCODING_SKIPLIST
不同类型和编码的对象
REDIS_STRING REDIS_ENCODING_INT
REDIS_STRING REDIS_ENCODING_INT
REDIS_STRING REDIS_ENCODING_RAW
REDIS_LIST REDIS_ENCODING_ZIPLIST
REDIS_LIST REDIS_ENCODING_LINKEDLIST
REDIS_HASH REDIS_ENCODING_ZIPLIST
REDIS_HASH REDIS_ENCODING_HT
REDIS_SET REDIS_ENCODING_INTSET
REDIS_SET REDIS_ENCODING_HT
REDIS_ZSET REDIS_ENCODING_ZIPLIST
REDIS_ZSET REDIS_ENCODING_SKIPLIST
使用 OBJECT ENCODING 命令可以查看一个数据库键的对象的编码
通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，
极大地提升了Redis的灵活性和效率， 因为Redis可以根据不同的使用场景来为一个对象设置不同的编码，
从而优化对象在某一场景下的效率。
举个例子，在列表对象包含的元素比较少时，Redis使用压缩列表作为列表对象的底层实现；
1.因为压缩列表比双端列表更节约内存，并在元素数量较少时，
在内存中以联系块的方式保存的压缩列表比起双端链表可以更快被载入缓存中；
2.随着列表对象的增多，压缩列表优势消失，底层又可以切换到功能更强、更适合保存大量元素的双端链表。
8.2 字符串对象
字符串对象的编码可以是int，raw或者embstr；embstr编码是专门用于保存短字符串的一种优化编码方式（只读）
8.2.1 编码的转换
8.2.2 字符串命令的实现
8.3 列表对象
列表对象的编码可以是ziplist或者linkedlist
8.3.1 编码转换
当列表对象可以同时满足以下两个条件时，列表对象使用ziplist编码：
列表对象保存的所有字符串元素长度都小于64字节（list-max-ziplist-value）
列表对象保存的元素数量小于512（list-max-ziplist-entries）
不能满足以上两个条件的列表对象需要使用linkedlist编码
8.3.2 列表命令的实现
LPUSH 推入头部
RPUSH 推入尾部
8.4 哈希对象
哈希对象的编码可以是 ziplist 或者 hashtable
8.4.1 编码转换
基本等同于8.3.1（64+512）
8.4.2 哈希命令的实现
8.5 集合对象
集合对象的编码可以是 intset 或者 hashtable
8.5.1 编码转换
intset 到 hashtable 的转换条件
集合对象保存的所有元素都是整数值；
集合对象保存的元素个数不超过512；
8.5.2 集合命令的实现
8.6 有序集合对象
有序集合的编码可以是 ziplist 或者 skiplist
skiplist 编码的有序集合对象使用 zset 结构作为底层实现，同时包含一个字典和一个跳跃表
typedef struct zset {
zskiplist * zsl;
dict *dict;
} zset;
这样做的好处融合两种数据结构的优点
访问成员 O(1)
范围操作
8.6.1 编码的转换
ziplist --> skiplist
有序集合保存的元素数量小于128；
有序集合保存的所有元素成员的长度都小于64字节；
8.6.2 有序集合命令的实现
8.7 类型检查与命令多态
Redis中用于操作键的命令基本上可以分为两种类型
其中一种命令可以对任何类型的键执行
DEL EXPIRE RENAME TYPE OBJECT
另一种只能读特定类型的键执行
SET GET APPEND STRLEN 等 字符串
HDEL HSET HGET HLEN 等 哈希键
RPUSH LPOP LINSERT LLEN 等 列表键
SADD SPOP SINTER SCARD 等 集合键
ZADD ZCARD ZRANK ZSCORE 等 有序集合键
8.7.1 类型检查的实现
8.7.2 多态命令的实现
8.8 内测回收
Redis在自己的对象系统中构建了一个引用计数计数实现的内测回收机制
typedef struct redisObject {
...
int refcount; // 引用计数
...
}
8.9 对象共享
初始化时，会创建一万个字符串对象（0--9999）
8.10 对象的空转时长
typedef struct redisObject {
...
unsigned lru;
...
}
第9章 数据库
9.1 服务器中的数据库
Redis服务器将所有数据库都保存在服务器状态 redis.h/redisServer 结构的 db 数组中，
db 数组的每个项都是一个 redis.h/redisDb 结构，每个 redisDb 结构代表一个数据库
struct redisServer {
// 一个数组，保存着服务器中的所有数据库
redisDb *db;
// 服务器数据库的数量
int dbnum;
};
9.2 切换数据库
select x // x为数据库号
在服务器内部，客户端状态 redisClient 结构的 db 属性记录了客户端当前的目标数据库，
是一个指向 redisDb 结构的指针
typedef struct redisClient {
redisDb *db;
} redisClient;
redis 没有显示当前数据库的命令（本书出版时）
9.3 数据库键空间
服务器中的每个数据库都由一个 redis.h/RedisDb 结构表示，
其中 redisDb 结构的 dict 字典保存了数据库中的所有键值对，
我们将这个字典称为键空间（key space）
typedef struct redisDb {
// 数据库键空间，保存着数据库中的所有键值对
dict *dict;
}
键空间的键就是数据库的键，每个键都是一个字符串对象
键空间的值就是数据库的值，每个值可以是字符串对象、列表对象、哈希表对象、集合对象、
有序集合对象 中的任意一种 Redis 对象
9.3.1 添加新键
9.3.2 删除键
9.3.3 更新键
9.3.4 对键取值
9.3.5 其他键空间操作
FLUSHDB 清库
RANDOMKEY 随机key
DBSIZE 数量
EXISTS 是否存在
RENAME 重命名
KEYS 获取所有key
9.3.6 读写键空间时的维护操作
1.在读取一个键之后，服务器会根据键是否存在来更新键空间命中（hit）次数或不命中（miss）次数
2.在读取一个键之后，服务器会更新键的LRU（Least Recently Used）
3.如果读取一个键时发现过期，会先删除这个键，然后执行其他操作
4.如果有客户端使用 WATCH 命令监视了某个键，那么该键被修改之后，服务器会将其标记为 dirty ，
从而让事务程序注意到
5.服务器每次修改一个键，都会都 dirty 值增加1，这个计数器会出发服务器的持久化以及复制操作
6.如果服务器开启了数据库通知功能，那么键在修改之后，服务器会发送相应的通知
9.4 设置键的生存时间或过期时间
EXPIRE PEXPIRE 客户端以秒或者毫秒为精度设置生存时间（Time To Live，TTL）
EXPIREAT PEXPIREAT 以时间戳设置过期时间
9.4.1 设置过期时间
EXPIRE <key> <ttl>
PEXPIRE <key> <ttl>
EXPIREAT <key> <timestamp>
PEXPIREAT <key> <timestamp>
以上四个命令底层都是通过 PEXPIREAT 来实现的
9.4.2 保存过期时间
redisDb 结构的 expires 字典保存了数据库中所有键的过期时间，这个字段成为过期字典
1.过期字典的键是一个指针，指向键空间中的某个键对象
2.过期字典的值是一个 long long 类型的整数，一个毫秒精度的 UNIX 时间戳
9.4.3 移除过期时间
PERSIST
9.4.4 计算并返回剩余生存时间
TTL
9.4.5 过期键的判定
1.检查给定键是否存在与过期字典，如果在，取得过期时间；
2.检查当前UNIX时间戳是否大于过期时间，并判定是否过期
9.5 过期键删除策略
三种删除策略
定时删除
惰性删除
定期删除
9.5.1 定时删除
对内存友好，对CPU不友好
9.5.2 惰性删除
对CPU友好，对内存不友好
9.6.3 定期删除
综合
9.6 Redis的过期键删除策略
Redis使用的是惰性删除和定期删除两种策略
9.6.1 惰性删除策略的实现
9.6.2 定期删除侧露的实现
随机检查一部分键的过期时间，并删除过期的键
9.7 AOF、RDB 和复制功能对过期键的处理
9.7.1 生成RDB 文件
使用 SAVE / BGSAVE 生成 RDB 文件时，会忽略过期的键
9.7.2 载入 RDB 文件
主服务器模式
忽略所有过期键
从服务器模式
不忽略
9.7.3 AOF 文件写入
过期键被删除之后，会向AOF文件追加 （append） 一个 DEL 命令
9.7.4 AOF 重写
9.7.5 复制
当服务器运行在复制模式下时，从服务器的过期键删除动作由主服务器控制
从服务器执行客户端读命令时，遇到过期键也不会将其删除，只有等主服务器通知删除了，才删除
9.8 数据库通知
since Redis 2.8
该功能可以让客户端通过订阅给定的频道或者模式，来获知数据库中键的变化，以及数据库中命中的执行情况
9.8.1 发送通知
9.8.2 发送通知的实现
第10章 RDB持久化
10.1 RDB文件的创建与载入
生成
SAVE / BGSAVE
载入
启动时自动完成
10.1.1 SAVE 命令执行时的服务器状态
会阻塞Redis服务器进程
10.1.2 BGSAVE 命令执行时的服务器状态
会拒绝新的 SAVE / BGSAVE 命令
BGREWRITEAOF 会延迟到 BGSAVE 结束，反过来就是拒绝
10.1.3 RDB文件载入时的服务器状态
10.2 自动间隔性保存
10.2.1 设置保存条件
struct redisServer {
// 记录了保存条件的数组
struct saveparam *saveparams;
};
struct saveparam {
// 秒数
time_t seconds;
// 修改数
int changes;
}
save 900 1
save 300 10
save 60 10000
10.2.2 dirty 计数器和 lastsave 属性
dirty 计数器记录距离上一次成功执行 SAVE 或者 BGSAVE 命令之后，服务器对数据库状态进行了多少次修改
lastsace 属性是一个UNIX时间戳，记录了服务器上一次成功执行 SAVE 命令或者 BGSAVE 命令的时间
10.2.3 检查保存条件是否满足
serverCron 检查 save 条件是否满足，满足就执行一次 BGSAVE
10.3 RDB 文件结构
REDIS | db_version | database | EOF | check_sum
10.3..1 database 部分
REDIS | db_version | database 0 | database 3 | EOF | check_sum
|
SELECTDB | db_number | key_value_pairs
|
TYPE | key | value 带有过期时间的 EXPIRETIME_MS | ms | TYPE | key | value
|
7种不同类型
10.4 分析 RDB 文件
10.4.1 不包含任何键值对的RDB文件
10.4.2 包含字符串的RDB文件
10.4.3 包含带有过期时间的字符串键的RDB文件
10.4.4 包含一个集合键的RDB文件
10.4.5 关于分析RDB文件的说明
第11章 AOF 持久化
除了RDB持久化功能之外，Redis还提供了AOF（Append Only File）持久化功能。
11.1 AOF持久化的实现
命令追加
文件写入
文件同步
11.1.1 命令追加
struct redisServer {
// AOF缓冲区
sds aof_buf;
}
11.1.2 AOF 文件的写入与同步
11.2 AOF 文件的载入与数据还原
11.3 AOF 重写
11.3.1 AOF 文件重写的实现
保存数据库状态
11.3.2 AOF 后台重写
AOF 重写缓冲区
第12章 事件
Redis服务器是一个事件驱动程序，服务器需要处理以下两类事件：
1.文件事件（file event）： Redis服务器通过套接字与客户端（或其他服务器）进行链接，
而文件事件就是服务器对套接字操作的抽象。服务器与客户端（或者其他服务器）的通信会产生相应的文件事件，
而服务器则通过监听并处理这些事件来完成一系列网络通信操作。
2.时间事件（time event）：Redis 服务器中的一些操作（比如serverCron函数）需要在给定的时间点执行，
而时间事件就是服务器对这类定时操作的抽象
12.1 文件事件
12.1.1 文件事件处理器的构成
套接字
文件事件就是多套接字操作的抽象
I/O多路复用
将所有事件放入一个队列中
文件事件分派器
事件处理器
12.1.2 I/O多路复用
通过包装常见的 select epoll evport kqueue 这些库实现的
12.1.3 事件的类型
AE_READABLE
AE_WRITEABLE
12.1.4 API
12.1.5 文件事件的处理器
1.连接应答处理器
2.命令请求处理器
3.命令回复处理器
4.一次完整的客户端与服务器连接事件示例
12.2 时间事件
1.定时事件
2.周期性事件
一个时间事件有以下三个属性
id
when
timeProc
12.2.1 实现
服务器将所有时间事件都放在一个无序链表中，每当时间事件执行器运行时，
它就遍历整个列表，查找所有已经到达的时间事件，并调用相应的事件处理器
12.2.2 API
12.2.3 时间事件应用实例：serverCron 函数
1.更新服务器的各类统计信息，如时间、内存占用、数据库占用
2.清理数据库中的过期键值对
3.关闭和清理连接失效的客户端
4.尝试进行AOF 或 RDB 持久化操作
5.如果服务器是主服务器，则对从服务器进行定期同步
6.如果处于集群模式，对集群进行定期同步和连接测试
12.3 事件的调度与执行
第13章 客户端
对于每一个与服务器连接的客户端，服务器都为之建立了相应的 redis.h/redisClient 结构（客户端状态），
这个结构保存了客户端当前的状态信息，以及执行相关功能时需要用到的数据结构
13.1 客户端属性
13.1.1 套接字描述符
int fd;
13.1.2 名字
robj *name;
13.1.3 标志值
int flags;
13.1.4 输入缓冲区
sds querybuf;
13.1.5 命令与命令参数
robj **argv;
int argc;
13.1.6 命令的实现函数
struct redisCommand *cmd;
13.1.7 输出缓冲区
char buf[REDIS_REPLY_CHUNK_BYTES]
int bufpos;
13.1.8 身份验证
int authenticated;
13.1.9 时间
time_t ctime;
time_t lastinteraction;
time_t obuf_soft_limit_reached_time;
13.2 客户端的创建与关闭
13.2.1 创建普通客户端
13.2.2 关闭普通客户端
1.网络连接被关闭
2.发送了不符合协议的命令
3.成为了CLIENT KILL 命令的目标
4.timeout
5.发送的命令请求的大小超过了输入缓冲区
6.回复命令的大小超过了输出缓冲区
服务器使用两种模式来限制客户端输出缓冲区的大小
硬性限制
超出则直接关闭客户端连接
软性限制
继续记录超出软性限制的时间，超过一定时间后关闭
client-output-buffer-limit <class> <hard limit> <soft limit> <soft seconds>
13.2.3 Lua 脚本的伪客户端
redisClient *lua_client;
13.2.4 AOF 文件的伪客户端
第14章 服务器
14.1 命令请求的执行过程
从客户端发送 SET KEY VALUE 命令到获得回复 OK 期间，客户端和服务器共需要执行以下操作：
1.客户端向服务器发送命令请求 SET KEY VALUE
2.服务器接收并处理客户端发来的命令请求 SET KEY VALUE ， 在数据库中进行设置操作，并产生命令回复 OK
3.服务器将命令回复 OK 发给客户端
4.客户端收到 OK ，并打印给用户
14.1.1 发送命令请求
客户端会将命令请求转换成协议格式，然后通过连接发送到服务器的套接字
14.1.2 读取命令请求
1.读取套接字中协议格式的命令请求，并将其保存到客户端状态的输入缓冲区里
2.读取输入缓冲区里中的命令请求进行分析，读取命令请求中的命令参数、参数个数，保存到客户端状态的 argv 和 argc 属性中
3.调用命令执行器，执行指定命令
14.1.3 命令执行器（1）：查找命令实现
根据 argv[0] 在命令列表 command table 中查找命令【不区分大小写】
命令列表 command table 是一个字典，键是命令名字，值是 redisCommand
redisCommand 结构的主要属性
属性名 类型 作用
name
proc redisCommandProc* 函数指针
arity int 命令参数个数
sflags char * 命令属性（写命令/读命令等）
flags int 与sflags相关
calls long long 服务器总共执行了多少次这个命令
milliseconds long long 服务器执行这个命令所耗费的总时长
sflags 属性标识值
标识 意义 部分命令
w 写入命令 set rpush del
r 只读命令 get strlen EXISTS
m 这个命令可能会占用大量内存， set append rpush lpush sadd
执行前需要先检查内存使用情况， sinterstore
如果内存资源紧缺的话禁止执行
a 这是一个管理命令 save shutdown
P 发布与订阅功能方面的命令 publish
s 不可在lua脚本中使用 BRPOP
R 随机命令 SPOP
S lua脚本中需要对结果排序 SUNION
l 可以在服务器载入过程中使用 INFO
t 允许服务器在带有过期数据时使用 PING
M 在监视器模式下不会自动传播 EXEC
14.1.4 命令执行器（2）：执行预备操作
1.检查客户端状态的 cmd 是否指向 null
2.根据 cmd 指向的 redisCommand 结果的 arity 属性，检查命令请求的参数个数是否正确
3.检查客户端是否已经通过了身份验证，未通过的只能执行 auth 命令
4.如果服务器打开了 maxmemory 功能，检查服务器内存占用情况，需要的话进行回收
5.如果上一个 BGSAVE 执行失败，且打开了 stop-writes-in-bgsave-error ， 且将要执行写命令，则拒绝
6.如果客户端当前正在用 subscribe 命令订阅频道，或正在用 psubscribe 命令订阅模式，
那么服务器只会执行客户端发来的 subscribe psubscribe punsubscribe unsubscribe 四个命令，其他都拒绝
7.如果服务器正在进行数据载入，那么客户端发送的命令必须带有 l 标识（info，shutdown，publish）才会被执行，其他都拒绝
8.如果客户端正在执行事务，那么服务器只会执行 exec discard multi watch 四个命令，其他都拒绝
9.如果服务器打开了监视功能，那么将命令和参数发给监视服务器
完成以上步骤之后，可以开始执行命令了 （集群或复制模式下，预备操作会更多）
14.1.5 命令执行器（3）：调用命令的实现函数
client->cmd->proc(client);
14.1.6 命令执行器（4）：执行后续工作
1.如果服务器开启了慢查询日志功能，那么需要检查是否需要为刚执行的命令添加慢查询日志
2.更新刚执行命令的 redisCommand 结构的 milliseconds 和 calls
3.AOF 如果开启，则将刚执行的命令写入 AOF 输入缓冲区
4.如果有其他服务器正在复制当前这个服务器，那么服务器会将刚执行的命令传播给所有从服务器
14.1.7 将命令回复发送给客户端
14.1.8 客户端接收并打印命令回复
14.2 serverCron 函数
默认每隔100ms执行一次
14.2.1 更新服务器时间缓存
Redis中的当前时间是缓存在 redisServer 中的
struct redisServer {
// 秒级的当前时间
time_t unixtime;
// 毫秒级的当前时间
long long mstime;
}
14.2.2 更新 LRU 时钟
struct redisServer {
// 默认每10秒更新一次的时钟缓存，用于计算键的空转（idle）时长
unsigned lruclock;
}
每个 Redis 对象都会有一个 lru 属性，这个属性保存了对象最后一次被命令访问的时间
typedef struct redisObject {
unsigned lru;
}
当服务器要计算一个数据库键的空转时间，程序会用服务器的 lruclock 属性记录的时间减去对象的 lru 属性记录的时间
14.2.3 更新服务器每秒执行命令次数
14.2.4 更新服务器内存峰值记录
size_t stat_peak_memory;
14.2.5 处理 SIGTERM 信号
int shutdown_asap;
14.2.6 管理客户端资源
serverCron 每次执行都会调用 clientsCron 函数，进行以下两项检查
1.释放超时的客户端连接
2.释放超过一定长度的输入缓冲区，重建一个默认大小的输入缓冲区
14.2.7 管理数据库资源
databasesCron
删除过期键、字典收缩等
14.2.8 执行被延迟的 BGREWRITEAOF
int aof_rewrite_scheduled;
14.2.9 检查持久化操作的运行状态
pid_t rdb_child_pid;
pid_t aof_child_pid;
检查以上两个 pid 是否不为 -1，如果有，检查是否有子进程发来信号
1.如果有信号，表示RDB等文件已经生成完成，服务器需要替换新旧文件
2.如果没有，do nothing
如果以上两个 pid 都是 -1，则会进行如下三个检查
1.查看是否有 BGREWRITEAOF 被延迟了，如果有则执行之
2.检查自动保存条件是否已满足，满足则执行一次 BGSAVE
3.检查AOF重写条件是否满足，满足则执行
14.2.10 将AOF缓冲区中的内容写入AOF文件
14.2.11 关闭异步客户端
14.2.12 增加cronloops 计数器的值
14.3 初始化服务器
14.3.1 初始化服务器状态结构
初始化 server 变量的工作由 redis.c/initServerConfig 函数完成，其主要工作包含：
1.设置服务器运行的ID
2.设置服务器默认运行频率
3.设置服务器的默认配置文件路径
4.设置服务器的默认端口号
5.设置服务器的运行架构
6.设置服务器的默认RDB持久化条件和AOF持久化条件
7.初始化LRU时钟
8.创建命令表
14.3.2 载入配置选项
14.3.3 初始化服务器数据结构
initServer
1.为服务器设置进程信号处理器
2.创建共享对象：
“OK”，1到10000的字符串，“ERR”等
3.打开服务器的监听端口
4.为serverCron 函数创建时间事件，等待服务器正式运行时执行 serverCron 函数
5.AOF开启的话，打开AOF文件，如果文件不存在，创建一个新的
6.初始化服务器的后台 I/O 模块
14.3.4 还原数据库状态
RDB / AOF
14.3.5 执行循环事件
第15章 复制
在Redis中，用户可以通过执行 slaveof 命令或者设置 slaveof 选项，
让一个服务器去复制（replicate）另一个服务。
15.1 旧版复制功能的实现
15.1.1 同步
15.1.2 命令传播
15.2 旧版复制功能的缺陷
短线重连和初始化一样的操作
15.3 新版复制功能的实现
PSYNC 取代 SYNC
PSYNC 命令具有两种模式
完整重同步 full resynchronization
部分重同步 partial resynchronization
15.4 部分重同步的实现
部分重同步功能由以下三个部分组成
1.主服务器的复制偏移量（replication）和从服务器的复制偏移量
2.主服务器的复制积压缓冲区（replication backlog）
3.服务器的运行ID（run ID）
15.4.1 复制偏移量
offset
执行复制的双方会分别维护一个复制偏移量
15.4.2 复制积压缓冲区
复制积压缓冲区是由主服务器维护的一个固定长度先进先出队列，默认大小1MB
当从服务器重新连接上主服务器且发送 SYNC 命令，并将自己的复制偏移量发给主服务器之后，
主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作
1.如果offset之后的数据仍然存在与复制积压缓冲区里面，则执行部分重同步
2.如果offset之后的数据已经不在复制积压缓冲区，则执行完整同步操作
15.4.3 服务器运行ID
每个Redis 服务器，不论主从，都有自己的运行ID
每个运行ID在服务器启动时自动生成，由40个随机的十六进制字符串组合
15.5 PSYNC 命令的实现
PSYNC 命令由两种调用方法
1.如果从服务器从未复制过任何主服务器，或执行过 salve of on one 命令，
那么新开始的复制将向主服务器发送 PSYNC ? -1 命令，主动请求完整重同步
2.如果已经同步过，则发送 PSYNC <runid> <offset>
接收到 PSYNC 命令的主服务器会返回以下三种回复中的一种：
1.+FULLRESYNC <runid> <offset>，执行完成重同步
2.+CONTINUE，执行部分重同步
3.-ERR，主服务器版本低于2.8，这是从服务器将发送SYNC进行完整同步
15.6 复制的实现
15.6.1 步骤1: 设置主服务器的地址和端口
char *masterhost;
int masterport;
15.6.2 步骤2: 建立套接字链接
15.6.3 步骤3: 发送 PING 命令
PING 命令有两个作用
1.检查套接字的读写状态是否正常
2.检查主服务器是否能正常处理命令
从服务器发送 PING 之后将遇到如下三种情况
1.超时回复，需要断开重连
2.返回一个错误，需要断开重连
3.返回 PONG ，可以执行下一个步骤
15.6.4 步骤4: 身份验证
15.6.5 步骤5: 发送端口信息
从服务器执行命令 REPLCONF listening-port <port>，
向主服务器发送从服务器的监听端口号。
主服务器会将其记录到对应客户端的 slave_listening_port 属性中
15.6.6 步骤6: 同步
发送 PSYNC 命令
双方都是彼此的客户端
15.6.7 步骤7: 命令传播
15.7 心跳检测
命令传播阶段，从服务器默认会以每秒一次的频率向服务器发送命令：
replconf ack <replication_offset>
这有三个作用
1.检测网络链接状态
2.辅助实现 min-slaves 选项
3.检测命令丢失
15.7.1 检测主从服务器的网络连接状态
15.7.2 辅助实现 min-slave 配置选项
第16章 Sentinel
Sentinel(哨岗，哨兵)是Redis 高可用性的解决方案，用来在主服务器下线时选择其他服务器替代之
16.1 启动并初始化 Sentinel
redis-sentinel /path/to/sentinel.conf
redis-server /path/to/sentinel.conf --sentinel
初始化需要执行以下步骤
1.初始化服务器
2.将普通的Redis服务器使用的代码替换成 Sentinel 专用代码
3.初始化 Sentinel 状态
4.更具配置文件，初始化 Sentinel 的监视主服务器列表
5.创建连向主服务器的网络连接
16.1.1 初始化服务器
Sentinel 模式下 Redis 服务器主要功能使用情况
数据库和键值对方面的命令，set，del等 不使用
事务命令，multi，watch等 不使用
脚本命令，eval 不使用
RDB持久化、AOF持久化 不使用
复制命令 不使用
发布与订阅命令，publish，subscribe 使用
文件事件处理器 内部使用
时间时间处理器 内部使用
16.1.2 使用 Sentinel 专用代码
更改端口 6379 -> 26379
更改命令表
16.1.3 初始化 Sentinel 状态
struct sentinelState {
// 当前纪元，用于实现故障转移
uint64_t current_epoch;
// 保存了所有被这个 sentinel 监视的主服务器，字典的键是主服务器的名字，
// 值则是一个指向 sentinelRedisInstance 结构的指针
dict *masters;
// 是否进入了 TILT 模式
int tilt;
// 目前正在执行的脚本的数量
int running_scripts;
// 进入 TILT 模式的时间
mstime_t tilt_start_time;
// 最后一次执行时间处理器的时间
mstime_t previous_time
// 一个FIFO队列，包含了所有需要执行的用户脚本
list *scripts_queue;
} sentinel;
16.1.4 初始化 Sentinel 状态的 masters 属性
typedef struct sentinelRedisInstance {
// 标识值，记录了实例的类型，以及该实例的当前状态
int flags;
// 实例的名字，主服务器有配置文件设置，从服务器ip:port
char *name;
// 实例的运行id
char *runid;
// 配置纪元，用于实现故障转移
uint64_t config_epoch;
// 实例的地址
sentinelAddr *addr;
// sentinel down-after-milliseconds 选项设定的值
// 实例无响应多少毫秒之后才会被判断为主观下线 （subjectively down）
mstime_t down_after_period;
// sentinel monitor <master-name> <ip> <port> <quorum> 选项中的 quorum 参数
// 判断这个实例为客观下线（objectively down）所需的支持投票数量
int quorum;
// sentinel parallel-syncs <master-name> <number> 选项的值
// 在执行故障转移操作时，可以同时对新的主服务器进行同步的从服务器数量
int parallel_syncs;
// sentinel failover-timeout <master-name> <ms> 选项的值
// 刷新故障转移状态的最大时限
mstime_t failover_timeout;
} sentinelRedisInstance;
16.1.5 创建连向主服务器的网络连接
对于每个被 sentinel 监视的主服务器，sentinel 会创建两个连向主服务器的异步网络连接：
1.一个是命令连接，用于向主服务器发送命令并接收回复
2.一个是订阅连接，这个连接专门用于订阅主服务器的 __sentinel__:hello 频道
16.2 获取主服务器信息
16.3 获取从服务器信息
16.4 向主服务器和从服务器发送信息
publish __sentinel__:hello "<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_name>,<m_ip>,<m_port>,<m_epoch>"
16.5 接收来自主服务器和从服务器的频道信息
subscribe __sentinel__:hello
16.5.1 更新 sentinels 字典
Sentinel 为主服务器床的实例结构中的 sentinels 字典保存了除 Sentinel 本身之外，所有同样监视这个主服务器的其他 Sentinel 的资料：
1.sentinel 字典的键是其中一个 Sentinel 的名字（ip:port）
2.sentinel 字典的值是键所对应的 Sentinel 的实例结构
当一个 Sentinel 接收到其他 Sentinel 发来的信息时，目标 Sentinel 会从信息中分析并提取以下两方面的参数：
1.与 Sentinel 有关的信息： 源 Sentinel 的ip地址、端口号，运行ID和配置纪元
2.与主服务器有关的参数：源 Sentinel 正在监视的主服务器的名字、IP地址、端口号和配置纪元
16.5.2 创建连向其他 Sentinel 的命令连接
当 Sentinel 通过频道信息发现一个新的 Sentinel 时，它不仅会为新 Sentinel 在 sentinel 字典中创建相应的结构，
还会创建一个连向新 Sentinel 的命令连接，彼此形成网络。
16.6 检测主观下线状态
PING --> +PONG -LOADING _MASTERDOWN
16.7 检测客观下线状态
当 Sentinel 判断一个主服务器主观下线之后，会询问其他 Sentinel 该主服务器是否主观下线，如果主观下线数量够了，则客观下线
16.7.1 发送 SENTINEL is-master-down-by-addr 命令
SENTINEL is-master-down-by-addr <ip> <port> <current_epoch> <runid>
16.7.2 接收 SENTINEL is-master-down-by-addr 命令
回复
1.<down_state>
2.<leader_runid>
3.<leader_epoch>
16.7.3 接收 SENTINEL is-master-down-by-addr 命令的回复
16.8 选举领头 Sentinel
1.所有在线的 Sentinel 都有资格
2.每次选择之后，不论成败，所有的配置纪元都要自增一次。配置纪元就是一个计数器
3.在一个配置纪元里面，所有的 Sentinel 都有一次将某个 Sentinel 设置为局部领头 Sentinel 的机会，
并且一旦设置在这个配置纪元里面就不能更改
4.每个发现主服务器进入客观下线的 Sentinel 都会要求其他 Sentinel 将自己设置为局部领头 Sentinel
5.当源 Sentinel 向目标 Sentinel 发送 SENTINEL is-master-down-by-addr 命令，且 runid 参数不是 * 符合而是源 Sentinel 的运行ID时，
这表示源要求目标将前者设置为后者的局部领头 Sentinel
6.设置局部领头的规则是先到先得
7.目标 Sentinel 回复 SENTINEL is-master-down-by-addr 时，
回复中的 leader_runid 参数和 leader_epoch 参数分别记录了目标 Sentinel 的局部领头信息
8.源 Sentinel 收到命令回复之后，会检查其中的 leader_epoch 和自己的是否相同，相同继续查看 leader_runid，如果也相同，则自己是目标 Sentinel 的局部领头
9.如果某个 Sentinel 被半数以上设置成了局部领头，其就成为领头 Sentinel
10.因为领头的产生需要半数以上，且每个配置纪元里只能设置一次局部领头，所以一个配置纪元里只能产生一个领头 Sentinel
11.如果给定时间没有完成选举，那么将在一定时间之后再次选举，知道选举成功
16.9 故障转移
选举产生领头 Sentinel 之后，领头 Sentinel 将对已下线的主服务器执行故障转移操作：
1.选一个从服务器，转换为主服务器
2.让其他所有从服务器复制新的主服务器
3.将已经下线的主服务器设置为新的主服务器的从服务器，它再次上线之后复制新主服务器
16.9.1 选出新的主服务器
向选中的机器发送 slaveof no one 将其转换为主服务器
选择规则：
1.删除下线或短线状态的从服务器
2.删除最近五秒没有回复过 INFO 命令的从服务器
3.删除与已下线主服务器断开超过 down_after_milliseconds * 10 毫秒的从服务器
4.根据优先级排序，选最高的
5.在根据偏移量排序，选最高的
6.选运行ID最小的
16.9.2 修改从服务器的复制目标
slaveof
16.9.3 将旧的主服务器变为从服务器
第17章
17.1 节点
连接各个节点的工作使用 CLUSTER MEET 命令来完成
CLUSTER MEET <ip> <port>
向一个节点 node 发送 CLUSTER MEET 命令，可以让 node 节点与 ip 和 port 所指定的节点进行握手（handshake），
握手成功时，node 节点就会将 ip 和 port 所指定的节点添加到 node 节点当前所在集群中
17.1.1 启动节点
Redis 服务器启动时会根据 cluster-enabled 配置选项是否为 yes 来决定是否开启服务器的集群模式
只有在集群模式下才会用到的数据，节点将它们保存到了 cluster.h/clusterNode 结构、 clusterLink 结构、 clusterState 结构
17.1.2 集群数据结构
clusterNode 结构保存了一个节点的当前状态，比如创建时间、名字、配置纪元、ip地址和端口号等
struct clusterNode {
// create time
mstime_t ctime;
//
char name[REDIS_CLUSTER_NAMELEN];
int flags;
uint64_t configEpoch;
char ip[REDIS_IP_STR_LEN];
int port;
clusterLink *link;
};
typedef struct clusterLink {
mstime_t ctime;
// TCP 套接字描述符
int fd;
// 输出缓冲区，保存着等待发送给其他节点的消息
sds sndbuf;
// 输入缓冲区，保存着从其他节点收到的消息
sds rcvbuf;
// 与这个连接相关联的节点，如果没有的话就为 null
struct clusterNode *node;
} clusterLink;
typedef struct clusterState {
// 指向当前节点的指针
clusterNode *myself;
// 集群当前的配置纪元，用于实现故障转移
uint64_t currentEpoch;
// 集群当前的状态
int state;
// 集群中至少处理着一个槽的节点的数量
int size;
// 集群节点名单（包括myself）
// 字典的键为节点的名字，字典的值为节点对应的 clusterNode 结构
dict *nodes;
}
17.1.3 CLUSTER MEET 命令的实现
发送 MEET 消息
客 节 ---------------> 节
CLUSTER MEET <B_ip> <B_port> 发送 PONG 消息
户 ------------------------------> 点 <--------------- 点
发送 PING 消息
端 A ---------------> B
17.2 槽指派
Redis 集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为16384个槽（slot），
数据库中的每个键都属于这16384个槽的其中一个，集群中的每个节点可以处理0个或最多16384个槽。
当数据库中的16384个槽都有节点在处理时，集群处于上线状态（ok）；否则就处于下线状态（fail）
通过命令
CLUSTER ADDSLOTS <slot> [slot ...]
可以将一个或多个槽指派（assign）给节点负责
17.2.1 记录节点的槽指派信息
struct clusterNode {
unsigned char slots[16384/8];
int numslots;
};
slots 数组的索引 i 上的二进制位表示节点负责（1）或不负责（0）处理槽 i
17.2.2 传播节点的槽指派信息
告知其他节点的自己的槽信息，集群中所有节点都知道16384个槽的指派信息
17.2.3 记录集群所有槽的指派信息
typedef struct clusterState {
clusterNode *slots[16384];
} clusterState;
slots[i] 指针指向 null ，表示 i 未指派
slots[i] 指针指向一个 clusterNode 结构，那么表示槽 i 已经指派给了 clusterNode 结构所代表的节点
clusterState.slots 数组记录了集群中所有槽的指派信息，
clausterNode.slots 数组只记录了 clusterNode 结构所代表的节点的指派信息
17.2.4 CLUSTER ADDSLOTS 命令的实现
17.3 在集群中执行命令
当客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的数据库键属于哪个槽，并检查是否指派给了自己：
1.如果是自己，直接执行
2.如果不是当前节点，节点会向客户端返回一个 MOVED 错误，指引客户端转向至正确的节点，并再次发送之前想要执行的命令
17.3.1 计算键属于哪个槽
def slot_number(key):
return CRC16(key) & 16383
17.3.2 判断槽是否由当前节点负责处理
17.3.3 MOVED 错误
MOVED <slot> <ip>:<port>
17.3.4 节点数据库的实现
节点和单机服务器在数据库方面的一个区别是，节点只能使用0号数据库，而单机Redis 服务器没有这一限制
除了将键值对保存在数据库里面之外，节点还会用 clusterState 结构中的 slots_to_keys 跳跃表来保存槽和键之间的关系
typedef struct clusterState {
zskiplist *slots_to_keys;
} clusterState;
slots_to_keys 跳跃表每个节点的分值（score）都是一个槽号，而每个节点的成员（member）都是一个数据库键
CLUSTER GETKEYSINSLOT <slot> <count>
这个命令返回最多 count 个属于槽 slot 的数据库键，就是用 slots_to_keys 实现的
17.4 重新分片
Redis 集群的重新分片操作可以将任意数量已经指派给某个节点（源节点）的槽改为指派给另一个节点（目标节点），
并且相关槽所属的键值对也会从源节点被移动到目标节点
重新分片可以在线进行
重新分片的实现原理
集群管理软件 redis-trib 对集群的单个槽 slot 进行重新分片的步骤：
1.redis-trib 对目标节点发送 CLUSTER SETSLOT <slot> IMPORTING <source_id> 命令
2.redis-trib 对源节点发送 CLUSTER SETSLOT <slot> MIGRATING <target_id>
3.redis-trib 对源节点发送 CLUSTER GETKEYSINSLOT <slot> <count>
4.对于3的每个键，redis-trib 都向源节点发送一个 MIGRATE <target_id> <target_port> <key_name> 0 <timeout>
5.重复步骤3和步骤4
6.redis-trib 向集群中的任意一个节点发送 CLUSTER SETSLOT <slot> NODE <target_id> 命令，将槽 slot 指派给目标节点。随后集群都会知道该变化
17.5 ASK 错误
重新分片进行中的源节点，客户端请求其已经分片完成的键，会返回 ASK 错误
17.5.1 CLUSTER SETSLOT IMPORTING 命令的实现
clusterNode *importing_slots_from[16384];
17.5.2 CLUSTER SETSLOT MIGRATING 命令的实现
clusterNode *migrating_slots_to[16384];
17.5.3 ASK 错误
17.5.4 ASKING 命令
打开发送该命令的客户端的 REDIS_ASKING 标识
17.5.5 ASK 错误和 MOVED 错误的区别
MOVED 已经转移负责权
ASK 临时措施
17.6 复制与故障转移
Redis 集群中的节点分为主节点（master，可多个）和从节点（slave），主节点用于处理槽，从节点用于某个主节点，当其下线时替代之
17.6.1 设置从节点
CLUSTER REPLICATE <node_id>
1.接收该命令的节点会先在自己的 clusterNode.nodes 字典中找到 node_id 所对应的 clusterNode 结构，
并将自己的 clusterNode.myself.slaveof 指针指向这个结构
2.修改 clusterNode.myself.flags，关于 REDIS_NODE_MASTER，打开REDIS_NODE_SLAVE 标识
3.开始复制
17.6.2 故障检测
集群中的每个节点都会定期地向其他节点发送 PING 消息，超时未回复的节点回被标记为疑似下线（probable fail, PFAIL）
// 一个链表，记录了所有其他节点对该节点的线下报告
list *fail_reports;
集群中半数以上处理槽的主节点都将某主节点标记为疑似下线，则该主节点将被标记为已下线（FAIL）
17.6.3 故障转移
1.已下线主节点的从节点中，选中一个
2.选中节点执行 slaveof no one，成为主节点
3.新的主节点会撤销对已下线主节点的槽指派，并指派给自己
4.新的主节点会向集群广播一条 PONG 消息
5.开始处理命令，故障转移完成
17.6.4 选举新的主节点
发现故障的从节点向其他主节点报告并要求投票，超过半数就成功，配置纪元
Raft算法的领头选择（leader election）
17.7 消息
节点发送的消息主要有以下五种
1.MEET 当发送者接收到客户端的 CLUSTER MEET 命令时，发送者会向接收者发送 MEET 消息，请求接收者加入发送者当前集群
2.PING 检查是否在线
3.PONG 回复 MEET PING，或 立即刷新对发送节点的认知
4.FAIL 当节点A判断节点B进入 FAIL 状态时，节点A会向集群广播关于B节点的 FAIL 消息，收到消息的节点都将B标记为下线
5.PUBLISH
17.7.1 消息头
cluster.h/clusterMsg
17.7.2 MEET PING PONT 消息的实现
17.7.3 FAIL 消息的实现
17.7.4 PUBLISH 消息的实现
第18章 发布与订阅
略
第19章 事务
略
第20章 lua脚本
略
第21章 排序
略
第22章 二进制位数组
略
第23章 慢查询日志
略
第24章 监视器
略
