Redis设计与实现第一部分：第8章：Redis-对象

　　　　Redis主要数据结构：SDS、双端链表、字典、压缩列表、整数集合等等。

　　Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这 5 种类型的对象。每种对象都至少用到了上述所说的数据结构。

　　通过这5 种不同类型的对象，Redis可以在执行命令前，根据对象的类型来判断对象是否可以执行给定的命令。使用对象的另一个好处就是可以针对不同的使用场景为对象设置不同的数据结构实现，从而优化对象在不同场景下的使用效率。

　　除此之外，Redis的对象系统还实现了基于引用计数计数的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动是否；另外，Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库共享同一个对象来节约内存。

　　最后，Redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了maxmemory功能的情况下，空转时长越大的那些键就可能会优先被服务器删除。

　　对象的类型与编码：

　　Redis使用对象表示数据库中的键和值，Redis每次在数据库中创建一个键值对时，至少会创建两个对象：一个对象用作键值对中的键（键对象），一个用作键值对中的值（值对象）。

　　Redis中的每个对象都由一个redisObject结构表示，该结构中保存有与数据相关的三个属性：

typedef struct redisObject{
   
    //类型
    unsigned type:4;

    //编码
	unsigned encoding:4;
		 
	//指向底层实现数据结构的指针
	void *ptr; 
	
}robj;

　　类型：

　　type属性指向的对象的类型：

　　对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值可以是字符串对象，列表对象，哈希对象，集合对象或者有序集合对象中的其中一种。

　　TYPE命令的实现方式：当对一个数据库键执行TYPE命令时，命令返回的结果为数据库键对应的值的对象类型，而不是键对象的类型。

　　编码和底层实现：

　　对象的ptr指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定。

　　encoding属性记录了对象所使用的编码，也就是说这个对象使用了什么数据结构作为对象的底层实现。这个属性的值可以是以下列表列出的常量的其中一个：

　　上述说明的是不同对象的编码所对应的底层数据结构，而且每种类型的对象都至少使用了两种不同的编码，下表列出了每种类型的对象可以使用的编码：

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

　　下表列出了不同编码对象所对应的OBJECT ENCODING命令输出：

　　 通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种特定的编码，极大的提升了Redis的灵活性和效率，因为Redis可以根据不同的使用场景为一个对象设置不同的编码，从而优化对象在某一场景下的使用。

　　字符串对象：

　　字符串对象的编码可以是int、raw或者embstr。

　　1. 如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码设置为int。

　　2. 如果一个字符串对象保存的是一个字符串值，并且这个字符串值的长度大于39字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw。

　　3. 如果一个字符串对象保存的是一个字符串值，并且这个字符串值的长度小于39字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值。

　　embstr编码方式是专门用于保存短字符串的一种优化编码方式，这种编码和raw编码一样，都是由redisObject结构和sdshdr结构来表示字符串对象，但raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续空间，空间中依次包含redisObject和sdshdr两个结构，

　　embstr编码的字符串在执行命令时，产生效果和raw编码的字符串对对象执行命令时产生的效果是相同的，但使用embstr编码的字符串对象保存短字符串值有以下好处：

　　1. embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次。

　　2. 释放embstr编码的字符串对象只需要一次内存释放函数，而释放raw编码的字符串对象需要调用两次内存释放函数。

　　3. 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比其raw编码的字符串对象能够更好地利用缓存带来的优势。

　　最后要说的是，可以用long double类型标识的浮点数在Redis中也是作为字符串值来保存的。如果我们要保存一个浮点数到字符串对象里面，那么程序会先将这个福电视转换成字符串值，然后再保存转换所得的字符串值。在需要的时候，程序会将保存在字符串对象里面的字符串值转换回福电视值，执行某些操作，然后再执行操作所得的浮点数值转换回字符串值，并继续保存在字符串对象里面。

　　字符串对象保存各类型值的编码方式：

　　int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转化为raw编码的字符串对象。

　　对于int编码的字符串对象来说，如果我们向对象执行了一些命令，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对象的编码将从int变为raw。

　　另外，因为Redis没有为embstr编码的字符串对象编写任何相应的修改程序（只有int编码的字符串对象和embtsr编码的字符串对象有这些程序），所以，embstr编码的字符串对象实际上只是只读的。当我们对embstr编码的字符串对象执行修改命令时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。因为这个原因，embstr编码的字符串对象在执行修改命令之后，总会变为一个raw编码的字符串对象。

　　列表对象：

　　列表对象的编码可以是ziplist或者是linkedlist.

　　1. ziplist编码的列表对象使用压缩列表作为底层实现，，每个压缩列表节点（entry）保存了一个列表元素。

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

　　注意：linkedlist编码的列表对象在底层的双端链表结果中包含了多个字符串对象，这种嵌套字符串对象的行为在稍后介绍的哈希对象、集合对象和有序集合对象中都会出现，字符串对象是Redis五种类型的对象中唯一一种会被其他四种对象嵌套的对象。

　　编码转换：

　　当列表对象满足以下两个条件时，列表对象使用ziplist编码：

　　1. 列表对象保存的所有字符串元素的长度都小于64字节；

　　2. 列表对象保存的元素数量小于512个；不能满足这两个条件的列表对象使用linkedlist编码。

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

　　哈希对象：

　　哈希对象的编码可以为ziplist和hashtable；

　　1、ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对需要加入哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表节点末尾，然后再讲保存了值的压缩列表节点推入压缩列表节点末尾。所以保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前面，保存值得节点在后面；先添加到哈希对象的键值对会被放在压缩列表的表头方向，而后来的压缩列表节点会被放在压缩列表的表尾方向。

　　举个例子：执行HSET命令，服务器将会创建一个列表对象作为profile的值：

redis>HSET profile name "Tom"
(integer) 1

redis>HSET profile age 25
(integer) 1

redis>HSET profile career "Programmer"
(integer) 1

　如果profile键的值对象使用的是ziplist编码，那么值对象将会是下图所示，这个压缩列表对象使用的底层实现如下下图所示：

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

　　　　a. 字典的每个键都是一个字符串对象，对象中保存了键值对的键；

　　　　b. 字典的每个值都是一个字符串对象，对象中保存了键值对的值；

　　举个例子：如果前面profile键创建的不是ziplist编码的哈希对象，而是hashtable编码的哈希对象，则该哈希对象如图所示：

　　编码转换：

　　当哈希对象可以同时满足一下两个条件时，哈希对象使用ziplist编码：

　　1. 哈希对象保存的键值对的键和值的字符串换长度都小于64字节；

　　2. 哈希对象保存的键值对数量小于512个；

　　不能满足这两个条件的哈希对象需要使用hashtable编码；

　　对于使用zuolist编码的列表对象来说，当使用ziplist编码所满足的两个条件中的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有键值对就会被转移并保存到字典里面，对象的编码也会从ziplist变未hashtable。

　　备注：除了键的长度太大会引起编码转换以外，值得长度太大也会引起编码转换。

　　集合对象：

　　集合对象的编码可以是intset或者是hashtable；

　　1. intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有的元素都保存在整数结婚里面。

　　举个例子：以下代码将创建一个下图所示的intset编码的及核对象：

redis> SADD numbers 1 3 5
(integer) 3

　　2. hashtable编码的集合对象使用字典作为底层实现，字典的每一个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL。

　　举个例子：以下代码将创建一个如下图所示的hashtable编码集合对象：

　　编码的转换：

　　当集合对象可以同时满足以下两个条件时，对象使用intset编码：

　　1. 集合对象保存的所有元素都是整数值；

　　2. 集合对象保存的元素数量不超过512个；

　　不能满这两个条件的集合对象需要使用hashtable编码。

　　有序集合对象：

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

　　1. ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个节点保存元素的分值（score）。

　　压缩列表的集合元素按照分值大小从小到大排序，分值较小的元素被放在靠近表头的位置，分值较大的元素被放在靠近表尾的位置。

　　举个例子：执行ZADD命令，那么服务器将会创建一个有序集合对象作为price键的值：

redis>ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

　　如果price键的值对象使用的是ziplist编码，那么这个值对象将会是下图所示：

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

typedef struct zset{
   
    zskiplist *zsl;

    dict *dict;
	
}zset;

　　zset 结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表保存了一个集合元素：跳跃表的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值。通过这个跳跃表，程序可以对有序集合进行范围型操作。

　　除此之外，zset结构中的dict字典为有序集合创建了一个成员到分支的映射，字典中的每一个键值对都保存类一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以通过O(1)复杂度查找给定成员的分值，ZSCRE命令就是根据这一特性实现的。值得一提的是，虽然zset结构同时使用跳跃表和字典保存有序集合元素，但是这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。

　　为什么有序集合要同时使用跳跃表和字典来实现？

　　同时使用肯定是因为性能有所提高！

　　原因：

　　1. 如果只是使用了字典来保存有序集合，那么虽然是以O(1)的时间复杂度来查找成员的分值这一特性会被保留，但是，因为字典是以无序的方式来保存集合元素，所以每次在执行范围型操作——比如：ZRANK、ZRANGE等命令时，程序都要对字典保存的所有元素进行排序，完成这种排序操作需要至少O(NlogN)时间复杂度，以及额外的O(N)内存空间（因为要创建一个数组来保存排序后的元素）

　　2. 如果只是使用了跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查询号分值这一操作的复杂度就会从O(1)上升到O(logN)。

　　举个例子：如果前面price键创建的不是ziplist比那么的有序集合，而是skiplist编码的有序结合对象。那么这哥有序集合对象将会是下图所示：而对象所使用的zset结构将会是下下图所示：

　　编码的转换：

　　当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码：

　　1.有序集合保存的元素数量小于128个；

　　2.有序集合保存的所有元素的长度都小于64个字节；

　　不能满足以上两个条件的有序集合对象都使用skiplist编码；

 　　类型检查和命令多态：

　　Redis中用于操作键的命令可以分为两种类型：

　　1. 可以对任何类型键执行的命令：比如DEL命令、EXPIRE命令、RENAME命令、TYPE命令、OBJECT命令等。

　　2. 而另一种命令只能对特定类型的键执行。比如：

　　　　SET、GET、APPEND、STRLEN等命令只能对字符串键执行；

　　　　RPUSH、LPOP、LINSET、LLEN等命令只能针对列表键执行；

　　　　SADD、SPOP、SINTER、SCARD等命令只能针对集合键执行；

　　　　ZADD、ZCARD、ZRANK、ZSCORE等命令只能针对有序集合键执行；

　　如果针对某类型键执行其它特定类型的键的命令，Redis就会返回一个类型错误。

　　类型检查的实现：

　　　　在执行一个类型特定键的命令之前，Redis会检查输入键的类型是否正确，然后再决定是否执行给定的命令。

　　　　类型特定命令所进行的类型检查是通过redisObject结构的type属性来实现的：

　　　　1. 在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型，如果是的话，服务器就会对键执行指定的命令。

　　　　　否则，服务器将拒绝执行命令，并想客户端返回一个类型错误。

　　　　下图为类型检查过程（以LLEN命令为例）：

　　多态命令的实现：

　　Redis除了根据值对象的类型来判断键是否能够执行指定命令之外，还会根据值对象的编码方式，选择正确的命令实现代码执行命令。

　　以列表对象为例：

　　1. 如果列表对象的编码为ziplist，则说明列表对象的编码为压缩列表，程序将会使用ziplistLen函数来返回列表的长度。

　　2.如果列表对象的编码为linkedlist，则说明列表对象的编码为双端链表，程序将会使用linkedlist函数来返回列表长度。

　　借用面向对象的术语回答，可以认为LLEN命令时堕胎的，执行执行LLEN命令时列表键，那么无论值对象使用的是ziplist编码或者是linkedlist编码，命令都可以正常执行。

　　内存回收：

　　因为C语言不具备内存回收功能，所以Redis在自己对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的是否自动释放对象并进行内存回收。

　　每个引用计数信息都是由redisObject结构的refcount属性记录：

typedef struct redisObject{
   
    //...

	//引用计数
    int refcount;
	
	//...
}robj;

　　对象的引用计数信息会随着对象的使用状态而不断变化：

　　1. 在创建一个新对象时，引用计数信息的值会被初始化为1；

　　2. 在对象呗一个新程序使用时，它的引用计数值会被增一；

　　3. 在对象不再被一个程序使用时，它的引用计数值会被键一；

　　4. 当对象的引用计数值变为0 时，对象所占用内存会被释放；

　　下表即为修改对象引用计数属性的API：

　　对象的整个生命周期可以划分为创建对象、操作对象、释放对象三个阶段。作为例子，以下代码展示了一个字符串对象从创建到被释放的过程：

//创建一个字符串对s，对象的引用计数值为1
robj *s = createStringObject(...)

//对象s执行各种操作....


//将对象s的引用计数减一，是的对象的引用计数变为0
//导致对象s被释放
decrRefCount(s)

　　对象共享：

　　除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用。

　　在Redis中，让多个键共享同一个值对象需要执行两个步骤：

　　1. 将数据库键的值指针指向一个现有的值对象。

　　2. 将被共享的值的引用计数增一。

　　共享对象机制对于节约内存非常具有帮助，数据库中保存的相同值对象越多，对象共享机制就能节约越多的内存。

　　目前来说，Redis在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象、

　　另外，这些共享对象不仅只有字符串键可以使用，那些在数据结构中嵌套了字符串对象的对象（linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象、以及zset编码的有序集合对象）都可以使用这些共享对象。

　　为什么Redis不共享包含字符串的对象？

　　当服务器考虑将一个共享对象设置为键的值对象时，程序需要先检查给定的共享对象和键想要创建的目标对象是否相同，只有在共享对象和目标对象完全相同的情况下，程序才会将共享对象作为键的值对象，而一个共享对象的保存的值越复杂，验证共享对象和慕白对象的时间复杂度就越高。消耗的CPU就越多。

　　1. 如果共享对象是保存整数值的字符串对象，那么验证操作的复杂度为O(1)。

　　2. 如果共享对象是包含字符串值的字符串对象，那么验证操作的复杂度为O(N)。

　　3. 如果共享对象是包含了多个值（或者对象）的对象，比如列表对象或者哈希对象，那么验证操作的复杂度为O(N^2)。

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

 　　空转时长：

　　除了前面介绍的tyoe、encoding、ptr和refCount属性之外，redisObject还有最后一个属性为lru属性。该属性记录了对象最后一次被命令程序访问的时间。

typedef struct redisObject{
   
    //...

	unsigned lru:22;
	
	//...
}robj;

　　1. OBJECT IDLETIME命令可以打印出给定键的空转时长，就是通过将当前时间减去值对象的lru属性计算得出。

　　2. 键的空转时长还有另一项作用：如果服务器打开了maxmemory选项，并且服务器回收内存的算法为volatile-lru或者alkeys-lru，那么当服务器占用的内存数超过了maxmemory选项设置的上限值时，空转时长较高的那部分键会优先被服务器是否，从而回收内存。