对象

当称呼一个数据库键为"字符串键"、"列表键"时，指的是这个键对应的值为"字符串对象"、"列表对象"。

Redis并没有直接使用前面介绍的数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象（string）、列表对象（list）、哈希对象（hash）、集合对象（set）、有序集合对象（zset）。

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

1. 对象的类型与编码

Redis使用对象来表示数据库中的键和值。

Redis中的每个对象都由一个redisObject结构表示。该结构中和保存数据有关的三个属性分别是type、encoding、ptr。

typedef struct redisObject{

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 指向底层实现数据结构的指针
    void *ptr;

    // ...
}

1.1 类型

对象的type属性记录了对象的类型，这个属性可以是下面表格中的一个。

类型常量	对象的名称	TYPE命令的输出
REDIS_STRING	字符串对象	"string"
REDIS_LIST	列表对象	"list"
REDIS_HASH	哈希对象	"hash"
REDIS_SET	集合对象	"set"
REDIS_ZSET	有序集合对象	"zset"

Redis数据库的键总是字符串对象，值是上面表格中的一种。

当称呼一个数据库键为"字符串键"、"列表键"时，指的是这个键对应的值为"字符串对象"、"列表对象"。

TYPE命令返回的也是数据库键对应的值对象的类型。

1.2 编码和底层实现

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

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

编码常量	编码所对应的底层数据结构	OBJECT ENCODING命令输出
REDIS_ENCODING_INT	long类型的整数	"int"
REDIS_ENCODING_EMBSTR	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"

每种类型的对象都至少使用两种编码，下面是每种类型对象可使用的编码：

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT	使用整数值实现的字符串对象
REDIS_STRING	REDIS_ENCODING_EMBTR	使用embstr编码的简单动态字符串实现的字符串对象
REDIS_STRING	REDIS_ENCODING_RAW	使用简单动态字符串实现的字符串对象
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_SKIPLIST	使用跳跃表和字典实现的有序集合对象

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

2. 字符串对象

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

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

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

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

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

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

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

long double类型表示的浮点数在Redis中也是作为字符串值来保存的。如果要保存一个浮点数到字符串对象里面，那么程序会先将这个浮点数转换成字符串值，然后再保存转换所得的字符串值。在有需要时，程序会将保存在字符串对象里面的字符串值转换回浮点数值，执行某些操作，然后再将执行操作所得的浮点数值转换回字符串值，并继续保存在字符串对象里面。

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

值	编码
可以用long类型保存的整数	int
可以用long double类型保存的浮点数	embstr或raw
字符串值，或者因为长度太大而没办法用long类型表示的整数，又或者因为长度太大而没办法用long double类型表示的浮点数	embstr或raw

2.1 编码的转换

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

SET number 10086

APPEND number " is a good number"

Redis没有给embstr编码的字符串对象编写任何相应的修改程序，只有int、raw编码的字符串对象有这些程序。embstr编码的字符串对象实际上是只读的。embstr编码的字符串对象在执行修改命令之后，总会变成一个raw编码的字符串对象。

2.2 字符串命令的实现

字符串命令的实现

3. 列表对象

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

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

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

RPUSH numbers 1 "three" 5

上面numbers键的值对象使用ziplist编码，结构如下图。

ziplist编码的numbers列表对象

如果上面的numbers键的值对象使用linkedlist编码，结构如下图。

linkedlist编码的numbers列表对象

其中，下面是上图中使用的简化字符串对象表示。

简化的字符串对象表示

下图是上面简图的完整表示

完整的字符串对象表示

3.1 编码转换

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

1. 列表对象保存的所有字符串元素的长度都小于64字节。
2. 列表对象保存的元素数量小于512个。

不能满足上面两个条件的列表对象使用linkedlist编码。

另外，上面两个条件的上限值是可以修改的，是配置文件中的list-max-ziplist-value、list-max-ziplist-entries。

3.2 列表命令的实现

[图片上传失败...(image-afe8b9-1582442860908)]

4. 哈希对象

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

ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾。于是：

1. 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后。
2. 先添加到哈希对象中的键值对会被放在压缩列表的表头方向，后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

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

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

HSET profile name "Tom"
HSET profile age 25
HSET profile career "Programer"

上面，profile是用ziplist编码实现，如下图

ziplist编码的profile哈希对象

如果，用hashtable实现profile，会是下面这样：

hashtable编码的profile哈希对象

4.1 编码转换

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

1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节。
2. 哈希对象保存的键值对数量小于512个。

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

另外，上面两个条件的上限值是可以修改的，是配置文件中的hash-max-ziplist-value、hash-max-ziplist-entries。

4.2 哈希命令的实现

哈希命令的实现

5. 集合对象

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

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

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

SAD Dfruits "apple" "banana" "cherry"

下图是两种编码表示的集合对象：

两种编码表示的集合对象

5.1 编码转换

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

1. 集合对象保存的所有元素都是整数值
2. 集合对象保存的元素数量不超过512个

不能满足上面两个条件的集合对象使用hashtable编码。

上面第二个条件的上限值可以通过set-max-intset-entries修改。

5.2 集合命令的实现

集合命令的实现

6. 有序集合对象

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

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

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

ZADD price 8.5 apple 5.0 banana 6.0 cherry

ziplist编码的有序集合对象

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

typedef struct zset{

    zskiplist *zsl;

    dict *dict;
}zset;

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

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

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

理论上，有序集合可以单独使用字典和跳跃表的其中一种数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低：

1. 如，只使用字典来实现有序集合，虽然以O(1)复杂度查找成员的分值这一特性会被保留，但是，因为字典以无序的方式来保存集合元素，所以每次在执行范围型操作——如ZRANK、ZRANGE等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少O(NlogN)时间复杂度，以及额外O(N)内存空间。
2. 如，只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值的这一操作的复杂度将从O(1)上升为O(logN)。

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

如果上述price集合对象使用skiplist编码，那么如下图所示。

skiplist编码的有序集合对象

上图在字典和跳跃表中重复展示了各个元素的成员和分值，但在实际中，字典和跳跃表会共享元素的成员和分值，所以并不会造成任何数据重复，也不会因此而浪费任何内存。

6.1 编码转换

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

1. 有序集合保存的元素数量小于128个。
2. 有序集合保存的所有元素成员的长度都小于64字节。

不能同时满足以上两个条件的有序集合对象将使用skiplist编码。

以上两个条件的上限值可以通过zset-max-ziplist-entries和zset-max-ziplist-value来设置。

6.2 有序集合命令的实现

有序集合命令的实现方法

7. 类型检查与命令多态

Redis中用于操作键的命令基本上可以分为两类：

1. 其中一种命令可以对任何类型的键执行，如DEL、EXPIRE、RENAME、TYPE、OBJECT。
2. 另一种命令只能对特定类型的键执行，如
   • SET、GET、APPEND、STRLEN等命令只能对字符串键执行。
   • HDEL、HSET、HGET、HLEN等命令只能对哈希键执行。
   • RPUSH、LPOP、LINSERT、LLEN等命令只能对列表键执行。
   • SADD、SPOP、SINTER、SCARD等命令只能对集合键执行。
   • ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执行。

7.1 类型检查的实现

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

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

1. 在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型，如果是，服务器就对键执行指定的命令。
2. 否则，服务器将拒绝执行命令，并向客户端返回一个类型错误。

7.2 多态命令的实现

Redis还会根据值对象的编码方式，选择正确的命令实现代码来执行命令。

8. 内存回收

C语言不具备自动回收内存的功能，Redis在自己的对象系统中构建了引用计数技术实现的内存回收机制。

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

typedef truct redisObject{

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

    // ...
} robj;

对象的引用计数信息的变化情况：

1. 在创建一个新对象时，引用计数的值会被初始化为1。
2. 当对象被一个新程序使用时，引用计数增1。
3. 当对象不再被一个新程序使用时，引用计数减1。
4. 当对象的引用计数值变为0时，对象所占用的内存会释放。

下图是修改对象引用计数的API。

修改对象引用计数的API

对象的整个生命周期分为创建对象、操作对象、释放对象三个阶段，下面是一个字符串对象从创建到释放的过程。

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

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

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

9. 对象共享

对象的引用计数还带有对象共享的作用。如下图是被共享的字符串对象。

被共享的字符串对象

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

1. 将数据库键的值指针指向一个现有的值对象。
2. 将被共享的值对象的引用计数增1。

目前来说，Redis会在初始化服务器时，创建0——9999这一万个字符串对象，服务器会使用这些共享对象，不再创建新对象。可以修改redis.h/REDIS_SHARED_INTEGERS常量来修改创建的共享这些包含整数值的字符串对象的数量。

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

Redis只对包含整数值的字符串对象进行共享，因为：

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

上面说的验证操作指的是Redis要比较需要创建的新对象与已经存在的对象的值是否相同。

10. 对象的空转时长

redisObject结构中的lru属性记录了对象最后一次被命令程序访问的时间。

typedef struct redisObject{

    // ...

    unsigned lru:22;

    // ...
} robj;

OBJECT IDLETIME可以打印给定键的空转时长，通过计算当前时间减去键的值对象的lru时间得出。

OBJECT IDLETIME不会修改值对象的lru属性。

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