Redis 核心数据结构(一)

Redis 核心数据结构(一)

Redis 目前是使用最广泛的缓存中间件。其突出特点就是支持多种常见的数据结构。对比 JDK 集合类的实现,Redis 的实现表现出很多独到之处,很多地方设计得别具匠心。下面就来简要介绍一下。

linkedlist

Redis 底层也有很多地方使用到 linkedlist,并且也是双向链表。

adlist.h
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

Redis 的 linkedlist 实现特点是:

  1. 双向:节点带有前后指针;

  2. 无环:首尾没有相连,所以没有构成环状;

  3. 链表保存了首尾指针;

  4. 多态:可以保存不同类型的值,这里成为泛型也许更符合 Java 中的语义。

Redis 在 2014 年实现了 quicklist,并使用 quicklist 代替了 linkedlist。所以,现在 linkedlist 几乎已经是废弃状态。

ziplist

Redis 官方在 ziplist.c 文件的注释中对 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 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.c

就是说,ziplist 是一个经过特殊编码的双向链表,它的设计目标就是为了提高存储效率。ziplist 可以用于存储字符串或整数,其中整数是按真正的二进制表示进行编码的,而不是编码成字符串序列。它能以 O(1) 的时间复杂度在表的两端提供 pushpop 操作。

The general layout of the ziplist is as follows:

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

NOTE: all fields are stored in little endian, if not specified otherwise.
redis ziplist structure
  1. <zlbytes>: 32bit,表示ziplist占用的字节总数(也包括<zlbytes>本身占用的4个字节)。

  2. <zltail>: 32bit,表示ziplist表中最后一项(entry)在ziplist中的偏移字节数。

    <zltail> 的存在,使得我们可以很方便地找到最后一项(不用遍历整个ziplist),从而可以在ziplist尾端快速地执行push或pop操作。

  3. <zllen>: 16bit, 表示ziplist中数据项(entry)的个数。zllen字段因为只有16bit,所以可以表达的最大值为216-1。<zllen> 等于16bit全为1的情况,那么 <zllen> 就不表示数据项个数了,这时要想知道 ziplist 中数据项总数,那么必须对ziplist从头到尾遍历各个数据项,才能计数出来。

  4. <entry>: 表示真正存放数据的数据项,长度不定。一个数据项(entry)也有它自己的内部结构,这个稍后再解释。

  5. <zlend>: ziplist 最后 1 个字节,是一个结束标记,值固定等于 255。

ziplist 将表中每一项存放在前后连续的地址空间内,一个ziplist整体占用一大块内存。它是一个表(list),但其实不是一个链表(linked list)。

ziplist 为了在细节上节省内存,对于值的存储采用了变长的编码方式。

每一个数据项<entry>的构成:

<prevlen> <encoding> <entry-data> // (1)
  1. <prevlen>: 表示前一个数据项占用的总字节数。

    1. 如果前一个数据项占用字节数小于254,那么 <prevlen> 就只用一个字节来表示,这个字节的值就是前一个数据项的占用字节数: <prevlen from 0 to 253> <encoding> <entry>

    2. 如果前一个数据项占用字节数大于等于254,那么 <prevlen> 就用5个字节来表示,其中第1个字节的值是254(作为这种情况的一个标记),而后面4个字节组成一个整型值,来真正存储前一个数据项的占用字节数

      0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>  // (2) (3)
  2. <encoding>: 表示当前数据项的类型,整型或者字符串。

  3. <entry-data>: 数据

关于 <encoding> <entry-data> 的编码,直接引用官方文档:

ziplist.c
The encoding field of the entry depends on the content of the
entry. When the entry is a string, the first 2 bits of the encoding first
byte will hold the type of encoding used to store the length of the string,
followed by the actual length of the string. When the entry is an integer
the first 2 bits are both set to 1. The following 2 bits are used to specify
what kind of integer will be stored after this header. An overview of the
different types and encodings is as follows. The first byte is always enough
to determine the kind of entry.

 |00pppppp| - 1 byte
      String value with length less than or equal to 63 bytes (6 bits).
      "pppppp" represents the unsigned 6 bit length.
 |01pppppp|qqqqqqqq| - 2 bytes
      String value with length less than or equal to 16383 bytes (14 bits).
      IMPORTANT: The 14 bit number is stored in big endian.
 |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
      String value with length greater than or equal to 16384 bytes.
      Only the 4 bytes following the first byte represents the length
      up to 2^32-1. The 6 lower bits of the first byte are not used and
      are set to zero.
      IMPORTANT: The 32 bit number is stored in big endian.
 |11000000| - 3 bytes
      Integer encoded as int16_t (2 bytes).
 |11010000| - 5 bytes
      Integer encoded as int32_t (4 bytes).
 |11100000| - 9 bytes
      Integer encoded as int64_t (8 bytes).
 |11110000| - 4 bytes
      Integer encoded as 24 bit signed (3 bytes).
 |11111110| - 2 bytes
      Integer encoded as 8 bit signed (1 byte).
 |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.
      Unsigned integer from 0 to 12. The encoded value is actually from
      1 to 13 because 0000 and 1111 can not be used, so 1 should be
      subtracted from the encoded 4 bit value to obtain the right value.
 |11111111| - End of ziplist special entry.

引用在网上找的例子,来做个说明:

redis ziplist sample
  1. 这个ziplist一共包含 33 个字节。字节编号从 byte[0]byte[32]。图中每个字节的值使用 16 进制表示。

  2. 头 4 个字节(0x21000000)是按小端(little endian)模式存储的 <zlbytes> 字段。什么是小端呢?就是指数据的低字节保存在内存的低地址中(参见维基百科词条 Endianness)。因此,这里 <zlbytes> 的值应该解析成 0x00000021,用十进制表示正好就是33。

  3. 接下来 4 个字节(byte[4..7])是 <zltail>,用小端存储模式来解释,它的值是 0x0000001D(值为29),表示最后一个数据项在 byte[29] 的位置(那个数据项为 0x05FE14)。

  4. 再接下来 2 个字节(byte[8..9]),值为 0x0004,表示这个 ziplist 里一共存有4项数据。

  5. 接下来 6 个字节(byte[10..15])是第 1 个数据项。其中,prevlen=0,因为它前面没有数据项;len=4,相当于前面定义的9种情况中的第1种,表示后面4个字节按字符串存储数据,数据的值为:name

  6. 接下来 8 个字节(byte[16..23])是第 2 个数据项,与前面数据项存储格式类似,存储 1 个字符串:tielei

  7. 接下来 5 个字节(byte[24..28])是第 3 个数据项,与前面数据项存储格式类似,存储 1 个字符串: age

  8. 接下来3个字节(byte[29..31])是最后一个数据项,它的格式与前面的数据项存储格式不太一样。其中,第 1 个字节 prevlen=5,表示前一个数据项占用 5 个字节;第 2 个字节 = FE,相当于前面定义的9种情况中的第8种,所以后面还有1个字节用来表示真正的数据,并且以整数表示。它的值是20(0x14)。

  9. 最后1个字节(byte[32])表示 <zlend>,是固定的值255(0xFF)。

有两个问题需要注意:

  1. 如何反向遍历 ziplist ?

    <prevlen>: 表示前一个数据项占用的总字节数。那么就能找到前一个元素的起始位置,就能实现反向遍历。

  2. 如何从 ziplist 中添加/删除数据?删除数据后,对应位置的 Bits 位怎么处理?

    在某个/某些节点的前面添加新节点之后, 程序必须沿着路径挨个检查后续的节点,是否满足新长度的编码要求, 直到遇到一个能满足要求的节点(如果有一个能满足,则这个节点之后的其他节点也满足), 或者到达 ziplist 的末端 zlend 为止, 这种检查操作的复杂度为 O(N2) 。

    因为只有在新添加节点的后面有连续多个长度接近 254 的节点时, 这种连锁更新才会发生, 所以可以普遍地认为, 这种连锁更新发生的概率非常小, 在一般情况下, 将添加操作看成是 O(N) 复杂度也是可以的。

    删除元素就进行内存移位,覆盖 target 原本的数据,然后通过内存重分配,收缩多余空间。

Redis 在下面这个几个地方使用了 ziplist:

  1. 列表包含少量的列表项,并且列表项只是整数或者短小的字符串时。(在下面 quicklist 小节中,在最新版 Redis 中测试,显示的是 quicklist,而 quicklist 内部使用的是 ziplist 来存储数据,只是外面被 quicklist 包裹着。)

  2. 在哈希键值包含少量键值对,并且每个键值对只包含整数或短小字符串时。

    $ redis-cli --raw
    
    127.0.0.1:6379> HMSET site domain "https://www.diguage.com" owner "D瓜哥"
    OK
    
    127.0.0.1:6379> HGET site domain
    https://www.diguage.com
    
    127.0.0.1:6379> HGET site owner
    D瓜哥
    
    127.0.0.1:6379> TYPE site
    hash
    
    127.0.0.1:6379> OBJECT encoding site
    ziplist

quicklist

Redis 对外暴露的 list 数据类型,它底层实现所依赖的内部数据结构就是 quicklist。

list 是一个能维持数据项先后顺序的列表(各个数据项的先后顺序由插入位置决定),便于在表的两端追加和删除数据,而对于中间位置的存取具有 O(N) 的时间复杂度。

quicklist.c - A doubly linked list of ziplists

— redis/quicklist.c

Redis 在 quicklist.c 就说明了,quicklist 是一个双向链表,而且是一个 ziplist 的双向链表。quicklist 的每个节点都是一个 ziplist。这样设计大概又是一个空间和时间的折中:

  1. 双向链表便于在表的两端进行 pushpop 操作,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。

  2. ziplist 由于是一整块连续内存,所以存储效率很高。但是,它不利于修改操作,每次数据变动都会引发一次内存的 realloc 。特别是当 ziplist 长度很长的时候,一次 realloc 可能会导致大批量的数据拷贝,进一步降低性能。

于是,结合了双向链表和 ziplist 的优点,quicklist 就应运而生了。

新问题:到底一个 quicklist 节点包含多长的 ziplist 合适呢?

  1. 每个quicklist节点上的ziplist越短,则内存碎片越多。

  2. 每个quicklist节点上的ziplist越长,则为ziplist分配大块连续内存空间的难度就越大。

Redis 提供了一个配置参数 list-max-ziplist-size 让使用者可以来根据自己的情况进行调整:

list-max-ziplist-size -2

这个参数可正可负:

  • 当取正值的时候,表示按照数据项个数来限定每个 quicklist 节点上的 ziplist 长度。

  • 当取负值的时候,表示按照占用字节数来限定每个 quicklist 节点上的 ziplist 长度。这时,它只能取 -1-5 这五个值,每个值含义如下:

    • -5: 每个 quicklist 节点上的 ziplist 大小不能超过 64 Kb。(注:1kb ⇒ 1024 bytes)

    • -4: 每个 quicklist 节点上的 ziplist 大小不能超过 32 Kb。

    • -3: 每个 quicklist 节点上的 ziplist 大小不能超过 16 Kb。

    • -2: 每个 quicklist 节点上的 ziplist 大小不能超过 8 Kb。(-2是Redis给出的默认值)

    • -1: 每个 quicklist 节点上的 ziplist 大小不能超过 4 Kb。

list的设计目标是能够用来存储很长的数据列表的。当列表很长的时候,最容易被访问的很可能是两端的数据,中间的数据被访问的频率比较低。list 还提供了一个选项,能够把中间的数据节点进行压缩,从而进一步节省内存空间。Redis 的配置参数 list-compress-depth 就是用来完成这个设置的。

list-compress-depth 0 // 0 是特殊值,表示都不压缩,默认值。

这个参数表示一个quicklist两端不被压缩的节点个数。注:这里的节点个数是指quicklist双向链表的节点个数,而不是指ziplist里面的数据项个数。一个 quicklist 节点上的 ziplist,如果被压缩,就是整体被压缩的。

Redis 对于 quicklist 内部节点的压缩算法,采用的 LZF ——一种无损压缩算法。

  1. 添加过程中,如何处理中间位置的压缩工作?

  2. 头部或者尾部删除,导致 quicklistNode 的非压缩节点不符合设置,怎么处理?

  3. 如果中间删除,节点为压缩节点,怎么处理?

quicklist.h
/* Node, quicklist, and Iterator are the only data structures used currently. */

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

/* Bookmarks are padded with realloc at the end of of the quicklist struct.
 * They should only be used for very big lists if thousands of nodes were the
 * excess memory usage is negligible, and there's a real need to iterate on them
 * in portions.
 * When not used, they don't add any memory overhead, but when used and then
 * deleted, some overhead remains (to avoid resonance).
 * The number of bookmarks used should be kept to minimum since it also adds
 * overhead on node deletion (searching for a bookmark to update). */
typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmakrs are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. */
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    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;

typedef struct quicklistIter {
    const quicklist *quicklist;
    quicklistNode *current;
    unsigned char *zi;
    long offset; /* offset in current ziplist */
    int direction;
} quicklistIter;

typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    unsigned int sz;
    int offset;
} quicklistEntry;
redis quicklist structure
$ redis-cli --raw

127.0.0.1:6379> RPUSH names diguage "D瓜哥" "https://www.diguage.com/"
2

127.0.0.1:6379> LRANGE names 0 -1
diguage
D瓜哥
https://www.diguage.com/

127.0.0.1:6379> TYPE names
list

127.0.0.1:6379> OBJECT encoding names
quicklist

本文篇幅已经很长,其余数据结构,放在下一篇内容来讲解: Redis 核心数据结构(2)