关于后端:Redis数据结构详解下

上期，咱们具体介绍了 Redis 的 3 种底层数据结构。上面咱们介绍其余的数据结构，来看看它们是如何实现的。

压缩列表

压缩列表是 Redis 为了节约内存而开发的，是由一系列非凡编码的间断内存块组成的程序性数据结构，咱们能够从源码的正文中看到官网对它的定义。

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 of characters. 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 是一种非凡编码的双向链表，指标是为了进步内存的存储效率。它的每个节点可用于存储字符串或整数值，其中整数是按真正的整数进行编码，而不是一系列字符。它容许在列表的任意一端以 O(1) 的工夫复杂度提供 push 和 pop 操作。然而，它的每个操作都须要进行内存重调配，理论的复杂性与 ziplist 应用的内存大小无关，也就是和它的存储的节点个数无关。

实际上，ziplist 充分体现了 Redis 对于存储效率的谋求。一个一般的双向链表，链表中每一项都占用独立的一块内存，各项之间用指针连接起来，这种形式会带来大量的内存碎片，而且地址指针也会占用额定的内存。而 ziplist 却是将表中每一项寄存在前后间断的地址空间内，一个 ziplist 整体占用一大块内存。从这种形式了解，其实它是一个表（list），并不是一个链表（linked list）。

另外，ziplist 为了在细节上节俭内存，对于值的存储采纳了变长的编码方式，也就是说，对于大的整数，就多用一些字节来存储，而对于小的整数，就少用一些字节来存储。咱们接下来就会探讨到这些实现细节。

实现

从源码正文中能够看到 ziplist 的组成构造：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

它并没有像其余数据结构一样，用自定义的 struct 之类的来表白，而就是简略的 unsigned char *，能够从它的创立 API 中就能够看出。

// 创立一个新的压缩列表
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

其中，各个局部的含意如下：

ziplist 中的每个节点都蕴含两个片段的元数据作为前缀。第一个元数据记录了前一个节点的长度，不便从后到前遍历列表。第二个元数据记录了节点存储数据的类型和长度。所以一个残缺的节点是这样存储的:
<prevlen> <encoding> <entry-data>

有时 <encoding> 属性自身即存储了节点本身的类型，也记录了节点的值，比方一些小整数。在这种状况下，能够示意为：
<prevlen> <encoding>

连锁更新

下面介绍中，entry 属性中保留的 prevlen 有 1 字节和 5 字节，所以就会呈现一种状况：当压缩列表存储的节点 e1 到 eN 的长度都介于 250 字节到 253 字节之间，如果在 e1 之前插入了一个长度大于等于 254 字节的新节点，因为 prevlen 的扭转，会导致连锁更新，工夫复杂度为 O(n^2)。尽管连锁更新的复杂度较高，但它真正造成性能问题的概率是很低的，起因如下：

• 压缩列表要恰好有多个间断的、长度介于 250 字节到 253 字节之间的节点，连锁更新才会被触发，但在理论中，这种状况很少见。
• 即便呈现，但只有被更新的节点数量不多，就不会对性能造成任何影响。

应用场景

ziplist 是 哈希对象的底层实现之一，当一个哈希对象蕴含大量键值对，并且每个键值对要么就是小整数值，要么就是长度比拟短的字符串时，Redis 就会应用 ziplist 来作为哈希对象的底层实现。在 Redis 3.2 版本之前，ziplist 也是列表对象的底层实现之一，但 3.2 版本之后被 quicklist 取代。

跳跃表

跳跃表是一种有序数据结构，通过在每个节点中维持多个指向其余节点的指针，来达到快速访问节点的目标。相比均衡树，其实现简略，而且在大部分状况下的效率能和均衡树相媲美。

实现

// 跳跃表节点实现
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;

多个跳跃表节点组成了跳跃表，程序能够以 O(1) 的工夫复杂度获取表头、表尾指针以及节点的数量；跳跃表中以 score 属性的大小进行排序，score 雷同，则以成员 ele 属性的字典序排列；新增节点的层数依据幂次定律获得一个介于 1 和 32 之间的值。

跳跃表的实现中，存在着一个不填充数据，但满层的头结点，头结点存在的起因如下：

• zskiplist 的头指针 head 不会随数据的变动而变动。
• 头结点的层数达到了最大值 32，在第一次查找时，能够和 zskiplist 中 level 属性定位查找节点，没有头结点的话，只能从第一个填充了数据的节点开始，但它的层数可能不是分层最高的，会拖慢查问的效率。

应用场景

Redis 应用跳跃表作为有序汇合键的底层实现之一，如果一个有序汇合蕴含的元素数量比拟多，又或者有序汇合中元素的成员是比拟长的字符串时，Redis 就会应用跳跃表来作为有序汇合键的底层实现。这里就有个问题，为什么 Redis 不应用均衡树呢？起因有以下几点：

1. 从算法实现难度比拟，skiplist 比均衡树要简略得多，更加直观，便于调试。
2. 从区间查找效率比拟，均衡树比 skiplist 操作要简单。在均衡树上，咱们找到指定范畴的小值之后，还须要以中序遍历的程序持续寻找其它不超过大值的节点。如果不对均衡树进行肯定的革新，这里的中序遍历并不容易实现。而在 skiplist 上进行范畴查找就非常简单，只须要在找到小值之后，对第 1 层链表进行若干步的遍历就能够实现。
3. 从插入和删除效率比拟，均衡树的插入和删除操作可能引发子树的调整，须要左旋或者右旋保障均衡，逻辑简单，而 skiplist 的插入和删除只须要批改相邻节点的指针，操作简略又疾速。
4. 从内存占用上比拟，skiplist 比均衡树更灵便一些。一般来说，均衡树每个节点蕴含 2 个指针（别离指向左右子树），而 skiplist 每个节点蕴含的指针数目均匀为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取 p = 1/4，那么均匀每个节点蕴含 1.33 个指针，比均衡树更有劣势。

整数汇合

整数汇合是 Redis 用来保留整数值的汇合形象数据结构，汇合中不会呈现反复的元素，并且是按值的大小从小到大有序地排列。

实现

// 整数汇合实现
typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 汇合蕴含的元素数量
    uint32_t length;
    // 保留元素的数组
    int8_t contents[];} intset;

其中，
1.encoding 属性的值有 3 个

• INTSET_ENC_INT16：代表元素为 16 位的整数
• INTSET_ENC_INT32：代表元素为 32 位的整数
• INTSET_ENC_INT64：代表元素为 64 位的整数

2.contents 属性的类型申明为 int8_t，但它不保留任何 int8_t 类型的值，而是取决于 encoding 属性。

降级

当整数汇合中元素的类型都是 int16_t 类型的值时，如果你须要增加一个 int32_t 类型的整数，会产生什么呢？这时就会执行降级操作，来保障大类型能够被放入数组。降级可表述为以下几步：

1. 依照降级后的类型和元素数量，分配内存空间。
2. 将元素的类型降级为新元素的类型，在保障有序性不变的前提下，放在新的地位上。
3. 将新元素增加到数组中（因为新元素的长度必定最大，所以总是在头或尾两个地位上）

降级的益处，就是能够尽可能的节约内存，晋升灵活性。

那么，提到降级，大家必定会想到是不是有降级，但整数汇合不反对降级，起因就是，既然曾经有大的元素插入，那么当前大概率也会有，降级后，再插入大类型的整数，还会进行降级操作，所以降级操作价值不大，而且降级波及内存重调配，也不是一种便宜的操作。

应用场景

整数汇合是汇合对象的底层实现之一，当一个汇合只蕴含整数值元素，并且元素数量不多时，Redis 就会应用整数汇合作为汇合对象的底层实现。

快表

快表是 Redis 在 3.2 版本中提供的一种数据结构，是一个基于 ziplist 的双向链表，从源码正文中对快表的定义就能够看出这一点。

A doubly linked list of ziplists

quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedList 按段切分，每一段应用 ziplist 来紧凑存储，多个 ziplist 之间应用双向指针链接起来。quicklist 为什么要这样设计呢，其实就是在空间和工夫上进行的均衡：

• 附加空间：双向链表每个节点除了保留数据，还要保留两个指针，占去 16 个字节 (64bit 零碎的指针是 8 个字节)。
• 内存碎片：双向链表的各个节点是独自的内存快，地址不间断，节点过多容易造成内存碎片，影响内存管理效率。
• ziplist 是一整块间断内存，所以存储效率很高。但它不利于进行批改操作，每次数据变动都会引发一次内存的 realloc。特地是当 ziplist 很长的时候，一次 realloc 可能会导致大批量的数据拷贝，进一步升高性能。

因而 Redis 从 3.2 版本开始对列表数据结构进行了革新，应用 quicklist 代替了 ziplist 和 linkedlist。但这也带来了一个新问题：quicklist 的一个节点中的 ziplist 包换多少数据项适合呢？这又是一个须要找到平衡点的难题。咱们从存储效率上剖析一下：

• 每个 quicklist 节点上的 ziplist 越短，则内存碎片越多，有可能在内存中产生很多无奈被利用的小碎片，从而升高存储效率。这种状况的极其是每个 quicklist 节点上的 ziplist 只蕴含一个数据项，这就堕落成一个一般的双向链表。
• 每个 quicklist 节点上的 ziplist 越长，则为 ziplist 调配大块间断内存空间的难度就越大。有可能呈现内存里有很多小块的闲暇空间（它们加起来很多），但却找不到一块足够大的闲暇空间调配给 ziplist 的状况。这同样会升高存储效率。这种状况的极其是整个 quicklist 只有一个节点，所有的数据项都调配在这仅有的一个节点的 ziplist 外面，这其实就堕落成一个 ziplist。

所以，Redis 提供了一个配置参数 list-max-ziplist-size，让使用者能够依据本人的利用场景进行调整。这个配置能够取正值，也能够取负值。上面咱们来解释下不同值代表的含意：

• 当配置为正值时，示意每个 quicklist 节点上的 ziplist 的最大数据项个数。例如，list-max-ziplist-size = 5 时，示意 ziplist 最多蕴含 5 个数据项。
• 当配置为负值时，示意依照占用字节数来限定每个 quicklist 节点上的 ziplist 长度。但这时，它只能取 -1 到 -5 这五个值，每个值含意如下：

另外，当列表很长的时候，最容易被拜访的很可能是两端的数据，两头的数据被拜访的频率比拟低（拜访起来性能也很低）。如果利用场景合乎这个特点，那么 quicklist 还提供了一个选项，可能把两头的数据节点进行压缩，从而进一步节俭内存空间。Redis 的配置参数 list-compress-depth 就是用来实现这个设置的。这个参数示意一个 quicklist 两端不被压缩的节点个数。注：这里的节点个数是指 quicklist 双向链表的节点个数，而不是指 ziplist 外面的数据项个数。实际上，一个 quicklist 节点上的 ziplist，如果被压缩，就是整体被压缩的。参数 list-compress-depth 的取值含意如下：

• 0: 是个非凡值，示意都不压缩。这是 Redis 的默认值。
• 1: 示意 quicklist 两端各有 1 个节点不压缩，两头的节点压缩。
• 2: 示意 quicklist 两端各有 2 个节点不压缩，两头的节点压缩。
• 3: 示意 quicklist 两端各有 3 个节点不压缩，两头的节点压缩。
• 依此类推 …

因为 0 是个非凡值，很容易看出 quicklist 的头节点和尾节点总是不被压缩的，以便于在表的两端进行疾速存取。Redis 对于 quicklist 外部节点的压缩算法，采纳的 LZF（一种无损压缩算法）。

实现

// 快表节点
typedef struct quicklistNode {
    // 上一个节点
    struct quicklistNode *prev;
    // 下一个节点
    struct quicklistNode *next;
    // 数据指针，如果未压缩，指向一个 ziplist，压缩后指向 quicklistLZF
    unsigned char *zl;
    // 指向的压缩列表的大小，如果被压缩，仍是未压缩前的大小
    unsigned int sz;             /* ziplist size in bytes */
    // ziplist 中蕴含的数据项的个数
    unsigned int count : 16;     /* count of items in ziplist */
    // 是否被压缩，1：未压缩 2：压缩（LZF）unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    // 数据容器，示意底层用什么数据结构存储数据，目前只有 ziplist 一个容器
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    // 如果是一个被压缩的数据，因应用相似 lindex 这样的命令要临时解压，须要标记一下，等前面从新压缩
    unsigned int recompress : 1; /* was this node previous compressed? */
    // Redis 自动化测试中应用的字段
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    // 扩大字段，供将来扩大应用
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
// 被压缩的 ziplist 构造
typedef struct quicklistLZF {
    /// 压缩后的 ziplist 大小
    unsigned int sz; /* LZF size in bytes*/
    // 是个柔性数组，寄存被压缩后 ziplist 的字节数组
    char compressed[];} quicklistLZF;
// 快表构造
typedef struct quicklist {
    // 表头节点
    quicklistNode *head;
    // 表尾节点
    quicklistNode *tail;
    // 所有 ziplist 数据项的总和
    unsigned long count;        /* total count of all entries in all ziplists */
    // quicklist 节点的数量
    unsigned long len;          /* number of quicklistNodes */
    // 单个节点的填充因子，寄存 list-max-ziplist-size 参数的值
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    // 节点压缩深度，寄存 list-compress-depth 参数的值
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];} quicklist;

上图中是一个含有 3 个节点的 quicklist，其中每个节点有 4 个数据项，两边的节点是未压缩的，两头的节点是压缩的。

应用场景

Redis 应用快表作为列表对象的底层实现，不过在 3.2 版本之前，列表对象的底层实现是链表或者压缩列表，应用快表替换链表和压缩列表的实现起因，下面曾经解说，这里就不再赘述了。

zipmap

zipmap 看名字，感觉和 ziplist 很像，zip 有压缩的意思，map 阐明是一个有对于键值对的数据结构，能够猜想是对 map 实现上的一种内存优化，上面咱们就来验证一下。

String -> String Map data structure optimized for size.

从上述源码正文中得悉，zipmap 其实就是一个 String，是一个压缩了的 map 构造，调配了一段间断的内存空间，用来保留间断的 key-value 汇合。它的特点是保护 map 所须要的额定信息很少，对于一个键值对起码只须要额定的三个字节来形容。不过这样做的结果就是，对 map 操作时须要进行遍历，工夫复杂度为 O(n)，但因为键值对的个数不会很多，所以并不会有性能问题。

实现

zipmap 的数据结构特地简略，简略到新创建后的 zipmap 只有两个字节，其中，首字节保留长度，尾字节保留结尾标记 ZIPMAP_END，其中 ZIPMAP_END = 255，能够从 zipmap 的创立 API 就可以看进去。

/* Create a new empty zipmap. */
unsigned char *zipmapNew(void) {unsigned char *zm = zmalloc(2);
    zm[0] = 0; /* Length */
    zm[1] = ZIPMAP_END;
    return zm;
}

那么 zipmap 是怎么保留键值对的呢，源码正文中有一个例子，如果要保留 “foo” => “bar”，”hello” => “world”，那么会是这样：

<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

其中

应用场景

Redis 中的哈希键，当元素个数比拟少时，会应用到 zipmap，当达到给定的个数时，会切换到字典。因为字典保留一个键值对须要的额定信息比拟大 sizeof(struct dictEntry) = 24，而 zipmap 起码只须要三个字节，最多 11 个字节。在查问效率上，当数据量特地小的时候，程序查问破费的工夫老本尽管是 O(n)，然而 n 小，所以是能够承受的，这样做能够节约内存。不过，这是在 Redis 2.6 版本之前才有，在 2.6 版本及之后的版本中曾经被 ziplist 代替，也就是说，当键值对比拟少时，会采纳 ziplist 去实现哈希类型的对象。

流

stream 是 Redis 5.0 版本新减少的数据结构，它底层数据的存储依赖于 一棵 radix tree，次要用于音讯队列的实现，stream 能够说是 Redis 底层数据结构中最简单的一个。

实现

typedef struct streamID {
    // unix 工夫戳
    uint64_t ms;        /* Unix time in milliseconds. */
    // 序号
    uint64_t seq;       /* Sequence number. */
} streamID;

typedef struct stream {
    // 指向 radix tree 的指针
    rax *rax;               /* The radix tree holding the stream. */
    // stream 中保留的元素的数量，以音讯 ID 为统计维度
    uint64_t length;        /* Number of elements inside this stream. */
    // stream 中最初一个音讯 ID
    streamID last_id;       /* Zero if there are yet no items. */
    // 保留监听该 stream 的消费者信息
    rax *cgroups;           /* Consumer groups dictionary: name -> streamCG */
} stream;

从上述实现中能够看出，streamID，也就是音讯 ID，是由工夫戳 + 序号两局部组成，各占 64 位，一共 128 位，此 ID 可由 Redis 主动生成，或者自定义，为了保障音讯的有序性，Redis 主动生成的 ID 是枯燥递增的。因为音讯 ID 中蕴含了工夫戳，为了防止 Redis 服务器工夫谬误，比方产生了时钟向后跳跃，stream 中都保护了一个 last_id，来记录最初一个音讯 ID，若与 last_id 比拟发现工夫戳退后，则采纳工夫戳延用 last_id，递增序号的形式生成音讯 ID（这也是序号应用 64 位示意的起因，保障有足够多的序号应用），从而保障音讯 ID 的枯燥递增。

而后，咱们再来看 rax 这个属性示意什么，从源码中的正文中能够失去答案，即 rax 是一棵 radix tree 的实现。

Rax — A radix tree implementation.

typedef struct raxNode {
    uint32_t iskey:1;
    uint32_t isnull:1;
    uint32_t iscompr:1;
    uint32_t size:29;
    unsigned char data[];} raxNode;

typedef struct rax {
    // radix tree 头结点指针
    raxNode *head;
    // radix tree 中存储元素的总数
    uint64_t numele;
    // radix tree 中节点总数
    uint64_t numnodes;
} rax;

上面咱们来具体介绍一下 raxNode 的属性：

上面咱们来开展介绍一下：

• 如果节点没有被压缩，那么会有 size 个子节点，每个子节点占 1 个字节，并且有 size 个子节点指针，指向每个子节点。

[header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)

• 如果节点是被压缩的，那么该节点只有 1 个子节点，占 size 个字节，也仅有 1 个子节点指针。

[header iscompr=1][xyz][z-ptr](value-ptr?)

当咱们应用 xadd key id field value [field value …] 向其中增加音讯时，还会波及另外一个数据结构 listpack，它是什么，也能够从源码中失去答案：

Listpack — A lists of strings serialization format

其实也是一个字符串，和 zipmap 很类似，从创立一个新的 listpack 的 API 就能够看出。

unsigned char *lpNew(void) {unsigned char *lp = lp_malloc(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;
}

增加元素时，会先找到 radix tree 中的最初一个节点，校验这个节点的 data 是否超过配置规定的大小（从占用空间和元素总数上），没有超过，则应用这个空间；若超过，则会新创建一个 listpack 构造，一个新创建的 listpack 中 field 的组织形式如下：

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

对于 value 的解决有两种形式，通常是以第一种形式组织，但当增加的 field 和原有的 field 雷同时，就采纳第二种形式。

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

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

因为 stream 的实现比较复杂，波及的内容比拟多，前面会独自来讲 stream，这里仅做以上概述。

应用场景

Redis 应用 stream 作为流对象的底层实现，性能就是咱们熟知的音讯队列，尽管 Redis 自身就有一个公布订阅（pub/sub）能够实现音讯队列的性能，但音讯不反对长久化，很容易造成音讯失落。另外 rax 还被用在了 Redis Cluster 中用于记录 slot 与 key 的对应关系。

总结

从上述对 Redis 底层数据结构的介绍，咱们能够看出，Redis 针对底层数据结构的设计是十分精密的，针对每个字节，甚至每一位都进行了考量，能够体现为以下几点：

• 存储效率。Redis 是基于内存来存储数据的，所以如何节俭内存资源就是 Redis 数据结构致力的一个方向，上述数据结构中，基本上都能看到为了缩小内存碎片，以及压缩存储空间等做出的设计。
• 响应工夫。对于 Redis 主模块单线程设计，如果对一个数据结构操作过慢，那将是劫难一样的事件，所以也能看到 Redis 对数据结构操作的工夫复杂度的优化。

（本文作者：李强）

本文系哈啰技术团队出品，未经许可，不得进行商业性转载或者应用。非商业目标转载或应用本文内容，敬请注明“内容转载自哈啰技术团队”。