

首页  思维导图  详情



Redis设计与实现

2022-02-20 16:48:16   18  举报





AI智能生成

redis设计与实现读书笔记

redis

redis设计图

redis集群

系统设计

模版推荐

作者其他创作

大纲/内容

数据结构与对象

简单动态字符串

sds的定义

数据结构

struct sdshdr {     int len;     int free;     char buf[]; };

属性

len

保存字符串的长度

free

数组中未使用字符的数量

buf

字节数组保存字符串

sds与c字符串区别

常数复杂度获取字符串的长度

sds记录了字符串长度

杜绝缓冲区溢出

sds记录了字符串长度，使用空间分配策略杜绝了缓冲区溢出

减少修改字符串时候带来的内存重分配

空间预分配

惰性空间释放

二进制安全

sds可以保存图片音频等二进制数据，不是空字符判断字符串是否结束

兼容部分c字符串函数

为了让保存文本数据的sds可以重用一部分string.h库定义的函数

内存分配策略

空间预分配

小于1m

小于1m分配len属性和free属性相同

len*2 +1（额外一字节用于保存空字符）

大于1m

大于1m分配free1m空间

len+1m+1(额外一字节用于保存空字符)

惰性空间释放

缩短时候放入free未使用空间中，方便后续增长操作，不需要时候可以调用删除api释放未使用空间

链表

链表和链表节点实现

链表

结构

链表节点

结构

特点

双端

链表节点带有pre和next指针

无环

表头节点pre指针和表尾节点指针next指向为空

带表头和表尾指针

通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。

带链表长度计数器

len属性对链表结构进行计数

多态

链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值

字典

字典的实现

哈希表

结构

哈希表节点

结构

字典

结构

哈希算法

公式

解决键冲突

概念

链地址法（separate chaining）来解决键冲突

dictEntry节点组成的链表

rehash

扩容

条件

服务器目前没有在执行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]里面

跳跃表

跳跃表实现

zskiplist

head

指向跳跃表的表头节点

tail

指向跳跃表的表头节点

level

录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。

length

记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

zskiplistNode

层

跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。

根据幂次定律（越大的数出现的概率越小），随机生成1-32之间的值作为level数组大小，这个大小叫做层的高度

前进指针

每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。

跨度

层的跨度（level[i].span属性）用于记录两个节点之间的距离

后退指针

节点的后退指针（backward属性）用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

分值和成员

节点的分值（score属性）是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。 节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。

查找逻辑，自上而下从头节点第一个跨度为1的层开始查找

整数集合

整数集合实现

作用

结构

属性

contents

length

encoding

升级

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。

将新元素添加到底层数组里面

升级好处

提升灵活性

节约内存

降级

集合不支持降级，一旦升级保持原有的类型

压缩链表

压缩列表的构成

zlbytes

记录整个压缩列表占用的内存字节数

再对压缩列表进行内存重分配，计算zlend位置时使用

zltail

记录压缩列表尾节点距离压缩列表的起始地址有多少字节

zllen

记录压缩列表包含的节点数量

entryX

压缩列表包含的各个节点

zlend

特殊值0xFF(十进制255)，用于标记压缩列表的末端

压缩列表节点构成

previous_entry_length

记录压缩列表种前一个节点的长度

encoding

记录了节点content属性所保存的数据的类型以及长度

content

负责保存节点的值

连锁更新

添加节点或者删除节点可能会造成连锁更新

恰好很多连续长度介于250-253字节之间的节点

对象

对象类型和编码

类型

编码以及底层实现

字符串对象

编码转换

字符串命令实现

列表对象

ziplist

linklist

编码转换

列表对象保存的所有字符串的长度都小于64字节

列表对象保存的元素数量小于512个

同时满足以上条件使用ziplist不满足使用linklist

哈希对象

ziplist

hashtable

编码转换

哈希对象保存的所有键值字符串长度都小于64字节

哈希对象保存的键值对数量小于512个

同时满足使用ziplist，不能满足使用hashtable

集合对象

intset

hashtable

编码转换

集合对象保存的所有元素都是整数值

集合对象保存的元素不超过512

同时满足上面条件使用intset，不满足使用hashtable

有序集合对象

ziplist

skiplist

编码转换

有序集合保存元素数量小于128个

有序集合保存的所有元素成员的长度都小于64字节

同时满足条件使用ziplist，不满足使用skiplist

类型检查与命令多态

类型检查的实现

多态命令的实现

内存回收

引用计数

对象生命周期

创建对象

操作对象

释放对象

对象共享

为什么redis不共享包含字符串对象

操作复杂度大

受到cpu时间的限制

目前只包含整数值的字符串对象进行共享

对象的空转时长

作用

单机数据库的实现

数据库

服务器中的数据库

切换数据库

数据库键空间

添加新键

删除键

更新键

对键取值

其他键空间操作

读写键空间时候的维护操作

设置键生存时间或过期时间

过期键删除策略

redis的过期键删除策略

aof,rdb和复制功能对过期键的处理

数据库通知

rdb持久化

rdb文件的创建和载入

自动间隔性保存

rdb文件结构

分析rdb文件

aof持久化

aof持久化实现

aof文件的载入和数据还原

aof重写

事件

文件事件

时间事件

事件的调度与执行

客户端

客户端属性

客户端的创建和关闭

服务器

命令请求的执行过程

serverCron函数

初始化服务器

多机数据库的实现

复制

旧版复制功能实现

旧版复制功能缺陷

新版复制功能的实现

新版本重同步的实现

psync命令的实现

复制的实现

心跳检测

sentinel

启动并初始化

获取主服务信息

获取从服务信息

向主服务器和从服务器发送信息

接受来自主服务器和从服务器的频道信息

检查主观下线状态

检查客观下线状态

选举领头sentinel

故障转移

集群

节点

槽指派

在集群中执行命令

重新分片

ask错误

消息

独立功能的实现

发布订阅

频道的订阅与退订

模式的订阅与退订

发送消息

查看订阅信息

事务

事务的实现

watch命令的实现

事务的acid性质

lua

创建并且修改lua环境

lua环境协作组件

eval命令的实现

evalsha命令的实现

脚本管理命令的实现

脚本复制

排序

sort<key>命令的实现

alpha选项的实现

asc选项和desc选项的实现

by选项的实现

带有alpha选项的by选项的实现

limit选项的实现

store选线的实现

多个选项的执行顺序

二进制位数组

位数组的表示

getbit命令的实现

setbit命令的实现

bitcount命令的实现

bittop命令的实现

慢查询日志

慢记录的保存

慢日志的阅览和删除

添加新日志

监视器

成为监视器

向监视器发送命令信息

 Collect

Get Started

redis设计与实现

 Collect

Get Started

Redis设计与实现

 Collect

Get Started

Redis设计与实现

 Collect

Get Started

Redis设计与实现





0 条评论

下一页