Redis 内部数据结构详解

Redis 时间和空间的折中-quicklist

2019-08-28  本文已影响0人  多多的大白

1.quicklist 简介

quicklist 并不像前面章节介绍的sds、链表、zskiplist、ziplist 没有很明确的对外暴露，而它直接对外暴露的我们平常使用的List 。

quicklist.c - A doubly linked list of ziplists

上面解释从quicklist.c 文件拿来的 ，官方对quicklist的解释是一个ziplist的双向链表，可以理解为一个双向链表其中内部的Node 都是ziplist结构。
ziplist 我们的知道本身就是能维持数据项先后顺序的列表 并且在内存上是连续，上一章Redis 存储效率的追求-ziplist 有很详细的讲解。
在前面章节的基础上和看到quicklist的官方解释大体就能猜到quicklist 是怎么样的结构，作为一个list 必然需要考虑俩个比较大的问题：查找和更新（包含插入）。在我们工作学习中都会用很多的列表、链表等并且都会在这俩个问题中进行选择。
下面我们了解下quicklist这样设计到底为了什么

1、ziplist 内存是连续，存储的效率非常高，但是它并不适合大量的更新，每次的数据更新都导致内存的重新分配甚至导致连锁反应。在数据量比较大的情况，可能是灾难性的。
2、双向链表 优点本身就很明显，数据的更新本身就它具备的优势。

双向链表的节点都是单独的内存空间并且不连续，链表大来必然会导致大量的内存碎片，作为以性能为优势的redis 肯定是不能容忍的。如果我们将node 全部以ziplist进行存储，可想而知性能肯定是比较大的提升，这样就产生了我们的quicklist。总结起来， quicklist是对时间和空间的一种折中方案。

既然我们大体了解quicklist的结构，我们可能会有这样一些个疑问

针对上面的问题我们先看下redis.conf 俩个配置项

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2
# Lists may also be compressed.
# Compress depth is the number of quicklist ziplist nodes from *each* side of
# the list to *exclude* from compression.  The head and tail of the list
# are always uncompressed for fast push/pop operations.  Settings are:
# 0: disable all list compression
# 1: depth 1 means "don't start compressing until after 1 node into the list,
#    going from either the head or tail"
#    So: [head]->node->node->...->node->[tail]
#    [head], [tail] will always be uncompressed; inner nodes will compress.
# 2: [head]->[next]->node->node->...->node->[prev]->[tail]
#    2 here means: don't compress head or head->next or tail->prev or tail,
#    but compress all nodes between them.
# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]
# etc.
list-compress-depth 0

我们先看下list-max-ziplist-size 字面上很容理解列表最大的ziplist长度，但是为什么会是负数，在redis.conf里面已经有比较详细的解释，下面我们来看下。

list-max-ziplist-size 负数情况只有5个选值为-1到-5，它表示并不是size等于多少个，而是大小。

我们在看下list-compress-depth 字面理解是quicklist的压缩深度，官方注释意思是这个配置项表示quicklist 压缩节点ziplist的数量并且两端不被压缩，还解释到为了快速的 push/pop操作 head和tail不进行压缩。

看到俩个配置项就已经解释了上面的俩个问题。

2、quicklist 结构定义

/* 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: 12 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;
/* 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. */
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 : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

quicklistNode结构代表quicklist的一个节点，其中各个字段的含义如下：

quicklistLZF结构表示一个被压缩过的ziplist。其中：

quicklist的数据结构：

上面的quicklistNode.count 表示ziplist里面包含的数据项个数，我们考虑下这个16bit大小的字段是否真的够用？

3、总结

上一篇 下一篇

猜你喜欢

热点阅读