likes
comments
collection
share

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

作者站长头像
站长
· 阅读数 29

本文首发于公众号：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

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

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

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 跳跃表则按照分值从小到大保存了所有集合元素，示意图如下：

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

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

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

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

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

转载自:https://juejin.cn/post/7248599585736114213
评论
请登录