

首页  思维导图  详情



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使用字符串保存<br>整数数太大不能用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)<br>其实不一定有更好的算法不一定是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

载入时检查键过期<br>

主服务器键过期删除

从服务器不删除

从服务器与主服务器同步时就被删除所有键了

载入时阻塞

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同时执行强制写入文件

让操作系统自己同步<br>即write函数  操作系统自己控制当然有时效安全问题

写入buf

载入

伪客户端执行命令

重写即bgrewriteaof 命令实现

为了解决文件膨胀问题

分析文件读取数据库值进行生成最简单的命令保存

使用子进程

使用重写缓冲区即如果有子进程存在进行aof写入buf的时候也会写入这个缓冲区

重写完通知父进程阻塞进行文件替换

主从复制

主服务器

发现键过期则删除

并发del给从服务器

从服务器

发现键过期都不管直接返回

数据库通知

配置文件可以设置允许通知类型

事件

文件事件

io多路复用 reactor模型

write read accept

处理器

连接应答

命令请求

命令回复

时间事件

无序链表保存

遍历查看时间到达的就执行

应用

serverCron函数

统计服务器状态

清理过期键

关闭清理过期客户端

持久化

主服务器的话同步

集群的话同步与连接测试

 Collect

Get Started

Redis持久化机制原理图、流程图

 Collect

Get Started

需求实现基本流程

 Collect

Get Started

基于redis实现验证码验证技术

 Collect

Get Started

redis基本实现原理知识框架总结分享





0 条评论

下一页