Redis设计与实现
2022-03-12 16:32:57 0 举报AI智能生成
redis设计与实现读书笔记，同时包括了面试题及项目实战解决方案，持续更新中
作者其他创作
大纲/内容
第一部分
简单动态字符串
英文缩写SDS
数据结构
int len
记录buf中已使用字节数量
int free
记录buf中未使用字节数量
char buf[]
保存字符串
SDS与c语言字符串的区别
常数复杂度获取字符串长度
C 语言的字符串长度获取 strlen 函数，需要通过遍历的方式来统计字符串长度，时间复杂度是 O（N）
杜绝缓冲区溢出
C语言函数把缓冲区大小是否满足操作的工作交由开发者来保证，程序内部并不会判断缓冲区大小是否足够用
减少修改字符串带来的内存重分配次数
二进制安全
SDS 不需要用 “\0” 字符来标识字符串结尾
兼容部分C字符串函数
链表
每个链表节点使用一个adlist.h/listNode结构来表示
前置节点
后置节点
节点的值
因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表
链表的缺陷也是有的，链表每个节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存
字典
Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对
rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的
哈希冲突
哈希表实际上是一个数组，数组里多每一个元素就是一个哈希桶
当一个键值对的键经过 Hash 函数计算后得到哈希值，再将(哈希值 % 哈希表大小)取模计算，得到的结果值就是该 key-value 对应的数组元素位置，也就是第几个哈希桶
Redis 采用了「链式哈希」的方法来解决哈希冲突
链式哈希局限性也很明显，随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O（n）
rehash 操作
给「哈希表 2」 分配空间，一般会比「哈希表 1」 大 2 倍
将「哈希表 1 」的数据迁移到「哈希表 2」 中
迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备
为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash
在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上
在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行
跳跃表
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的
层（level）：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度
后退（backward）指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用
分值（score）：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列
成员对象（obj）：各个节点中的o1、o2和o3是节点所保存的成员对象
整数集合
压缩列表
压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现
压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构
对象
第二部分
数据库
Redis服务器将所有数据库都保存在服务器状态redis.h/redisServer结构的db数组中，db数组的每个项都是一个redis.h/redisDb结构，每个redisDb结构代表一个数据库
Redis是一个键值对（key-value pair）数据库服务器，服务器中的每个数据库都由一个redis.h/redisDb结构表示，其中，redisDb结构的dict字典保存了数据库中的所有键值对
键空间的键也就是数据库的键，每个键都是一个字符串对象
键空间的值也就是数据库的值，每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的任意一种Redis对象
持久化
RDB持久化
SAVE命令会阻塞Redis服务器进程，直到RDB文件创建完毕为止，在服务器进程阻塞期间，服务器不能处理任何命令请求
BGSAVE命令会派生出一个子进程，然后由子进程负责创建RDB文件，服务器进程（父进程）继续处理命令请求
RDB文件结构
开头REDIS部分来判断是否RDB文件
version代表RDB文件版本号
databases部分包含着零个或任意多个数据库，以及各个数据库中的键值对数据
每个非空数据库在RDB文件中都可以保存为SELECTDB、db_number、key_value_pairs三个部分
SELECTDB常量的长度为1字节，当读入程序遇到这个值的时候，它知道接下来要读入的将是一个数据库号码
db_number保存着一个数据库号码
key_value_pairs部分保存了数据库中的所有键值对数据
EOF常量的长度为1字节，这个常量标志着RDB文件正文内容的结束
check_sum是一个8字节长的无符号整数，保存着一个校验和，这个校验和是程序通过对REDIS、db_version、databases、EOF四个部分的内容进行计算得出的
AOF持久化
AOF持久化功能的实现可以分为命令追加（append）、文件写入、文件同步（sync）三个步骤
服务器在执行完一个写命令之后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾
为了提高文件的写入效率，将一些数据写入到文件的时候，操作系统通常会将写入数据暂时保存在一个内存缓冲区里面，等到缓冲区的空间被填满、或者超过了指定的时限之后，才真正地将缓冲区中的数据写入到磁盘里面，这种做法虽然提高了效率，但也为写入数据带来了安全问题，因为如果计算机发生停机，那么保存在内存缓冲区里面的写入数据将会丢失。为此，系统提供了fsync和fdatasync两个同步函数，它们可以强制让操作系统立即将缓冲区中的数据写入到硬盘里面，从而确保写入数据的安全性
Redis读取AOF文件并还原数据库状态的详细步骤
创建一个不带网络连接的伪客户端
从AOF文件中分析并读取出一条写命令
使用伪客户端执行被读出的写命令
一直执行步骤2和步骤3，直到AOF文件中的所有写命令都被处理完毕为止
AOF重写过程
创建新 的AOF文件
遍历数据库并忽略空数据库
遍历数据库中所有键，忽略过期的键
根据键类型对键重写
string：使用get命令获取字符串键的值
使用set命令重写字符串键
重写会进行大量的写入操作，线程容易被长时间阻塞，所以重写程序由子进程执行
为了解决这种数据不一致问题，Redis服务器设置了一个AOF重写缓冲区，这个缓冲区在服务器创建子进程之后开始使用，当Redis服务器执行完一个写命令之后，它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区
事件
文件事件处理器的四个组成部分，它们分别是套接字、I/O多路复用程序、文件事件分派器（dispatcher），以及事件处理器
IO多路复用器监听多个socet套接字，然后将所产生的事件套接字都放入队列，以有序、同步、每次一个套接字的方式向文件事件分派器传送套接字
IO多路复用程序
Redis的I/O多路复用程序的所有功能都是通过包装常见的select、epoll、evport和kqueue这些I/O多路复用函数库来实现的
I/O多路复用程序可以监听多个套接字的ae.h/AE_READABLE事件和ae.h/AE_WRITABLE事件
当套接字变得可读时，或者有新的可应答（acceptable）套接字出现时，套接字产生AE_READABLE事件
当套接字变得可写时（客户端对套接字执行read操作），套接字产生AE_WRITABLE事件
文件事件处理器
连接应答处理器
用于对连接服务器监听套接字的客户端进行应答
命令请求处理器
负责从套接字中读入客户端发送的命令请求内容
命令回复处理器
负责将服务器执行命令后得到的命令回复通过套接字返回给客户端
时间事件
定时事件：让一段程序在指定的时间之后执行一次。比如说，让程序X在当前时间的30毫秒之后执行一次
周期性事件：让一段程序每隔指定时间就执行一次。比如说，让程序Y每隔30毫秒就执行一次
服务器将所有时间事件都放在一个无序链表中，每当时间事件执行器运行时，它就遍历整个链表，查找所有已到达的时间事件，并调用相应的事件处理器
事件的调度和执行规则
1、获取到达时间离当前时间最接近的时间事件
2、因为文件事件是随机出现的，如果等待并处理完一次文件事件之后，仍未有任何时间事件到达，那么服务器将再次等待并处理文件事件
3、对文件事件和时间事件的处理都是同步、有序、原子地执行的，服务器不会中途中断事件处理，也不会对事件进行抢占
4、时间事件在文件事件之后执行，并且事件之间不会出现抢占，所以时间事件的实际处理时间，通常会比时间事件设定的到达时间稍晚一些
客户端
由I/O多路复用技术实现的文件事件处理器，Redis服务器使用单线程单进程的方式来处理命令请求，并与多个客户端进行网络通信
Redis服务器状态结构的clients属性是一个链表，这个链表保存了所有与服务器连接的客户端的状态结构
服务端
命令请求的执行过程
客户端向服务器发送命令请求SET KEY VALUE
客户端会将这个命令请求转换成协议格式，然后通过连接到服务器的套接字，将协议格式的命令请求发送给服务器
服务器接收并处理客户端发来的命令请求SET KEY VALUE，在数据库中进行设置操作，并产生命令回复OK
服务器接收并处理客户端发来的命令请求SET KEY VALUE，在数据库中进行设置操作，并产生命令回复OK
客户端接收服务器返回的命令回复OK，并将这个回复打印给用户观看
第三部分
复制
旧版
同步（sync）
同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态
从服务器向主服务器发送SYNC命令
收到SYNC命令的主服务器执行BGSAVE命令，在后台生成一个RDB文件，并使用一个缓冲区记录从现在开始执行的所有写命令
当主服务器的BGSAVE命令执行完毕时，主服务器会将BGSAVE命令生成的RDB文件发送给从服务器，从服务器接收并载入这个RDB文件，将自己的数据库状态更新至主服务器执行BGSAVE命令时的数据库状态
主服务器将记录在缓冲区里面的所有写命令发送给从服务器，从服务器执行这些写命令，将自己的数据库状态更新至主服务器数据库当前所处的状态
命令传播（commandpropagate）
在主服务器的数据库状态被修改，导致主从服务器的数据库状态出现不一致时，让主从服务器的数据库重新回到一致状态
主服务器需要对从服务器执行命令传播操作：主服务器会将自己执行的写命令，发送给从服务器执行，当从服务器执行了相同的写命令之后，主从服务器将再次回到一致状态
缺点
断线后重复制再次sync比较耗时，需要同步所有RDB文件
新版
PSYNC
完整重同步
完整重同步用于处理初次复制情况：完整重同步的执行步骤和SYNC命令的执行步骤基本一样，它们都是通过让主服务器创建并发送RDB文件，以及向从服务器发送保存在缓冲区里面的写命令来进行同步
部分重同步
主服务器可以将主从服务器连接断开期间执行的写命令发送给从服务器，从服务器只要接收并执行这些写命令
主服务器的复制偏移量（replication offset）和从服务器的复制偏移量
主服务器每次向从服务器传播N个字节的数据时，就将自己的复制偏移量的值加上N（从服务器亦如此）
主服务器的复制积压缓冲区（replicationbacklog）
复制积压缓冲区是由主服务器维护的一个固定长度（fixed-size）先进先出（FIFO）队列
如果offset偏移量之后的数据仍然存在于复制积压缓冲区里面，那么主服务器将对从服务器执行部分重同步操作
如果offset偏移量之后的数据已经不存在于复制积压缓冲区，那么主服务器将对从服务器执行完整重同步操作
服务器的运行ID（run ID）
复制的实现
设置主服务器的地址和端口
建立套接字连接
发送PING命令
通过发送PING命令可以检查套接字的读写状态是否正常
通过发送PING命令可以检查主服务器能否正常处理命令请求
身份验证
从服务器在收到主服务器返回的"PONG"回复之后，如果从服务器设置了masterauth选项，那么进行身份验证
发送端口信息
同步
从服务器将向主服务器发送PSYNC命令，执行同步操作，并将自己的数据库更新至主服务器数据库当前所处的状态
命令传播
心跳检测
在命令传播阶段，从服务器默认会以每秒一次的频率，向主服务器发送命令
检测主从服务器的网络连接状态
辅助实现min-slaves选项
检测命令丢失
哨兵机制
如果server1故障下线，Sentinel系统会挑选server1属下的其中一个从服务器，并将这个被选中的从服务器升级为新的主服务器
Sentinel系统会向server1属下的所有从服务器发送新的复制指令，让它们成为新的主服务器的从服务器
Sentinel还会继续监视已下线的server1，并在它重新上线时，将它设置为新的主服务器的从服务器
哨兵系统建立过程
启动并初始化Sentinel
初始化服务器
将普通Redis服务器使用的代码替换成Sentinel专用代码
初始化Sentinel状态
根据给定的配置文件，初始化Sentinel的监视主服务器列表
创建连向主服务器的网络连接
获取主服务器信息
Sentinel默认会以每十秒一次的频率，通过命令连接向被监视的主服务器发送INFO命令，并通过分析INFO命令的回复来获取主服务器的当前信息
获取从服务器信息
当Sentinel发现主服务器有新的从服务器出现时，Sentinel除了会为这个新的从服务器创建相应的实例结构之外，Sentinel还会创建连接到从服务器的命令连接和订阅连接
向主服务器和从服务器发送信息
Sentinel会以每两秒一次的频率，通过命令连接向所有被监视的主服务器和从服务器发送命令
接收来自主服务器和从服务器的频道信息
检测主观下线状态
Sentinel会以每秒一次的频率向所有与它创建了命令连接的实例（包括主服务器、从服务器、其他Sentinel在内）发送PING命令，并通过实例返回的PING命令回复来判断实例是否在线
检查客观下线状态
当Sentinel将一个主服务器判断为主观下线之后，为了确认这个主服务器是否真的下线了，它会向同样监视这一主服务器的其他Sentinel进行询问，看它们是否也认为主服务器已经进入了下线状态
选举领头Sentinel
当一个主服务器被判断为客观下线时，监视这个下线主服务器的各个Sentinel会进行协商，选举出一个领头Sentinel，并由领头Sentinel对下线主服务器执行故障转移操作
Redis选举领头Sentinel的规则
所有在线的Sentinel都有被选为领头Sentinel的资格
每次进行领头Sentinel选举之后，不论选举是否成功，所有Sentinel的配置纪元（configuration epoch）的值都会自增一次
在一个配置纪元里面，所有Sentinel都有一次将某个Sentinel设置为局部领头Sentinel的机会
当一个Sentinel（源Sentinel）向另一个Sentinel（目标Sentinel）发送命令，这表示源Sentinel要求目标Sentinel将前者设置为后者的局部领头Sentinel
Sentinel设置局部领头Sentinel的规则是先到先得
目标Sentinel在接收到命令之后，将向源Sentinel返回一条命令回复
源Sentinel在接收到目标Sentinel返回的命令回复之后，那么表示目标Sentinel将源Sentinel设置成了局部领头Sentinel
如果有某个Sentinel被半数以上的Sentinel设置成了局部领头Sentinel，那么这个Sentinel成为领头Sentinel
故障转移
领头Sentinel将对已下线的主服务器执行故障转移操作
在已下线主服务器属下的所有从服务器里面，挑选出一个从服务器，并将其转换为主服务器
删除列表中所有处于下线或者断线状态的从服务器，这可以保证列表中剩余的从服务器都是正常在线的
删除列表中所有最近五秒内没有回复过领头Sentinel的INFO命令的从服务器，这可以保证列表中剩余的从服务器都是最近成功进行过通信的
删除所有与已下线主服务器连接断开超过down-after-milliseconds*10毫秒的从服务器
删除所有与已下线主服务器连接断开超过down-after-milliseconds*10毫秒的从服务器
领头Sentinel将根据从服务器的优先级，对列表中剩余的从服务器进行排序，并选出其中优先级最高的从服务器
如果有多个具有相同最高优先级的从服务器，那么领头Sentinel将按照从服务器的复制偏移量，对具有相同最高优先级的所有从服务器进行排序，并选出其中偏移量最大的从服务器
如果有多个优先级最高、复制偏移量最大的从服务器，那么领头Sentinel将按照运行ID对这些从服务器进行排序，并选出其中运行ID最小的从服务器
让已下线主服务器属下的所有从服务器改为复制新的主服务器
将已下线主服务器设置为新的主服务器的从服务器
集群
节点
一个Redis集群通常由多个节点（node）组成
连接各个节点的工作可以使用CLUSTER MEET命令来完成
槽指派
Redis集群通过分片的方式来保存数据库中的键值对
集群的整个数据库被分为16384个槽（slot），数据库中的每个键都属于这16384个槽的其中一个，集群中的每个节点可以处理0个或最多16384个槽
在集群中执行命令
在对数据库中的16384个槽都进行了指派之后，集群就会进入上线状态，这时客户端就可以向集群中的节点发送数据命令了
当客户端向节点发送与数据库键有关的命令时，接收命令的节点会计算出命令要处理的数据库键属于哪个槽，并检查这个槽是否指派给了自己
重新分片
Redis集群的重新分片操作可以将任意数量已经指派给某个节点（源节点）的槽改为指派给另一个节点（目标节点），并且相关槽所属的键值对也会从源节点被移动到目标节点
ASK错误
当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据库键恰好就属于正在被迁移的槽时
源节点会先在自己的数据库里面查找指定的键，如果找到的话，就直接执行客户端发送的命令
如果源节点没能在自己的数据库里面找到指定的键，那么这个键有可能已经被迁移到了目标节点，源节点将向客户端返回一个ASK错误，指引客户端转向正在导入槽的目标节点
复制与故障转移
设置从节点
集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此来检测对方是否在线
如果接收PING消息的节点没有在规定的时间内，向发送PING消息的节点返回PONG消息，那么发送PING消息的节点就会将接收PING消息的节点标记为疑似下线
如果在一个集群里面，半数以上负责处理槽的主节点都将某个主节点x报告为疑似下线，那么这个主节点x将被标记为已下线（FAIL）
当一个从节点发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移
复制下线主节点的所有从节点里面，会有一个从节点被选中
被选中的从节点会执行SLAVEOF no one命令，成为新的主节点
新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己
新的主节点向集群广播一条PONG消息，这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点
新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成
新主节点选举
集群的配置纪元是一个自增计数器，它的初始值为0
当集群里的某个节点开始一次故障转移操作时，集群配置纪元的值会被增一
对于每个配置纪元，集群里每个负责处理槽的主节点都有一次投票的机会，而第一个向主节点要求投票的从节点将获得主节点的投票
当从节点发现自己正在复制的主节点进入已下线状态时，从节点会向集群广播一条消息，要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票
如果一个主节点具有投票权（它正在负责处理槽），并且这个主节点尚未投票给其他从节点，那么主节点将向要求投票的从节点返回一条消息，表示这个主节点支持从节点成为新的主节点
每个参与选举的从节点都会接收消息，并根据自己收到了多少条这种消息来统计自己获得了多少主节点的支持
如果集群里有N个具有投票权的主节点，那么当一个从节点收集到大于等于N/2+1张支持票时，这个从节点就会当选为新的主节点
因为在每一个配置纪元里面，每个具有投票权的主节点只能投一次票，所以如果有N个主节点进行投票，那么具有大于等于N/2+1张支持票的从节点只会有一个
如果在一个配置纪元里面没有从节点能收集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止
消息
集群中的各个节点通过发送和接收消息（message）来进行通信
第四部分
发布与订阅
Redis的发布与订阅功能由PUBLISH、SUBSCRIBE、PSUBSCRIBE等命令组成
事务
Redis通过MULTI、EXEC、WATCH等命令来实现事务（transaction）功能
事务提供了一种将多个命令请求打包，然后一次性、按顺序地执行多个命令的机制
事务开始
MULTI命令
命令入事务队列
执行事务
当一个处于事务状态的客户端向服务器发送EXEC命令时，这个EXEC命令将立即被服务器执行。服务器会遍历这个客户端的事务队列，执行队列中保存的所有命令
WATCH命令的实现
WATCH命令是一个乐观锁（optimistic locking），它可以在EXEC命令执行之前，监视任意数量的数据库键，并在EXEC命令执行时，检查被监视的键是否至少有一个已经被修改过了，如果是的话，服务器将拒绝执行事务
Lua脚本
排序
Redis的SORT命令可以对列表键、集合键或者有序集合键的值进行排序
二进制位数组
Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组
慢查询日志
Redis的慢查询日志功能用于记录执行时间超过给定时长的命令请求，用户可以通过这个功能产生的日志来监视和优化查询速度
slowlog-log-slower-than选项指定执行时间超过多少微秒（1秒等于1 000 000微秒）的命令请求会被记录到日志上
slowlog-max-len选项指定服务器最多保存多少条慢查询日志
监视器
通过执行MONITOR命令，客户端可以将自己变为一个监视器，实时地接收并打印出服务器当前处理的命令请求的相关信息
第五部分（常见面试题）
数据结构
string底层SDS
list底层双向链表，压缩列表
hash底层压缩列表、哈希表
set底层哈希表，整数集合
zset底层压缩列表、跳表
收藏
收藏
0 条评论
下一页
