redis基本实现原理知识框架总结分享
2022-10-19 17:07:41 0 举报
AI智能生成
redis基本实现原理知识框架总结分享
作者其他创作
大纲/内容
提供了api可以处理内存浪费
惰性空间释放
简单动态字符串 SDS
双向链表
保护list与listnode结构体
链表
字典结构体
记录哈希表状态等 如大小 已使用大小 掩码
哈希表
记录key跟value
哈希实体
包含三个结构体
MurmurHsah已更新到3版本
Redis基于MurmurHsah 2 算法
冲突时使用单向链表
哈希算法
扩容跟缩小容量时使用
同时使用两个哈希表
使用rehashindex记录 当值为-1时 表明无进行reshash
进行rehash时进行查找 先在0表如果没有则找1表
渐进式rehash
服务器无执行 bgsave 或者 bgrewriteaof 且负载因子大于等于1
服务器执行 bgsave 或者 bgrewriteaof 且负载因子大于等于5
负载因子小于0.1则缩容
触发条件
已用数量 / 哈希表大小
负载因子算法
reshash
字典
内部使用在有序集合以及集群节点
使用list 跟 listnode组合
层高为1-32之间的随机数
对象唯一 分值可不唯一
跳跃表
集合键的底层实现之一
encoding记录整形长度 16 32 64
从小到大排序
content数组内容 固定int8数组
length标识已记录长度
数据结构
当新入的元素比集合元素大
改变encoding
升级复杂度 O(N)
升级
不支持降级
整数集合
列表键与哈希键底层实现之一
总字节数
尾结点偏移
节点数量
前节点长度
10 五字节
00一字节
01两字节
content保存字节数组
11开头
content保存常规类型
encoding
content
节点x
标记节点末端位置
结构
从尾到头
遍历
记录前节点的长度变动导致
连锁更新
压缩列表
内部基本数据结构
分支主题
集合命令实现
列表命令实现
哈希命令实现
有序集合命令实现
命令实现
字符串
列表
哈希
集合
有序集合
类型
例如 set num 10086
使用整型实现字符串对象
只使用一次内存分配
使用embstr编码的sds对象
两次内存分配 连续空间
直接使用sds
longDouble使用字符串保存<br>整数数太大不能用long表示也被转字符串
embstr编码字符串无法修改 一旦修改则转raw 即sds实现
列表对象总长度小于64字节 &&
&& 列表保存元素小于512个
可在配置文件设置
使用压缩列表
双端列表
压入列表尾部
键-值 两两排
存储结构
键值对象总长度小于64字节 &&
&& 键值保存元素小于512个
只用了键 值为null 与java的hashset实现原理差不多
O(1)查找
范围取值O(N*logN)
字典 dist
范围取值O(N)
查找O(logN)
跳表 zsl
zset
与类型组合
编码
值指针
内存回收使用
引用计数
0-9999字符串对象
整型判断复杂度为O1
字符串判重为O(N)<br>其实不一定 有更好的算法 不一定是O(N)
为什么字符串不共享
对象共享
空转时长:记录最后被访问时间 LRU使用
RedisObject
对象类型
redisDb上维护 * dist
键空间命中统计
lru时间更新
监听过期
标记dirty
读写时维护
使用* expires dist来存储过期时间
expire key ttl
pexpire key ttl
expireat key timestamp
根本实现
pexpireat key timestamp
命令
寻找键在expire dist中是否存在 存在则获取里面的过期时间与当前时间相比
过期判断
定时
读写数据库之前执行
惰性
使用current_db记录当前检查的库
定期
删除策略
过期设置
键空间
主服务器 键过期删除
从服务器与主服务器同步时就被删除所有键了
从服务器 不删除
载入时阻塞
载入时检查键过期<br>
主进程阻塞直到文件写完
save
子进程
进行中 执行sava bgsave命令不允许
bgrewriteaof 会被等待到bgsave执行完
bgsava
save bgsave命令
使用dirty记录数据库变动次数
使用lastsave记录最后一次更新时间
900 1 表示 900s内 对数据库进行了一次修改
满足配置可自动执行保存rdb文件
服务器主进程 每100ms执行一次检查保存规则
定时保存
RDB
过期键与rdb一样不会写入aof文件
重写
写入buf同时 执行强制写入文件
always
everysec
让操作系统自己同步<br>即write函数 操作系统自己控制 当然 有时效安全问题
写入buf
no
根据配置写文件
使用记录客户端命令的方式记录
伪客户端 执行命令
载入
分析文件 读取数据库值 进行生成最简单的命令保存
为了解决文件膨胀问题
使用重写缓冲区 即如果有子进程存在 进行aof写入buf的时候也会写入这个缓冲区
重写完通知父进程 阻塞进行文件替换
使用子进程
重写 即bgrewriteaof 命令实现
AOF
发现键过期则删除
并发del给从服务器
主服务器
发现键过期都不管 直接返回
从服务器
主从复制
配置文件可以设置允许通知类型
数据库通知
数据库
io多路复用 reactor模型
write read accept
连接应答
命令请求
命令回复
处理器
文件事件
遍历 查看时间到达的就执行
无序链表保存
统计服务器状态
清理过期键
关闭清理过期客户端
持久化
主服务器的话 同步
集群的话 同步与连接测试
serverCron函数
应用
时间事件
事件
redis基本实现原理知识框架总结分享
0 条评论
回复 删除
下一页