《Redis 设计与实现》读书概要

注：

一、底层数据结构

1. SDS(Simple Dynamic String)：简单动态字符串，优化了的C语言字符串的实现，最显著的特征是内部保存了字符串长度len和可用长度free，且字符数组buf和C语言一样，结尾为\0字符，因此可复用C语言的字符串函数。

2. 链表：Redis中用到的链表是双向无环链表，是实现列表键List的数据结构（仅当一个列表键包含了数量比较多的元素，或者列表中包含的元素都是比较长的字符串时），此外发布与订阅、慢查询、监视器等功能也用到了链表。链表节点listNode与普遍的链表节点相同，包含prev、next和value，但是redis又将listNode包装在了list中，记录了head、tail、节点数len及实现多态链表的功能性函数。

3. 哈希表(dictht)：实现字典(dict)数据类型的底层数据结构，同时，字典也是redis数据库数据存储的数据结构。dict的内部包含两个dictht，便于当 load factor 达到一定值时进行rehash 操作。rehash 不是一次性的，而是渐进式的。

4. 跳跃表(skiplist)：是实现有序集合zset的数据结构。和原本跳跃表只通过节点连接的实现不同，redis的跳跃表节点包装在一个zskiplist类型中，其包括zskiplistNode类型的header、tail、表示表中节点数的length和最大层数的level组成。zskiplistNode不仅包含sds类型的元素值对象、节点分值score，还包含一个zskiplistLevel类型的数组level和一个指向前一个节点的后退指针backward，level数组的长度是节点的层高，在创建节点时确定，是根据幂次定律随机生成的一个介于1-32之间的数。zskiplistLevel表示节点中的每个层级，包括一个指向其后面其他节点的指针forward和当前层的跨度span。

5. 整数集合(intset)：是集合对象的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，redis就会使用intset作为集合键的底层实现。当有比当前集合中最大的值更大一级的元素需要保存时，intset可以通过元素类型的升级来改变元素存储的类型，这可以尽量节约内存。但intset不会降级。

6. 压缩列表(ziplist)：仅用在7.0版本之前，是一种为节约内存而开发的用一块连续的内存空间来紧凑地保存数据的顺序型数据结构（内存紧凑型数据结构），被用作列表、哈希和有序集合的底层实现之一。压缩列表节点previous_entry_length、encoding和content构成，content可以保存字节数组或整数值，保存的值类型由encoding决定，previous_entry_length可以用于向前回溯任意节点，达到从表尾遍历表头的目的。但是压缩列表存在“连锁更新”的问题，7.0版本之后由listpack取代。

7. listpack
   5.0版本中引入，7.0版本之后完全替换ziplist成为列表、哈希和有序集合的底层数据结构之一。listpack 的每个节点不再保存前一个节点的长度从而避免“连锁更新”问题。

二、对象系统

使用TYPE命令查看值对象的数据类型：

SET、RPUSH、HSET、SADD、ZADD
使用OBJECT ENCODING 命令可查看值对象的底层数据结构：

字符串对象

编码可以是int、raw 和 embstr
int：整数值且该值可以用long类型来表示，对其进行字符串相关操作时，其会被转为raw编码，例如 APPEND 操作
embstr：字符串值且其长度小于或等于32，一次分配内存，能更好地利用缓存，但是embstr为只读字符串，不可修改，APPEND 一个embstr会被转为raw编码
raw：字符串且其长度大于32，两次分配内存
浮点数被当作字符串保存，但在需要的时候还是会转回浮点数
字符串对象操作命令：

列表对象

编码可以是 ziplist/listpack 或 linkedlist
ziplistlistpack：默认情况，所有字符串长度都小于64字节，或保存的元素数量小于512个，可修改配置
linkedlist：除ziplist的情况
当ziplist编码的任一条件不满足时，列表会被转为linkedlist编码。
列表对象操作命令：

哈希对象

编码可以是 skiplist/listpack 或 hashtable，编码转换条件和列表对象相同。
哈希对象操作命令：

集合对象

存疑
编码可以是 intset/listpack/hashtable。
intset：集合中所有元素都是整数且元素个数小于512时
listpack/hashtable：除了intset的情况。hashtable 实现集合的方式是将键值对的值置为NULL。
集合对象操作命令：

有序集合对象

编码可以是ziplist/listpack 或 skiplist + dict
ziplist/listpack：默认配置下，集合元素小于128或集合成员长度小于或等于64字节
skiplist：除 ziplist/listpack 情况下
有序集合对象操作命令：

三、持久化

有两种，RDB 和 AOF，如果服务器开启了AOF持久化，那么会优先使用AOF文件来还原数据库状态，否则使用RDB文件来还原数据库状态。

RDB

直接以键值对的形式保存数据库数据信息。
有两个命令可以用于生成RDB文件，SAVE和BGSAVE。SAVE 会阻塞服务器进程，而 BGSAVE 会创建子进程执行，不会阻塞。

BGSAVE命令可以自动间隔性执行，以达到自动持久化的目的，其执行间隔由save配置的seconds和changes两个值确定。代码为：

if(sever.dirty >= saveparam.changes && save_interval > saveparam.seconds) {
    BGSAVE();
}

即，服务器状态在 seconds 秒内发生了 changes 次修改时，自动执行 BGSAVE。

AOF

AOF 通过保存Redis执行的最新写命令来记录数据库数据信息。
appendonly：是否开启AOF，默认为 no
appendfsync：aof_buf 缓冲同步策略，有 always、everysec、no三个值
AOF重写（名字有歧义）：(aof_rewrite函数)以最新的数据库状态直接生成一个新的AOF文件代替原有AOF文件，避免原有文件过大。由于AOF重写是在子进程和服务器主进程同时工作的，因此会出现AOF重写子进程状态滞后的问题，为此，在AOF缓冲区的基础上引入AOF重写缓冲区，将AOF重写之后的命令同步追加到这两个缓冲区，在AOF重写完成后再将AOF重写缓冲区的内容写入到AOF文件中，再将AOF文件重命名为特定文件名，完成新旧文件的替换。

四、事件

redis服务器是一个 事件驱动 程序，服务器处理的事件分为文件事件和时间事件。

文件事件

文件事件处理器是基于 Reactor模式 实现的IO多路复用网络通信程序

时间事件

分为定时和周期性事件，一般只执行serverCron()周期性事件
文件事件和时间事件的调度和执行都是由ae.c/aeMain中调用aeProcessEvents函数负责，先遍历执行文件事件列表，再遍历时间事件链表处理时间事件。

五、客户端和服务端

客户端

redisClient/client 对象保存在redisServer的 list* clients 链表中。
客户端有输入缓冲区和输出缓冲区，都有大小限制（可配置）。

服务端

服务端接收客户端传入的命令并保存在客户端输入缓冲区querybuf中，然后解析命令，提取出 argv 和 argc （client对象中），通过argv[0]获取命令，在命令表字典中查找对应的redisCommand，并将客户端结构的cmd指向该redisCommand，此后再进行一系列权限、参数、状态等检查，最后再调用命令对应的实现函数redisCommandProc(client)即可。执行完后将结果保存在客户端输出缓冲区buf中，经过客户端套接字关联的回复处理器处理后返回给客户端。此外，执行完实现函数后，服务器还需要做一些后续工作以使服务端状态完整。
服务端的serverCron函数定时处理很多更新数据库状态的操作。

1. 服务器初始化
2. 初始化服务器状态结构redisServer server：执行redis.c/initServerConfig函数（变量赋初值，生成命令表）
3. 载入配置项：执行loadServerConfig函数（加载配置参数和配置文件，用其覆盖server属性）
4. 初始化数据结构：执行initServer函数（创建相应数据结构并赋初值，设置一些操作）
5. 还原数据库状态：载入RDB或AOF文件
6. 执行事件循环

六、主从复制

5.0.0 版本之后用REPLICAOF代替SLAVEOF命令创建redis从服务器，且如果主服务器设置了密码，则在从服务器的 masterauth 配置中也要配置主服务器的密码，否则无法同步。
从服务器同步主服务器的状态分为两种情况，一是初始化时的全量复制同步，另一种是初始同步后的增量同步。2.8版本之前的初始全量同步使用SYNC命令（从向主发送SYNC命令），但SYNC命令比较耗时，2.8版本之后使用PSYNC命令，以达到在主从断开重连后的部分重同步需要。增量同步通过命令传播的方式实现，即从服务器（作为服务端）也执行一次主服务器（作为客户端）发送来的写命令。PSYNC的部分重同步是通过在主服务器端维护一个复制积压缓冲区（replication backlog）实现的，复制积压缓冲区是一个固定长度FIFO的队列，记录最近传播的命令和命令的每个字节的偏移量。从服务器重连到主服务器后，会通过PSYNC命令告诉自己目前的复制偏移量，主服务器会根据这个偏移量之后字节是否在缓冲区中来决定执行全量重同步(full resync)还是从偏移量之后开始部分重同步(partial resync)。复制积压缓冲区的大小由repl-backlog-size配置。此外，还有一种情况会执行全量重同步，即主服务器的ID发生变化（主服务器重启），当从服务器重连主服务器后，主服务器发现从服务器发送的主服务器ID和自己当前ID不一致，则执行全量重同步，否则认为可以执行部分重同步（依然视从服务器的偏移量决定）。

七、Sentinel 模式

Sentinel，哨兵，可以用来监视主从服务器，在系统出现异常时进行重新选主以保障系统继续运行。Sentinel 会根据配置文件为每个要监视的主服务器创建相应的实例，并创建连接主服务器的命令连接和订阅连接；
Sentinel也会创建主服务器的从服务器的实例结构，通过向主服务器发送INFO命令获取从服务器信息来实现，同样，也会创建连接到从服务器的命令连接个订阅连接。
此外，监视同一主服务器的sentinel之间会以每秒一次的频率向被监视服务器的__sentinel__:hello 频道发送自身信息，这样每个Sentinel 也会知道其他 Sentinel 的存在，并为对方创建相应实例结构和命令连接（没有订阅连接）。
Sentinel 会以每秒一次的频率向实例（主、从、其他sentinel）发送PING命令并根据实例的回复判断实例是否在线，如果在指定时长连续收到无效回复则该实例被判断为主观下线(OD)，然后再向同样监视该服务器的其他sentinel询问是否同意该实例进入主观下线状态，如果收集到一定数量(quorum)的主观下线投票，则判断该实例为客观下线(SD)，并发起一次针对主服务器的故障转移(failover)。
故障转移的第一步就是选举领头 Sentinel，由它来完成故障转移工作。选举领头 Sentinel 的方法是对Raft算法的实现，总结就是“快者为主”。

八、集群模式

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

创建集群

• 首先，打开集群模式配置，即将配置文件中的cluster-enabled修改为 yes
• 指定集群节点文件，即设置配置文件中的cluster-config-file为指定文件，例如nodes.conf。如果是同一个节点中在同一个Redis目录下启动伪集群，且需要为每个配置文件都单独指定。例如在 6379 和 6380 端口创建伪集群节点，则 6379 的配置可以为cluster-config-file nodes-6379.conf，6380 的配置文件为cluster-config-file nodes-6380.conf。
• 启动所有集群节点
• 用CLUSTER MEET命令添加节点，添加后可用CLUSTER NODES命令查看
• 分配槽。添加完节点后，集群仍处于下线状态（可用CLUSTER INFO命令查看状态，如果cluster_state:fail则为下线状态，如果为cluster_state:ok则为正常状态），要使用CLUSTER ADDSLOTS或CLUSTER ADDSLOTSRANGE命令为每个节点分配槽（槽号范围为 0~16383 共16384个），只有所有的节点都分配完16384个槽后，集群才会处于上线。
• 分配完后用CLUSTER INFO命令查看，如果出现cluster_state:ok，则表示集群已上线。

分配哈希槽

用CLUSTER KEYSLOT key命令可查看 key 所在的槽号。例如，查看 name 会分配到哪个槽可用CLUSTER KEYSLOT命令，例如查看键为 name 的槽号，命令为CLUSTER KEYSLOT name。

添加槽可用CLUSTER ADDSLOTS命令，删除槽可用CLUSTER DELSLOTS命令。7.0 版本之后可以用CLUSTER ADDSLOTSRANGE命令按范围分配槽，用CLUSTER DELSLOTSRANGE可以按范围移除槽。

运行命令

运行集群模式命令时，最好以集群参数进入客户端，即加上-c参数：

redis-cli -c ...

这样，当操作的键的槽号不在当前节点时，会自动转向键所在槽的结点执行。

修改集群

CLUSTER RESET // 重置集群
CLUSTER FORGET node-id // 将节点从集群中移除

故障转移

集群中的节点分为主节点（master）和从节点（slave），其中主节点用于处理槽，而从节点则用于复制某个主节点，并在被复制的主节点下线时，代替下线主节点故障转移，继续处理命令请求。

在从节点上执行CLUSTER REPLICATE <node_id>命令，可以让当前从节点复制指定的主节点。因为节点的复制功能和单机Redis服务器的复制功能使用了相同的代码，所以让从节点复制主节点相当于向从节点发送命令SLAVEOF（REPLICAOF）。

当一个从节点发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移。故障转移前会从下线的主节点的从节点中先选举出新的主节点，选举算法和选举领头 Sentinel 一样，都基于 Raft 算法。选举出新的主节点后，新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己，并向集群中其他节点广播一条PONG命令，让其他节点知道其已经接管原来下线的节点称为新的主节点。

九、发布与订阅

Redis的发布与订阅功能与 MQ 消息的生产与消费类似，其消息的订阅分为频道订阅和模式订阅。

• 频道订阅
  频道订阅频道名固定，其信息保存在redisServer.pubsub_channels中，使用时由SUBSCRIBE channel命令指定，例如客户端 client1 订阅频道为 hello 的频道：
  > SUBSCRIBE hello
  运行该命令后，命令行将会进入阻塞，等待接收其他客户端向该频道发送的消息。发送消息用PUBLISH message命令，例如，客户端 client2 向该频道发送 “My name is Redis”：
  > PUBLISH "Hello, My name is Redis"
  则 client1 的窗口会立即接收到该消息。

• 模式订阅
  模式订阅即按正则表达式模式匹配频道名，其信息保存在redisServer.pubsub_patterns中，使用时由PSUBSCRIBE命令指定，例如客户端 client1 订阅模式为go[h|th]ere的频道：
  > PUBSCRIBE go[h|th]ere
  则表示，该客户端同时订阅了名为gohere和gothere的频道，有其他客户端向其中任一频道发送消息，client1 都会接收到。

取消订阅用UNSUBSCRIBE和PUNSUBSCRIBE命令，用法同上。

如果想查看发布订阅相关的信息，可以用PUBSUB命令的三个子命令
PUBSUB CHANNELS：查看当前被订阅的频道
PUBSUB NUMSUB channel：查看频道 channel 的订阅者数
PUBSUB NUMPAT：查看订阅模式数

十、事务

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

用MULTI命令开始事务，然后输入一个事务的多条命令，这些命令的执行将会按顺序保存在一个队列中(QQUEUED)，在最后用EXEC命令提交事务。

WATCH命令是一个乐观锁（optimistic locking），它可以在EXEC命令执行之前，监视任意数量的数据库键，并在EXEC命令执行时，检查被监视的键是否至少有一个已经被修改过了，如果是的话，服务器将拒绝执行事务，并向客户端返回代表事务执行失败的空回复。
Redis事务实现了 ACID 特性。

十一、Lua 脚本

Lua 脚本函数化执行，即 Redis 会将输入的 Lua 脚本转换为函数调用在 Lua 环境中执行。
可以使用EVAL命令执行 Lua 脚本。

// 执行 PING 命令
EVAL "return redis.call('PING')" 0
// 执行 SET 命令
EVAL "return redis.call('SET', KEYS[1], ARGV[1])" 1 "msg" "hello world"

SCRIPT LOAD、SCRIPT EXISTS、SCRIPT FLUSH以及SCRIPT KILL命令可用于管理 Lua 脚本执行。

参考

《Redis 设计与实现》