likes
comments
collection
share

Redis 基本数据类型深度历险记

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

一步一步探索 Redis 基本数据类型的奥秘

前言

Redis 是一款内存数据库，可以作为缓存、向量数据库、文档数据库、实时处理引擎，甚至是消息队列

挺拔的山峰之下，往往有坚固的基石。Redis 也是如此，Redis 功能强大，这离不开底层精心设计的数据类型

一、初探基本数据结构

Redis 的基本数据类型有以下 5 种

  • Strings - 字符串
  • Lists - 列表
  • Sets - 集合
  • Hashes - 哈希
  • Sorted Set(zset) - 有序集合

从 Redis1.1 才开始支持 Sorted Set，从 Redis2.0 才开始支持 Hashes 数据类型，到目前的 Redis7.2，基本数据类型还是这 5 种

Redis 基本数据类型深度历险记

用一张示例图描述 5 种基本数据类型 Redis 基本数据类型深度历险记

二、再探基本数据结构

本着一探究竟的心态，翻看了 Redis 的文档和一些源码。Redis 是用 C 语言实现的，接下来尽量用通俗易懂的语言和插图来记录探索过程

Redis 中的一个重要数据结构是 redisObject，Redis3.2 版本前，定义在 src/redis.h 文件中；Redis3.2 版本后，定义在 src/sesrver.h文件中。 redisObject 可以表示 Redis 的其他数据结构

typedef struct redisObject {
    unsigned type:4;
    unsigned storage:2;
    unsigned encoding:4;
    unsigned lru:22;
    int refcount;
    void *ptr;
} robj;

Redis src/object.c 文件中定义了按类型创建对象的各种方法，如创建 Strings, Lists, Sets

Strings

先从最简单的数据结构 Strings 入手，也就是字符串，所有的 key 都是字符串

SDS

Redis 字符串基于 antirez 自研的 SDS(Simple Dynamic Strings)，SDS 非常高效，使用简单，并且兼容原生 C 字符串方法

SDS 在设计上与 C 语言的字符串不同，每个 SDS 字符串有一个前缀(Header)，并且以 Null term 为结束标志，如下图所示

Redis 基本数据类型深度历险记

其中 SDS Header 定义如下

struct sdshdr {
    int len;
    int free;
    char buf[];
};

细化后的结构图如下

Redis 基本数据类型深度历险记

字符串编码方式

在 Redis3.0 之前，字符串只支持 RAW 编码方式，从 Redis3.0 开始，新增了 EMBSTR 编码方式，EMBSTR 即 Embedded String

当字符串对象保存的是短字符串（长度小于 OBJ_ENCODING_EMBSTR_SIZE_LIMIT，最开始是 39，Redis3.2 扩大为 44）时，Redis 会使用 EMBSTR 编码，该编码方式使用了前面介绍的 SDS。这种编码的特点是将对象头和实际的字符串值分配在同一块连续的内存中，这可以减少内存碎片，并提高内存利用率和访问速度

这种编码的字符串对象在修改时有一定的限制，由于对象头和字符串值是连续存储的，如果要对字符串进行修改（如追加字符），可能会导致原有的内存空间不足以容纳新的字符串，这时 Redis 可能需要重新分配内存空间，并可能导致对象从 EMBSTR 编码转换为 RAW 编码

相关源码，基于 Redis.7.2

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

限制

默认配置下，单个字符串对象的值最大为 512M

Lists

Lists 是双向列表，支持从两端增删元素

ziplist

Redis 早期的 Lists 底层实现是 ziplist，即压缩列表，是一种特殊的双向链表。ziplist 可以存储字符串或整数，以紧凑的数据结构存储在连续的内存块中，元素之间没有指针，内存使用率非常高

内存分布

由于 ziplist 直接存储在连续内存块中，并没有定义结构体，其内存分布图如下 Redis 基本数据类型深度历险记 各个部分详情如下表所示

内存分布属性长度描述
zlbytes4 字节整个 ziplist 在内存中占用的字节数
zltail4 字节最后一个元素的偏移量，便于从尾部开始操作
zllen2 字节ziplist 元素个数，最大值为UINT16_MAX(65534)，如果超过这个值，这里只会保存为 65535，真正的个数需要遍历整个列表才能算出来
entry不固定连续存储的 0-n 个节点
zlend1 字节特殊值 0xFF，ziplist 的结束标志

接下来探索 ziplist 中的元素，也就是 entry Redis 基本数据类型深度历险记

  • prevlen为前一个 entry 占用的字节数，这是为了从尾部往前遍历时，快速定位前一个 entry，这是 ziplist 没有指针也能实现双向列表的原因。占 1 个或 5 个字节

    • 如果前一个 entry 长度小于 254 字节，只用一个字节来保存长度
    • 如果前一个 entry 长度大于或等于 254 字节，用5 个字节保存长度，第 1 个字节固定为 0xFE，后 4 个字节为真实长度

  • encoding 是类型编码，记录 entry-data 的类型及其长度

  • entry-data 大部分情况下存储实际数据，但部分情况下，可以没有 entry-data

先从 encoding 入手继续深入探索，前面已经介绍过，ziplist 既可以存储字符串，也可以存储整数

  • 存储字符串
    • encoding 由 00、01、10 开头，则 entry 保存的是字符串，encoding 分别占 1、2、5 个字节
  • 存储整数
    • encoding 由 11 开头，则 entry 保存的是整数。这种情况下，encoding 只占 1 个字节

字符串 encoding 详情如下表所示

编码前缀编码模式编码长度字符串长度描述
0000p{6}1 字节[0, 26−12^{6} - 126−1] 字节6 位无符号数，p{6} 表示 6 个 p
0101p{6}q{8}2 字节[262^626, 214−12^{14} - 1214−1] 字节14 位，Big Endian 存储
10100{6}q{8}r{8}s{8}t{8}5 字节[2142^{14}214, 232−12^{32} - 1232−1] 字节32 位，Big Endian 存储

整数 encoding 详情如下表所示

编码模式编码长度整数类型整数长度描述
110000001 字节int16_t2 字节
110100001 字节int32_t4 字节
111000001 字节int64_t8 字节
111100001 字节24bit signed3 字节
111111101 字节8bit signed1 字节
1111xxxx1 字节4 位xxxx 处直接填充数值，0001~1101，减 1 后即为实际值

整数编码为 1111xxxx 时，entry-data 可以不存在，此时 entry 的值为 xxxx - 1 表示的十进制数

ziplist 局限性

初始化 ziplist

unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    
    /* Big Endian 处理 */
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

初始化时，只分配了除 entry 以外的内存

新增元素

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    /* 其他代码 ... */
    newlen = curlen+reqlen+nextdiff;
    zl = ziplistResize(zl,newlen);
    /* 其他代码 ... */
}

unsigned char *ziplistResize(unsigned char *zl, size_t len) {
    assert(len < UINT32_MAX);
    zl = zrealloc(zl,len);
    ZIPLIST_BYTES(zl) = intrev32ifbe(len);
    zl[len-1] = ZIP_END;
    return zl;
}

ziplist 在新增元素时，会调用 zrealloc(zl, len) 重新分配内存，此外，其他写操作也会重新分配内存。因此，ziplist 只适用于元素个数不多的场景

在 Redis 的早期版本，还没有 quicklist，对于元素个数很多的 Lists，使用 linkedlist（类似于 Java 的 LinkedList），相关代码位于 src/adlist.c

quicklist

ziplist 内存使用率很高，但在频繁进行元素增删操作的场景下，每次重新分配内存会加重 Redis 的整体负担。此外，ziplist 还可能出现连锁更新问题。为了改善 Lists 性能，Redis3.2 引入了 quicklist，将 ziplist 和普通的双向链表结合起来

先看一下 Redis6.0 中 quicklist 定义，位于 quicklist.h 中

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;
    unsigned long len;
    signed int fill : QL_FILL_BITS;
    unsigned int compress : QL_COMP_BITS;
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
属性描述
head头节点指针
tail尾节点指针
count所有 ziplist/listpack 中 entry 的总数量
lenquicklistNode 数量
fill每个 quicklistNode 中 entry 的最大数量
compress压缩深度。0，表示所有节点都未压缩；大于 0，表示从两端开始有多少个节点未压缩
bookmark_countbookmarks 数组的大小，Redis6.0 新增
bookmarksquicklistBookmark 数组，当 quicklist 节点非常多（上千）时使用。Redis6.0 新增

Redis6.0 quicklistNode 定义

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;
    unsigned int count : 16;
    unsigned int encoding : 2;
    unsigned int container : 2;
    unsigned int recompress : 1;
    unsigned int attempted_compress : 1;
    unsigned int extra : 9;
} quicklistNode;
属性描述
prev前一个 quicklistNode 节点指针
next后一个 quicklistNode 节点指针
zl节点未压缩时，指向 ziplist；节点压缩时，指向 quicklistLZF
szziplist 总字节数
countziplist 中包含的节点数量
encoding节点数据类型编码。RAW==1，LZF==2
containerNONE==1，ZIPLIST==2
recompressbool 类型，该节点之前是否压缩过。如果为 true，表示节点被临时解压缩以便使用
attempted_compressbool 类型，测试时使用
extra暂未使用，预留

quicklist, quicklistNode, ziplist, quicklistLZF 之间的关系如下图所示 Redis 基本数据类型深度历险记

其中 quicklistLZF 使用 LZF 无损压缩算法实现，其结构如下

typedef struct quicklistLZF {
    unsigned int sz;
    char compressed[];
} quicklistLZF;

listpack

Redis5.0 引入了 listpack 数据结构，作为 Streams 类型的底层数据结构的一部分。Redis6.0 将 listpack 作为 Hashes 类型的底层数据结构的一部分。Redis7.0 将 listpack 作为 Lists 类型的底层数据结构的一部分

listpack 即紧凑列表，其数据结构与 ziplist 相似，但解决了 ziplist 的连锁更新问题

listpack 发挥的作用越来越大，接下来就深入探索一下。listpack 相关的代码位于 src/listpack.c 中

#define LP_HDR_SIZE 6
#define LP_EOF 0xFF
unsigned char *lpNew(size_t capacity) {
    unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : LP_HDR_SIZE+1);
    if (lp == NULL) return NULL;
    lpSetTotalBytes(lp,LP_HDR_SIZE+1);
    lpSetNumElements(lp,0);
    lp[LP_HDR_SIZE] = LP_EOF;
    return lp;
}

初始化 listpack 时，只分配了 HEADER(6 字节，4 字节表示总长度 + 2 字节表示元素个数) 和结束标志的内存，可以看到，没有指向最后一个元素的偏移量了 Redis 基本数据类型深度历险记

虚拟属性描述
lpbyteslistpack 在内存中的占用的总长度，单位为 byte
lplenlistpack 中元素个数
entry0～n 个元素
lpendlistpack 的结束标志，固定值 0xFF

listpack 中的单个元素 entry，可以存储字符串或者整数，每个 entry 由 3部分 组成 Redis 基本数据类型深度历险记 与 ziplist entry 不同的是，listpack entry 不是保存前一个 entry 长度，而是保存的自身除去 element-length 以外的长度。同样地，element-data 可能不存在

encoding 支持多种编码方式，以优化空间使用。对于小整数，使用一种紧凑的编码方式，直接在 encoding 中存储整数值，element-data 不存在。对于大整数或字符串，使用更通用的编码方式

限制

Redis Lists 的元素个数最大为 232−12^{32} - 1232−1

Sets

Redis7.2 以前，Sets 底层可能使用 intset 或者 hashtable。Redis 2.4 以前还会使用 zipmap，这将在介绍 Hashes 类型时简单介绍

Redis7.2 及以后，Sets 底层可能使用 intset，listpack 或者 hashtable 数据结构

intset

先看看 intset 结构体定义，位于 src/intset.h 中

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

其中，encoding 为编码，用于区分 int16, int32, int64 等不同数据类型，Redis 会将存储的数据中最大的整数的类型作为 encoding

虽然 Sets 类型不含重复元素，且不保证元素之间的顺序，但如果底层使用的 intset 数据结构，则元素之间是有序的

hashtable

在 redis7.2 以前，当满足以下条件时，Sets 底层转换为 hashtable 结构

  • intset 中的元素个数大于 set_max_intset_entries，默认为 512
  • intset 中加入了字符串元素

hashtable 的定义位于 src/dict.h 和 src/dict.c 中，Redis7.2

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
    void *metadata[];
};

struct dict {
    dictType *type;
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    long rehashidx;
    int16_t pauserehash;
    signed char ht_size_exp[2];
    void *metadata[];
};

可以看到，dict 结构中的 ht_table[2] 大小为 2，即有 2 个 dictEntry 实例，这是为了扩容时，需要将之前的数据拷贝到新的内存，然后执行 rehash 操作

listpack

在 Redis7.2 及以后，当满足以下条件时，Sets 底层转换为 listpack 结构

  • intset 中的元素个数大于 set_max_intset_entries，默认为 512
  • intset 中加入了字符串元素

在 Redis7.2 及以后，当满足以下条件时，Sets 底层由 listpack 转换为 hashtable 结构

  • listpack 元素个数大于 set_max_listpack_entries，默认值为 128

示例

可以通过 object encoding xxx 命令查看当前 Sets 底层使用的什么数据类型

# 假设当前版本为 Redis7.2

# 底层数据结构为 intset 时，元素有序排列
> sadd my_intset 6 5 4 3 2 1
(integer) 6
> object encoding my_intset
"intset"
> smembers my_intset
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"

# 底层数据结构为 listpack
> sadd my_listpack 1 3 5 str2 str4
(integer) 6
> object encoding my_listpack
"listpack"

# 底层数据结构为 hashtable
> sadd my_hashtable str001 str002 ... str128 str129
(integer) 129
> object encoding my_hashtable
"hashtable"

限制

一个 Sets 实例中最多保存 232−12^{32} - 1232−1 个元素

Sorted Set

Sorted Set，简称为 zset，当满足以下条件时，zset 底层的数据结构为 skiplist，即跳跃表

  • 包含的元素数量 比较多，默认配置下为 128
  • 元素是 比较长 的字符串，默认配置下，字符串长度大于 64

不满足以上条件时，zset 底层的数据结构为 ziplist(Redis7.0 以前)、listpack(Redis7.0 及以后)

skiplist

skiplist 相关的定义位于 src/server.h 中

#define ZSKIPLIST_MAXLEVEL 32

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

skiplist 字段说明

字段描述
header头节点指针，指向一个 zskiplistNode
tail尾节点指针，指向一个 zskiplistNode
length元素个数
level层数，最多为 32 层，即 ZSKIPLIST_MAXLEVEL

skiplistNode 字段说明

字段描述
ele字符串元素，整型值也存储为字符串
score节点分值，排序关键字段
backward向后一个节点的指针
levelzskiplistLevel 数组，zskiplistLevel 有一个前向指针 forward 和跨度 span

zskiplist 与 zskiplistNode 的关系如下图所示

Redis 基本数据类型深度历险记 假设当前 skiplist 中有 5 个元素，即 zskiplist 的 length 等于 5

假设当前 skiplist 的 zskiplistNode 中最长的层级数组长度为 3，即 zskiplist 的 level 等于 3

从上图可以看出，层级越往上，当前层的节点数越少。由于 skiplist 有序，因此可以从上层往下依次查找，类似于二分查找。skiplist 对于查询、插入、删除的平均时间复杂度为 O(logN)

接下来以新增一个元素为例，详细说明按层级搜索的过程 Redis 基本数据类型深度历险记

  1. 待插入节点的 score 为 6，大于节点 nodeA 对应的 score
  2. 沿同一层级来到 score = 3 的节点 nodeC
  3. 待插入节点的 score > 3，继续沿着当前层级向前查找，此时 forward 指向 NULL，降低一级
  4. 第 2 层的 forward 不为空，节点 nodeF 对应的 score=9
  5. 待插入节点的 score < 9，继续返回 nodeC，并下降到第 1 层
  6. forward 不为空，准备检查 forward 对应节点 nodeD 的 score
  7. 待插入节点的 score > 4，继续沿着当前层级向前查找
  8. forward 对应节点 nodeE score=8，待插入节点的 score < 8，但已经在最低层级，找到目标位置，执行插入操作

限制

同样地，元素个数最大为 232−12^{32} - 1232−1

Hashes

Hashes 类型的键和值都是字符串类型

Hashes 底层使用的数据结构为 hashtable 或者 ziplist(Redis7.0 以前) / listpack(Redis7.0 及以后)。在 Redis2.4 及以前，Hashes 类型底层还用到了 zipmap 数据结构，不过在 Redis2.6 就已经废弃了

zipmap

zipmap 即压缩字典，是一种紧凑的数据结构。当 Hashes 或 Sets 中的元素数量较少时（<= 254），为了节省内存，会使用 zipmap。当元素数量逐渐增多时，会转换为其他数据结构。Redis2.6 就已经废弃了，因此不做详细介绍

hashtable

前面介绍 Sets 时已经介绍过 hashtable，只不过 Sets 类型在使用 hashtable 时，设置的值都是 NULL。Hashes 类型在使用 hastable 时，设置真实的值

Redis7.0 以前

当不满足以下条件时，Hashes 底层使用 hashtable 数据结构，否则使用 ziplist

  • 元素个数不超过 hash_max_ziplist_entries 表示的值，默认为 512

Redis6.0 相关代码

int hashTypeSet(robj *o, sds field, sds value, int flags) {
    int update = 0;
    /* 默认使用 ziplist */
    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        /* 省略其他代码 */
    
        /* 检查是否需要转换为 hashtable */
        if (hashTypeLength(o) > server.hash_max_ziplist_entries)
            hashTypeConvert(o, OBJ_ENCODING_HT);
    }
    /* 省略其他代码 */
}

Redis7.0 及以后

当不满足以下条件时，Hashes 底层使用 hashtable 数据结构，否则使用 listpack

  • 元素的键的长度不超过 hash_max_listpack_value 表示的值，默认为 64
  • 元素的值的长度不超过 hash_max_listpack_value 表示的值，默认为 64

Redis7.2 相关代码

int hashTypeSet(robj *o, sds field, sds value, int flags) {
    int update = 0;
    /* 默认使用 listpack */
    if (o->encoding == OBJ_ENCODING_LISTPACK) {
        if (sdslen(field) > server.hash_max_listpack_value || sdslen(value) > server.hash_max_listpack_value)
            /* 转换为 hashtable */
            hashTypeConvert(o, OBJ_ENCODING_HT);
    }
    /* 省略其他代码 */
}

限制

每个 Hashes 最多可以保存 232−12^{32} - 1232−1 个键-值对，实际情况下，还受 Redis 部署服务器的总内存限制

三、总结

用一张图总结 5 种基本数据类型底层使用的数据结构 Redis 基本数据类型深度历险记

  1. 与 Java 的实现类似，Redis 中 Sets 类型和 Hashes 类型底层会复用相同的数据结构，只是 Sets 类型在使用 hashtable 时，值恒为 NULL
  2. quicklist 会复用其他底层数据结构，如 ziplist/listpack
  3. 逐步使用 listpack 替代 ziplist，到 Redis7.0 为止，源代码中已经没有对 ziplistNew 调用了

参考文档

Understand Redis data types

Simple Dynamic Strings

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