本文首发于公众号: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 123object 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.14object 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 1object encoding a# "int"append a " hello"object encoding a# "raw"

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

尽管追加字符串值之后,它的长度并没有超过 44 字节,然而 Redis 没有为 embstr 编码的字符串对象编写任何批改程序(只有 intraw 编码的字符串对象有),所以对 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 3object 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 nameobject 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。

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