关于后端: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。

如果想获取更多相干文章，可扫码关注浏览：