Redis核心原理
2021-09-28 18:02:47 0 举报AI智能生成
Redis设计与实现
作者其他创作
大纲/内容
单机数据库的实现
数据库
Redis数据库结构
Redis将所有数据库都保存在redisServer结构的db数组中，数组中没个项都是一个redisDB结构，每个结构代表ige数据库
切换数据库
客户端db属性记录了客户端当前的目标数据库，这个属性是一个指向redisDB结构的指针，select命令会切换指针到指定数据库
键空间
数据库键空间是个字段
读写键空间维护操作
读取一个键后（读写操作都会对键读取），服务器会根据键是否存在来更新键空间的命中次数或见空间不命中次数
读取键后，服务器会更新键的LRU（最后一次使用）时间
读取时发现键已过期，会先删除这个过期键
客户端使用WATCH监视了某个键，键被修改后，会标记为脏（dirty）,让事务程序注意到这个键已经被修改
每次修改一个键之后，都会对脏（dirty）键计数器的值增1
如果开了通知功能，对键修改后服务器会按配置发送响应的数据库通知
键的生存时间和过期时间
redisDB结构中expires字典保存了数据库中所有键的过期时间
过期字典的键是一个指针，这个指针指向键空间中的某个键
过期字典的值是一个long类型的整数
Redis过期键删除策略
惰性删除
获取键时检查键是否过期，过期则删除
定期删除
每隔一段时间检查一次数据库，删除过期键
AOF、RDB和复制功能对过期键的处理
已过期的键不会保存到新创建的RDB文件中
已过期未删除的键AOF写入不会对这个键产生影响，AOF重写和RDB文件处理方式一致
过期键是否被删除从服务会从主服务同步
RDB持久化
RDB文件的创建和载入
RDB文件创建命令
SAVE
会阻塞进程<br>
BGSAVE
派生一个子进程创建RDB<br>
执行期间SAVE、BGSAVE命令会被拒绝<br>
dirty计数器
记录上一次执行SAVE和BGSAVE命令后对数据库进行了多少次修改<br>
lastsave属性
记录上一次执行SAVE和BGSAVE命令的时间
载入
如果开启了AOF，会优先使用AOF文件，AOF关闭时才会使用RDB文件<br>
载入RDB文件期间，会一直处于阻塞状态<br>
RDB文件结构
REDIS
5个字节保存"REDIS"字符用来检查是否为RDB文件<br>
db_version
4字节保存了RDB文件版本号<br>
database[0~n]<br>
数据库和键值对数据
SELECTDB
1字节，表示接下来将读取一个数据库号码
db_number
数据库号码，读取后服务器会调用SELECT命令<br>
key_value_pairs<br>
数据库所有键值对的数据
TYPE
key
value
EOF
1字节标志正文内容结束
check_sum
保留这一个效验和，检查RDB文件是否有损坏
AOF持久化
命令追加
写命令会追加到服务状态aof_buf缓冲区的末尾
AOF文件写入与同步
Redis进程是一个事件循环
每次一个事件循环结束前会调用函数考虑（AOF同步参数配置）是否将缓冲区内容写入AOF文件
AOF文件的载入与数据还原
步骤
1.创建一个不带网络连接的伪客户端；因为Redis命令只能在客户端上下文中执行
2.从AOF文件中分许并读取出一条写命令
3.使用伪客户端执行被读出的命令
4.重复步骤2和3直到AOF所有命令执行完毕
AOF重写
解决AOF文件体积膨胀的问题，提供了AOF文件重写（rewrite）功能，会创建一个新的AOF文件来代替现有的AOF文件
重写并不需要对现有AOF文件进行操作，而是通过读取当前数据库的状态来时间；去读当前键的值，将多个值的操作命令合并为一条；只包含数据库所必须的命令不会浪费任何硬盘空间
AOF重新程序在子进程里执行
子进程重新和当前数据库不一致的问题：Redis设置了一个AOF重写缓冲区，这个缓冲区在服务器创建子进程后开始使用，Redis执行完一个写命令后会同时将这个命令发送给AOF缓冲区和AOF重写缓冲区
完成AOF重写工作后会给父进程发一个信号，父进程接受到信号后会将重新缓冲区的所有内容写入AOF新文件中，然后对新文件改名原子的覆盖现有AOF文件
事件
文件事件
服务端与客户端的通信会产生文件事件
文件事件处理器（Reactor模式实现的网络通信程序）
套接字
I/O多路复用程序
文件事件分派器
事件处理器
应答处理器：对连接服务器的客户端进行应答
命令请求处理器：接收客户端传来的命令请求
命令回复处理器：向客户端返回命令的执行结果
复制处理器：主服务器和从服务器复制操作
AE_READABLE(读事件)、AE_WRITABLE(写事件)
时间事件
定时事件（未使用）
周期性事件
事件的属性
id
when:毫秒精度的UNIX时间戳
timeProc:时间事件处理器，一个函数
实现
所有事件都保存在一个无序链表中，执行时遍历整个链表查找已到达时间的事件
客户端
服务端状态结构clients属性
clients属性是一个链表，保存了所有与服务器连接的客户端的状态结构
属性
套接字描述符：fd
伪客户端fd值为-1
普通客户端fd的值大于-1
名字：*name
标志：flags
记录了客户端的角色和客户端目前所处的状态
输入缓冲区：querybuf
保存客户端发送的命令请求
命令与命令参数：**argv、argc
querybuf解析后的命令参数和参数的个数
命令的实现函数
输出缓冲区
保存执行命令的命令回复，每个客户端有两个输出缓冲区，一个大小是固定的一个市可变的
身份认证
记录客户端是否通过了身份认证
时间
创建客户端的时间
与服务器最后一次互动的时间
客户端空转的时间
多机数据库的实现
复制
PSYNC
完整重同步
用于初次复制
1.主服务器收到PSYNC命令执行BGSAVE命令，再后台生成一个RDB文件，并使用一个缓冲区记录从现在开始执行的所有命令
2.主服务器将RDB文件发送给从服务器，从服务器接收并载入这个RDB文件
3.主服务器将记录在缓冲区里面的所有写命令发送给从服务器，从服务器执行这些写命令
部分重同步
处理断线后重复制情况
主服务器的复制偏移量和从服务器的复制偏移量
主服务器每次向从服务器传播N个字节的数据时，就将自己的复制偏移量的值加上N
从服务器每次收到主服务器传播来的N个字节的数据时，就将自己的复制偏移量的值加上N
可以根据偏移量知道主从服务器是否处于一致状态
主服务器的复制积压缓冲区
是由服务器维护的一个固定长度先进先出（FIFO）队列，默认大小为1MB（公式：断线重连平均时间*平均每秒写数据量），会为队列中每个字节记录相应的复制偏移量
主服务器将写命令发送给从服务器时还会将写命令入队到复制积压缓冲区里，
从服务重新连上主服务器时，从服务器会通过PSYNC命令将自己的复制偏移量offset发送给主服务器，主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作：
如果offset偏移量之后的数据仍然存在于复制积压缓冲器里面，那么执行部分冲同步操作
相反如果offset偏移量之后的数据已经不存在于复制积压缓冲区，将执行完整重同步操作
服务器运行的ID
Redis主和从服务器都有自己的运行ID，由40个随机的十六进制字符组成
从服务器对主服务器进行初次复制时，主服务器会将自己的运行ID传给从服务器
从服务器断线重连后从服务器会向主服务器发送之前保存的运行ID
如果ID相同表示断线前复制的就是这个服务器的数据，可以继续尝试部分同步
如果不同执行完整重同步
PSYNC命令的实现
从服务器
从服务没有复制过任何主服务器，向主服务器发送PSYNC ? -1命令进行完整重同步
从服务器已经复制过某个主服务器，向主服务器发送PSYNC <runid> <offset>命令进行部分重同步
主服务器
主服务器返回+FULLRESYNC <runid> <offset>表示主服务器将与从服务器执行完整重同步操作
主服务器返回+CONTINUE表示执行部分重同步操作
主服务器返回-ERR表示主服务器版本低于Redis2.8 无法识别PSYNC命令
复制的实现
1.设置主服务器的地址和端口
将客户端给定的主服务器地址和端口保存到服务状态masterhost属性和masterport属性中
2.建立套接字连接
和主服务器建立连接
3.发送PING命令
检查套接字读写状态
检查主服务器能否正常处理命令
4.身份验证
设置了masterauth需要进行身份验证，否则不需要
5.发送端口信息
向服务器发送从服务器监听端口
6.同步
从服务器向主服务器发送PSYNC命令
7.命令传播
同步完成后进入命令传播阶段
心跳检测
从服务器默认每秒一次的频率向主服务器发送检测命令
检测从服务器的网络连接状态
辅助实现min-slaves选项：防止主服务器在不安全的情况下执行写命令
检测命令丢失
通过偏移量检测命令是否丢失
Sentinel
启动并初始化
1.初始化服务器
2.将普通服务器使用的代码替换成Sentinel专用代码
一些命令和结构的替换
3.初始化Sentinel状态
4.根据配置文件，初始化Sentinel监视主服务器列表
5.创建连向主服务器的网络连接
一个命令连接，向主服务器发送命令并接收回复
一个订阅连接，订阅主服务器的_sentinel_:hello频道
获取主服务器信息
Sentinel会以每10秒一次的频率向被监视的主服务器发送INFO命令
获取主服务器本身的信息
获取主服务器下所有从服务器的IP和端口
获取从服务器的信息
Sentinel会以每10秒一次的频率向从服务器发送INFO命令
从服务器的运行ID
从服务器的角色role
主服务器的IP和端口
主从服务器的连接状态
从服务器的优先级
从服务器的复制偏移量
向主服务器和从服务器发送信息
Sentinel会以每2秒一次的频率向所有主服务器和从服务器发送PUBLISH命令
接收来自主服务器和从服务器的频道信息
检测主观下线状态
Sentinel会以每秒一次的频率向所有主从服务器和其他Sentinel发送PING命令
检查客观下线状态
当主服务器被检测为主观下线后，会向同样监视它的其他Sentinel进行询问，收到足够数量的下线，会对从服务器判定为客观下线并对主服务器执行故障转移操作
选举领导Sentinel
被检测为客观下线后各个Sentinel会进行协商选举一个领头Sentinel,由领头Sentinel对下线主服务器执行故障转移操作
所有Sentinel都有被选为Leader的资格
每次选举后不管是否成功Sentinel配置纪元的值都会自增一次
一个配置纪元里所有Sentinel都有一次将某个Sentinel设置为领头的机会
发现主服务器下线的Sentinel都会要求自己被选为领头
被半数以上的Sentinel头片会被选为Leader
选举失败会重新选举
故障转移
对已下线主服务器的所有从服务器里选出一个转换为主服务器
排除处于下线或断线状态的从服务器
排除最近5秒没有回复INFO命令的
排除连接断开时间超过配置时间的
根据优先级排序
优先级相同根据复制偏移量排序
偏移量相同选ID最小的
让所有从服务器复制新的主服务器
将已下线主服务器转为从服务器
集群
节点
一个Redis集群有多个节点（node）组成
运行在集群模式的服务器会继续使用所有单机模式中的组件
数据结构
clusterNode保存了一个节点的当前状态：创建时间、节点名字、节点当前的配置纪元、节点IP和端口号
每个节点都有一个clusterNode,并为集群中的所有其他节点都创建一个相应的clusterNode结构来记录其他节点状态
CLUSTER MEET命令将两个节点进行握手
节点A为节点B创建一个clusterNode结构并保存
节点A向节点B发送IP和端口号
节点B为A创建clusterNode并保存
发送PING和PONG消息
槽指派
集群通过分片的方式来保存数据库中的键值对
集群的整个数据库被分为16384个槽（slot），数据库中每个键都属于16384个槽的其中一个，每个节点可以处理0个或最多16384个槽
clusterNode结构的slots属性和numslot属性记录了节点负责处理哪些槽
slots是一个二级制数组位，长度为16384/8=2048个字节
Redis以0为起始索引16383为终止索引，对slots数组中的16384个二进制位编号，并根据索引i上的二进制位的值判断节点是否处理槽i
结点会将自己的slots数据通过消息发送给集群其他节点来告知自己目前负责处理的槽
slots数据记录了所有槽的指派信息，每个槽位对应一个clasterNode
集群执行命令：接收命令的节点会计算出命令要处理的键属于哪个槽，并检查这个槽是否指派给了自己
键所在的槽刚好指派给了当前节点，节点直接执行命令
键所在的槽没有指派给当前节点，节点会返回一个MOVED错误指引客户点转向正确的节点并再次发送命令
CRC16(key) & 16383 计算槽位
集群节点保存键值对和过期时间的方式和单机实现一致
节点还会使用clasterState结构中的slots_to_keys跳跃表来保存槽和键之间的关系
重新分片
可以将任意数量已经指派给投个节点的槽指派给另一个节点
实现原理：由redis-trib实现
1.对目标节点发送命令让目标节点准备导入源节点键值对
2.向源节点发送命令准备迁移slot的键值对到目标节点
3.向源节点发送命令获取count个slot键值对的键名
4.对获取的每个键名发送命令原子的从源节点迁移至目标节点
5.重复步骤3和4直到属于slot槽的所有键值对都被迁移完成
6.向任意节点发送命令将slot指派给目标节点，这一信息会通过消息发送至整个集群所有节点都会知道slot已被指派给目标节点
复制和故障转移
复制
向一个节点发送命令设置为指定节点的从节点后，会修改自身的clusterNode结构中主节点的属性指向指定的节点
会关闭原本的master标志打开slave标志，然后开始向主节点进行复制，和单机复制功能相同
故障检测
定期向集群其他节点发送PING消息，规定时间内没返回PONG会将未返回消息的节点标记为疑似下线
半数以上主节点将某个节点标记为疑似下线，那么这个节点将会标记为已下线，并向整个集群广播
故障转移
当节点发现正在复制的主节点进入已下线状态开始进行故障转移
下线主节点的所有从节点里会有一个被选为新的主节点
新的主节点会撤销所有已下线主节点的槽指派，并将这些槽指派给自己
新的主节点向集群广播一条PONG消息通知其它节点已下线主节点已变更为新的主节点
新主节点开始接收自己负责处理的槽有关的命令请求
主节点的选举
集群配置纪元是一个自增器，它的初始值为0
集群中某个节点开始一次故障转移时集群配置纪元的值会增一
每个配置纪元及集群里的主节点都有一次投票的机会，第一个向主节点要求投票的从节点将获得主节点的投票
从节点发现主节点进入已下线状态后会向集群广播一条消息，要求其他主节点向这个从节点投票
每个从节点统计从其他主节点接收到多少个投票消息
从节点收到大于等于N/2+1张票时选为新的主节点
如果没有从节点收集到足够的票，进入新的配置纪元再次进行选举
消息
集群中的各个节点通过发送和接收消息来进行通信
消息头：clusterMsg结构
消息正文:clusterMsgData<br>
集群节点通过Gossip协议交换各自关于不同节点的状态消息
数据结构与对象
简单动态字符串（SDS）
定义
char buf[]<br>
字节数组用于保存字符串
int len
记录buf数组中已使用字节的数量<br>
int free
记录buf数组中未使用字节的数量
遵循C字符串已空字符结尾的惯例，空字符串1字节不计算在len里<br>
区别
SDS记录了len获取长度的复杂度为O(1)，C字符串必须遍历整个数组复杂度为O(N)<br>
SDS进行修改时API会自动将空间扩展至所需的大小（拼接一个新的c字符串空间），不会发生缓冲区溢出的情况
避免内存重分配的策略
空间预分配
优化SDS字符串增长操作
SDS长度（len属性值）小于1MB会分配len同样大小的未使用空间
大于1MB会分配1MB的未使用空间
惰性空间释放
优化SDS字符串缩短操作
不会立即回收空间，而是使用free记录空间长度以后使用
使用二进制存储
链表
list结构
listNode *prev<br>
前置节点
listNode *next
后置节点
*value<br>
节点的值
listNode *head
表头节点
listNode *tail
表尾节点
long len
l链表所包含的节点数量<br>
节点值复制函数<br>
复制链表节点所保存的值
节点值释放函数
释放链表节点所保存的值
节点值对比函数
对比链表节点所保存的值和另一个输入值是否相等<br>
特性
双端
无环
带表头指针和表尾指针
带链表长度计数器
多态（可以通过函数保存各种不同类型的值）<br>
字典
哈希表结构（dictht）
dictEntity **table
哈希表数组
void *key
键
union{} // 值 v
void *val
uint64_tu64
int64_ts64_ts64
dictEntity *next
指向下个哈希表节点，形成链表
long size
哈希表大小
long sizemask
哈希表大小掩码，用于计算索引值，总是等于size-1
long used
哈希表已有节点的数量
字典结构(dict)
dictType *type
类型特定函数，每个dictType结构保存了一簇用于操作特定类型键值对的函数
*privdata
私有数据，保存了传给那些特定函数的可选参数
dictht ht[2]
哈希表，包含两个项，字典只使用ht[0]哈希表，ht[1]哈希表只会在ht[0]哈希表进行rehash时使用
in trehashidx
rehash索引，当rehash不再进行时，值为-1；记录了rehash目前的进度
rehash
为字典ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量<br>
将ht[0]所有键值对rehash到ht[1]<br>
释放ht[0],将ht[1]设置为ht[0]，并在ht[1]创建一个空白哈希表<br>
数据量大时，rehash是渐进式的分多次进行<br>
渐进式rehash进行期间，删除、查找、更新会在两个哈希表上进行<br>
跳跃表
跳跃表结构
跳跃表（zskiplist）
header
指向跳跃表的表头节点
tail
指向表尾节点
length
跳跃表长度，跳跃表目前包含节点的数量
level
记录表内层数最大的那个节点的层数
特性
有序集合的底层实现之一
每个跳跃表节点的层高都是1至32之间的随机数
多个节点可以包含相同的分值，但每个节点的成员对象必须时唯一的
按分值大小排序，分值相同按照成员对象大小排序
整数集合
结构
整数集合（intset）
uint32_t encoding
编码方式
uint32_t length
元素数量
int8_t contents[]
保存元素的数组
每个元素占16位空间
升级
1.根据新元素的类型，扩展整数集合底层数据的空间大小
2.将底层元素转换成新元素相同的类型，并将转换后的元素放在正确的位置，保证有序性质不变<br>
3.新元素添加到底层数组里<br>
可以同时保存int16_t、int32_t、int64_t三种类型的值<br>
特性
集合键的底层实现之一
以有序无重复的方式保存集合元素，可以根据新元素的类型改变数组的类型<br>
升级可以提升灵活度和节约内存
只支持升级，不支持降级
压缩列表
结构
由一系列连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多的节点，每个节点可以保存一个字节数据或者一个整数值
uint32_t zlbytes
4字节，记录整个压缩列表占用的内存数，内存重分配或计算zlend的位置时使用
uint32_t zltail
4字节，记录尾节点到起始地址有多少个字节，可以快速确定尾节点的地址
uint16_t zllen
2字节，压缩列表节点的数量
entryX
列表节点，长度由内容决定
previous_entry_length
以字节为单位，记录了列表中前一个节点的长度；前一节点长度小于254字节用1字节保存，大于254字节用5字节保存
encoding
记录了content属性所保存数据的类型以及长度
content
保存节点的值
uint8_t zlend
1字节，标记压缩列表末端
连锁更新
列表插入和删除节点，如果列表中有多个长度介于250到253字节的节点会造成连锁更新
特性
为节约内存而开发的顺序型结构
列表键和哈希键的底层实现
可以包含多个节点，每个节点可以保存一个字节数组或整数值
对象
类型
每次在Redis创建一个键值对时，至少会创建两个对象，一个键对象，一个值对象
字符串对象（REDIS_STRING）
使用整数值实现
小于32字节，使用embstr简单动态字符串实现
大于32字节，简单动态字符串实现
列表对象(REDIS_LIST)
压缩列表实现
列表对象保存的所有字符串长度都小于64字节
列表对象保存的元素数量小于512个
双端链表实现
不满足以上两个条件时使用，条件可在配置中修改
哈希对象(REDIS_HASH)
压缩列表实现
哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
哈希对象保存的键值对数量小于512个
字典实现
不满足以上两个条件时使用，条件可在配置中修改
集合对象(REDIS_SET)
整数集合实现
保存的所有元素都是整数值
元素数量不超过512个
字典实现
不满足以上两个条件时使用，条件可在配置中修改
有序集合对象(REDIS_ZSET)
压缩列表实现
每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的值，第二节点保存元素的分值
元素数量小于128个
所有元素长度都小于64字节
跳跃表和字典实现
跳跃表和字典通过指针共享元素的成员和分值，跳跃表为了实现排序和范围操作，字典实现元素分值的O(1)查询，只用跳跃表或字典来实现性能会有降低
编码
long类型的整数（REDIS_ENCODING_INT）
embstr编码的简单动态字符串（REDIS_ENCODING_EMBSTR）
简单动态字符串（REDIS_ENCODING_RAW）
字典（REDIS_ENCODING_HT）
双端链表（REDIS_ENCODING_LINKEDLIST）
压缩列表（REDIS_ENCODING_ZIPLIST）
整数集合（REDIS_ENCODING_INTSET）
跳跃表和字典（REDIS_ENCODING_SKIPLIST）
类型检查和命令多态
类型检查
在执行命令前会先检查输入的键的值对象是否为执行命令所需的类型
多态命令
会根据对象的编码方式选择正确的命令代码来执行命令
内存回收
Redis构建了一个引用计数技术实现的内存回收机制
对象共享
库中以存在和插入键相同的值
将键的值指针指向一个现有的值对象
将被共享的值对象的引用计数增一
独立功能的实现
发布与订阅
频道的订阅与退订
频道订阅关系都保存在pubsub_channels字典里
订阅
如果频道已经有其他订阅者，在pubsub_channels字典中必然有相应的订阅者链表
如果频道还没有订阅者，在字典里为频道创建一个键，键的值设置为链表第一个元素为客户端
退订
根据被退订频道的名字从订阅者链表中删除客户端信息
如果订阅频道链表为空就删除频道对应的键
模式的订阅与退订
模式订阅关系都保存在pubsub_patterns链表里
订阅
新建一个pubsub_pattern结构将pattern属性设置为被订阅的模式，client属性设置为订阅模式的客户端
将pubsub_pattern结构添加到pubsub_patterns链表的表尾
退订
从链表中删除对应的订阅
发送消息
将消息发送给指定频道的所有订阅者
如果一个或多个pattern与指定的频道向匹配，将消息发送给所有pattern模式的订阅者
事务
事务的实现
事务开始
MULTI命令执行标志事务的开始。将客户端切换到事务状态
命令入队
客户端发送EXEC、DISCARD、WATCH、MULTI命令，服务端会立即执行
客户端发送其他命令，服务器会将命令放入一个事务队列里，然后向客户端返回QUEUED回复
事务命令会存放在事务队列（FIFO）中
事务执行
客户端向服务器发送EXEC命令时服务器会遍历这个客户端的事务队列，执行其中的所有命令并将命令执行结果返回给客户端
WATCH命令
一个乐观锁可以在EXEC执行前监视任意数量的数据库键，检查被监视的键是否至少有一个已经被修改过了，如果是服务器将拒绝执行事务
慢查询日志
用于记录执行时间超过指定时长的命令
0 条评论
下一页
