Redis设计与实现笔记
数据结构
SDS
- 简单动态字符串（Simple Dynamic String）
- 字段：
len, free, []char,len+free+1(空字符) = len([]char) - 保留空字符是为了重用部分C函数。
- 修改字符串时减少内存重分配次数。增长时使用free，缩短时惰性回收。如果free不够用重新申请内存，
free = newLen < 1MB ? newLen : 1MB(free最多1MB)
链表
- 双端链表，无环。
字典
- 通过链表解决键冲突。
- 两个数组，其中一个作为rehash使用。
rehash
发生的条件：扩展时：负载因子（节点数/数组大小）> 1, 如果在执行BGSAVE | BGREWRITEAOF则 > 5，收缩时：负载因子<0.1。
扩张后的数组大小：大于等于（2*当前节点数）的最小的2^n^。
收缩后的数组大小：大于等于（当前节点数）的最小的2^n^。
渐进式rehash: 用rehashidx表示当前正在rehash的索引，rehash时对字典的操作会同时在两个数组上进行。
跳跃表
。。。
整数集合intset
- 有序，无重复。
- encoding:
int16（初始）, int32, int64 - 升级。比如当前是int16，当添加一个int32类型的整数时就需要升级，新添加的整数要么大于所有旧元素，要么小于所有旧元素？？？
- 搜索使用二分查找。
- 添加和删除的最坏时间复杂度为
O(n)。
压缩列表ziplist
- 特殊编码的连续内存块。
- 主要是为了省内存。
- 可以保存1，2，5字节长的字节数组或者1字节长的整型。
- 连锁更新：在表头插入了新节点（>=254字节），导致后面所有的节点的“前节点长度”都从1字节变为5字节了。删除也可能会导致连锁更新。最坏复杂度是
O(n^2)。 - 添加的复杂度是
O(n)|O(n^2)， 按索引查找的复杂度O(n), 按值查找的复杂度O(n^m)（m是字节数组的长度，因为要比较值）.删除的复杂度O(n)|O(n^2)。（O(n^2）都是因为可能会连锁更新）
对象
- type:
string, list, hash, set, zset - encoding:
int, embstr, raw, hashtable, linkedlist, ziplist, intset, skiplist
string
可用：int, embstr, SDS
保存整数并且这个整数可以用long来表示时，使用int。
<= 32字节 使用 embstr
> 32字节 使用 SDS
embstr 就是 redisObject 和 sdshdr 放到了连续的内存块中。
embstr 是只读的，如果执行了修改命令，那么就转换成 SDS 编码了。
使用 long double 表示的浮点数可是使用字符串来保存的（embstr 或者 SDS）
list
可用：linkedList, zipList
使用zipList的条件: 所有字符串元素小于64字节 && 元素数量小于512
hash
可用：hashtable, zipList
使用zipList: 每次将键和值保存到列表尾部
使用zipList的条件：所有键值对的字符串小于64字节 && 键值对数量小于512个。
set
可用：intset, hashtable
使用intset的条件：元素都是整数值 && 元素数量小于512个。
zset
可用：zipList, skipList
使用zipList：元素+分值，按照分值从小到大排序
使用skipList时：zset中有一个字典用于保存元素到分值的映射，可以在O(1)时间内获取元素的分值。
使用zipList的条件：元素长度小于64字节 && 元素数量小于128个。
内存回收
- 引用计数
对象共享
- redis初始时会创建从0到9999共一万个字符串对象。
- 不共享复杂对象（比如列表）的原因：使用共享对象时要先检查共享对象和预期的是否一样，对象越复杂校验的复杂度越高，占CPU越多。
空转时长
- 记录对象最后一次被访问的时间。
- 空转时长就是当前时间减去最后一次被访问的时间，也就是存活时间。
- 如果配置了
maxmemory并且算法是lru时，空转时长较高的会优先被释放。
单机数据库
数据库
- 默认创建16个数据库，使用数组保存数据库信息。
- 客户端会保存数据库信息的指针，
select 1命令就是修改这个指针。 - 数据库保存一个字典
dict，键是字符串，值是各种类型的对象。 - 数据库保存一个字典
expires，记录键的过期时间。键是指针，值是毫秒的unix时间戳。 - 过期键删除策略：惰性删除（使用键之前先检查是否过期）和定期删除（多次遍历数据库，随机检查部分键）
- 生成rdb文件时：过期键不会被保存到rdb中。
- 载入rdb文件时：主服务器模式忽略过期键，从服务器模式都会加载。
- AOF文件写入：过期键被删除时追加一条删除命令。
- AOF重写：过期键不会被保存到AOF中。
- 复制模式：主服务器会主动发送删除命令，如果没有发出，从服务器会返回过期键的值。
RDB持久化
- 可以手动执行，也可以定期执行。
- rdb文件是一个经过压缩的二进制文件。
- rdb的创建：
SAVE阻塞进程，不处理命令。BGSAVE派生子进程，可以继续处理命令。 - 载入rdb文件时服务器处于阻塞状态。
BGSAVE可以配置保存的频率，比如多少秒内执行了多少次修改就会触发持久化。（多少次修改由dirty计数器统计）
AOF持久化
- 先将写命令追加到
aof_buf中，之后事件循环会在每次循环时将aof_buf中的内容写入到文件中，至于要不要同步到aof文件中由配置决定（总是同步，距离上次1秒以上同步-默认，不同步由操作系统决定） - AOF重写：AOF文件会越来越大，重写是用新的AOF文件代替大的文件。直接从数据库读取值生成写命令，过期键不写。如果数量多于64个，每64个作为一个命令。使用子进程来重写，重写期间新的命令被放到aof缓冲区和重写缓冲区，重写结束后由父进程将重写缓冲区中的内容写到新的aof文件中。
事件
文件事件
- 与客户端连接的socket。
- I/O多路复用，产生事件的套接字被放到一个队列中一个一个执行。
- 如果套接字同时可读可写，先读，后写。读 - 客户端执行write， 写 - 客户端执行read
时间事件
- 事件被放在一个无序链表中，每次检查都遍历所有的事件，选出需要执行的。
- 正常模式下只有
serverCron一个事件，所以即使遍历所有节点也不影响性能。
事件调度
- 先获取距离最近的时间事件
- 等待文件事件，如果有就处理，没有的话就阻塞，阻塞时间由第1步获取的时间决定。
- 处理时间事件。
服务器不会中途中断事件处理，也不会对时间进行抢占，靠事件处理自觉让出执行权。
客户端
- 输入缓冲区：根据输入内容动态调整，大小超过1G时会关闭这个客户端。
- 命令和参数都保存在argv数组中。
- 服务器有一个命令表（字典），根据命令的名称查找命令应该执行的结构体
redisCommond。 - 输出缓冲区有两个，一个固定大小（16KB）的用于缓存小回复，一个可变大小的用于缓存大回复。固定大小的缓冲区用完后或者回复太大时才用可变缓冲区？可变大小的缓冲区也是有上限的（硬性限制和软性限制）。
服务器
命令执行的步骤
- 客户端向服务端发送命令
- 服务端将命令保存到客户端的输入缓冲区
- 分析命令，提取参数，查找命令对应的command
- 预备操作（检查参数，身份验证，内存占用... …）
- 调用实现函数，将响应放到客户端的输出缓冲区
- 执行后续工作（是否加入慢查询日志，调用计数器增一，AOF缓冲区，其他从服务器......）
- 将响应发送给客户端并清空客户端的输出缓冲区。
serverCron函数
- 每100毫秒执行一次
- 更新服务器时间缓存，用于对时间精度要求不高的功能，比如打印日志，更新服务器的LRU时钟，决定是否执行持久化任务等。
- 更新服务器的LRU时钟，对象的lru时间就是根据这个计算的。
- 更新服务器每秒执行的命令次数。使用一个环记录每次抽样的结果，最后取平均值。
- 更新内存使用的最大值。
- 检查是否退出服务。SIGTERM信号的处理器会将shutdown_asap标识记为1，serverCron会检查这个标识，然后执行退出步骤，退出时还会进行rdb持久化。
- 管理客户端资源。连接是否超时，调整输入缓冲区大小。
- 管理数据库。删除过期键，对字典进行收缩等。
- 将AOF缓冲区写入到AOF文件中。
初始化服务器
- 初始化服务器状态结构
- ID
- 默认运行频率
- 默认配置文件路径
- 运行架构32或64
- 默认端口号
- LRU时钟
- 命令表
- 载入配置，参数或者配置文件
- 初始化数据结构
- clients链表
- db数组
- 设置操作
- 信号处理器
- 创建共享对象
- 监听端口
- 为serverCron创建时间事件
- 打印redis图标
- 还原数据库，AOF文件 || RDB文件
- 执行事件循环
多机数据库
复制
127.0.0.1:12345> SLAVEOF 127.0.0.1 6379
:6370为主服务器，:12345为从服务器，从服务器复制主服务器。
旧版复制功能
- 从服务器向主服务器发送SYNC命令
- 主服务器执行
BGSAVE，生成RDB文件，并用一个缓冲区记录从现在开始的写命令。 - 主服务器将RDB文件发给从服务器，从服务器载入RDB
- 主服务器将缓冲区的写命令发给从服务器
- 命令传播：主服务器将自己执行的写命令不断地发给从服务器。
缺陷：
断线后重连：如果主从断线，从连接上主后，将发送SYNC命令生成RDB，如果断线时间短，缺失的命令比较少，这样做很浪费资源。
新版复制功能
使用PSYNC代替SYNC
- 完整重同步：和SYNC的过程一样。
- 部分(partial)重同步：只将断线后的写命令发给从服务器。
PSYNC的实现：
- 如果没有复制过或者上次复制的主服务器ID不一致，执行完整重同步。
- 主服务器有一个固定大小的先进先出的队列，记录发给从服务器的写命令。如果从服务器的复制偏移量(按byte来算的)在这个队列范围内，那么执行部分重同步，否则执行完整重同步。
心跳检测
- 从服务器发给主服务器
- 每秒一次
- 参数：复制偏移量
三个作用：
- 检查主从间的网络连接状态（超过一秒没有回复说明有问题）
- 实现
min-slaves: 当从服务器少于3个或者3个从服务器的延迟都>=10秒，主服务器拒绝执行写命令。 - 检测命令丢失。根据从服务器的复制偏移量，主服务器知道哪些写命令丢失了，将从缓冲区里重新发送。
Sentinel哨兵
- 哨兵系统有一个或多个哨兵实例组成。
- 哨兵系统监听主服务器和它的所有从服务器。
- 当主服务器下线时长超过设置值时，从 从服务器 中选择一个作为主服务器，并向其他从服务器发送新的复制指令。
- 监视已下线的主服务器，当它上线后，将它设置成从服务器。
细节：
- Sentinel作为主服务器的客户端，创建两个连接，一个用于向主服务器发送命令，一个用于订阅。
- Sentinel每10秒向主服务器发送INFO命令，分析主服务器的信息和从服务器的信息。
- Sentinel每10秒向从服务器发送INFO命令，分析从服务器信息。也是两个连接。
- Sentinel每2秒向主从发送Sentinel和主服务器的信息，通过订阅频道。
选举Sentinel
- S1向其他S发送请求，每个S在一个纪元内只能选一个领头者，先到先得，获得半数以上投票的当选。
从服务器中选主服务器
- 所有从服务器存到一个列表中
- 删除下线的从服务器，保证都是正常运行的
- 删除最近5秒没有回复领头Sentinel的INFO命令的，保证都是最近成功进行通信的。
- 删除过早与主服务器断开连接的，保证数据比较新
- 选择优先级最高的
- 优先级相同的话，选择复制偏移量最大的，再就是选择ID最小的
集群
- 16384（2048*8）个槽都有节点处理时，集群处于上线状态。
重新分片
独立功能
发布与订阅
- 订阅频道：
subscribe "new.it" - 订阅模式：
subscribe "new.*" - 频道订阅信息在redis中是一个
pubsub_channels的字典，键为频道名称，值为client的列表。 - 模式订阅信息在redis中是一个
pubsub_patterns的列表，元素是client。当发布信息时，需要遍历整个列表找出匹配的模式。
事务
事务的实现
MULTI时客户端状态打开REDIS_MULTI。- 如果是
EXEC, DISCARD, WATCH, MULTI中的一个，就立即执行命令。 - 发送的其他命令被放到一个事务队列中（先进先出）。
- 遇到
EXEC命令时就立刻执行队列中的命令，并将结果发给客户端。
WATCH命令的实现
- 每个数据库都保存着
watched_keys字典，键是数据库键，值是客户端列表。 - 当执行对数据库修改的命令时就查看有没有监控这个键的客户端，有的话就将客户端的
REDIS_DIRTY_CAS标识打开，标识事务的安全性被破坏了。 - 当执行客户端发来的
EXEC命令时，就检测REDIS_DIRTY_CAS是否被打开，是的话就拒绝执行事务。返回nil
事务的ACID性质
- A：原子性。如果命令入队出错，那么整个事务都不会被执行。如果命令在执行时出错，那么整个事务都将继续执行。
- C：一致性。事务要么执行要么不执行，宕机后要么恢复(rdb, aof)，要么空白。
- I：隔离性。单线程执行，事务是串行执行的。
- D：持久性。只有在AOF模式下，并且总是同步文件时才有持久性。
二进制数组
- 使用SDS保存。
- 逆序存储。最低位保存在数组的开始。当扩展时不需要移动原来的数据。
1的个数
- 遍历数组，遇到1，计数器就增一。
- 查表。表的键是8位或者16位二进制组合，值是其中包含的1的个数，这样每8位只需要查一次表。
- variable-precision SWAR算法，通过位运算，先两个两个，再四个四个。。。，一次可以处理32位。
redis使用查表和variable-precision SWAR算法结合。
如果未处理的二进制位数>=128位，就调用4次variable-precision SWAR算法。
如果未处理的二进制位数<128位，就查表，表的key是8位的排列。
慢查询日志
- 通过
slowlog-log-shower-than指定执行时间超过多少微妙会被记录到日志上。 slowlog-max-len指定最多保存多少条慢查询日志。- 使用先进先出的链表保存日志，达到最大值时将最开始的删除。
监视器
MONITOR实时接收并打印服务器当前处理的命令。- 客户端的
REDIS-MONITOR标识被打开，并且被添加到monitors链表末尾。