Redis对象

Redis用到的主要数据结构，如简单动态字符串、双端链表、字典、压缩列表、整数集合等。Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象。

1 对象的类型和编码

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

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

1.1 类型

对象的type属性记录了对象的类型，使用type key命令可以查看键的类型：

127.0.0.1:6379> set msg redis
OK

127.0.0.1:6379> type msg
string

下表表示redisObject中type的值，和对应type命令的输出值

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

1.1 编码和底层实现

对象的ptr指针指向对象的底层数据结构，而这些数据结构是由对象的encoding属性决定。下图表示不同的类型和对应编码的关系

编码常量	编码所对应的底层数据结构
REIDS_ENCODING_INT	long类型的整数
REIDS_ENCODING_EMBSTR	embstr编码的简单动态字符串
REIDS_ENCODING_RAW	简单动态字符串
REIDS_ENCODING_HT	字典
REIDS_ENCODING_LINKEDLIST	双端链表
REIDS_ENCODING_ZIPLIST	压缩列表
REIDS_ENCODING_INTSET	整数集合
REIDS_ENCODING_SKIPLIST	跳跃表和字典

注：Redis3.2版本提供了quicklist内部编码，它是一个以ziplist为节点的linkedlist，它结合了ziplist和linkedlist两者的优势。

可以使用object encoding key命令查看key的内部编码。

127.0.0.1:6379> object encoding msg
"embstr"

2 字符串对象

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

2.1 int

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象使用int编码来保存这个整数。

127.0.0.1:6379> set num 10086
OK

127.0.0.1:6379> object encoding num
"int"

2.2 embstr和raw

(2) 如果字符串对象保存的是一个字符串值，并且这个字符串的长度大于44字节（Redis version 3.2.100版本，不同版本可能不同），那么字符串对象使用一个简单动态字符串（SDS）来保存这个字符串，相应的编码为raw。反之，如果字符串长度小于44字节，则使用embstr编码的简单动态字符串保存这个值，相应的编码为embstr。

127.0.0.1:6379> set msg redis
OK

127.0.0.1:6379> object encoding msg
"embstr"

127.0.0.1:6379> set str longstringlonglongstringlonglongstringlonglongstringlong
OK

127.0.0.1:6379> strlen str
(integer) 56

127.0.0.1:6379> object encoding str
"raw"

2.3 embstr编码和raw编码的区别

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

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

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

2.4 编码的转换

int编码和embstr编码的字符串对象在条件满足的情况下回被转换成raw编码的字符串对象。
(1) 对于int编码的字符串，如果执行一些命令，使得这个对象保存的不再是整数值，而是一个字符串，那么字符串对象的编码会从int转换为raw。

127.0.0.1:6379> set num 1
OK

127.0.0.1:6379> get num
"1"

127.0.0.1:6379> object encoding num
"int"

127.0.0.1:6379> append num a
(integer) 2

127.0.0.1:6379> get num
"1a"

127.0.0.1:6379> object encoding num
"raw"

(2) 同理，embstr编码的字符串对象在执行APPEND命令追加后，无论字符串的长度是否超过限值（44字节），都会转换为raw。

127.0.0.1:6379> set msg redis
OK

127.0.0.1:6379> object encoding msg
"embstr"

127.0.0.1:6379> append msg mysql
(integer) 10

127.0.0.1:6379> object encoding msg
"raw"

这是因为Redis没有为embstr编码的字符串对象编写任何相应的修改程序（只有int编码和raw编码的字符串有这些程序），所以embstr编码的字符串对象是只读的。所以当对一个embstr编码的字符串对象执行任何修改操作时，程序都是先将对象的编码从embstr转换为raw编码，然后再执行修改命令*。

3 列表对象

列表对象的编码可以是ziplist和linkedlist（Redis 3.2版本之前）。之后的版本使用的是quicklist编码。

3.1 ziplist

ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩节点保存了一个列表元素。例如，执行以下命令：

127.0.0.1:6379> lpush numbers 1 three 5
(integer) 3

如果使用的ziplist编码，这个对象的结构如下：

ziplist编码的numbers列表对象

3.2 linkedlist

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

linkedlist编码的numbers列表对象

编码转换：

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

当同时满足以上两个条件时，列表对象使用ziplist编码，而以上两个条件任意一个不满足时，使用linkedlist来编码。

3.3 linkedlist

由于ziplist数据结构需要连续的内存进行存储，所以对于列表个数较多或者元素字节过大就需要较大的连续内存。linkedlist由于链表附加的内存空间相对较高，并且每个节点都要分配独立的空间，加速了内存的碎片化。所以quicklist综合了两者的优点，quicklist是一个以ziplist为节点的linkedlist。它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。（注：图片出处）

4 哈希对象

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

4.1 ziplist

ziplist编码的哈希对象使用压缩列表作为底层实现，当有新的键值对加入哈希对象时：

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

例如，执行以下命令：

127.0.0.1:6379> hset user name tom
(integer) 1

127.0.0.1:6379> hset user age 22
(integer) 1

127.0.0.1:6379> hset user sex man
(integer) 1

那么ziplist编码保存的对象如下图所示

4.2 hashtable

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

4.3 编码转换

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

同时满足上面两个条件的哈希对象会使用ziplist编码，任意一个不满足时使用hashtable编码。

127.0.0.1:6379> object encoding user
"ziplist"
127.0.0.1:6379> hset user descrption oooooooooooooooooooooooooooooooooooooooooooooooooo
oooooooooooooooooooooooo
(integer) 1
127.0.0.1:6379> object encoding user
"hashtable"

5 集合对象

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

127.0.0.1:6379> sadd nums 1 2 3
(integer) 3

hashtable编码的集合对象使用字典作为底层实现，字典中的每个键都以个字符串对象。

127.0.0.1:6379> sadd fruits cherry apple bnana
(integer) 3

编码转换

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

同时满足上面两个条件的集合对象会使用intset编码，任意一个不满足时使用hashtable编码。

6 有序集合对象

有序集合对象可以是ziplist或者skiplist

6.1 ziplist

ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存的元素的成员，而第二个元素保存元素的分值。
压缩列表内的集合元素按分值从小到大进行排序，分值较小的在表头方向，分值较大的在表尾方向。

127.0.0.1:6379> zadd price 8.5 apple 5.0 bnana 6.0 cherry
(integer) 3

6.2 skiplist

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

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

zset结构中的zkl跳跃表按照分值从小到大保存了所有集合元素，每个跳跃表节点保存了一个集合元素：跳跃表节点的object属性保存了元素的成员，而跳跃表节点score属性则保存了元素的分值。
zset结构的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值保存了元素的分值。通过这个字典可以用O(1)的复杂度查找给定成员的分值。

注：虽然zset结构同时使用跳跃表和字典保存有序集合元素，但是这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存这两种数据结构不会产生任何重复成员或者分值，也不会浪费额外的内存。

为什么使用两种数据结构实现有序集合？
(1) 仅使用字典实现有序集合，虽然可以以O(1)复杂度查找成员的分值，但是对于范围操作，由于字典是无序的，所以需要排序，完成排序复杂度至少为O(NlogN)时间复杂度，以及额外的内存空间。
(2) 仅使用跳跃表实现有序集合，虽然可以执行范围操作，但是查找某个成员的分值，时间复杂度就为O(logN)。
所以，使用两种字典和跳跃表两种数据结构实现有序集合，综合了两种数据结构的优点，提高了性能。

6.3 编码的转换

(1) 有序集合保存的元素小于128个。
(2) 有序集合保存的所有的元素都小于64个字节。

同时满足上面两个条件的有序集合对象会使用ziplist编码，任意一个不满足时使用skiplist编码。

127.0.0.1:6379> object encoding price
"ziplist"

127.0.0.1:6379> zadd price 10 oooooooooooooooooooooooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooooo
(integer) 1

127.0.0.1:6379> object encoding price
"skiplist"

7 内存回收

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

// 引用计数
int refcount;
} robj
对象引用计数信息会随着对象的使用状态不断而变化：

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

8 对象共享

除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用。
假设键A创建了一个包含整数值100的字符串对象作为值对象，如果这时键B也要创建一个同样保存了整数值100的字符串对象作为值对象，那么Redis会让A和B共享这个字符串对象。通过这种方式可以节省内存。

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

127.0.0.1:6379> set num 999
OK

127.0.0.1:6379> object refcount num
(integer) 2

9 对象空转的时长

redisObject除了type、encoding、ptr、refcount四个属性外，还有一个lru属性，它记录了对象最后一次被命令程序访问的时间。
OBJECT IDLETIME命令可以打印给定键的空转时长（单位：s），这个时长是通过当前时间减去键对象的lru时间计算出。

127.0.0.1:6379> set message hello
OK

127.0.0.1:6379> object idletime message
(integer) 14

127.0.0.1:6379> object idletime message
(integer) 22

127.0.0.1:6379> object idletime price
(integer) 1183

10 小结

(1) Redis数据库中每个键值对都是一个对象。
(2) Redis共有字符串、列表、哈希、集合、有序集合五种类型的对象，每种类型的对象至少都有两种或以上的编码方式，不同的编码可以在不同的使用场景上优化对象的使用效率。
(3) Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，该对象所占用的内存就会被自动释放。
(4) Redis会共享值为0到9999的字符串对象。
(5) 对象会记录自己的最后一次被访问的时间，这个时间可以用于计算对象的空转时间。
本文完

z注：本文参考《Redis设计与实现》，如发现错误，请指正！