Redis数据结构八之各对象对应的底层实现

本文首发于公众号：Hunter后端

原文链接：Redis数据结构八之各对象对应的底层实现

本篇笔记介绍各对象及其编码和底层实现结构。

一个对象的结构如下：

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

type 属性用于表示这个对象的类型，比如 string，list，hash，set，zset 分别表示字符串对象，列表对象，哈希对象，集合对象和有序集合对象。

encoding 属性则表示该对象使用的编码

ptr 则是指向底层的指针

1、 字符串对象

字符串对象的编码有三种，int、embstr 和 raw

1. int

如果字符串对象保存的是整数值，并且这个整数值可以用 long 类型来表示，那么字符串对象会将整数值保存到对象的 ptr 属性里，且将编码设置为 int。

例如我们执行：

set number 123

object encoding number
# "int"

执行下面的命令返回的就是 number 的编码，为 int

2. embstr

在 Redis 3.2 版本之前，如果字符串保存的是一个字符串值，且这个字符串值的长度小于等于 39 字节，那么字符串对象会使用 embstr 编码的方式来保存。

但是我使用 Redis 7.0.11 版本测试的时候，这个值已经变成了 44，也就是说字符串值的长度小于等于 44 字节时，会使用 embstr 来编码，否则使用 raw 编码。

set embstr_str "this is a long long long long long story"

object encoding embstr_str
# "embstr"

3. raw

当我们设置的字符串值的长度大于 44 字节时，字符串对象会使用 raw 编码保存

set raw_str "this is a long long long long long long story"
object encoding raw_str

# "raw"

4. embstr 编码的好处

embstr 编码是专门用于保存短字符串的一种优化编码方式，这种编码和 raw 编码一样都使用 redisObject 结构和 sdshdr 结构来表示字符串对象。

但 raw 编码会调用两次内存分配来分别创建 redisObject 和 sdshdr 结构，而 embstr 编码则调用一次内存分配函数来分配一块连续的空间，依次包含 redisObject 和 sdshdr 两个结构。

使用 embstr 编码的好处如下：

• 创建字符串对象的时候内存分配次数从 raw 编码的两次降低为一次
• 释放 embstr 编码的字符串对象只需要调用一次内存释放函数，而 raw 编码的字符串对象需要调用两次内存释放函数
• embstr 编码的字符串对象的所有数据都保存在一块连续的内存里，所以比 raw 编码的字符串对象能更好地利用缓存带来的优势

5. 各类型值的编码方式

如果保存的是一个浮点数，在 Redis 中也是以字符串值来保存的，比如：

set pi 3.14
object encodng pi
# "embstr"

在有需要的时候，比如对 pi 进行运算的时候，程序会将这个字符串值转换回浮点数值，执行运算之后，再将其转换回字符串值保存，比如：

incrbyfloat pi 2

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

6. 编码的转换

对于 int 编码的整数来说，如果我们对其进行了数值上的操作，比如 incr 等，它仍然是一个 int 编码。

但是如果对其操作之后使其变成了字符串值，那么它的编码会变成 raw，比如通过 append 命令向其追加字符串：

set a 1
object encoding a
# "int"

append a " hello"
object encoding a
# "raw"

程序执行逻辑是先将其转换成字符串值，然后进行追加操作。

虽然追加字符串值之后，它的长度并没有超过 44 字节，但是 Redis 没有为 embstr 编码的字符串对象编写任何修改程序（只有 int 和 raw 编码的字符串对象有），所以对 int 或者 embstr 执行 append 这种修改逻辑之后，它的编码总是会变成 raw。

2、 列表对象

Redis 3.2 版本之前，列表对象的底层实现是由 ziplist 或者 双向链表实现的。

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

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

以上两个条件任一不被满足，列表对象就会使用双向链表的方式存储列表数据。

而在 Redis 3.2 版本之后，列表对象的底层实现就变成了 quicklist。

Redis 7.0 版本中，quicklist 的结构是双向链表和 listpack 的混合结构，quicklist 拥有多个 quicklistNode 节点，其节点下是 listpack 结构保存多个元素。

3、哈希对象

Redis 7.0 版本之前，哈希对象的底层实现用的是 ziplist 和 字典。

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

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

当上面两个条件任一不被满足，哈希对象就会使用字典作为编码。

接下来我们测试一下：

hset book name "this is short name"
object encoding book
# "ziplist"

hset book name "this is a long long long long long long long long long long long long"
object encoding book
# "hashtable"

注意：这里我们测试的是将 name 的 value 值设置长度大于 64 字节，如果我们将 name 替换成一个大于 64 字节的 key，同样会引起底层结构变成字典。

Redis 7.0 版本已经正式对 ziplist 进行了替换，所以哈希对象的底层实现变成了 listpack 和字典

4、集合对象

集合对象的编码可以是 intset 或者 hashtable，由整数集合或者字典构成。

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

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

接下来我们进行一个测试：

sadd set_test 1 2 3
object encoding set_test
# "intset"

sadd set_test "Python"
object encoding set_test
# "hashtable"

因为哈希表节点是 key-value 结构，所以当使用字典结构保存集合的时候，字典的 value 全部被设为 NULL。

5、有序集合对象

Redis 7.0 版本以前，有序集合的编码是 ziplist 或 skiplist。

底层实现是压缩列表或者跳跃表。

但是底层实现是跳跃表的时候，为了查询更方便，并不仅仅使用跳跃表结构，还是用了字典进行辅助查询，这个我们后面细讲。

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

• 有序集合保存的元素成员长度小于 128 个
• 有序集合保存的所有元素成员的长度都小于 64 字节

我们来测试一下长度的变化引起编码的改变：

zadd zset_test 1.2 name
object encoding zset_test
# "ziplist"

zadd zset_test 2.1 long_long_long_long_long_long_long_long_long_long_long_long_long_name 
# "skiplist"

当有序集合对象使用的是压缩列表作为底层实现时，每个集合元素使用两个紧挨在一起的压缩列表节点保存，第一个节点保存元素的成员（member），第二个元素保存元素的分值（score），且按照分值从小到大进行排序，分值较小的元素被放置在靠近表头的位置，分值较大的被放置在靠近表尾的位置。

假设我们创建的下面这个数据：

zadd price 8.5 apple 5.0 banana 6.0 cherry

那么在 ziplist 中保存的结构如下所示：

| zlbytes | zltail | zllen | "banana" | 5.0 | "cherry" | 6.0 | "apple" | 8.5 | zlend |

当有序集合对象的的编码是 skiplist 时，它的底层实现是 zset，一个 zset 结构同时包含一个字典和一个跳跃表，如下：

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

其中，dict 字典创建了一个从成员到分值的映射，zskiplist 跳跃表则按照分值从小到大保存了所有集合元素，示意图如下：

为什么会用两个结构来保存有序集合对象呢？

因为方便，如果需要对有序集合进行范围查找，比如ZRANK、ZRANGE，可以基于跳跃表 API 进行查询，如果要查询给定成员的分值，可以用 dict 结构。

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

Redis 7.0 版本之后，有序集合底层的 ziplist 也被替换成了 listpack。