redis基本实现原理
2019-07-29 10:27:39 0 举报AI智能生成
Redis基本原理
作者其他创作
大纲/内容
内部基本数据结构
简单动态字符串 SDS
结构体,保存字符串长度 空余空间跟字符数组
惰性空间释放
提供了api可以处理内存浪费
api安全 比c原始的字符串类型安全,如内存管理与效率
链表
保护list与listnode结构体
双向链表
字典
包含三个结构体
字典结构体
记录字典类型,方便指向对应类型的处理函数
两个哈希表,一个存数据,另一个作为rehash的时候使用
哈希表
记录哈希表状态等 如大小 已使用大小 掩码
哈希实体
记录key跟value
链表结构,当哈希冲突时使用
哈希算法
Redis基于MurmurHsah 2 算法
MurmurHsah已更新到3版本
冲突时使用单向链表
reshash
扩容跟缩小容量时使用
使用结构体中第二个哈希表,分配空间并进行rehash
渐进式rehash
同时使用两个哈希表
如果发现reshash大于-1,则证明rehash进行中,对字典的curd都会顺带移动0表到1表,idx++
使用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
前节点长度
如果前节点字节数小于254,则一个字节记录前节点长度,否则就是5个字节记录,第一个字节固定0xFE
encoding
content保存字节数组
10 五字节
00一字节
01两字节
content保存常规类型
11开头
content
标记节点末端位置
遍历
从尾到头
通过结构体的zltail找到尾,再从尾遍历
连锁更新
记录前节点的长度变动导致
命令实现
集合命令实现
列表命令实现
哈希命令实现
集合命令实现
有序集合命令实现
对象类型
RedisObject
类型
字符串
列表
哈希
集合
有序集合
编码
与类型组合
字符串
使用整型实现字符串对象
例如 set num 10086
使用embstr编码的sds对象
只使用一次内存分配
直接使用sds
两次内存分配 连续空间
longDouble使用字符串保存
整数数太大不能用long表示也被转字符串
整数数太大不能用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)
其实不一定 有更好的算法 不一定是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
当发生惰性删除和定期删除时,才发送一条append del命令给aof文件命令其删除
重写
过期键与rdb一样不会写入aof文件
使用记录客户端命令的方式记录
根据配置写文件
always
写入buf同时 执行强制写入文件
everysec
每秒执行,使用子进程同步文件
写入buf同时 执行强制写入文件
no
让操作系统自己同步
即write函数 操作系统自己控制 当然 有时效安全问题
即write函数 操作系统自己控制 当然 有时效安全问题
写入buf
载入
伪客户端 执行命令
重写 即bgrewriteaof 命令实现
为了解决文件膨胀问题
分析文件 读取数据库值 进行生成最简单的命令保存
使用子进程
使用重写缓冲区 即如果有子进程存在 进行aof写入buf的时候也会写入这个缓冲区
重写完通知父进程 阻塞进行文件替换
主从复制
主服务器
发现键过期则删除
并发del给从服务器
从服务器
发现键过期都不管 直接返回
数据库通知
配置文件可以设置允许通知类型
事件
文件事件
io多路复用 reactor模型
write read accept
处理器
连接应答
命令请求
命令回复
时间事件
无序链表保存
遍历 查看时间到达的就执行
应用
serverCron函数
统计服务器状态
清理过期键
关闭清理过期客户端
持久化
主服务器的话 同步
集群的话 同步与连接测试
收藏
收藏
0 条评论
下一页
