Redis设计与实现之数据结构与对象—对象

对象

Redis没有直接使用这些数据结构构建键值对数据库，而是基于这些数据结构构建了一套对象系统，这个系统包括了字符串对象，列表对象，哈希对象，集合对象，有序集合对象这五种类型的对象，每种对象都至少使用了前面两种数据机构作为实现。

使用对象的好处： 
1. 可以根据对象的类型，判断这个对象是否可以执行给定的命令 
2. 可以根据不同的使用场景，为对象设置不同的数据结构实现，从而优化对象在 不同场景下的使用效率。 
除此之外，redis的对象系统基于引用计数实现了下面两个功能： 
1.redis通过引用计数*实现了内存回收机制，当程序不在使用某个对象时，这个对象占用的内存就会被自动释放； 
2.redis通过引用计数实现了对象共享机制，这一机制在适当的条件下，通过让多个数据库键共享同一个对象来节约内存 
最后，redis对象还记录了访问时间信息，该信息可以用于计算数据库键的空转时长，当数据库服务器启用了maxmemory功能时，空转时长较大的数据库键可能会优先被服务器删除。

7.1 对象的类型与编码

Redis使用对象来表示数据库键和值，每当我们数据库中保存一个键值对时，都至少创建两个对象，键对象和值对象；键对象是字符串对象，值对象可以是上面提到的五种对象。 
另外，我们常叫“字符串键”“列表键”都是指值对象的类型。字符串，列表

Redis中的每个对象都油一个redisObject结构表示，该结构有三个属性：type、encoding和ptr

typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    ....
}robj;

7.1.1 类型

对象的type字段记录对象的类型，当我们对一个数据库键执行TYPE命令时，命令返回结果是数据库键对应的值对象的类型。 
type命令的输出： 

7.1.2 编码和底层实现

对象的ptr指针指向对象的底层实现数据结构，而这些数据结构有encoding属性决定。 
对象的encoding属性记录了对象所使用的编码，也即是这个对象使用了什么数据结构作为底层实现。 
每种类型的对象至少使用了两种不同的编码： 

使用object encoding 命令可以查看一个数据库键的值对象的编码

7.2 字符串对象

字符串对象的编码可以是int、raw或者embstr。 
如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在对象结构(redisObject)的ptr属性里(将void*装换成long)，并将字符串的编码encoding设置为int。 

如果字符串对象保存的是一个字符串值，并且字符串值长度大于32字节，那么将用简单动态字符串(sds)保存，并将编码设置为raw。 

如果字符串长度小于等于32字节，那么字符串对象将使用embstr编码方式保存这个字符串值 
embstr编码是一种专门用来保存短字符串的一种优化编码方式，这种编码和raw编码一样，都是用redisObject机构和sdshdr结构，但raw会调用两次内存分配函数分别创建redisObject和sdshdr，而embstr则通过调用一次，分配一块连续的内存空间。 
embstr相对于raw的优点： 
1. 内存分配次数从两次降为一次 
2. 内存回收次数也从两次降为一次（调用内存释放函数） 
3. embstr编码的字符串对象将所有我的数据都保存在一块连续的内存里，所以相对于raw编码的字符串对象，他能更好地利用缓存带来的优势。 
对于浮点数，redis保存的类型是字符串类型的值；在需要取浮点数进行数学运算时，会将字符串类型的浮点数值取出来转回浮点数值，执行完计算后，再转换成字符串保存。 

 

7.2.1编码的转换

int编码和embstr编码的字符串对象在合适的条件下会转换成raw编码的字符串对象。 
当int编码的字符串对象进行某些操作后不在是整数值时，会转换为raw编码的字符串 
embstr编码的字符串是只读的，他没有任何修改的方法函数，所以放对embstr编码的字符串对象执行修改命令后，都会转换为raw编码的字符串

7.2.2 字符串命令的实现

7.3 列表对象

列表对象的编码可以是ziplist或者linkedlist。 
zip编码的列表对象使用压缩列表最为底层实现，每个压缩列表节点（entry）保存一个列表元素

 

linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点（node）都保存一个字符串对象(redisObject)，每个字符串对象都保存一个列表元素。 

       注意，linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象。字符串对象是redis五种类型中唯一一种会被其他类型对象嵌套的对象。

7.3.1 编码转换

当列表对象可以满足以下两个条件时，列表对象使用ziplist： 
1. 列表对象保存的每个字符串对象元素的长度都小于64字节 
2. 列表对象保存的元素个数小于512个。 
当不能满足这两个条件时，列表对象需要使用linkedlist编码

以上两个条件的上限是可以自定义调整的，具体在配置文件中关于list-max-ziplist-value和list-max-ziplist-entries选项的说明。

对于使用ziplist编码的列表对象来说，当不能满足ziplist所需的两个条件的任意一个时，对象编码的转换操作就会被执行，原本保存在压缩列表中的所有列表元素都会被转移并保存到双端链表中，对象的编码也会从ziplist变为linkedlist。

7.3.2 列表命令的实现

7.4 哈希对象

哈希对象的编码可以是ziplist和hashtable 
ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象中，程序会将保存了键的压缩列表节点推入压缩列表表尾，然后再将值节点推入表尾。哈希对象中键值对两个节点紧挨在一起，键在前，值在后。 

hashtable编码的哈希对象使用字典作为底层实现，哈希对象的每个键值对都是用一个字典的键值对保存 

7.4.1 编码转换

当哈希对象可以同时满足下面两个条件时，哈希对象使用ziplist编码： 
1. 哈希对象保存的键值对的键和值的字符串长度都小于64字节 
2. 哈希对象保存的键值对数量小于512个 
不能满足上面任意一个条件，都会使用hashtable编码 
注意，上限可以自定义调整，具体参照配置文件中hash-max-ziplist-value和hash-max-ziplsit-entriescan选项的说明。 
当不能满足上面任何一个条件时，转换操作被执行，原本保存在压缩列表中的所有键值对都会被转移到字典中，对象的编码也会从ziplist转换为hashtable。

7.4.2 哈希命令的实现

7.5 集合对象

集合对象的编码可以是intset和hashtable。 
intset编码的集合对象使用整数集合作为底层实现，集合包含的所有元素都被保存在整数集合里面。 
hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象都包含一个集合元素，而字典的值则全被设置为null。

7.5.1 集合的转换

当集合对象可以同时满足以下两个条件时，对象使用intset编码 
1. 集合对象所保存的所有元素都是整数值； 
2 .集合对象所保存的所有元素数量不超过512个。 
不能满足上面两个条件时，对象使用编码 
注意，上面的第二个条件是可以自定义调整的，具体参照配置文件的set-max-intset-entries选项的说明。

对于使用intset编码的集合对象，当上面任意一个条件不能满足时，就会执行对象的编码转换操作，原本保存在整数集合中的所有元素被转换并保存到字典中，并且对象的编码从intset变为hashtable。

7.5.2 集合命令的实现

7.6 有序集合对象

有序集合对象的编码可以是ziplist和skiplist。 
ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合对象使用两个紧挨在一起的压缩列表节点保存，第一个节点保存集合元素的成员（member），第二个保存元素的分值（score）。 
压缩列表内的集合元素按分值（score）大小从小到大排序。分值小的靠近表头。 

skiplist编码的有序集合对象使用zset结构作以为底层实现，一个zset结构包含一个字典和一个跳跃表：

typedef struct zset{
    zskiplist *zsl;
    dict *dict;
} zset;

zset结构中的zsl按集合分值从小到大保存了所有集合元素，每个跳跃表节点保存一个集合元素：跳跃表节点的object属性保存了元素的成员（member），跳跃表节点的score属性保存元素的分值。通过这个跳跃表，程序可以对有序集合进行范围型的操作，如zrange，zrank等命令就是基于跳跃表的api实现的。

zset结构中的dict字典为有序集合创建了一个从成员到分值的映射关系，字典中的每个键值对保存一个集合元素：字典的键保存元素的成员（member），字典的值保存元素的分值（score）。通过这个字典，程序可以用O(1)复杂度查找给定成员的分值，zscore命令就是基于这个实现的。

有序集合每个元素的成员都是一个字符串对象，每个分值都是一个double类型的浮点数。zset结构中跳跃表和字典都是通过指针共享每个元素的成员（member）和分值（score），并不会造成内存浪费。

7.6.1 编码的转换

当有序集合对象同时满足以下两个条件时，使用ziplist编码： 
1. 有序集合每个元素的成员长度都小于64字节； 
2. 有序集合对象保存的元素数量小于128和。 
不能同时满足上面两个条件，使用skiplist编码 。 
注意，以上两个条件可以自定义调整，具体参照配置文件中关于zset-max-ziplist-value和zset-max-ziplist-entries选项的说明。

7.6.2 有序集合命令的实现

7.7 类型检查和命令多态

Redis中操作键的命令可以分为两种： 
其中一种命令可以对任何类型进行操作，比如del，expire，rename，type，object等。 
而另一种只能针对特定类型的键执行，比如： 
set，get，append，strlen等命令只能对字符串键执行； 
hdel，hset，hget，hlen等命令只能对哈希键执行； 
rpush，lpop，linsert，llen等命令只能对列表键执行； 
sadd，spop，sinsert，scard等命令只能对集合键执行； 
zadd，zcard，zrank，zscore等命令只能对有序集合执行。 
否则会报类型错误 

7.7.1 类型检查和实现

redis在执行命令前，会先检查输入键的类型，判断该类型是否可以执行给定的命令；类型检查是通过redisObject对象的type属性实现的： 
在执行一个类型特定命令前，服务器会先检查输入数据库键的值对象是否为给定命令所需的类型，如果是则执行 
否则。服务器向客户端返回一个类型错误。

7.7.2 多态命令的实现

redis会根据值对象的编码，选择正确的命令 实现代码来执行命令； 
这种根据对象的不同编码来选择不同命令实现来执行命令，称之为多态 
举个例子，llen命令会根据数据库键的值对象的编码（ziplist或linkedlist），选择不同的命令实现来执行命令。 
ziplist编码，选择压缩列表的api来实现命令 
linkedlist编码，选择双端链表的api来实现命令

实际上，可以将del，expire，rename，type，object命令也称为多态命令。 
del，expire命令相对于llen命令的区别在于，前者是基于类型的多态——一个命令可以用来处理多种不同类型的键；后者是基于编码的多态—— 一个命令可以同时用于处理多种不同编码的键。

7.8 内存回收

C语言不具备自动内存回收功能，所以redis在自己的对象系统中构建了一个基于引用计数技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。 
对象的引用计数信息有redisObject结构中的refcount属性记录：

typedef struct redisObject{
    //...
    //引用计数
    int refcount;
    //...
}robj;

对象的引用计数信息会随着对象的使用状态而不断变化： 
1. 在创建一个新对象时，引用计数的值被初始化为1； 
2. 当对象被一个新程序使用时，引用计数的值 +1； 
3. 当对象不再被一个程序使用时，引用计数的值 -1； 
4. 当对象的引用计数值变为0时，对象所占用的内存会被释放。 

对象的整个生命周期都可以划分为创建对象，操作对象和释放对象三个阶段。

7.9 对象的共享

对象的引用计数属性处理用于内存回收机制外，还可以用于对象共享。 
在Redis中，让多个键共享同一个值对象需要下面两个步骤： 
1. 将数据库键的值指针指向一个现有的值对象； 
2. 将被共享的之对象的引用计数+1

Redis会共享值为0到9999的字符串对象 
Redis在初始化服务器时，创建0到9999这一万个对象；当用到这些对象时，不在创建，而是共享。 
Redis不共享包含字符串的对象，虽然共享能节约内存，但对象对比时会耗费时间： 
1. 整数值的字符串对象：验证目标对象和更新对象是否完全相同的时间复杂度为O(1)； 
2. 字符串值的字符串对象：验证目标对象和更新对象是否完全相同的时间复杂度为O(N)； 
3. 共享对象包含了多个值（或对象）的对象，比如列表对象或者哈希对象，那么验证目标对象和更新对象是否完全相同的时间复杂度为O(N^2)；

因此尽管共享复杂对象可以节约内存，但受到执行时间的限制， 
Redis只对包含整数值的字符串对象进行共享

7.10 对象的空转时长

redisObject结构除了上面介绍的type，encoding，ptr和refcount四个属性外，还包含的最后一个属性是lru属性，该属性记录了对象最后一次被命令程序访问的时间：

typedef struct redisObject{
    //...
    unsigned lru:22;
    //...
}robj;

object idletime 命令可以打印出给定键的空转时长，这个空转时长就是通过当前时间减去键的值对象的lru时间计算得出的。 
注意：object idletime命令的实现是特殊的，这个命令在访问键的值对象时，不会修改值对象的lru属性

除了可以被object idletime命令打印出来之外，键的空转时长还有另外一项作用： 
如果服务器开启了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么当服务器占用的内存超过了maxmemory选项设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。

重点回顾

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