首页  思维导图  详情

Redis 设计与实现

2020-05-22 14:58:08   0  举报





AI智能生成

Redis原理

Redis设计与实现

软件开发

学习笔记

作者其他创作

大纲/内容

数据结构与对象

数据结构

简单动态字符串（SDS）

结构：

sdshdr {
int len：记录buf数组中已使用字节数量
int free：记录buf数组中未使用字节数量
char buf[]：字节数组，用于保存字符串（用来保存一系列的二进制数据）
}

对比C字符串的优点：

1、杜绝缓冲区溢出：会先检查空间十分满足，如果不满足的话会扩展

2、减少修改字符串带来的内存重分配次数：

空间预分配：len小于1MB，那么会分配和len属性同样大小的未使用空间，free和len相同；
如果len大于等于1MB，那么会分配1MB的未使用空间

惰性空间释放：并不会立即内存重分配来回收缩短多出来的字节，而是使用free记录下来，
再下次增长操作会用上，避免了频繁的内存重分配，在有需要的时候可以调用api真正的释放未使用空间

二进制安全：会处理二进制的方式来处理SDS放在buf数字里

作用

保存字符串，作为缓存区

双端链表(list)

结构：

链表的结构：

list {
listNode *head：头节点
listNode *tail：尾节点
long len：链表包含的节点数量
}

链表节点的结构：

listNode {
listNode *prev：前置节点
listNode *next：后置节点
void *value：节点的值
}

作用：

发布与订阅、慢查询、监视器；保存多个客户端的状态信息，客户端输出的缓冲区

字典(map)

结构：

字典结构

dict {
dictType *type：类型特定函数
void *privdata：私有数据
dictht ht[2]：哈希表，一个rehash用
int trehashidx：rehash索引，没在rehash为-1
}

哈希表结构

dictht {
dictEntry **table：哈希表数组
long size：哈希表大小
long sizemask：哈希表大小掩码，用于计算索引值，总是等于size-1
long used：该哈希表已有的节点数量
}

哈希表节点结构

dictEntry {
void *key：键
union {
void *val
uint64_t u64
int64_t s64
} 值
dictEntry *next：下一个哈希节点，形成链表
}

哈希算法

hash = dict.type.hashFunction(key)
index = hash & dict.ht[x].sizemask：x为0或1

MurmurHash2 是一种非加密型哈希函数，适用于一般的哈希检索操作。与其它的哈希函数相比，
对于规律性较强的key，MurmurHash的随机分布特征表现更良好

解决hash冲突

链地址法（separate chaining）,用next来形成一个链表，
因为没有表尾指针，为了速度，新节点放在链表的表头（头插法）

重新散列（rehash）

负载因子的计算：load_factor = ht[0].used / ht[0].size

扩展

扩展条件

服务器没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希的负载因子大于等于1

服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于5

画外音：在执行上俩个命令时，需要创建当前的子进程，而大多数操作系统采用写时复制（copy-on-write）来优化子进程的效率，
所以在子进程存在的期间，服务器会提高执行扩展操作的负载因子，尽可能避免在子进程存在期间进行哈希表的扩展操作

ht[1]的大小为第一个大于等于ht[0].used*2的2的n次幂，
比如ht[0].used=6,则ht[1].size=16>=6*2

收缩

收缩条件：当负载因子小于0.1时，会自动对哈希表收缩

ht[1]的大小为第一个大于等于ht[0].used的2的n次幂
比如ht[0].used=6,则ht[1].size=8>=6

过程

当ht[0]中的所有键值对都迁移到了ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上

当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变空表），释放ht[0]，将ht[1]设置为ht[0]。并在ht[1]新创建一个空白的哈希表，为下次rehash做准备

渐进式rehash

扩展和收缩需要将ht[0]里面的所有的键值对rehash到ht[1]里面，
但是这个rehash动作并不是一次性、集中性的完成，而是分多次、渐进式的完成的

如果要一次性的将这些键值对全部rehash到ht[1]中，庞大的计算量可能会导致服务器在一段时间内停止服务，所以分多次、渐进式

4个步骤

1、为ht[1]分配空间，让字典同时持有ht[0]和ht[1]俩个哈希表

2、在字典中维持一个索引计数量rehashidx,并把它从-1设置为0，表示rehash工作正式开始

3、在rehash进行期间，每次对字典执行的任何（读写）操作，程序除了执行指定的操作外，
还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当完成后，再将rehashidx属性的值增一（每次操作的记录，类似循环i++）

4、随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对rehash到ht[1]，这时将rehashidx设置为-1，表示完整的rehash操作已完成了

优点：采用分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个读写操作上，从而避免了集中式的rehash而带来的庞大计算量

在渐进式rehash执行期间，字典会同时使用ht[0]和ht[1]俩个哈希表，删、改、查会在俩个哈希表上进行，
会先在ht[0]查找，没找到会继续到ht[1]里面查找，而新添加到字典的键值对一律会被保存到ht[1]里面，
而ht[0]则不在进行任何添加操作，这样就保证ht[0]包含的键值对只减不增，随着rehash操作而最终变成空表

跳跃表(skiplist)

跳跃表结构

skiplist {
zskiplistNode *header：表头节点
zskiplistNode *tail：表尾节点
long length：节点的数量（表头节点不算在内）
int level：表中层数最大的节点层数（表头节点不算在内）
}

跳跃表节点

结构

zskiplistNod {
zskiplistNode *backwawrd：后退指针
double score：分值
robj *obj：成员对象
zskiplistLevel {
zskiplistNode *forward：前进指针
int span：跨度
} leve[]：层
}

层：level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，层的数量越多，访问其他节点的速度就越快。每次创建新的跳跃表节点，就会随机生成一个1-32之间的值，就是层的高度

前进指针：level[i].foward，用于从表头向表尾方向访问节点

跨度：level[i].span，用于记录俩个节点之间的距离，计算排位rank

后退指针：backward，用于从表尾向表头方向访问节点

分值：score，是一个double类型的浮点数，跳跃表的所有节点都按分值从小到大排序

成员：obj，是一个指针，他指向一个字符串对象，而字符串对象保存着一个sds值

画外音：在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值可以是相同的，
分值相同的节点将按照成员对象在字典序的大小来从小到大排序

整数集合(intset)

结构

intset {
uint32_t encoding：编码方式，16，32，64
uint32_t length：集合包含的元素数量
int8_t contents[]：保存元素的数组
是整数集合的底层实现，各个项在数组中按值的大小从小到大有序的排列
并且不包含任何的重复项
}

升级

当将一个新元素添加到整数集合中，并且新元素的类型比整数集合现所有的元素的类型都要长时，整数集合需要先进行升级，才能将新元素添加到整数集合中

3个步骤

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

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

3、将新元素添加到新底层数组中

好处：提升整数集合的灵活性，尽可能的节约内存

降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态

压缩列表(ziplist)

是一系列特殊编码的连续内存块的顺序型数据结构，为了节约内存而开发

组成部分

zlbyte uint32_t 4字节：记录整个压缩列表占用的内存字节数；内存重分配和计算zlend的位置用到

zltail uint32_t 4字节：记录压缩列表表尾点的距离压缩列表的起始地址有多少字节
通过这个偏移量，无线遍历整个压缩列表就可以确定表尾节点的地址

zllen uint_16_t 2字节：记录了压缩列表包含的节点数量

entryX 列表节点不定压缩列表包含的各个节点，节点长度又节点保存的内容决定

节点构成

previous_entry_length：以字节为单位，记录压缩列表中前一个节点的长度。可以是1字节或者5字节，如果前一个节点的长度小于254字节那他就是1字节，如果前一个节点的长度是大于等于254字节那他就是5字节，第一个字节会被设置成0xFE,而后4个字节则用于保存前一个节点的长度

encoding：记录了content属性所保存数据的类型与长度

content：负责保存的节点的值，可以是一个字节数组或者整数

zlend uint8_t 1字节：特殊值0xFF，用于标记压缩列表的末端

连锁更新

添加新节点、删除新节点都可能会引发连锁更新，在连续多个处于临界长度（254字节）才会发生，所以并不多见

对象（RedisObject）

结构

redisObject {
unsigned type：类型（type key）
unsigned encoding：编码 (object encoding key)
void *ptr：指向底层实现数据结构的指针
int reference：引用计数
unsigned lru：最后一次被访问的时间
}

查看键对应的值对象类型命令：type key

字符串对象（string）

编码

int：使用整数值

embstr：简单动态字符串

字符串长度小于等于39

通过调用一次内存分配来分配一块连续的空间，依次包含redisObejct和sdshdr俩个结构，释放也只需要调用一次

只读的，有修改会变成raw

raw：简单动态字符串

长度大于39

会调用俩次内存分配来分别分配redisObject和empstr结构，需要调用俩次内存释放

列表对象（list）

编码

ziplist：压缩列表

linkedlist：双端列表

同时满足所有字符串元素的长度都小于64字节，元素数量小于512个则使用ziplist编码，否则使用linkedlist编码

list-max-ziplist-value和 list-max-ziplist-entries 可修改上面的值

哈希对象（hash）

编码

ziplist：压缩列表

ht：字典

同时满足所有的键值对的字符串长度都小于64字节，键值对数量小于512个则使用ziplist，否则使用hashtable

hash-max-ziplist-value 和 hash-max-ziplist-entries 可修改上面的值

集合对象（set）

编码

intset：整数集合

ht：字典

同时满足所有的元素都是整数值，并且元素数量不超过512个，则使用intset，否则使用ht

set-max-inset-entries 可修改

有序集合对象（zset）

编码

ziplist：压缩列表

skiplist：跳跃表和字典

无论单独使用跳跃表还是字典对比同时使用俩种都有性能降低

zset {
dict：字典
skiplist：跳跃表
}

同时满足元素数量小于128个，并且所有元素成员的长度都小于64字节，则使用ziplist，否则使用skiplist

zset-max-ziplist-entries 和 zset-max-ziplist-value 可修改

编码类型与对应的数据结构

查看键对应的值对象的编码：object encoing key

Redis_Encoding_Int：long类型的整数

Redis_Encoding_Embstr：embstr编码的简单动态字符串

Redis_Encoding_raw：简单动态字符串

Redis_Encoding_Ht：字典

Redis_Encoding_Linkedlist：双端链表

Redis_Encoding_Ziplist：压缩列表

Redis_Encoding_Intset：整数集合

Redis_Encoding_Skiplist：跳跃表和字典

特性

类型检查

有的命令只能对特定类型键执行，否则返回一个类型错误

根据 redisObejct.type来实现

命令多态

基于类型的多态：del、expire

基于编码的多态：llen

内存回收

引用计数（reference counting）

创建新对象会初始化为1

被新程序使用会被增一

当对象不再被一个程序使用，计数值会减一

值变为0，对象占用的内存会释放

查看值命令：object refcount key

对象共享

将键的值指针指向一个现有的值对象，将被共享的值对象的引用计数增一

对节约内存有帮助

Redis在初始化服务器的时候，会创建一万个字符串对象，从0到9999

只有在共享对象和目标对象完全相同的情况下，程序才会将共享对象作为键的值对象

对象的空转时长

查看键的空转时长：object idletime key

跟内存回收有联系

单机数据库的实现

数据库

结构

服务器结构

redisServer {
redisDb *dbs：一个数组，保存着服务器所有的数据库
int dbnum：服务器数据库数量，默认是16
saveparam *saveparams：记录保存条件的数组
long long dirty：修改计数器
time_t lastsave：上次执行保存的时间
}

客户端结构

redisClient {
redisDb *db：记录客户端当前正在使用的数据库
}

select num 切换目标数据库

数据库结构

redisDb {
dict *dict：字典，数据库键空间，保存着数据库中所有的键值对
键空间的键也就是数据库的键，每个键都是一个字符串对象；
键空间的值也就是数据库的值，每个值可以是任意一种RedisObject对象
dict *expires：过期字典，保存着键的过期时间，毫秒精度的unix时间戳
}

键的生存时间和过期时间

设置过期时间

expire <key> <ttl> 命令用于将键key的生存时间设置为ttl秒

pexire <key> <ttl> 命令用于将键key的生存时间设置为ttl毫秒

expireat <key> <timestamp> 命令用于将键key的生存时间设置为timestamp所指定的秒数时间戳

pexpireat <key> <timestamp> 命令用于将键key的生存时间设置为timestamp所指定的毫秒数时间戳

画外音：无论执行的是以上4个命令的哪一个，经过转换后，最终的效果都和执行pexpireat命令一样

保存过期时间：在dict *expires 结构中存储

过期键的删除策略

定时删除

在设置键的过期时间同时创建一个定时器（time），让定时器在键的过期时间来临，立即执行键的删除操作

对内存的友好的，很快的删除释放内存；但是对cpu是不友好的，在定时器删除键会对服务器的响应时间和吞吐量造成影响

惰性删除

放任键过期不管，但是每次从键空间中获取键时，都检查获取的键是否过期，如果过期则删除该键，否则返回

对Cpu时间是友好的，只会在读取的时候会有额外删除操作；但是对内存是不友好的，如果一直没有读取到，就会一直存储在内存中，除非是用户手动去scan扫描读取、触发删除，可以看成一种内存泄露

定期删除

每个一段时间程序就对数据库进行一次检查，删除里面的过期键，至于删除多少和检查多少，由算法决定

对内存和cpu相对来说都是友好的，每隔一段时间来执行删除过期键的操作来减少内存浪费，并通过限制删除操作的执行时长和频率来减少删除操作对Cpu的影响

Redis的使用

惰性删除和定期删除俩种策略，通过俩种策略来合理使用cpu和避免浪费内存去的平衡

惰性删除策略的实现：expireIfNeeded函数实现，过期则删除，否则正常处理

定期删除策略实现：activeExpireCycle 函数实现，他在规定的时间内，遍历服务器的所有数据库，从数据库的expires字典中随机检查一部分键的过期时间，并删除其中的过期键，当到了时间会记录当前遍历的数据库current_db，下次就直接从这个db开始，所有遍历一遍current_db会被置零

RDB、AOF、和复制功能对过期键的处理

RDB：已过期的键不会被包含到新创建的RDB文件中，从服务器载入不关系是否过期都会载入数据库中

AOF：已过期的键不会被保存到重写后的AOF文件中，当键别策略删除，程序会想AOF文件追加一个del命令

复制：在复制模式下，从服务器的过期键删除动作都由主服务器控制，在主服务器删除一个键后，会显式的向所有从服务器发送一个del命令通知从服务器删除该键。
从服务器在读到已过期未删除的键，不会主动删除该键，而是像处理未过期的键一样来处理（也就是说从服务器上可能读到已过期未删除的键，是一个bug，在3.2版本中修复了），这种统一、中心化的过期键删除策略可以保证主持服务器的数据一致性

RDB持久化

SAVE：会阻塞Reids服务器进程，直到RDB文件创建完毕，这个期间不能处理任何命令请求

BGSAVE：会派生一个子进程，子进程负责创建RDB文件，父进程继续处理命令请求

服务器启动载入会先判断是否开启AOF持久化，如果开启则载入AOF文件，否则载入RDB文件（因为AOF文件的更新频率通常比RDB文件要高）

自动间隔性保存

条件结构

saveparam {
int seconds：秒数
int changes：修改数
}

通过检查条件redisServer.saveparams、修改计数器dirty、上次执行save或bgsave命令的时间lastsave来判断是否需要自动执行bgsave命令来保存

AOF 持久化

多机数据库的实现

独立功能的实现