前言
在之前的章节中,介绍了Redis的基本操作及命令的执行过程。但是Redis并没有直接去使用这些数据结构作为键值对数据库,而是基于这些数据结构构建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这5种类型。也就是我们所说的Redis上层提供了5种数据结构的API。通过这五种类型的对象,Redis可以在执行命令之前根据对象的类型来判断这些对象是否可以执行想要执行的命令。除此之外,还可以针对不同的使用场景为对象设置多种不同的数据结构实现从而优化对象的使用效率。
除此之外，Redis的对象系统还实现了基于引用计数计数的内存回收机制,当程序使用到某个对象时这个对象的引用计数就会+1，不再使用的时候减1，如果减到0了，就代表没程序在使用了，就会被自动释放。另外提供了对象的共享机制0-9999的数组字符串对象共享。但是没有共享普通字符串。(判断相等至少 N 的时间复杂度)。
1. 对象类型及编码
Redis使用对象来标识数据库中的键值，每当我们在Redis中新建一个键值对的时候，总是会至少创建2个对象，键对象和值对象。而Redis中的每个对象都是一个redisObject结构,这个结构中有三个属性需要关注
typedef strutc redisObject{
// 类型
unsigned type;
// 编码
unsigned encoding;
// 指向底层实现数据结构的指针
void *ptr;
// ...
}robj;
对于类型,有如下几种
| 类型常量 | 对象的名称 | type命令输出 |
|---|---|---|
| REDIS_STRING | 字符串对象 | string |
| REDIS_LIST | 列表对象 | list |
| REDIS_HASH | 哈希对象 | hash |
| REDIS_SET | 集合对象 | set |
| REDIS_ZSET | 有序集合对象 | zset |
对于Redis来说键总是一个字符串对象,值可以是列表中的任意一种。
再回到刚才的redisObject上,ptr指针指向对象的底层实现数据结构,而这些数据结构由对象的encoding值决定的。encoding记录了对象使用的编码方式,也就是说这个对象底层使用的是什么数据结构作为对象的实现的。
| 编码常量 | 编码对应的底层数据结构 |
|---|---|
| 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_SKPLIST | 跳跃表和字典 |
而它们和上层对象的对应关系如下:
| 类型 | 编码 | 对象 |
|---|---|---|
| REDIS_STRIG | REDIS_ENCODING_INT | 整数数值实现的字符串对象 |
| REDIS_STRING | REDIS_ENCODING_EMBSTR | embstr编码的SSD字符串对象 |
| REDIS_STRING | REDIS_ENCODING_RAW | SSD实现的字符串对象 |
| REDIS_LIST | REDIS_ENCODING_ZIPLIST | 压缩列表实现的列表对象 |
| REDIS_LIST | REDIS_ENCODING_LINKEDLIST | 双端列表实现的 列表对象 |
| REDIS_HASH | REDIS_ENCODING_ZIPLIST | 压缩列表实现的哈希对象 |
| REDIS_HASH | REDIS_ENCODING_HT | 字典实现的哈希对象 |
| REDIS_SET | REDIS_ENCODING_INTSET | 整数集合实现的集合对象 |
| REDIS_SET | REDIS_ENCODING_HT | 字典实现的集合对象 |
| REDIS_ZSET | REDIS_ENCODING_ZIPLIST | 压缩列表实现的有序集合对象 |
| REDIS_ZSET | REDIS_ENCODING_SKPLIST | 跳跃表实现的有序集合对象 |
可以通过encoding属性来设定对象所使用的编码,而不是为特定类型的对象关联一种固定的编码,最大化提升Redis的灵活性和效率。比如,在列表对象包含的比较少的时候,Redis底层使用的是压缩列表来节约空间,随着对象越来越多非常多的时候再使用双端链表。
相信这看着的确很费劲,没关系,我又画了一个简图。之后开始每个对象的具体分析
Redis的五种数据类型总结.png
1.1 字符串对象
字符串对象的编码可以是
int、 raw、 embstr,为啥它有3个?还不是因为用的多,最常用了,所以作者才特别关照对它千方百计的优化。如果一个字符串保存的是整数值,并且这个值可以用long类型表示,那么字符串对象会将整数值保存在字符串对象结构的ptr属性里。并将字符串编码encoding设置为int。此处要注意,1-9999之间的数值字符串在内存中可以复用,后面会说到。如果保存的是一个字符串的值,并且长度大于44字节(redis3.0之前是39),那么字符串对象将使用raw编码的简单动态字符串保存这个值。如果长度小于等于44,将使用embstr编码的简单动态字符串保存这个值。
39/44这个值从哪里来的:
要先看下当字符串类型时,redisObject的结构：
STRING.png
原因是,3.0版本之前,sdshdr这个结构里len和free记录了这个SDS的长度和空余空间,是unsigned int类型的,可以保存很大的数字,但是对于很短的SDS就浪费空间了(2个unsigned占8个字节)。而Redis分配内存一般是8 16 32 64这种分配的,redisObject占16个字节,最初free和len各占4个字节,字符串buf后面还有1个\0字节。所以当buf中为39字节时,16+8+39+1=64字节。当字符数少于39都会分配64字节的长度,3.0之前的39界限从这里得来的。3.0之后发现对于一些短的这样做不太合理,于是做了一次优化,优化点主要就在len free这2个属性上,之前一个len和一个free分别占用4字节,现在分别占用1个字节,又加了一个标识位flag占用1个字节,于是从原来的8到现在的 1*2+1=3。刚好缩短了5个字节,从39变成了44。另外embstr是只读的,在它进行运算时会先转成raw类型。具体介绍下它们二位:
1.1.1 embstr与raw
上面说过,在redis3.0之后,如果一个字符串的长度小于等于44就使用embstr这种编码方式。它是专门用来保存短字符串的一种优化编码方式,它和raw一样都使用redisObject和sdshdr来表示字符串对象,但是raw编码会调用2次内存分配分别分配redisObejct和sdshdr空间。而embstr只需要申请一块连续的空间即可,空间中一次包含redisObject和sdshdr2个结构,并且连续的。同理释放的时候释放一次即可。而且它两个结构位置相邻,找也方便,可以更好利用缓存的优势。如图 embstr结构:(raw类型结构同理,只是需要把下面的ptr指针指向sdshdr即可,保证内存空间上非连续的)
embstr结构.png
所有对字符串(int/embstr)类型的修改操作,都是先将它们转换成raw类型的,然后再执行修改命令,并且不可逆。因为redis只为raw编码的提供了修改接口,这个过程不可逆也会导致修改完之后对象的编码总是为raw类型。
1.2 列表对象
列表对象的编码可以是ziplist、linkedList结构。也就是压缩列表和双向链表结构。ziplist编码的列表对象使用压缩列表作为底层实现,每个压缩列表节点保存了一个列的元素。如下：
zlbytes记录整个压缩列表占用的内存字节数,在对压缩列表进行内存重分配或计算zlend的位置时使用。zltail记录压缩列表尾节点距离压缩列表的起始地址有多少字节,通过这个偏移量,可以直接确定尾节点的位置。zllen记录压缩列表包含的节点数量,xxx/yyy/zzz表示各种节点,数量和长度不一定。zlend用于标记压缩列表的末端。
ziplist编码的list.png
再来看下linkedList编码的list,如果节点数过长或者每个节点的大小都比较大,就会使用linkedList编码list。底层使用双端列表实现。链表的每个节点都是一个个的字符串对象。关于字符串对象上面1.1 字符串对象部分有过介绍。这是一种对象嵌套对象的结构,后面我们所使用的哈希对象、集合对象等一些比较复杂的结构都是嵌套对象实现的。而stringObejct对象,也就是字符串对象也是唯一一种会被其它四种对象嵌套的对象。
linkedList编码的list.png
和stringObejct的embstr和raw一样,一个对象如果有多种编码的话,肯定有一个转换的条件,不会平白无故的转换的。而ziplist和linkedList的转换。当列表对象同时满足下面条件时使用ziplist,否则使用linkedList。并且这2个界限值是可以修改的,在配置文件中。
- 列表对象保存的所有字符串元素都不小于64字节
- 列表存储的元素数量小于512个
1.2.12 Redis3.2对ziplist动刀子
Redis3.2废弃了上面所说的那2个参数,又新增了一个参数,同时也不再使用ziplist结构,引入了一个全新的结构quicklist,它是一个由ziplist组成的双向链表。从上面的介绍可以知道,ziplist是由zlbytes、zltail等属性及要存储的元素若干个节点组成的,提高内存的利用率,便于存储较短的较少的列表。但是它也有缺点,当插入元素的时候将会频繁调用内存申请,然后把旧数据搬移到新的数组上,这个过程是比较消耗时间的,所以才进行了优化。而使用了quicklist结构,它这个链表的每个节点都是一个ziplist结构,也就意味着,quicklist每个节点保存的都是一片数据,而不再是一块数据。而这个参数就是限制每个ziplist的大小的,默认每个ziplist不大于8kb。
使用quicklist带来的好处:
-
quicklist是一个双向链表,进行插入和删除时比较方便,虽然复杂度为O(N),但是它不需要再去内存中的数据进行复制,而且访问2端的时间复杂度都是O(1)。 -
quicklist的每个节点都是内存连续且顺序存储的,可以通过O(LogN)定位某个元素。总体来说和B树很像。
quicklist的结构如图所示:
quicklist.png
1.3 哈希对象
哈希对象的底层编码可以是ziplist或者hashtable,目前仅分析之前版本的ziplist结构的哈希。新版本的(我看的是3.2的源码,发现哈希对象没有像list一样废弃那2个参数)
1.3.1 ziplist编码的hash对象
ziplist作为哈希对象的底层实现的时候,每当有新的键值对要加入到哈希对象时,程序会先把键放到ziplist的末尾,再把值放在ziplist的末尾。因此键值总是挨在一起的,键在前,值在后。如下图所示:
ziplist编码的hash.png
1.3.2 hashtable编码的hash对象
除了ziplist编码的哈希对象之外,hashtable编码也是哈希对象的选择,也就是使用字典作为底层实现,哈希对象中的每个键值对都使用一个字典来保存,有如下特性,简图如下:
- 字典中的每个键都是字符串对象,保存键
-
字典中的每个值都是字符串对象,保存值
hashtable编码的hash.png
1.3.3 编码类型转换
同刚刚所说的stringObject listObject一样,有多种编码的话就代表会相互转换,也同listObject的ziplisyt对象一样,同时满足下面2个条件使用ziplist编码
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512
这2个值也是在配置文件中可以修改的在redis.conf,但是我在3.2中的源码里并没有看到这2个参数被废弃。
1.4 集合对象set
集合对象也有2种编码,分别是intset整数集合和hashtable哈希表。简单介绍一下：
intset编码的集合对象使用整数集合作为底层实现,集合对象包含的所有元素都被保存在整数集合里面。
intset.png
另一方便,hashtable编码的集合对象使用字典作为底层实现,字典的每个键都是一个字符串对象,每个字符串对象包含了一个集合元素,而字典的值则全部被设置为null.
hashtable编码的set.png
直接切入正题:编码转换,当集合对象同时满足下面2个条件,使用intset,否则使用hashtable
- 集合里所有元素都是整数值
- 集合元素个数不超过512(可配置,redis.conf)
localhost:6379> sadd numbers 1 2 3 4 5
(integer) 5
localhost:6379> object encoding numbers
"intset"
localhost:6379> sadd numbers aaa
(integer) 1
localhost:6379> object encoding numbers
"hashtable"
localhost:6379>
1.5 有序集合对象
底层编码可以是ziplist或者skiplist结构,压缩列表特性之前说过,每个元素的集合使用2个位置相邻的节点保存,在有序集合中,第一个存放的是元素本身,第二个存放的是元素的分值score。压缩列表的集合元素按分值从小到大进行排序,分值较小的元素被放置在靠近表头的位置。
localhost:6379> zadd socres 10.2 b 10.1 c 9 d 11 a
(integer) 4
localhost:6379> object encoding socres
"ziplist"
它的底层结构如下:
ziplist编码的zset
而skiplist编码的有序集合对象使用zset作为底层结构实现,一个zset结构同时包含一个字典和一个跳跃表。
typedef struct zset{
zskiplist *zsl;
dict *dict;
}zset;
zset结构中,zsl跳跃表按照分值大小保存了所有的集合元素,每个跳跃表节点都保存了一个集合元素,跳跃表节点的object属性保存了元素的成员,score保存了元素的分值,这个分值其实就是用来参与排名号码。通过这个跳跃表,程序可以对有序集合进行范围操作。除此之外,zset结构中的dict字典为有序集合创建了一个从成员到分值的映射,每个节点的键为元素本身,值为元素的分值。这样可以实现o(1)查找元素的分值。
跳跃表结构
有序集合的每个元素的分值都是double类型的,虽然zset结构同时使用跳跃表和字典保存有序集合元素,但是这2种数据结构都会通过指针来共享相同元素的成员和分值,所以使用跳跃表和字典不会产生重复成员或者分值,因此也不会浪费内存。再进一步分析,为什么zset要同时使用2种元素,实际上,无论是字典还是跳跃表,都可以单独完成zset的功能,但是如果只用字典,我们的集合是没有顺序的,每次命令都需要先排序。如果只用跳跃表,我们想知道某个元素的分值的时候又会变得困难,综合而言这是一种比较好的解决方案。
同样,它们是可以相互转换的。ziplist编码需要同时满足2个条件(可配置,redis.conf)
- [x]有序集合保存元素数量小于128
- [x] 所有成员的长度小于64字节
2 Redis的类型检查与多态指令
首先redis总的命令分为2种,1种是特定命令,这种命令只能用于对应的结构的操作,另一种是通用命令,比如DEL EXPiRE OBJECT等等。
2.1 Redis的类型检查的实现
为了确保只有指定类型的键可以执行某些命令,Redis会先检查输入键的类型是否正确再决定是否执行给定的命令。根据redisObject的type属性实现的,比如要实行hset命令首先检查输入的值对象是否为哈希类型,也就是检查redisObject的type属性是否为REDIS_HASH。是的话执行,否则直接拒绝。而对象的多态指令指的就是,对于有不同底层实现的对象来说,指令都是可以使用的,比如列表对象有ziplist和linkedlist.命令对于上层来说都是正常执行的,这是一种编码的多态。而类型的多态就是通用的命令,不区分类型,比如DEL EXPIRE等等。
2.2 内存回收
C语言回收内存都是手动回收的,所以并没有自动回收的功能,所以redis在自己的对象系统中构建了一个引用计数计数实现内存回收机制,通过这一机制,程序可以通过跟踪对象的引用计数信息refcount,在适当的时候自动释放对象并回收内存。在创建一个新的对象时refcount=1赋值,当对象被一个新的程序使用是refcount+1,当对象不再被一个程序使用时refcount-1,当refcount==0时,占用的内存被释放。
2.3 对象共享
对象的引用属性还带有对象共享的作用,在0-9999之内的数值字符串,都会被共享,redis服务在初始化时会创建这一万个字符串的对象,共享是节约内存的一个处理。比如键1和键2的值都是"888",为了节约内存,它们的值共享同一个字符串对象,共享步骤如下:
- 将数据库的键的值指向同一个现有的值对象
- 将被共享的值对象的引用计数增1
localhost:6379> set aaa 999
OK
localhost:6379> OBJECT REFCOUNT aaa
(integer) 2
localhost:6379> set bbb 999
OK
localhost:6379> OBJECT REFCOUNT aaa
(integer) 3
localhost:6379> OBJECT REFCOUNT bbb
(integer) 3
注意:普通字符串并没有被共享,因为字符串的底层SDS还是有一个buf数组的,如果要判断字符串相等的话,复杂度为O(N),如果共享的是哈希或者其它的就更高了,对于redis来说太不高效了。主要是受到CPU时间的限制。
2.4 对象的空转时长
前面介绍了redisObject中的type encoding ptr refcount,还有最后一个lru属性,这个属性记录的是对象最后一次被命令程序访问的时间。使用OBJECT IDLETIME命令就可以打印出给定键的空转时长,这一空转时长就是通过将当前时间减去键的值对象的lru时间计算得到的,比如此时我打印上面例子的aaa的空转时长。如果键处于活跃状态,那么空转时长为0,还有这个命令OBJECT IDLETIME只是看下,不算访问。
localhost:6379> OBJECT IDLETIME aaa
(integer) 4405
空转时长的作用:如果redis.conf打开了maxmemory并且回收算法为volatile-lru或者allkeys-lru,当服务器达到内存上限时会优先回收空转时长较高的对象，
3. 总结
第一部分介绍了redis的5种对象及其编码实现
第二部分介绍了redisObject对象中的属性及其属性的作用
也看到了作者一直在内存上斤斤计较的优化
网友评论