1 对象
Redis基于C语言实现了简单动态字符串,双端链表,字典,压缩列表,整数集合等数据结构,基于这些数据结构实现了五种对象,字符串对象,列表对象,哈希对象,集合对象,有序集合对象。
一个Redis对象至少包含type,encoding,ptr三个属性
typedef struct redisObject {
//类型,区分对象是五种对象中的哪一张
unsigned type:4;
//编码
unsigned encoding:4;
//指向底层实现数据结构的指针
void *ptr;
// ...
}
2 类型
3 编码和底层实现
Redis可以根据使用场景,对每种Redis对象使用不同底层数据结构来做为实现,而使用哪种数据结构作为底层实现用encoding属性标识
4 字符串对象
字符串对象的编码可以是int,raw或者embstr,具体如下图所示:
字符串对象.png
4.1 int
当字符串对象保存的是一个整数值,并且可以使用long类型表示,那么字符串对象就会把整数值保存在字符串对象的 ptr 属性里面。这样做的优点是:
1、节省内存
2、对于整数值的字符串对象可能会被执行INCR操作,SDS需要先将字符串转成整形,在执行加减操作,再将结果转成字符串保存如果底层保存一个整形变量就不需要做类型转换了(将void*转换成long)
4.2 raw
如果字符串对象保存的是一个字符串,并且字符串值的长度大于32,那么字符串对象将使用一个简单动态字符串来保存这个字符串值,并将对象的编码设置为raw。
下图是一个使用raw编码的字符串对象
字符串raw编码.png
4.3 embstr
embstr编码是一种专门用于保存短字符串的优化编码方式,这种编码和raw编码一样,都是使用redisObject和sdshdr结构来表示字符串对象,但是raw编码会调用两次内存分配函数来分别创建redisObject和sdshdr结构,而embstr编码是通过调用一次内存分配函数来分配一块连续的空间。除此以外,因为所有数据都保存在一块连续的内存里面,可以更好利用缓存带来的优势。
最后,如果是浮点数,在Redis中也是使用字符串来进行表示的,在有需要进行数值计算时,会将字符串转换为浮点数,然后进行计算。
5 列表对象
列表对象的底层实现可以是ziplist或者linkedlist,当列表对象保存的字符串长度小于64字节时且元素个数小于512个时,列表对象会使用ziplist编码来实现,否则会使用linkedlist来实现。(这两个上限值可以通过配置参数修改)
下图是保存了1,"three",5三个元素的列表对象,使用ziplist实现,
下图是保存了1,"three",5三个元素的列表对象,使用linkedlist实现,linkedlist的双端链表结构包含了多个字符串对象,字符串对象是五种类型中唯一一种会被其他四种类型对象嵌套的对象。
6 哈希对象
哈希对象的底层实现可以是ziplist或者hashtable,当哈希对象保存的字符串长度小于64字节时且元素个数小于512个时,哈希对象会使用ziplist编码来实现,否则会使用hashtable来实现。(这两个上限值可以通过配置参数修改)
当使用ziplist实现的列表对象时,当有新的键值对要加入到哈希表时,Redis会先将键推入压缩列表表尾,然后再将值加入压缩列表表尾,保证同一键值对的两个节点紧挨在一起。如下图所示:
当使用hashtable实现哈希对象时,哈希对象中的每个键值对都是使用一个字典键值对来保存,字典的每个键和值都是一个字符串对象,如下图所示:
7 集合对象
集合对象的底层实现可以是inset或者hashtable,当集合对象保存的都是整数值且元素个数小于512个时,集合对象会使用inset编码来实现,否则会使用hashtable来实现。(这两个上限值可以通过配置参数修改)
7.1 inset
inset编码的集合对象使用整数集合作为底层实现,所有元素都保存在整数集合里面。如下图所示:
7.2 hashtable
hashtable编码的结婚对象使用字典作为底层实现,字典的每个键是一个字符串对象,保存集元素,字典的值则全部被设置为NULL。如下图所示:
8 有序集合对象
有序集合对象的底层实现可以是ziplist或者skiplist,当有序集合对象保存的元素长度都小于64字节且元素个数小于512个时,集合对象会使用ziplist编码来实现,否则会使用skiplist来实现。(这两个上限值可以通过配置参数修改)
8.1 ziplist
当有序集合对象使用ziplist作为底层实现时,每个集合元素使用两个挨在一起的压缩列表节点报错,第一个节点保存元素的成员,第二个节点保存元素的分值,压缩列表内按分值从小到大排序,分值较小的放置在靠近表头的位置,分值较大的放置在靠近表尾的方向。如下图所示:
8.2 skiplist
skiplist编码的有序集合对象使用zset结构作为底层实现,一个在set结构同时包含一个字典和一个跳跃表:
typedef struct zset {
zskiplist *zsl;
dict *dict;
} zset;
zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素,每个跳跃表节点保存了一个集合元素,跳跃表节点object属性保存了元素的成员,score属性保存了分值。可以以O(NlogN)的复杂度来实现范围型查找操作
zset结构中的dict字典为有序结合创建了一个从成员到分支的映射,字典的键保存了元素的成员,值保存了元素的分值。
有序集合之所以采用字典和跳跃表两个数据结构的原因是字典可以以O(1)复杂度查找成员的分值,而跳跃表可以以O(NlogN)的复杂度来实现范围型查找操作,缺一不可。
有序集合如下图所示:
9 对象共享
当一个键已经创建了一个整数值的字符串对象时,后续其他键也需要这个整数值的字符串对象时,不会重新创建一个新的整数值的字符串对象,而是将字符串对象的引用计数加一,两个键一起使用这些共享对象。Redis会在初始化服务器时,创建一万个字符串对象,这些对象包含了从0到9999的所有整数值)
这些共享对象不单单只有字符串键可以使用,那些在数据结构中嵌套了字符串对象的对象(linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象,以及zset编码的有序集合对象)都可以使用这些共享对象。
目前对象共享只对保存整数值的字符串对象有效,因为当服务器考虑将一个共享对象设置为键的值对象时,程序需要先检查给定的共享对象和键想创建的目标对象是否完全相同,只有在共享对象和目标对象完全相同的情况下,程序才会将共享对象用作键的值对象,而一个共享对象保存的值越复杂,验证共享对象和目标对象是否相同所需的复杂度就会越高,消耗的CPU时间也会越多。
如果共享对象是保存整数值的字符串对象,那么验证操作的复杂度为O(1);
如果共享对象是保存字符串值的字符串对象,那么验证操作的复杂度为O(N);
如果共享对象是包含了多个值(或者对象的)对象,比如列表对象或者哈希对象,那么验证操作的复杂度将会是O(N 2)。
10 对象空转时长
除了前面介绍过的type、encoding、ptr和refcount四个属性之外,redisObject结构包含的最后一个属性为lru属性,该属性记录了对象最后一次被命令程序访问的时间。
键的空转时长主要用于内存回收,如果服务器打开了maxmemory选项,并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru,那么当服务器占用的内存数超过了maxmemory选项所设置的上限值时,空转时长较高的那部分键会优先被服务器释放,从而回收内存。
网友评论