【Redis】270- 你需要知道的那些 redis 数据结构

2022-10-03 22:49:44

本文出自「掘金社区」，欢迎戳「阅读原文」链接和作者进行技术交流 ??

作者简介

世宇，一个喜欢吉他、MDD 摄影、自走棋的工程师，属于饿了么上海物流研发部。目前负责的是网格商圈、代理商基础产线，平时喜欢专研技术，主攻 Java。

redis 对于团队中的同学们来说是非常熟悉的存在了，我们常用它来做缓存、或是实现分布式锁等等。对于其 api 中提供的几种数据结构，大家也使用得得心应手。

api 中的数据结构有如下几种：

string
list
hash
set
sorted set

这些 api 提供的“数据结构”，在 redis 的官方文档中有详细的介绍。就不多做展开，本次重点在于讨论 redis 数据结构的内部更底层的实现。如下：

sds
adlist(在 3.2 版本中被 quicklist 所代替)
dict
skiplist
intset
ziplist
object

在学习了解 redis 几个底层数据结构的过程中，处处可以体会到作者在设计 redis 时对于性能与空间的思考。附 redis 源码下载。本期主要介绍 sds 和 ziplist。

一、sds 简单动态字符串

1、sds 结构

redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串），而是自己构建了一种名为简单动态字符串（simple dynamic string，sds）的抽象类型，并将 sds 用作 redis 的默认字符串表示。

根据传统，C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符数组的最后一个元素总是空字符 '' 。如下图：

因为 C 字符串并不记录自身的长度信息，所以为了获取一个 C 字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为 O(N) 。

和 C 字符串不同，因为 sds 在 len 属性中记录了 sds 本身的长度，所以获取一个 sds 长度的复杂度仅为 O(1) 。与此同时，它还通过 alloc 属性记录了自己的总分配空间。下图为 sds 的数据结构：

区别于 C 字符串，sds 有自己独特的 header，而且多达 5 种，结构如下：

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.

 * However is here to document the layout of type 5 SDS strings. */

struct __attribute__ ((__packed__)) sdshdr5 {

    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */

    char buf[];

};

struct __attribute__ ((__packed__)) sdshdr8 {

    uint8_t len; /* used */

    uint8_t alloc; /* excluding the header and null terminator */

    unsigned char flags; /* 3 lsb of type, 5 unused bits */

    char buf[];

};

struct __attribute__ ((__packed__)) sdshdr16 {

    uint16_t len; /* used */

    uint16_t alloc; /* excluding the header and null terminator */

    unsigned char flags; /* 3 lsb of type, 5 unused bits */

    char buf[];

};

struct __attribute__ ((__packed__)) sdshdr32 {

    uint32_t len; /* used */

    uint32_t alloc; /* excluding the header and null terminator */

    unsigned char flags; /* 3 lsb of type, 5 unused bits */

    char buf[];

};

struct __attribute__ ((__packed__)) sdshdr64 {

    uint64_t len; /* used */

    uint64_t alloc; /* excluding the header and null terminator */

    unsigned char flags; /* 3 lsb of type, 5 unused bits */

    char buf[];

};

之所以有 5 种，是为了能让不同长度的字符串可以使用不同大小的 header。这样，短字符串就能使用较小的 header，从而节省内存。

通过使用 sds 而不是 C 字符串，redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ，这是一种以空间换时间的策略，确保了获取字符串长度的工作不会成为 redis 的性能瓶颈。

2、内存分配策略

再来看 sds 的定义，它是简单动态字符串。可动态扩展内存也是它的特性之一。sds 表示的字符串其内容可以修改，也可以追加。在很多语言中字符串会分为 mutable 和 immutable 两种，显然 sds 属于 mutable 类型的。当 sds API 需要对 sds 进行修改时， API 会先检查 sds 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 sds 的空间扩展至足以执行修改所需的大小，然后才执行实际的修改操作，所以使用 sds 既不需要手动修改 sds 的空间大小，也不会出现 C 语言中可能面临的缓冲区溢出问题。

提到字符串变化就不得不提到内存重分配这个问题，对于一个 C 字符串，每次发生变更，程序都总要对保存个 C 字符串的数组进行一次内存重分配操作：

如果程序执行的是增长字符串的操作，比如拼接操作（append），那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小 —— 如果忘了这一步就会产生缓冲区溢出。

如果程序执行的是缩短字符串的操作，比如截断操作（trim），那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间 —— 如果忘了这一步就会产生内存泄漏。

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作：

在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的。
但是 redis 作为一个内存数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分，如果这种修改频繁地发生的话，可能还会对性能造成影响。

为了避免 C 字符串的这种缺陷，sds 通过未使用空间解除了字符串长度和底层数组长度之间的关联：在 sds 中， buf 数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些未使用字节的数量可以由 sds 的 alloc 属性减去len属性得到。

通过未使用空间，sds 实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

空间预分配用于优化 sds 的字符串增长操作：当 sds 的 API 对一个 sds 进行修改，并且需要对 sds 进行空间扩展的时候，程序不仅会为 sds 分配修改所必须要的空间，还会为 sds 分配额外的未使用空间，并根据新分配的空间重新定义 sds 的 header。此部分的代码逻辑如下：

    /* Return ASAP if there is enough space left. */

    if (avail >= addlen) return s;

    len = sdslen(s);

    sh = (char*)s-sdsHdrSize(oldtype);

    newlen = (len+addlen);

    if (newlen < SDS_MAX_PREALLOC)

        newlen *= 2;

    else

        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

简单来说就是：

如果对 sds 进行修改之后，sds 的长度（也即是 len 属性的值）将小于 1MB ，那么程序分配和 len 属性同样大小的未使用空间，这时 SDSsds alloc 属性的值将正好为 len 属性的值的两倍。举个例子，如果进行修改之后，sds 的 len 将变成 13 字节，那么程序也会分配 13 字节的未使用空间，alloc 属性将变成 13字节，sds 的 buf 数组的实际长度将变成 13+13+1=27 字节（额外的一字节用于保存空字符）。
如果对 sds 进行修改之后，sds 的长度将大于等于 1MB ，那么程序会分配 1MB 的未使用空间。举个例子，如果进行修改之后，sds 的 len 将变成 30MB，那么程序会分配 1MB 的未使用空间，alloc 属性将变成 31MB ，sds 的 buf 数组的实际长度将为 30MB+1MB+1byte。

通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。通过这种空间换时间的预分配策略，sds 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。

内存预分配策略仅在 sds 扩展的时候才触发，而新创建的 sds 长度和 C 字符串一致，是长度 + 1byte。

惰性空间释放

惰性空间释放用于优化 sds 的字符串缩短操作：当 sds 的 API 需要缩短 sds 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。

通过惰性空间释放策略，sds 避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。与此同时，sds 也提供了相应的 API sdsfree，让我们可以在有需要时，真正地释放 sds 里面的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。源码如下:

/* Free an sds string. No operation is performed if 's' is NULL. */

void sdsfree(sds s) {

    if (s == NULL) return;

    s_free((char*)s-sdsHdrSize(s[-1]));

}

细想一下，惰性空间释放策略也是空间换时间策略的实现之一，作者对于性能的追求是非常执着的。当然也不是说为了性能，就不在乎内存的使用了，且看下一部分。

二、ziplist压缩链表

1、ziplist介绍

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values,where integers are encoded as actual integers instead of a series ofcharacters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

这是位于 ziplist.c 头部的一段介绍。翻译过来就是：ziplist 是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist 可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以 O(1) 的时间复杂度在表的两端提供 push 和 pop 操作。然而，由于 ziplist 的每次变更操作都需要一次内存重分配，ziplist 实际的复杂度和其实际使用的内存量有关。

ziplist 充分体现了 Redis 对于存储效率的追求。一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。而 ziplist 却是将表中每一项存放在前后连续的地址空间内，一个 ziplist 整体占用一大块内存。它是一个表（list），但其实不是一个链表（linked list） -- zhangtielei

2、ziplist 结构

ziplist entry 结构

ziplist 中的每个节点都以包含两个部分的元数据为前缀信息。首先，有 prevlen 存储前一个节点的长度，这提供了能够从尾到头遍历列。其次， encoding 表示了节点类型，是整数或是字符串，在本例中字符串也表示字符串有效负载的长度。所以完整的条目存储如下：

<prevlen> <encoding> <entry-data>

有的时候 encoding 也会用于表示节点数据本身，比如较小的整数，在这种情况下节点会被省去，此时只需如下结构即可表示一个节点，这也是为节省内存而设计：

<prevlen> <encoding>

上一个节点的长度 <prevlen> 是按以下方式编码的：如果上一节点长度小于 254 字节，则它将只使用一个字节，表示长度为一个未指定的 8 位整数。当长度大于或等于 254 时，将消耗 5 个字节。第一个字节设置为 254（0xFE），表示后面的值较大。剩下的 4 个字节将前一个条目的长度作为值。

节点的的 encoding 字段取决于节点的内容。当该节点是一个字符串时，首先是编码的前 2 位 byte 将保存用于存储字符串长度的编码类型，后跟字符串的实际长度。当条目为整数时前 2 位都设置为 1，后 2 位用于指定此节点将存储哪种整数。不同 encoding 类型和编码如下。

|00pppppp| - 占用空间 1 byte

表示长度小于等于63字节的字符串(6 bits)。

如："pppppp" 表示无符号6bit的字符串长度。

|01pppppp|qqqqqqqq| - 占用空间  2 bytes

表示长度小于等于16383字节的字符串(14 bits)。

|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 占用空间  5 bytes

表示长度大等于16384字节的字符串(14 bits)。

只有后面的4个字节表示长度，最多32^2-1。不使用第一个字节的6个低位，并且全部设置为零。

|11000000| - 占用空间  3 bytes

后面两个字节表示 int16_t 的无符号整数 (2 bytes)。

|11010000| - 占用空间  5 bytes

后面四个字节表示 int32_t 的无符号整数 (4 bytes)。

|11100000| - 占用空间 9 bytes

后面八个字节表示 int32_t 的无符号整数 (8 bytes).

|11110000| - 占用空间 4 bytes

后面三个字节表示24bits的有符号整数 (3 bytes).

|11111110| - 2 bytes

后面一个字节表示8bits的有符号整数 (1 byte).

|1111xxxx| - (xxxx 在 0000 到 1101 之间) 的4bits整数.

但是它其实只用来表示0到12，因为0000、1111、1110都已经被别的encoding使用过了，

所以这种情况下需要用这4bit所对应的值减去1来获取它真实表示的值。

|11111111| - 表示ziplist结尾的特殊节点。

其后的 entry-data 就用于存储 encoding 中定义的数据了。

总结一下：

ziplist 体现了 Redis 对于存储效率的追求,它是一种为节约内存而开发的顺序型数据结构。
ziplist 被用作列表键和哈希键的底层实现之一。
ziplist 可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
ziplist 的设计为将各个数据项挨在一起组成连续的内存空间，这种结构并不擅长做修改操作。一旦数据发生改动，就会引发内存重分配。

三、本期总结

redis 在设计中并不是一味得追求性能，存储效率也是它追求的一个目标，不止 sds 和 ziplist，其他的底层数据结构也是在追求时间复杂度和空间效率这一目标中的产物。通过解析 redis 的数据结构设计，能更好的帮助我们理解 redis 使用过程中的执行过程和原理。

下一期会解析 quicklist，敬请期待！

参考资料

redis设计与实现
redis源码
redis内部数据详解

每一个“在看”，都是对我最大的肯定！

码农公寓