第一部分 数据结构与对象

第二章、简单动态字符串SDS

SDS除了保存数据库中的字符串之外，SDS还被用作缓冲区（buffer）：AOF缓冲区、客户端状态的输入缓冲区等；
1、SDS内部实际上是维护：字节数组buf、使用空间len、空闲空间free，且遵循C字符串风格；

SDS的空间管理如下：
1.1）空间预分配：

1.2）惰性空间释放（手动调用api释放，不然就不释放空间）

第三章、链表（双向无环链表）

第四章、字典（hash表实现）

第五章、跳跃表

第六章、整数集合

第七章、压缩列表

1、压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构；一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。
2、每个压缩列表节点有三部分组成：
1）previous_entry_length：前一个节点的长度（为节约内存，前一个字节长度小于254字节，则其占用一个字节，否则占用5字节）；
2）encoding：记录节点content属性所保存数据的类型和长度（前两位用作编码，指出数据类型，并指出encoding本身的大小）；
3）content：保存节点的值，可以是一个字节数组或者是整数，其类型和长度由节点的encoding属性决定；
3、连锁更新：
原因：压缩列表的节点是处于连续内存空间上的，当增删节点时，可以导致后面一个节点的previous_entry_length需要改变，这会改成该节点扩容（引起内存重分配），而这一节点大小改变后，也可以会导致再后一个节点的previous_entry_length需要改变，如果迭代。导致最坏结果会出现O(N)次的内存重分配。

第八章、对象

1、字符串对象
编码：int、raw、embstr
如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么使用编码int；如果一个字符串对象保存的是一个字符串值，且其长度大于32字节，则使用编码raw（即SDS）；如果一个字符串对象保存的是一个字符串值，且其长度小于等于32字节，则使用编码embstr。
注：raw编码，会进行两次内存分配，即redisObject和sdshdr，因此这两个结构内存不连续；而embstr则是一次将redisObject和sdshdr的内存空间申请好，即两者在内存上是连续的（有利于缓存）。



2、列表对象
编码：ziplist（压缩列表）、linkedlist（双端链表）


3、哈希对象
编码：ziplist、hashtable

4、集合对象
编码：intset、hashtable；

5、有序集合对象
编码：ziplist、skiplist；
注：skiplist编码的有序集合对象使用zset结构作为地城实现；一个zset结构同时包含一个字典和一个跳跃表。通过跳跃表可以对有序集合进行范围操作等；而dict字典为有序集合创建了一个从成员到分数的映射，因此可以用O(1)复杂度查找给定成员的分值。



6、类型检查与命令多态


7、内存回收（引用计数）
8、对象共享


8、空转时间（当前时间减去键的值对象的lru时间）

第二部分 单机数据库的实现

第9章 数据库

1、数据库键空间


2、设置键的生存时间或过期时间


3、保存过期时间

4、移除过期时间
PERSIST命令可以移除一个键的过期时间；
5、计算并返回剩余生存时间
TTL/PTTL
6、 过期键删除策略

7、Redis使用惰性删除和定期删除两种策略配合；
1） 惰性删除：在访问键时，先判断一下是否过期，如果过期则删除；
2） 定期删除：周期性执行，在规定时间内，分多次遍历服务器中的各个数据库，从数据库的expires字典中随机检查一部分键的过期时间，并删除其中的过期键。
8、AOF、RDB和复制功能对过期键的处理；
1） RDB文件：过期键不会保存；当以主服务器运行时，过期键不会载入；而当以从服务器运行时，都会载入；
2） AOF文件：当过期时，会追加一条Del message命令；
3） 复制：主服务器会删除过期键，并发送一个DEL命令，告知从服务器删除这个过期键；而如果从服务器在执行读命令时，发现过期键，也不会删除，只有主服务器发送DEL命令后，才会删除该过期键；
——通过主服务器控制从服务器统一地删除过期键，可以保证主从服务器数据的一致性。
9、数据库通知；
1） 键空间通知（key-space notification）关注于“某个键执行了什么命令”；
2） 键事件通知（key-event notification）关注于“某个命令被什么键执行了”；

第10章 RDB持久化

1、 RDB文件是一个进过压缩的二进制文件；
2、 生成RDB的文件的命令为SAVE和BGSAVE；SAVE命令会阻塞Redis服务器进程，直至RDB文件创建完成；而BGSAVE 命令会派生出一个子进程负责创建RDB文件；
3、 RDB载入是自动检测载入的（载入完成前会阻塞）；

4、 Redisserver内存维护了saveparams（触发bgsave条件）、dirty计数器、lastsave属性；

5、RDB文件结构

第11章 AOF持久化

1、 AOF持久化通过保存Regis服务器执行的写命令来记录数据库状态；
2、 AOF持久化实现：命令追加append、文件写入、文件同步sync；

3、 AOF载入，创建一个不带网络连接的伪客户端，进行载入AOF；
4、 AOF重写：新建一个子进程，根据数据库中的数据状态生成AOF，而不是对原来的AOF进行整理。此外为了保证在重写过程中的数据一致性，redix服务器会设置一个AOF重写缓冲区，这个缓冲区在服务器创建子进程之后开始使用，当redis服务器执行完一个写命令之后，它会同时将这个写明了发送给AOF缓冲区和AOF重写缓冲区。（AOF缓冲区是为了原AOF文件的完整持久化，AOF重写缓冲区则是在重写完成后，服务器父进程会将其追加到重写后的AOF，并覆盖原AOF文件）

第12章 事件

1、 Redis基于Reactor模式开发了自己的网络事件处理器；
2、 文件事件
3、 时间事件：定时事件、周期性事件；
Redis使用无序链表维护所有的时间事件（不按when先后）；
时间事件应用实例：serverCron函数（定期对自身资源和状态进行检测和调整）；

4、 由IO多路复用，驱动文件事件和时间事，而且因为某一次IO多路复用返回，对文件事件和时间事件的处理都是同步、有序、原子地执行，服务器不会中断事件处理，也不会对事件进行抢占。因此他们都应该尽可能减少程序的阻塞时间，并在有需要时让出执行权，冲那个人降低造成时间饥饿的可能性。
5、 由于时间事件在文件事件之后执行，并且事件之间不会出现抢占，所以时间事件的处理时间通畅比设定的到达时间稍晚一点；

第13章 客户端

第14章 服务器

第三部分 多机数据库的实现

第15章 复制

1、同步



PSYNC实现原理（主服务器的复制偏移量offset、主服务器的复制积压缓冲区、服务器的运行ID）：
1） 如果从服务器第一次执行复制，则进行完整同步；
2） 否则，主服务器得到从服务器发送来的offset和id，判断id是不是自己，如果不是，则执行完整同步，并且从服务器更新其保存的主服务器ID；
3） 否则，主服务器在断连期间会维护一个复制积压缓冲区（固定长度的FIFO队列），如果从服务器的offset处在队列中，则进行部分从同步，即将复制积压缓冲区对应部分发送过去；
4） 否则，执行完整同步；
注：这里的复制积压缓冲区为固定长度的FIFO队列，默认1M。其中放置着写命令和对应的偏移量；

2、命令传播

3、复制的实现；
1）设置主服务器的地址和端口；
2）建立套接字连接；
3）发送PING命令；
4）身份验证；
5）发送端口信息；
6）同步；
7）命令传播；
3、心跳检测；

第16章 Sentinel

原理：
1） 首先sentinel通过与主服务器建立命令连接和订阅连接。通过命令连接发送INFO命令，可以发现其从服务器；而通过订阅连接则可以发现其他的sentinel（sentinel会两秒一次都在订阅频道中发送信息，其中包括sentinel自己的信息，这时其他的sentinel可以发现他）；
2） Sentinel在发现其他sentinel时，会分别创建一个命令连接；
3） Sentinel会每秒一次向所有实例发送PING命令，以判断啊实例是否在线；如果在一定时间内发挥无效恢复，则判定为主观下线；
4） 当某一个sentinel发现主服务器主观下线后，会向其他sentinel询问主服务器是否下线；如果超过一定数量的sentinel判定主服务器下线，则主服务器为客观下线；
5） 在sentinel之间选举出一个leader，以负责故障转移。即在每个sentinel尝试将自己设置为leader前，收到其他sentinel的leader命令，则放弃成为leader，并认可这一个sentinel为leader；当有半数以上的sentinel认可某一个sentinel为leader时，则其才被选举为leader；（Raft）
6） Leader负责故障转移；即在从服务器中选择一个优秀新的主服务器，并让相关的从服务器复制这个新的主服务器的；同时将已下线的主服务器设置为新主服务器的从服务器；

第17章 集群

1、 redis通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为16384个槽slot，数据库中的每个键都属于这16384的其中一个。当所有的槽都有节点在处理时，集群处于上线状态；
2、 在集群中执行命令；

3、 重新分片（重新分配槽）——由redis-trib负责执行
注：在重新分片过程中，slot中的数据可能一部分在源节点，另一部分在目标节点。因此在查询键时，会先到源节点查看存不存在；不存在的话（这个键所处的槽正在迁移），源节点想客户端发送一个ASK错误，指引客户端转向正在导入槽的目标节点，并再次发送ASKING命令以及之前想要执行的命令；（发送ASKING命令，可以避免出现MOVED返回造成循环）

4、 复制与故障转移
1）每个主节点都存在有从节点；（也可以没有，但无法进行故障转移）
2）当通过PING命令半数以上的主节点发现某一个主节点A下线后，则判定A为已下线；
3）Raft选举新的主节点；（A的从节点进行自我推荐，但只有主节点具有投票权，且先到先得）；
4）故障转移；将被选举的从节点替换原来的主节点A（包括继承槽位），并通知给其它主节点；

第四部分 独立功能的实现

第18章 发布和订阅

1、Redis的发布订阅功能由PUBLISH、SUBSCRIBE、PSUBSCRIBE；
2、频道的订阅与退订；SUBSCRIBE、UNSUBSCRIBE；
3、模式的订阅与退订；PSUBSCRIBE、PUNSUBSCRIBE；（通过模式匹配要订阅的频道）
注：频道的订阅关系，以字典存放；模式的订阅关系，以链表存放；
4、发送消息；PUBLISH；
1）遍历该频道对应的订阅者链表，发送消息；
2）遍历模式链表，当匹配时，发送消息；
5、查看订阅信息；PUBSUB

第19章 事务

1、事务的实现
1）事务开始；MULTI
2）事务入队；
3）执行事务；EXEC

2、WATCH命令（乐观锁）

Redis数据库会维护一个watched_keys字典（表明那个键被哪些客户端监听）；如果数据被修改，则会修改对应客户端的REDIS_DIRTY_CAS，表示该客户端的事务安全性已经被破坏，因此在执行该客户端的事务时，会拒绝；
3、事务四大性质
1）原子性；redis具有，但是redis不支持回滚，及时事务队列中的某个命令在执行期间出现了错误；
2）一致性；redis具有；
入队错误（入队时命令不存在或格式不正确等，会拒绝执行事务）；
执行错误（入队时无法发现，其执行时错误不会影响事务执行，只是错误的语句不能执行）；
服务器停机（也一致）
3） 隔离性；redis具有；Redis的事务以串行的方式运行；
4） 持久性；由redis的持久化模式决定；（AOF+always）

第20章 Lua脚本

第21章 排序

1、 Redis的SORT命令可以列表键、集合键或者有序集合键进行排序；
2、为排序创建的数组结构，其中的obj指向实际的数据；

第22章 二进制位数组

1、GETBIT、SETBIT、BITCOUNT

第23章 慢查询日志

第23章 监视器