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