Redis之quicklist(Redis QuickList)

Redis的早期版本存储list列表的数据结构是ziplist和普通的双向链表linkedlist,元素个数少时使用ziplist,多时用linkedlist。

//链表的节点
struct listNode<T> {
    listNode* prev;
    listNode* next;
    T value;
}
//链表
struct list {
    listNode *head; //64位OS占8个字节
    listNode *tail; //64位OS占8个字节
    long length;
}

考虑到:1.链表的信息占用存储空间相对较高2.每个节点单独分配,会加剧内存的碎片化,影响管理效率所以后续新版本对list的结构进行了改造,统一为quicklist

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    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;

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;

为了进一步节约空间,Redis还会对ziplist进行压缩存储,使用LZF算法压缩,可以选择压缩深度。

【ziplist元素个数】看完了整体结构,我们需要看看每个quicknode中的ziplist里有多少个元素。quicklist默认单个ziplist长度位8KB,超出这个字节数,就会另起一个ziplist。ziplist的长度由配置参数list-max-ziplist-size决定。【quicklist压缩深度】默认为0,即不压缩。实际深度由list-compress-depth决定。压缩深度为1,即首尾第一个元素都不压缩,压缩深度为2,即首尾第一个以及第二个元素都不压缩。

————————

In the early versions of redis, the data structures for storing lists were ziplist and ordinary two-way linked list. Ziplist was used when the number of elements was small, and LinkedList was used when the number of elements was large.

//链表的节点
struct listNode<T> {
    listNode* prev;
    listNode* next;
    T value;
}
//链表
struct list {
    listNode *head; //64位OS占8个字节
    listNode *tail; //64位OS占8个字节
    long length;
}

Consider: 1 The storage space occupied by the linked list information is relatively high 2 The separate allocation of each node will aggravate the fragmentation of memory and affect the management efficiency. Therefore, the structure of list has been transformed into QuickList in the subsequent new version

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    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;

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;

In order to further save space, redis will also compress and store the ziplist. It uses lzf algorithm for compression, and the compression depth can be selected.

[number of ziplost elements] after reading the overall structure, we need to see how many elements are in the ziplost in each quicknode. QuickList defaults to a single ziplost with a length of 8KB. If the number of bytes is exceeded, another ziplost will be created. The length of the ziplist is determined by the configuration parameter list Max ziplist size. [QuickList compression depth] defaults to 0, that is, no compression. The actual depth is determined by list compress depth. The compression depth is 1, that is, the first and last elements are not compressed, and the compression depth is 2, that is, the first and second elements are not compressed.