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