Redis设计与实现-阅读笔记（第一部分）

type

Post

status

Published

date

Jul 2, 2021

slug

redis-read1-record

summary

Redis设计与实现-阅读笔记（第一部分）

Redis的编码类型

1.简单动态字符串（sds)

简单动态字符串(sds)包含三个部分

1)free:未使用的空间

2）len:标识存储字符串的长度

3）buff:存储的字符串值

Redis由C语言编写，为了沿用部分C语言的字符串库，redis也沿用的c的字符数组一样的结束标识符”\0”\

SDS与C字符串的区别

1）sds保存了字符串的长度，获取字符串长度为O(1)

2）sds支持自动扩容不用担心缓存区溢出。扩容策略，长度小于1mb，则free和len一样大。超过1mb，free只留1mb。此外惰性空间释放，加入存放的字符串更改后变小了，redis不会立马回收，而是直接修改free的大小

3）sds可以存储任何类型

阻碍、努力、结果

2.链表

一个普通的双端无环链表，只不过外部缓存了链表的节点数量，在获取len的时候可以达到O(1)

3.字典

底层为哈希表，与Java中的Map差不多

字典中有个sizemarsk属性，是记录哈希表大小掩码，存储计算的索引值，它总是等于哈希表的size-1。这个属性目的就是减少重复的size-1计算，且直接用sizemarsk进行位或运算。当然也可以用取余来计算，但redis为了性能选择了前者

另外字典生成的时候就会生成两个哈希表，分别是ht[0]和ht[1]

ht[1]在进行rehash时才会用到，而ht[1]的大小需要取决于执行的操作

1）扩展：ht[1]的大小为第一个大于等于ht[0].used*2的2n(2的n次方幂）假如ht[0].used=15,那么15*2=30,而大于30的2^n次方为32。

为什么是2的n次方幂？redis使用的hash算法为MurmurHash2，为了保证均匀性和更快的位或运算而定。

2）当发生rehash时，如下图used=4，按照上面的扩容来算4*2=8，而2^3次方正好是8，故而扩容量为8。

整个rehash过程并不是一次操作全部完成的，而是渐进式的，第一步则是将rehashidx设置为0，然后对ht[0]中的哈希表数组的[0]下标进行迁移到ht[1]中重新hash存放，接着再将rehashidx设置为1，直到完成并设置回-1，rehash过程中如果遇到新增，则会直接将新数据存放到ht[1]中。

完成上述步骤便把ht[1]设置为ht[0],然后重新分配一个新的ht[1]的哈希表

3）哈希表的扩展与收缩条件

哈希表的负载因子公式为

当服务器没有执行BGSAVE和BGREWRITEAOF命令，且负载因子大于等于1的时候触发rehash

当服务器正在执行BGSAVE和BGREWRITEAOF命令，且负载印在大于等于5的时候触发rehash

为啥BGSAVE和BGREWRITEAOF命令会影响rehash的负载因子呢？

多数操作系统采用的都是Copy-on-write写时复制来优化子进程的效率

写时复制原理：fork子进程时不会给子进程创建物理空间，一旦父进程或子进程的数据段发生变化，系统给子进程分配物理空间。rehash会导致父进程的数据段发生写操作。所以在bgsave, bgrewrite 时提高rehash负载因子，降低rehash概率，减少写时复制导致的物理内存消耗

当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作

4.跳跃表

skiplist 是一个概率型数据结构，查找、删除、插入的时间复杂度都是O(logN)。

skiplist是由多层有序的链表组成的，来加快查找速度。

其中第0层包含了所有元素，然后往上增加了多层的有序链表作为索引来加快查找速度。

这是跳表的结构

redis的skipList结构定义

下面给出跳表的java代码示例

插入

查找

5.整数集合

整数集合的实现，希望通过同一种数据结构来保存不同位宽的整数值，如果直接使用int64表示数组元素类型，太浪费空间，可能存储的元素是int16。为了节省空间，在整数集合结构体里面加一个字段encoding来表示数组元素的位宽，content元素类型虽然是int8，但是实际上是将encoding中指定的类型拆成高低位进行存储，元素数量有length指定。如果开始存储元素类型为int16，内存分配时按照每个元素16位进行计算、分配，后面存储64位元素时，会对content进行升级，将所有元素类型提升为64，这就要重新计算存储空间大小。但是删除位宽大的元素，不会触发降级。

6.压缩列表

压缩列表是一块连续的内存空间，每个节点内可以保存一个字节数组或一个整数

字节数组可以是以下其中之一:

1)长度小于等于63字节的数组

2）长度小于等于16383字节的数组

3）长度小于等于4294967295字节的数组

而整数型可以是一下6种长度之一

1）4位长，介于0-12之间的无符号整数

2）1字节长的有符号整数

3）3字节长的有符号整数

4）int16_t类型整数

5）int32_t类型整数

6）int64_t类型整数

previous前一个节点长度小于254字节，则previous长度位1字节，超过254字节，则为5字节，当头节点插入大于254字节的数据节点时，则有概率会发生扩容连锁反应，直至扩容到结尾，前提条件是所有的节点都是在250+字节，才会触发这种扩容连锁。不过不用担心，如果超过512个元素，redis会更换其他底层实现

redis后面已经将ziplist替换为quicklist

以上便是redis中常见的底层实现了，下面继续分享redis种的对象和底层实现

对象

1.对象的类型与编码

Redis中对象通过redisObject结构来表示，其中有三个属性和存储数据有关，分别是：类型、编码、指向底层数据结构的指针

对象类型redisObject对象维护属性type，一共有五种。分别是STRING,LIST,SET,ZSET,HASH。每一种对象类型都可以使用不同的redis数据结构实现，维护encoding属性表示。属性值共有embstr,int,raw,linkedlist,ht,intset,ziplist,skiplist

2.字符串对象

字符串对象的编码可以是int、raw或者embstr。 1-字符串对象保存的是整数且可以用long表示，编码用int 2-字符串对象存储的是长度大于32的字节，使用简单动态字符串存储，编码raw 3-字符串对象存储的是长度小于32的字节，使用编码embstr的方式存储

5.0版本后调整为44字节，embstr存储比sds少一次内存分配

3.列表对象

redis 3.2 列表对象由ziplist和linkedlist实现

列表的编码linkedlist转换为ziplist需要两个条件 1.元素保存的长度小于64字节 2.列表大小不能超过512个 Redis已更换为quicklist

4.哈希对象

哈希对象的编码可以是ziplist或hashtable

ziplist中同一键值对的两个节点总是挨着，键的节点在前，值的节点在后

哈希对象如果编码是hashtable转为ziplist的条件 1.键值都不能超过64字节 2.键值对小于512个

5.集合对象

集合对象的编码可以是intset或hashtable作为底层实现

当集合对象可以同时满足以下两个条件时，对象使用intset编码： 1）集合对象保存的所有元素都是整数值； 2）集合对象保存的元素数量不超过512个。不能满足这两个条件的集合对象需要使用hashtable编码。

而用hashtable时只有key存储数据，值置为null

6.有序集合对象

有序集合的编码可以是ziplist或者skiplist。

如果使用ziplist需要保证有序元素数量小于128个且所有元素长度小于64字节

在ziplist中score分值越小越靠近表头方向，反则亦之

在大多数情况下都会使用skiplist来实现，但是通过跳表来查询某个key的分值（score）时，那么ta的时间复杂度可能是O(logn),所以使用skiplist时还需一个字典来帮忙记录同样的内容，这样就可以O(1)的效率获得一个元素的score分值了

skiplist负责维护一组排序的元素，加速rank、range等命令

dict负责维护一组乱序元素，加速get等命令

7.类型检查与命令多态

Redis中用于操作键的命令基本上可以分为两种类型。其中一种命令可以对任何类型的键执行，比如说DEL命令、EXPIRE命令、RENAME命令、TYPE命令、OBJECT命令等。另一种命令只能对特定类型的键执行，比如说： ❑SET、GET、APPEND、STRLEN等命令只能对字符串键执行； ❑HDEL、HSET、HGET、HLEN等命令只能对哈希键执行； ❑RPUSH、LPOP、LINSERT、LLEN等命令只能对列表键执行； ❑SADD、SPOP、SINTER、SCARD等命令只能对集合键执行； ❑ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执行；

而至于命令多态指的是对象的操作命令，对多种不同的底层实现的方法。redis可以通过encoding来判断底层实现，跟java中的多态差不多

8.内存回收

在redisObject中其实还有一个属性refCount，redis中的每个对象都有。这个属性就是引用计数，跟jvm的引用计数回收差不多。

此处的引用计数应该是的是内容对象被多少个键指向，即引用。当一个键被删除是，引用计数就会减一。当引用计数为0时代表无任何键指向对象，内存释放

因为redis中的不太可能存在循环引用，就连引用层级都很低，所以redis可以使用引用计数，但jvm不行

9.对象共享

在redis启动的时候redis会创建0到9999的所有整数值，供后续使用。殊途同归，Java初始化了-128到127的整数，都是为了节省内存，提供复用。

为什么redis不进行对象的共享及复用？

验证共享对象中的值复杂度太高，如果对象有10000个属性那就要验证这10000个属性才能确认共享对象和目标对象完全一致，这会消耗cpu的时间，本末倒置

10.对象的空转时长

除了前面讲过的redisObject的固有属性外还有一个lru属性

redisobject包含了几个属性 type指代的类型 encoding指代的编码 ptr指代的底层实现的数据结构 refcount指代的引用计数器 lru指代的最后一次引用的时间

每次对对象操作都会有一些固有的操作，这些操作下一个部分会将，其中就包含了lru空转时长更新，假如我10秒前获取了一下这个对象，现在使用OBJECT IDLETIME打印key的空转时长就是10

OBJECT IDLETIME 命令是特殊的，在查询lru时不会修改lru的时间

如果服务器maxmemory打开，且volatile-lru或allkeys-lru为内存回收算法，那么内存超过maxmemory设置的上限，则会从空转时长交高的key中释放空间

11.回顾

字符串的底层数据结构有int、raw、embstr。

列表的底层数据结构有ziplist和linkedlist。

hash的底层数据结构有ziplist和hashtable。

set的底层数据结构有hashset和intset。

sort set的底层数据结构有ziplist和skiplist。

Redis数据库中的每个键值对的键和值都是一个对象。 ❑Redis共有字符串、列表、哈希、集合、有序集合五种类型的对象，每种类型的对象至少都有两种或以上的编码方式，不同的编码可以在不同的使用场景上优化对象的使用效率。 ❑服务器在执行某些命令之前，会先检查给定键的类型能否执行指定的命令，而检查一个键的类型就是检查键的值对象的类型。 ❑Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，该对象所占用的内存就会被自动释放。 ❑Redis会共享值为0到9999的字符串对象。 ❑对象会记录自己的最后一次被访问的时间，这个时间可以用于计算对象的空转时间。

以上为Redis设计与实现的第一个部分阅后总结

💡

有关Redis上的问题，欢迎您在底部评论区留言，一起交流~