乐趣区

关于后端:Redis数据结构八之各对象对应的底层实现

jiezi

本文首发于公众号：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 跳跃表则依照分值从小到大保留了所有汇合元素，示意图如下：

为什么会用两个构造来保留有序汇合对象呢？

因为不便，如果须要对有序汇合进行范畴查找，比方 ZRANK、ZRANGE，能够基于跳跃表 API 进行查问，如果要查问给定成员的分值，能够用 dict 构造。

上图中，为了展现不便，字典和跳跃表反复展现了各个元素的成员和分值，但在理论中，字典和跳跃表会共享元素的成员和分值，所以并不会任何数据的反复，也不会因而而节约任何内存。

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

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

退出移动版