Redis 中数据的编码方式

Redis 提供了字符串、列表、哈希表、集合、有序集合、流（Stream）和 Module 这 7 种数据类型，其中前 5 个是常见的基本数据类型。我们可以使用 set、lpush、hset 等命令来使用这些数据类型。

基础的数据结构无非字符串、链表、哈希表等等，Redis 提供的这 7 种数据类型能够满足大部分的场景，对于复杂的数据结构，也可以使用这些基础的数据类型组合得来。所以，可以将 Redis 视为一个数据结构服务。

这些数据类型在 Redis 中是如何实现的呢？我们使用命令写入的数据在 Redis 中是如何存储呢？本文将回答这些问题。

Redis 对象

Redis 是键值对数据库，所有的数据都存储在一个哈希表中，哈希表的键是字符串，值则可以是前面提到的那 7 种数据类型。

在一个哈希表中存储不同类型的数据，该如何区分 value 的类型呢？Redis 中将键和值都封装为 robj 对象，即 redis object，这个结构中包含数据类型的额外信息。

robj 的定义如下：

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

其中 type 是对象的类型，encoding 是编码方式，lru 字段用于记录该对象的访问时间、频次等信息，refcount 为引用计数，ptr 则为指向底层实际数据结构的指针。

对象的类型

type 字段记录对象的类型，对应前面提到的 7 种数据类型，目前可取值如下：

#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
#define OBJ_HASH 4      /* Hash object. */
#define OBJ_MODULE 5    /* Module object. */
#define OBJ_STREAM 6    /* Stream object. */

比如当执行 set str hello 命令时，Redis 会创建一个 type 为 OBJ_STRING 的对象来保存 key，另创建一个 type 为 OBJ_STRING 的对象来保持 value。 之后这两个对象都被保存到主哈希表中。

可以使用 type <key> 命令来查看一个 key 对应的 value 的类型：

redis> set str hello
OK
redis> type str
string
redis> lpush list 123
(integer) 1
redis> type list
list

对象数据的编码方式

robj 中的 ptr 指针指向实际保存数据的数据结构，这个数据结构该是什么类型，这是由 encoding 字段决定的。encoding 可取的值如下：

#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */

上面提到的 7 种数据类型，其底层实现中会用到多种数据结构，或者说会使用多种编码方式。对于同一种对象类型，其底层实现可能是不同的，这是为了提高性能或者节省内存。

比如对于值为 "9223372036854776000" 的 OBJ_STRING 类型对象，如果使用字符串来存储，需要至少 20 个字节，但因为它其实数字，可以用 64 位的证书表示，即可以使用 8 个字节来存储。

使用 object encoding <key> 命令可以查询一个对象的底层编码：

redis> set num 123456
OK
redis> object encoding num
"int"
OK
redis> set message hello
OK
redis> object encoding message
"embstr"

下面列出各数据类型底层使用到的底层数据结构：

关于 Module 的编码值单独讨论，本文将不涉及 Module 的内容。另外本文基于 Redis 6.2 的实现展开。

String 类型

字符串对象的底层表示有三种，分别是 int、raw、embstr。

如果一个字符串中存的是整数，且该整数可以用 long 类型来存储，此时就会编码为 OBJ_ENCODING_INT，此时 robj->ptr 中存储的就是对应的数字。

embstr

如果一个字符串的长度小于等于 OBJ_ENCODING_EMBSTR_SIZE_LIMIT 就会采用 embstr 编码，否则采用 raw 编码。

#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);
}

使用 raw 编码，则 robj->ptr 指向一个 sds 对象。embstr 编码中，sds 对象被内嵌到 robj 这个结构体的尾部，robj->ptr 指向尾部的 sds，实现方式就是在申请 robj 内存的时候额外申请一些，这样就有了容纳 sds 的空间了。

+------+----------+-----+-----+-----+
| type | encoding | lru | ptr | sds |
+------+----------+-----+-----+-----+

使用 embstr 的好处是减少内存分配的次数。常规情况下，sds 结构的头部需要一次内存分配，，如果在 robj 的结尾将 sds 头部的内存预留好，就可以减少内存分配次数。

sds

sds 意思是 simple dynamic string，这是一个很棒的实现，使用起来非常的方便，它的定义如下：

sds 在用户视角，它是这样的：

typedef char *sds;

这意味着 sds 可以和 c 语言中的字符串完全兼容，可以使用 string.h 和 strings.h 中的库函数。

通常实现动态字符串，一般都会封一个结构体，结构体中大致包含字符串长度、已分配空间，字符串实际内容的指针等等。sds 的实现也不例外，sds 的信息存储在 sdshdr 结构体中，其定义大致如下：

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

注：sdshdr 实际的实现比较复杂，这里对其简化，便于说明原理，详细实现可以参考源码 sds.h|c。

在创建 sds 的时候，会多分配一些空间来放置其头部，比如创建字符串 "abcde"，其内存中的结构大致如下：

|        sdshdr      |
| len  | alloc | buf |
+------+-------+-----+-----+-----+-----+-----+------+------+------+
|   5  |   8   | 'a' | 'b' | 'c' | 'd' | 'e' | '\0' |      |      |
+------+-------+-----+-----+-----+-----+-----+------+------+------+

创建完成后，会返回 buf 的值给用户。在操作 sds 的时候，可以向前偏移某个偏移量，就可以找到 sdshdr 了。

List 类型

列表的底层实现有两种，一种是 ziplist，另外一种是 quicklist。

ziplist

ziplist 意思是压缩列表，是一种为了节省内存开发的数据结构，它的格式如下：

+---------+--------+---------+--------+--------+-----+-----+
| zlbytes | zltail | entries | entry1 | entry2 | ... | end |
+---------+--------+---------+--------+--------+-----+-----+

zlbytes 中记录了当前列表消耗了多少内存，zltail 是最后一个元素的偏移量，entries 为当前列表中的元素数量，之后则存储了多个元素，最后是一个 ziplist 结束的标识 end，其值固定为 0xff。

一个列表中，存储的元素的长度往往不同，因此列表元素占用的字节数也不同，ziplist 中使用下面的结构来记录元素：

ziplist 元素编码格式:

+---------+----------+------------+
| prevlen | encoding | entry-data |
+---------+----------+------------+

字段说明：

- prelen: 前一个元素的字节数，如果小于 254，则消耗一个字节，否则消耗 5 个字节。
- encoding: 编码方式，需要区分数字和字符串，且表明数字占几个字节、字符串的长度
- entry-data: 实际数据

下面说明 encoding 的编码格式，encoding 占用的字节数不是固定的，它究竟占几个字节这可以从第一个字节的位模式中得出。下面描述了 encoding 的位模式，其中 L 表示这一位用于存储字符串的长度。

00LLLLLL
type: string

01LLLLLL LLLLLLLL
type: string

10000000 LLLLLLLL LLLLLLLL LLLLLLLL LLLLLLLL
type: string

11000000
type: int16_t

11010000
type: int32_t

11100000
type: int64_t

11110000
type: int24_t

11111110
type: int8_t

11111111
type: 结束

通过 encoding 第一个字节中的位模式，就可以知道编码的是字符串还是数值（包括数值的类型）。如果是字符串则需要基于 encoding 的模式选择是否在读取后面的字节。因此，编码 string 类型，最多需要 5 个字节（第一个字节表明是 string 类型，后面 4 个字节为字符串的长度）。

另外，当 encoding 的第一个字节为 0xFF 的时候，则说明没有元素了，这在顺序遍历 ziplist 的时候很有用。

在 Redis 代码的实现中，ziplist 没有对应的结构体来表示，它是在字节数组中存储的。在顺序遍历 ziplist 的时候，是从第一个元素开始，并解析出该元素占用的字节数，然后跳到下一个元素，当遇到结束标志 0xFF 的时候停止遍历。如果是反向遍历，则可以使用 zltail 直接定位到列表最后一个元素，并基于 prevlen 找到前一个元素。

ziplist 使用 prevlen 来获知前一个元素的长度，且为了节省内存，这个 prevlen 也是变长存储的，这导致一个隐患。如果一个元素被修改了，其长度变长了，其后的一个元素中的 prevlen 存储不下了，此时 prevlen 需要使用更多字节，因此后一个节点的大小也会变大，进而又会影响再往后的一个元素。如果所有的元素的长度都是 254，此时一旦某个元素长度变长了，prevlen 就需要大于一个字节的的空间来存储，这导致所有后续的节点都需要调整，这被称为链式更新，不过这种场景发生的概率不大。

另外，ziplist 中 encoding 和 prevlen 都需要解码，实现起来很麻烦，看一下 ziplist 的实现就知道了，ziplist.c 共有近 2600 行代码。

quicklist

为什么引入双向 quicklist？

quicklist 是 Redis 3.2 引入的，是 List 类型的底层存储方式。在引入 quicklist 之前，List 类型使用 ziplist 和 adlist（双向链表） 来存储。当元素比较少的时候，使用 ziplist，当元素增多到一定量的时候切换为 adlist。

双向链表的结构很简单，如下：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

可以看到，一个节点需要消耗 24 个字节的内存。另外双向链表的 value 是一个 robj 对象，这又需要消耗 16 个字节。所以存储一个数字，需要消耗 40 个字节。假设这个数字需要 8 个字节来存储，这会额外消耗 32 个字节。

但是如果是有 ziplist 来存储，存储一个 int64_t 只最少只需要需要消耗 10 个字节。

  1 bytes    1 bytes    8 bytes
+---------+----------+------------+
| prevlen | encoding | entry-data |
+---------+----------+------------+

如果存储大量的数字或者小字符串，那么使用双向链表就会消耗很多内存来存储元信息，而使用 ziplist 则可以将数据保存的更加紧凑，节省大量内存。但 ziplist 也存在明显的缺点，ziplist 是连续的内存，当元素比较多的时候，添加新的元素时常常需要重新分配内存，在头部和中间位置插入的性能也很差。

Redis 为了兼顾 ziplist 和 adlist 的优势，引入了 quicklist。quicklist 是 ziplist 构成的链表，即 quicklist 本身是个双向链表，其节点是 ziplist。这有点像 C++ 标准库中 deque 的实现，deque 就是连续内存构成的链表。

在插入元素的时候，如果某个 ziplist 没有空间了，只需要在后面再插入一个新的 ziplist 即可，删除数据的时候，可以将一个 ziplist 拆分为两个。

quicklist 既克服了双向链表浪费内存的缺点，也利用了 ziplist 节省内存的优点。而且使用 quicklist 来寻找某个下标的元素也更快速，因为它可以通过累加 ziplist 中元素的个数一次性跳过多个元素。

quicklist 的结构

quicklist 的定义如下：

typedef struct quicklist {
    /* head 和 tail 指向双向链表的首尾节点。*/
    quicklistNode *head;
    quicklistNode *tail;
    
    /* 每一个节点中存储的是 ziplist，count 字段记录了存储
     * 在 ziplist 中元素的总数 */
    unsigned long count;

    /* quicklist 中节点的数量。*/
    unsigned long len;

    /* 这个是指每个节点中的 ziplist 最多消耗多少内存或最多能有多少元素，
     * 可取值如下：
     *   -1 ~ -5: 表示消耗内存不能超过 4KB * abs(fill)
     *   大于 0 的正数：表示最多可以存储多少个元素 */
    int fill : QL_FILL_BITS;

    /* 为了节省内存，Redis 支持对 quicklist 链表中间的 ziplist 进行压缩。
     * 因为使用 List 类型常常是操作链表的头部和尾部元素，对首尾的节点进行
     * 压缩是不划算的，因为这可能会频繁地执行压缩和解压缩。所以 Redis 不会多首尾
     * 节点执行压缩。
     * compress 的取值如下：
     *   compress = 0: 不执行压缩
     *   compress = n: 对链表首尾的前 n+1 个节点不执行压缩，中间的都压缩。
     *             因为 Redis 不会压缩首尾节点，所以这里是 n+1 个节点。*/
    unsigned int compress : QL_COMP_BITS;

    /* bookmark 是一种优化手段，因为查找某个 quick list 的节点需要遍历 quicklist，
     * 假如知道某个节点会在之后再次被访问，此时可以为其建立一个索引，就是使用一个字符串
     * 映射到节点的指针上。看后面 quicklistBookmark 的定义就明白了。 */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

quicklist 的节点定义如下：

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;

    /* 指向 ziplist */
    unsigned char *zl;

    /* ziplist 的占用的字节数 */
    unsigned int sz;

    /* ziplist 中有多少个元素 */
    unsigned int count : 16;

    /* 编码方式：
     *  encoding == 1: RAW，即不压缩
     *  encoding == 2: LZF 压缩 */
    unsigned int encoding : 2;

    /* quicklist 节点中实际存储数据的是什么结构，目前只能是：
     * QUICKLIST_NODE_CONTAINER_ZIPLIST，即使用 ziplist 存储数据 */
    unsigned int container : 2;

    /* 如果该节点之前被压缩过，目前临时解压开读取数据，此标记为 1，
     * 在读取完成后，还需要在压缩回去。*/
    unsigned int recompress : 1;
    
    /* 是否已经压缩过 */
    unsigned int attempted_compress : 1;

    /* 暂时未使用到 */
    unsigned int extra : 10;
} quicklistNode;

quicklistBookmark 的定义如下：

typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

一个 bookmark 实际就是 name 到 quicklistNode 的映射，在 quicklist 的结构中，有一个 bookmark 的数组，可以使用 name 找到对应的 bookmark，并从中取出 node 的指针。如果知道某个节点会在之后被使用到，可以建立一个 bookmark。之后使用 name 去找这个 bookmark 即可，这样可以加快节点的查找速度。

quicklist 的整体结构如下：

Hash 类型

Redis 中哈希表使用 listpack 或者 dict 来存储数据。默认哈希类型使用 listpack 来存储，当 key 或 value 的长度超过某个阈值时，会将 listpack 转为 dict

listpack

listpack 和 ziplist 类似都是用于节省内存而实现的列表结构。与 ziplist 相比 listpack 实现原理更加简单。

listpack 的结构如下：

struct listpack{
    /* 总字节数 */
    int32_t bytes;
 
    /* 元素个数，如果值为 65535，需要遍历整个列表来统计有多少元素
     * 不过一般 listpack 也不会存储这么多的元素。*/
    int16_t size;
 
    /* 数据 */
    void* entries;
 
    /* 结束标志，固定值 0xFF */
    int8_t end;
}

listpack 中各元素的结构如下：

struct lpentry{
    /* 编码，长度变长，解析策略和 ziplist 差不多，详情见:
     * https://github.com/antirez/listpack/blob/master/listpack.md */
    int<var> encoding;
 
    /* 实际数据 */
    optional byte[] content;
 
    /* 元素的长度，变长存储 */
    int<var> length;
}

ziplist 中之所以存在链式更新的问题，是因为当前节点中存储了与前一个节点有关的 prevlen。这个 prevlen 在 ziplist 中是为了实现反向的遍历。

在 listpack 中，当前元素的尾部存储了自己的长度，这样就让元素直接彼此独立了。反向遍历的时候，可以使用 listpack 的指针和 listpack 的字节数定位到最后一个元素，然后向前读取前一个元素的长度，这样就实现了反向遍历。

我认为 ziplist 的实现无疑是不直观的，每个元素把自己的长度放到末尾是更加合理的策略。listpack 的转变本质不过把 ziplist 中 prevlen 放到前一个元素的末尾，并将其改名为 length 罢了。

ziplist 中元素的结构：

|              item 1             |             item 2              |
+---------+----------+------------+---------+----------+------------+
| prevlen | encoding | entry-data | prevlen | encoding | entry-data |
+---------+----------+------------+---------+----------+------------+


listpack 中元素的结构：

|              item 1             |             item 2              |
+----------+------------+---------+----------+------------+---------+
| encoding | entry-data | length  | encoding | entry-data |  length |
+----------+------------+---------+----------+------------+---------+

当哈希类型使用 listpack 存储时，field 和 value 依次存入 listpack 中。

hashtable

哈希对象初创建时，使用 listpack 类型来存储键值对，随着更多的数据被写入，会在某个时候将 listpack 转换为 hashtable 类型。转换的条件如下：

• 写入的 field 或 value 的长度超过 hash_max_listpack_value (默认为 64) 时候。
• listpack 中的元素数量超过 hash_max_listpack_entries（默认为 512） 时候。
• 总的字节数超过 1 GB 的时候。

当数据量较少的时候，使用 listpack 存储可以节省内存，当哈希表中存储的数据量较多的时候，数据变更后对 listpack 的修改代价就太大了，所以此时应该使用 dict 来存储数据。

Redis 中的 hashtable 使用的是拉链法实现，当有冲突的键时，value 会使用链表链起来。当哈希表中存储的数据过多时，会进行扩容。为了避免对 hashtable 扩容时候耗时太长而阻塞主线程，Redis 使用了两个哈希表来存储数据，在扩容的时候会创建一个更大的哈希表，然后逐渐将数据搬移到大的哈希表中，全部搬移完成后，再交换两个 hashtable。

hashtable 定义如下：

struct dict {
    /* 操作 dict 元素的一组方法，用户可以传入自己的实现，这样可以对 dict 的操作进行定制 */
    dictType *type;

    /* 两个 hashtable，一个存数据，另一个用于辅助 rehash */
    dictEntry **ht_table[2];
    /* 两个 hashtable 中的元素数量 */
    unsigned long ht_used[2];

    /* 当待 rehash 的 bucket 的下标，如果值为 -1，说明 rehash 没在进行中 */
    long rehashidx;

    /* 是否暂停 rehash */
    int16_t pauserehash;

    /* 当前 hashtable 中 bucket 的数量为: 2^ht_size_exp[i] */
    signed char ht_size_exp[2];
};

为了提供更高的灵活性，Redis 将 hash 函数、键比较、键和值的拷贝、键和值的释放等实现为接口，用户可以自己定义这些方法，来定制 dict 的行为。实现方法是使用 dictType 结构封装了一组方法，在创建 dict 的时候传入。

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(dict *d, const void *key);
    void *(*valDup)(dict *d, const void *obj);
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    void (*keyDestructor)(dict *d, void *key);
    void (*valDestructor)(dict *d, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    
    /* 获取 metadata 的大小 */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;

dict 中的 entry 的实现如下：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    /* 键冲突时候指向下一个节点 */
    struct dictEntry *next;

    /* 此节点的额外的信息，如果想要在 KV 之外再存储一些信息，
     * 就可以使用此字段，否则需要将 value 再封装一层。 */
    void *metadata[];
} dictEntry;

Set 类型

Redis 中 set 类型底层有两种编码方式，一种是 intset 另外一种是 hashtable。当集合中的元素都数字，且都可以使用 int64_t 表示的时候，使用 intset 来存储，这样可以节省内存。如果存在不是数字，或者超出 int64_t 表示范围时，会使用 hashtable 来存储。

redis> sadd nums 1 2 3 4 5 6 7 8 9
(integer) 9
redis> object encoding nums
"intset"
redis> sadd nums 0xff
(integer) 1
redis> object encoding nums
"hashtable"

intset

intset 的实现很简单，其结构如下：

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

encoding 字段说明了 set 中存储的是多长的数值，可取值如下：

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

content 字节数组中按照 encoding 和 length 即可定位一个个元素。

在查找 intset 的时候，如果当前查找的数大于当前编码所能表示的最大数，则一定查找不到。在插入的时候，如果当前数值大于当前编码能表示的最大数，则会改变编码，并调整各元素的位置。

intset 向 hashtable 转换的条件如下：

• 当插入 intset 无法存储的数据时，如字符串或者超过 64 位的数字。
• 当 intset 中数字数量大于 1G 的候。当数据过多的时候，在中间插入的时候搬移的数据会比较多。

另外，数字在 intset 中是有序存储的，插入的时候使用二分查找找到该插入的位置，然后将数字插入，并将后面的所有元素向后移动。查找的时候可以保证 nlogn 的时间复杂度。

hashtable

使用 hashtable 存储 set 的数据时，数据都存在唉 key 上，value 是 NULL。hashtable 的结构前面已经讲过，此处不再多说。

Sorted-Set 类型

sorted-set 提供了一种有序集合的数据结构，对于集合中的每一个元素都有与之关联的一个 score，score 是 double 类型，元素会按照 score 进行排序。在实现类似排行榜的东西时，这个功能就很有用。

sorted-set 底层使用了 listpack 和 zset 两种方式来实现。

listpack

当使用 listpack 存储时，score 和 element 依次存放在 listpack 的两个元素中。

<score 1> <element 1> <score 2> <element 2> ... <score n> <element n>

在 listpack 中存储的 (score,element) 对是按照 score 升序排列的。在插入的时候，需要顺序遍历，找到当前 (score, element) 的位置，然后将后面的元素往后挪动，腾出位置后插入 (score, element)。

当前 listpack：
<1> <A> <2> <B> <4> <D>

待插入数据：
<3> <C>

插入后：
<1> <A> <2> <B> <3> <C> <4> <D>

这里 listpack 中的 score 虽然是有序排列的，但是不能使用二分查找。为什么呢？因为 listpack 中的每个元素占用的字节数是不同的，是无法随机访问某一个 (score, element) 对的。

当 sorted-set 数据量较多时，会转换编码，使用 zset 来存储数据。条件如下：

• 写入的 field 或 value 的长度超过 zset_max_listpack_value (默认为 64) 时候。
• listpack 中的元素数量超过 zset_max_listpack_entries （默认为 128） 时候。
• 总的字节数超过 1 GB 的时候。

zset

zset 本质是 hashtable 和 skiplist 的组合，其定义如下：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

hashtable 可以实现集合的功能，skiplist 可以实现有序。zset 中的每一个元素其实是 (score, elememt)，score 是 double 类型，element 是字符串类型，它们会被保存在 zskiplistNode 中。

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

dict 中会存储 element -> scroe 的映射，这样即维护了集合，也方便查询某个 element 对应的 score。

Stream 类型

Stream 是 Redis 5.0 引入的一种数据类型，它提供了一种消息队列的抽象。

其底层存储的数据是一组 (id, data)，其中 id 是升序的，data 则是消息的内容。单纯看存储的数据，感觉可以使用 skiplist 来存储。skiplist 使用 id 来排序，节点中存储 data。

每条消息的 id 在 Redis 中常常是由 Redis 产生了，其构成是时间戳+序号，结构如下：

typedef struct streamID {
    uint64_t ms;        /* Unix time in milliseconds. */
    uint64_t seq;       /* Sequence number. */
} streamID;

可以将两者拼起来构成一个字符串，此时一个序号最长可能需要消耗 41 个字节（uint64_t 表示为字符串最长需要 20 个字节）。但实际上 Redis 将 uint64_t[2] 视为一个 16 字节的字符串来使用。

对于相邻的两个消息，其 id 编码为长度为 16 字节的字符串后，必然存在公共的前缀。这种情况下，使用 skiplist 来存储会造成大量的内存浪费。考虑到这一点，会想到使用字典树来存储。字典树可以实现较高效率的点查询，也可以实现范围查询，而且公共的前缀只会存一份。

实际上 Redis 使用了名为 rax 的数据结构。Redis 的源码中陈其为 A radix tree，即基数树，但感觉这我和认识的基数树不同。我感觉它更像是字典树（或前缀树）。

rax 的原理

考虑使用字典树来存储 “foobar” 和 “footer” 两个字符串，常规的字典树结构如下：

              (f) ""
                \
                (o) "f"
                  \
                  (o) "fo"
                    \
                  [t   b] "foo"
                  /     \
         "foot" (e)     (a) "foob"
                /         \
      "foote" (r)         (r) "fooba"
              /             \
    "footer" []             [] "foobar"

未经过优化的字典树中，树的深度和存储的最长的字符串一致。Redis 的实现中采用了一些优化，降低了树的高度。Redis 的做法是没有分叉的连续节点压缩为一个节点，压缩后的结构如下：

                  ["foo"] ""
                     |
                  [t   b] "foo"
                  /     \
        "foot" ("er")    ("ar") "foob"
                 /          \
       "footer" []          [] "foobar"

经过压缩后，树的深度降低了。虽然需要比较的字符数没有变化，但对压缩后的子字符的比较必然是快于跨多个节点比较的。另外因为节点变少了，还可以有效地节省内存。不过缺点也很明显，实现起来会复杂很多。因为插入新的字符串的时候，会涉及到压缩节点的分裂，删除后还需要做合并。

rax 的定义如下：

typedef struct rax {
    raxNode *head;
    uint64_t numele;
    uint64_t numnodes;
} rax;

typedef struct raxNode {
    /* 该节点是否存储了一个 key */
    uint32_t iskey:1;
    /* 这个节点上存储的值是 NULL */
    uint32_t isnull:1;
    /* 是否为压缩节点 */
    uint32_t iscompr:1;
    
    /* 有多少个子节点，如果是压缩节点，多个子节点存储为一个字符串，size 为字符串长度 */
    uint32_t size:29;
   
    /* 该节点下的数据 */
    unsigned char data[];
} raxNode;

raxNode 中存储数据的编码格式说明如下：

如果当前节点不是压缩节点：

data 中前 size 个字节为子节点对应的字符，紧接着是 size 个 raxNode 的指针，指向对应的子节点。如果当前节点存储了一个 key（iskey=1），且值不为 NULL (isnull=0)，则会存储一个指向 value 的指针。

+-----+-----+-----+-------+-------+-------+------------+
| 'a' | 'b' | 'c' | a-ptr | b-ptr | c-ptr | value-ptr? |
+-----+-----+-----+-------+-------+-------+------------+

如果当前节点是压缩节点：

如果是压缩节点，则只有最后一个字符会存在子节点。此时 data 部分前 size 个字节依然是字符串，接着是一个 raxNode 指针，再往后是 value 指针。

+-----+-----+-----+-------+------------+
| 'a' | 'b' | 'c' | c-ptr | value-ptr? |
+-----+-----+-----+-------+------------+

stream 中消息的存储格式

stream 中的一条消息是 (id, data)，其中 id 前面已经说了，这 data 是一组键值对。所以我们可以将 stream 中的一条消息的数据视为一个 dict。

这些 data 是如何编码的呢，它们是直接使用 id -> data 存储在 rax 中的吗？不是这样的。

如果直接存储在 rax 中，会导致 rax 的节点数过多，另外每个节点存储一个消息，在基于范围访问的时候效率不够高。考虑到 stream 中的数据都是追加写的，而且不会涉及到修改和删除。Redis 为了节省内存和提供读写效率，选择使用 listpack 来存储消息。一个 listpack 中会存储很多条消息，这里 listpack 会作为 rax 的 value，对应的 key 就是最小的消息 id。

因为往 stream 中写入的消息往往具有相同的 field，即消息的 KV 对中 K 都是一样的，为了避免重复存储这些 K，Redis 会首先将 field 存一份，后续的消息如果 field 匹配，就不再存储 field 的内容了。

写入 listpack 中的第一条消息时，会往 listpack 中写入一个 master entry，这个 master entry 中会记录下第一条消息的 field 的信息，还有一些统计信息。

stream 中的一条消息其实是由 listpack 中的多个元素构成的，这多个元素构成 stream 中的一个 entry，即一条消息。

master entry 实际上不是 stream 中的消息，它的结构如下：

+-------+---------+------------+---------+--/--+---------+---------+-+
| count | deleted | num-fields | field_1 | field_2 | ... | field_N |0|
+-------+---------+------------+---------+--/--+---------+---------+-+

• count: 当前 listpack 中有多少个 entry 是有效的
• deleted: listpack 中有多少 entry 被标记为删除
• num-fields：有多少个 field
• field_N：各个 field
• 最后的 0：在后续的 entry 中，这 0 的位置实际上存储的是 stream 中一个 entry 占用了 listpack 的几个元素，这里 master entry 中，此数为 0，这是用来标记这是一个 master entry。

后续的消息如果 field 和 master entry 中的 field 一致，就不需要在存储 field 了，其结构如下：

+-----+--------+-------+-/-+-------+--------+
|flags|entry-id|value-1|...|value-N|lp-count|
+-----+--------+-------+-/-+-------+--------+

• flags: 一些标记位，比如标记当前 entry 复用 master entry 的 field。
• entry-id：记录当前消息的 id，包含两部分 [ms - master.ms, seq - master.seq]，即存储和 master entry 中的差值，这样 entry-id 就由两个相对较小的数字来存储了，可以消耗更少的内存。
• value_i：field_i 对应的 value
• lp-count：这个 entry 中使用了 listpack 多少的元素。这个字段用于反向遍历消息，反向遍历的时候，知道前一个消息占用了多少个 listpack 的元素，就可以跳到前一个消息了。因为 master entry 中，这个位置存储的是 0，所以反向遍历的时候就可以知道何时停下来了。

如果后续的消息的 field 和 master entry 中存在差异，那就需要把 field 和 value 都记录下来，并在 flags 字段中做相应的标记，此时格式如下：

+-----+--------+----------+-------+-------+-/-+-------+-------+--------+
|flags|entry-id|num-fields|field-1|value-1|...|field-N|value-N|lp-count|
+-----+--------+----------+-------+-------+-/-+-------+-------+--------+

以上就是 stream 中数据存储的方式了。

总结

本文全面总结了 String、List、Hash、Set、Sorted-Set、Stream 这 6 种 Redis 类型底层的存储方式。Redis 对各个数据结构的实现细节本文没有进行描述，旨在从宏观层面了解 Redis 如何对数据进行编码，了解我们写入 Redis 的数据是如何存储的。对 Redis 的实现细节，可以通过阅读 Redis 源码来学习。