详解Redis的对象系统

前言

上篇文章介绍了Redis底层的一些数据结构。但是Redis并没有直接使用这些数据结构来实现键值对数据库，而是在这些数据结构上构建了一个对象系统，这个系统包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象这5种类型的对象，每种对象都至少用到了我们前面所讲的数据结构。

通过这5种对象，有2个明显的好处：

1. Redis可以在执行命令之前，根据对象的类型，来判断命令能否执行；
2. 可以根据不同的场景，来使用不同的底层数据结构，从而优化对象在不同场景下的使用效率；

此外，Redis的对象系统还使用了基于引用计数法的内存回收技术，还有通过引用引用计数法实现了对象共享机制。

最后，Redis的对象带有访问时间记录信息，用于计算键的空转时长，若服务器开启了maxmemory功能，空转时间大的键可能会被优先删除。

对象的类型和编码

Redis的每个对象都是由一个 redisObject 结构表示，该结果如下：

/* A redis object, that is a type able to hold a string / list / set */

/* The actual Redis Object */
/*
 * Redis 对象
 */
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用计数
    int refcount;

    // 指向实际值的指针
    void *ptr;

} robj;

redisObject属性里面，和保存数据相关的3个属性分别是 type, encoding, ptr，

类型

redisObject的type属性记录了对象的类型，这个属性可以是下表列出的常量中的其中一个：

类型常量	对象名称
REDIS_STRING	字符串对象
REDIS_LIST	列表对象
REDIS_HASH	哈希对象
REDIS_SET	集合对象
REIDS_ZSET	有序集合对象

对于Redis数据库 保存的键值来说，键总是一个字符串对象，而值可以是上表5个对象中的一个。我们说是XX键的时候，总是相对于它的值而言的，比如列表键，说的就是键值对的值是一个列表对象。

我们可以用 TYPE 命令来获知一个键值对是什么类型，如下：

redis> type msg
string
redis> type names
list

不同类型值对象的TYPE命令输出如下：

对象	type属性的值	TYPE命令的输出
字符串对象	REDIS_STRING	“string”
列表对象	REDIS_LIST	“list”
哈希对象	REDIS_HASH	“hash”
集合对象	REDIS_SET	“set”
有序集合对象	REIDS_ZSET	“zset”

编码及底层实现

redisObject的ptr指针指向对象的底层实现数据结构，而这些数据结构的类型由redisObject的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_SKIPLIST	跳跃表和字典

每种类型的对象都至少使用了2种不同的编码，下表列出了每种对象可以使用的编码：

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT	整数值实现的字符串对象
	REDIS_ENCODING_EMBSTR	embstr编码实现的简单动态字符串实现的字符串对象
	REDIS_ENCODING_RAW	简单动态字符串实现的字符串对象
REDIS_LIST	REDIS_ENCODING_ZIPLIST	压缩列表实现的列表对象
	REDIS_ENCODING_LINKEDLIST	双端链表实现的列表对象
REDIS_HASH	REDIS_ENCODING_ZIPLIST	压缩列表实现的哈希对象
	REDIS_ENCODING_HT	字典实现的哈希对象
REDIS_SET	REDIS_ENCODING_INTSET	整数集合实现的集合对象
	REDIS_ENCODING_HT	字典实现的集合对象
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	压缩列表实现的有序集合对象
	REDIS_ENCODING_SKIPLIST	跳表实现的有序集合对象

使用 OBJECT ENCODING 命令可以查看一个数据库键的编码：

redis> OBJECT ENCODING msg
"embstr"
redis> OBJECT ENCODING names
"ziplist"

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

编码常量	OBJECT ENCODING命令输出
REDIS_ENCODING_INT	“int”
REDIS_ENCODING_EMBSTR	“embstr”
REDIS_ENCODING_RAW	“raw”
REDIS_ENCODING_HT	“hashtable”
REDIS_ENCODING_LINKEDLIST	“linkedlist”
REDIS_ENCODING_ZIPLIST	“ziplist”
REDIS_ENCODING_INTSET	“intset”
REDIS_ENCODING_SKIPLIST	“skiplist”

通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，可以极大提升Redis的灵活性和效率，因为Redis可以根据不同的使用场景来为一个对象设定不同的编码，从而优化对象在某个场景的效率。比如，在列表对象包含的元素较少的时候，Redis使用压缩列表作为列表对象的编码：

• 因为压缩列表比双端列表更节约内存，并且在元素较少的时候，在内存中以连续块方式保存的压缩列表比起双端队列可以更快地被载入到缓存中；
• 随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失，对象就会将编码从压缩列表转换为功能更强、更适合保存大量元素的双端队列；

字符串对象

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

• int：如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整个整数值保存在字符串对象结构的ptr属性里面，并且将字符串对象的编码设置为int；
• embstr：如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值；
• raw：如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将字符串对象的编码设置为raw；

embstr编码是专门用来保存短字符串的一种优化编码方式，这种编码和raw编码一样，都使用redisObject结构和sdshdr结构，而embstr编码则通过一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr这2个结构，如下图：

使用embstr编码的字符串来保存短字符串有以下的好处：

• embstr编码将创建字符串对象所需的内存分配次数从raw编码的 2 次降低为 1 次；
• embstr编码将创建字符串对象只需要 1 次内存释放函数，而raw编码需要调用 2 次；
• 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串比起raw编码的字符串更够更好地利用缓存带来的优势；

编码的转换

int和embstr编码的字符串对象在条件满足的时候，会被转换为raw编码的字符串对象。如下：

redis> set number 10086
OK
redis> object encoding number
"int"
redis> append number " is a good number."
(integer) 23
redis> object encoding number
"raw"

注意，重新set一个字符串对象的话，就不是转换了，redis会重新创建一个字符串对象，并根据值设置相应的编码。如下：

redis> set number 10086
OK
redis> object encoding number
"int"
redis> set number "10086 is a good number."
OK
redis> object encoding number
"embstr"

另外，因为redis没有为embstr编码的字符串对象编写任何相应的修改程序（只有int编码和raw编码的字符串对象有这些程序），所以embstr编码的字符串对象实际上是只读的。当我们对embstr编码的字符串对象执行任何修改命令时，embstr编码的字符串在执行修改命令后，总会变为一个raw编码的字符串对象。如下：

redis> set msg "Hello Redis."
OK
redis> object encoding msg
"embstr"
redis> append msg " again!"
(integer) 19
redis> object encoding msg
"raw"

列表对象

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

• ziplist：当列表对象保存的所有字符串元素的长度都小宇64字节，并且保存的元素数量小宇512个时，列表对象采用ziplist编码；
• linkedlist：当列表对象不满足上面ziplist的条件时，就会使用linkedlist编码；

注意！ 使用ziplist编码的 2 个条件是可以修改的，具体查看配置文件中关于 list-max-ziplist-entries 和 list-max-ziplist-value选项的说明。

编码转换

对于使用ziplist编码的列表对象来说，当使用ziplist编码所需要的 2 个条件的任意一个不被满足时，对象的编码转换工作操作就会被执行，原本保存在ziplist里的所有元素都会被转移到linkedlist里面，对象的编码也会从ziplist变为linkedlist。

下面展示了列表对量因为保存了长度太大的元素而进行编码转换的情况：

redis> rpush blah "hello" "redis" "again"
(integer) 3
redis> object encoding blah
"ziplist"
redis> rpush blah "I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!"
(integer) 4
redis> object encoding blah
"linkedlist"

哈希对象

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

• ziplist：哈希对象保存的所有键值对的键和值的字符串长度都小于64字节，并且键值对的数量小于512个；
• hashtable：不满足ziplist条件时，哈希对象使用hashtable编码；

注意！使用ziplist编码的 2 个条件是可以修改的，具体查看配置文件中关于 hash-max-ziplist-entries 和 hash-max-ziplist-value选项的说明。

ziplist编码的哈希对象，每当有新的键值对加入到哈希对象的时候，程序会先将保存了键的ziplist节点push到ziplist的表尾，然后再将保存了值的ziplist节点push到ziplist表尾，因此：

• 保存了同一个键值对的 2 个节点总是紧挨在一起，保存了键的节点在前，保存了值的节点在后；
• 先添加到哈希对象中的键值对会被放在ziplist的表头方向，而后来添加到哈希对象中的键值对会被放到ziplist的表尾方向；

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

编码转换

对于使用ziplist编码的哈希对象来说，当使用ziplist编码所需的 2 个条件的任意一个不能被满足时，对象的编码转换就会被执行，原本保存在ziplist里面的所有键值对都会被转移并保存到字典里面，对象的编码也会从ziplist变为hashtable。

下面展示了哈希对象因为键值对的键长度太大而引起编码转换的情况：

redis> hset book name "Redis in Action."
(integer) 1
redis> object encoding book
"ziplist"
redis> hset book desc "I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!I'am archerda!"
(integer) 1
redis> object encoding book
"hashtable"

除了值的长度太长会引起编码转换外，键的长度太大也同样会引起编码转换。

集合对象

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

• intset：当集合对象保存的所有元素都是整数值，并且元素的数量不超过512个时，集合对象使用intset编码；
• hashtable：当不满足intset的 2 个条件时，集合对象使用hashtable编码；

注意！使用intset编码的条件是可以修改的，具体查看配置文件中关于 set-max-intset-entries 选项的说明。

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

有序集合对象

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

• ziplist：当有序集合对象保存的元素小于128个，并且保存的所有元素成员的长度都小于64字节的时候，有序集合将使用ziplist作为底层编码；
• skiplist：当不满足上面 2 个条件的任意一个时，有序集合将使用skiplist作为底层编码。

注意！使用ziplist编码的 2 个条件是可以修改的，具体查看配置文件中关于 zset-max-ziplist-entries 和 zset-max-ziplist-value选项的说明。

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

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

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

/*
 * 有序集合
 */
typedef struct zset {

    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;

    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;

} zset;

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

此外，zset结构的dict字典为有序集合创建了一个从成员到分值的映射，字典中每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用 O(1) 复杂度查找给定成员的分值，zscore命令就是根据这个特性实现的，而很多其他有序集合命令都在实现的内部用到了这个特性。

有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。值得一提的是，虽然zset结构同时使用skiplist和dict来保存有序集合的元素，但这 2 种数据结构都会通过指针来共享相同元素的成员和分值，所以不会产生任何重复的成员或者分值，也不会因此浪费额外的内存。

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

理论上，有序集合可以单独使用字典或者跳跃表的其中一个数据结构来实现，但是无论单独使用字典还是跳跃表，在性能上对比起同时使用都会有降低。比如说，如果我们只使用字典来实现有序集合，那么虽然可以以 O(1) 复杂度查找成员的分值，但是因为字典以无序的方式来保存集合元素，所以每次在执行范围操作的时候，程序都需要对字典保存的所有元素进行排序，完成这种排序至少需要 O(NlogN)的时间复杂度，以及额外的 O(N)的内存空间（因为要创建一个数组来保存排序后的元素）。

另一方面，如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点会被保留，但是因为没有了字典，所以根据成员查找分值这个操作的复杂度将从 O(1)升至 O(logN)。

综上，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表这 2 中数据结构来实现有序集合。

内存回收技术

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

每个对象的引用计数信息由redisObject的refcount属性记录：

typedef struct redisObject {

    // 引用计数
    int refcount;

    ...

} robj;

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

• 在创建一个新对象时，refcount会被初始化为1；
• 当对象被一个新程序使用时，它的refcount会被+1；
• 当对象不再被一个程序使用时，它的refcount会被-1；
• 当对象的refcount变为0的时候，对象所占用的内存会被释放。

对象共享技术

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

比如，键A创建了一个包含整数值100的字符串对象作为值对象，此时键B也要创建一个同样保存了整数值100到的字符串对象作为值对象，那么Redis会让键A和键B同时共享包含整数值100的那个字符串对象，并让其refcount的值+1。

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

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

注意！创建共享字符串对象的数量可以通过修改redis.h/REDIS_SHARED_INTEGERS 常量来修改。

下面是一个例子，可以看出A和B共享了对象。

redis> set A 100
OK
redis> object refcount A
(integer) 2
redis> set B 100
OK
redis> object refcount A
(integer) 3
redis> object refcount B
(integer) 3

为什么Redis不共享包含字符串的对象，而只共享包含整数值的对象？

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

• 如果共享对象是保存整数值的字符串对象，那么验证操作的复杂度为 O(1)；
• 如果共享对象是保存字符串值的字符串对象，那么验证操作的复杂度为O(N)；
• 如果共享对象是包含多个值（或者对象的）对象，比如列表对象或者哈希对象，那么验证的复杂度将会是 O(N^2)。

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

对象的空转时长

redisObject结构包含的最后一个属性为lru属性，该属性记录了对象最后一个被程序访问的时间：

typedef struct redisObject {

    // 对象最后一次被访问的时间
    unsigned lru:22; /* lru time (relative to server.lruclock) */

    ......

} robj;

OBJECT IDLETIME命令可以打印给定键的空转市场，这一空转时长就是通过将当前时间减去键的值对象的lru时间计算得出的：

redis> set msg hello
OK
redis> object idletime msg
(integer) 8
redis> object idletime msg
(integer) 13
redis> get msg
"hello"
redis> object idletime msg
(integer) 1

注意！OBJECT IDLETIME命令的实现是特殊的，这个命令在访问键的值对象时，不会修改值对象的lru属性。

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

参考文档

• Redis设计与实现（第二版）