redis源码解析（十四）快速链表结构分析

约定不等于承诺〃 2024-04-17 05:51 78阅读 0赞

### 一. 简介 ###

在redis源码中可以看到当前主要使用的并不是压缩链表而是快速链表，快速链表由节点、快速链表，迭代器组成。为什么这样设计呢？总结起来，大概又是一个空间和时间的折中：

双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。

*  首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；
 *  其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。

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

考虑到二者间的折中选择，就创造出了快速链表这种数据结构：快速链表从宏观来看是一系列节点组成的双向链表，而每个节点的数据则是由一个压缩链表存储。因此可以兼具二者的优点，规避二者的缺点，算是一个比较好的选择。

### 二. 结构体源码分析 ###

下面通过源码和注释来分析快速链表的结构

/* 快速链表节点：32字节，底层其实是压缩链表 * count：压缩链表中的节点数 * encoding:编码类型ziplist或者lzf * container：是否使用了ziplist * recompress：是否开启压缩/解压 * 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;
    
    /* 采用lzf压缩的数据存储结构体 * 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;              /* ziplist大小设置，存放list-max-ziplist-size参数的值 * fill factor for individual nodes */
        unsigned int compress : 16; /* 不需要压缩的尾结点数 depth of end nodes not to compress;0=off */
    } quicklist;
    
    
    /* 快速链表迭代器，包括链表指针，当前节点，偏移量，方向，当前quicklist节点中迭代的ziplist*/
    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;