Redis设计与实现
2022-02-20 16:48:16 18 举报AI智能生成
redis设计与实现读书笔记
作者其他创作
大纲/内容
数据结构与对象
简单动态字符串
sds的定义
数据结构
struct sdshdr {
int len;
int free;
char buf[];
};
int len;
int free;
char buf[];
};
属性
len
保存字符串的长度
free
数组中未使用字符的数量
buf
字节数组保存字符串
sds与c字符串区别
常数复杂度获取字符串的长度
sds记录了字符串长度
杜绝缓冲区溢出
sds记录了字符串长度，使用空间分配策略杜绝了缓冲区溢出
减少修改字符串时候带来的内存重分配
空间预分配
惰性空间释放
二进制安全
sds可以保存图片音频等二进制数据，不是空字符判断字符串是否结束
兼容部分c字符串函数
为了让保存文本数据的sds可以重用一部分string.h库定义的函数
内存分配策略
空间预分配
小于1m
小于1m分配len属性和free属性相同
len*2 +1（额外一字节用于保存空字符）
大于1m
大于1m分配free1m空间
len+1m+1(额外一字节用于保存空字符)
惰性空间释放
缩短时候放入free未使用空间中，方便后续增长操作，不需要时候可以调用删除api释放未使用空间
链表
链表和链表节点实现
链表
结构
链表节点
结构
特点
双端
链表节点带有pre和next指针
无环
表头节点pre指针和表尾节点指针next指向为空
带表头和表尾指针
通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。
带链表长度计数器
len属性对链表结构进行计数
多态
链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值
字典
字典的实现
哈希表
结构
哈希表节点
结构
字典
结构
哈希算法
公式
解决键冲突
概念
链地址法（separate chaining）来解决键冲突
dictEntry节点组成的链表
rehash
扩容
条件
服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
缩容
条件
负载因子小于0.1时，程序自动开始对哈希表执行收缩操作
过程
为字典的ht[1]哈希表分配空间
将保存在ht[0]中的所有键值对rehash到ht[1]上面
当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
负载因子
渐进式rehash
过程
为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。
随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。
优点
所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量
其他细节
渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。
先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找
新添加到字典的键值对一律会被保存到ht[1]里面
跳跃表
跳跃表实现
zskiplist
head
指向跳跃表的表头节点
tail
指向跳跃表的表头节点
level
录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
length
记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。
zskiplistNode
层
跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。
根据幂次定律（越大的数出现的概率越小），随机生成1-32之间的值作为level数组大小，这个大小叫做层的高度
前进指针
每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。
跨度
层的跨度（level[i].span属性）用于记录两个节点之间的距离
后退指针
节点的后退指针（backward属性）用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。
分值和成员
节点的分值（score属性）是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。
节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。
节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。
查找逻辑，自上而下从头节点第一个跨度为1的层开始查找
整数集合
整数集合实现
作用
结构
属性
contents
length
encoding
升级
根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
将新元素添加到底层数组里面
升级好处
提升灵活性
节约内存
降级
集合不支持降级，一旦升级保持原有的类型
压缩链表
压缩列表的构成
zlbytes
记录整个压缩列表占用的内存字节数
再对压缩列表进行内存重分配，计算zlend位置时使用
zltail
记录压缩列表尾节点距离压缩列表的起始地址有多少字节
zllen
记录压缩列表包含的节点数量
entryX
压缩列表包含的各个节点
zlend
特殊值0xFF(十进制255)，用于标记压缩列表的末端
压缩列表节点构成
previous_entry_length
记录压缩列表种前一个节点的长度
encoding
记录了节点content属性所保存的数据的类型以及长度
content
负责保存节点的值
连锁更新
添加节点或者删除节点可能会造成连锁更新
恰好很多连续长度介于250-253字节之间的节点
对象
对象类型和编码
类型
编码以及底层实现
字符串对象
编码转换
字符串命令实现
列表对象
ziplist
linklist
编码转换
列表对象保存的所有字符串的长度都小于64字节
列表对象保存的元素数量小于512个
同时满足以上条件使用ziplist不满足使用linklist
哈希对象
ziplist
hashtable
编码转换
哈希对象保存的所有键值字符串长度都小于64字节
哈希对象保存的键值对数量小于512个
同时满足使用ziplist，不能满足使用hashtable
集合对象
intset
hashtable
编码转换
集合对象保存的所有元素都是整数值
集合对象保存的元素不超过512
同时满足上面条件使用intset，不满足使用hashtable
有序集合对象
ziplist
skiplist
编码转换
有序集合保存元素数量小于128个
有序集合保存的所有元素成员的长度都小于64字节
同时满足条件使用ziplist，不满足使用skiplist
类型检查与命令多态
类型检查的实现
多态命令的实现
内存回收
引用计数
对象生命周期
创建对象
操作对象
释放对象
对象共享
为什么redis不共享包含字符串对象
操作复杂度大
受到cpu时间的限制
目前只包含整数值的字符串对象进行共享
对象的空转时长
作用
单机数据库的实现
数据库
服务器中的数据库
切换数据库
数据库键空间
添加新键
删除键
更新键
对键取值
其他键空间操作
读写键空间时候的维护操作
设置键生存时间或过期时间
过期键删除策略
redis的过期键删除策略
aof,rdb和复制功能对过期键的处理
数据库通知
rdb持久化
rdb文件的创建和载入
自动间隔性保存
rdb文件结构
分析rdb文件
aof持久化
aof持久化实现
aof文件的载入和数据还原
aof重写
事件
文件事件
时间事件
事件的调度与执行
客户端
客户端属性
客户端的创建和关闭
服务器
命令请求的执行过程
serverCron函数
初始化服务器
多机数据库的实现
复制
旧版复制功能实现
旧版复制功能缺陷
新版复制功能的实现
新版本重同步的实现
psync命令的实现
复制的实现
心跳检测
sentinel
启动并初始化
获取主服务信息
获取从服务信息
向主服务器和从服务器发送信息
接受来自主服务器和从服务器的频道信息
检查主观下线状态
检查客观下线状态
选举领头sentinel
故障转移
集群
节点
槽指派
在集群中执行命令
重新分片
ask错误
消息
独立功能的实现
发布订阅
频道的订阅与退订
模式的订阅与退订
发送消息
查看订阅信息
事务
事务的实现
watch命令的实现
事务的acid性质
lua
创建并且修改lua环境
lua环境协作组件
eval命令的实现
evalsha命令的实现
脚本管理命令的实现
脚本复制
排序
sort<key>命令的实现
alpha选项的实现
asc选项和desc选项的实现
by选项的实现
带有alpha选项的by选项的实现
limit选项的实现
store选线的实现
多个选项的执行顺序
二进制位数组
位数组的表示
getbit命令的实现
setbit命令的实现
bitcount命令的实现
bittop命令的实现
慢查询日志
慢记录的保存
慢日志的阅览和删除
添加新日志
监视器
成为监视器
向监视器发送命令信息
收藏
0 条评论
下一页
