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