Redis源码学习(12)-Redis中快速链表的实现（上）

根据前文的分析，我们了解到，基于经典双端链表的一些缺点，双端链表已经不再作为LIST对象的底层实现了。但是作为LIST的底层实现之一，压缩链表同样具有一定的劣势，压缩链表由于使用的是有一段连续的内存，这就意味着，执行插入操作导致内存大小发生变化时，便会引发一次内存的重新分配过程，同时还会执行一定量的数据移动。特别是对于压缩链表较长的情况下，大批量的数据移动势必会降低系统的性能。而在上述这个方面恰恰就是经典双端链表的优势，故此Redis设计实现了一种快速链表的数据结构，兼具经典双端链表与压缩链表的特点，实现了时间与空间上的一种折衷。

相信了解STL的人对上述的描述会有一种似曾相识的感觉。没错，STL中的deque便是使用上述思想实现的一种既可以在队列两端快速执行插入与删除操作，同时可以根据下标对数据进行随机访问的数据结构。

快速链表概述

在Redis中，作者结合了经典双端链表以及压缩链表的特性，实现了快速链表的数据结构。简单来说，使用双端链表的形式描述整个快速链表，而每一个快速链表的节点都是使用一个压缩链表作为底层数据存储，可以存储若干个数据节点。同时基于链表数据结构通常对头部与尾部的访问最为频繁，而对链表中间的数据访问并不是特别频繁，因此出于节省空间的目的，会对中间节点底层压缩链表所使用的内存进行压缩，Redis使用LZF算法对内存进行压缩，相应的算法被定义在src/lzf.h，src/lzfp.h，src/lzf_c.c，src/lzf_d.c这四个文件中，具体的压缩算法不属于Redis代码的核心，因此不做过多的讲解，有兴趣的同学可以自行研究，这里只给出压缩与解压的接口API：

unsigned int lzf_compress(const void *const in_data, unsigned int in_len, void *out_data, unsigned int out_len);unsigned int lzf_decompress(const void *const in_data, unsigned int in_len, void *out_data, unsigned int out_len);

其中快速链表节点quicklistNode
的数据结构如下所示：

typedef struct quicklistNode {    struct quicklistNode *prev;    struct quicklistNode *next;    unsigned char *zl;    unsigned int sz;    unsigned int count : 16;    unsigned int encoding : 2;    unsigned int container : 2;    unsigned int recompress : 1;    unsigned int attempted_commpress : 1;    unsigned int extra : 10;} quicklistNode;

在这个数据结构之中，

• quicklistNode.prev
  和quicklistNode.next
  这两节点作为双端链表的必要成员变量，用于指向当前节点的前序节点以及后续节点。

• quicklistNode.zl
  ，这个成员变量用于指向存储数据的内存，内存中可以是一个压缩链表，也可以是一个经过LZF算法压缩过的数据。

• quicklistNode.sz
  ，这个成员变量永远都会存储quicklistNode
  中压缩链表所占用的内存的长度，即使quicklistNode.zl
  中存储的是经过LZF算法压缩后的数据。

• quicklistNode.count
  ，用于存储在这个节点中的压缩率链表里数据节点的个数。

• quicklistNode.encoding
  ，用于表示这个节点中存储的数据是原始的压缩链表，还是经过LZF压缩过的数据，对于成员变量，Redis给出了两个定义，QUICKLIST_NODE_ENCODING_RAW
  用于表示当前quicklistNode.zl
  中存储的是原始的压缩链表；QUICKLIST_NODE_ENCODING_LZF
  用于表示当前quicklistNode.zl
  中存储的是经过LZF压缩的数据。

• quicklistNode.container
  ，用于表示当前这个节点所使用的容器类型，Redis给出两个容器类型的定义，QUICKLIST_NODE_CONTAINER_NONE
  ，这个定义在代码中并未使用；QUICKLIST_NODE_CONTAINER_ZIPLIST
  ，这个定义便是当前节点是使用压缩链表进行数据存储的。

• quicklistNode.recompress
  ，用于表示当前的节点是否处于临时被解压状态。

在本篇文章中，将会使用链表节点来表示quicklistNode
，同时使用数据节点来表示存储在quicklistNode
的压缩链表中的数据。

如果quicklistNode.encoding
是QUICKLIST_NODE_ENCODING_LZF
时，那么表示这个节点在quicklistNode.zl
中存储的是一个经过LZF压缩的数据，对于压缩数据，Redis也定义了对应的数据类型：

typedef struct quicklistLZF{    unsigned int sz;    char compressed[];} quicklistLZF;

这里quicklistLZF.sz
存储的是压缩数据的大小，quicklistLZF.compressed
则是存储压缩数据的具体内容。这里需要注意区别quicklisLZF.sz
和quicklistNode.sz
这两个字段，quicklistNode.sz
之所以要永远记录原始压缩链表的大小，是为了在对quicklistNode
节点进行某些操作时，可以不解压LZF数据，便可以确定原始数据的大小。

快速链表数据结构quicklist
便是以双端链表的形式，组织维护所有的quicklistNode
节点的，下面便是quicklist
的数据结构：

typedef struct quicklist{    quicklistNode *head;    quicklistNode *tail;    unsigned long count;    unsigned long len;    int fill : 16;    unsigned int compress : 16;} quicklist;

• quicklist.head
  和quicklist.tail
  两个指针分别指向了快速链表的头节点与尾节点。

• quicklist.count
  用于标记这个快速链表中的数据节点的个数，quicklist.len
  则是标记了快速链表节点quicklistNode
  的个数，这两个字段的区别需要注意。

• quicklist.fill
  是快速链表的装载因子，对于这个装载因子，有两种情况：

1. 如果装载因子为正数，那么表示每一个快速链表节点quicklistNode
   中存储数据节点的个数的上限，例如quicklist.fill
   被设置成10，那么意味着每个quicklisNode
   的压缩链表中最多只能存储10个数据节点。

2. 如果装载因子为负数，则标记了每个quicklistNode
   中压缩链表的最大内存大小，也就是quicklistNode.sz
   字段的上限。

• quicklist.compress
  则是这个压缩链表的压缩深度，因为前面已经提到过双端链表的访问主要集中在链表的两端，因此快速链表使用这个字段来确定在链表两端不被压缩的链表节点quicklistNode
  的个数；另外通常下情况下，链表处于中间的quicklistNode
  都是使用的LZF算法压缩后的数据，只有在需要访问的时候，才会被临时解压出来。

同样的，为了实现对这个快速链表中数据节点的遍历，Redis设计了快速链表迭代器的数据结构：

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

在这个数据结构中

• quicklistIter.quicklist
  表示这个迭代器所绑定的快速链表。

• quicklistIter.current
  表示这个迭代器当前遍历到的链表节点。

• quicklistIter.si
  表示这个迭代器当前遍历的数据节点。

• quicklistIter.offset
  表示这个迭代器当前遍历的数据节点在链表节点之中的偏移。

• quicklistIter.direction
  表示这个迭代器的遍历方向，Redis在src/quicklist.h头文件中定义了迭代器的遍历方向，AL_START_HEAD
  为正向遍历，AL_START_TAIL
  为反向遍历。

与压缩链表中所定义的zlentry
数据节点用以描述压缩链表中的节点类似，快速链表中也定义了类似的数据结构用来描述数据节点：

typedef struct quicklistEntry{    const quicklist *quicklist;    quicklistNode *node;    unsigned char *zi;    unsigned char *value;    long long longval;    unsigned int sz;    int offset;} quicklistEntry;

在这个数据结构中：

• quicklistEntry.quicklist
  指向这个数据节点所在的快速链表；quicklistEntry.node
  指向这个数据节点所在的链表节点；quicklistEntry.zi
  指向数据节点在链表节点之中的位置。

• 如果数据节点中存储的是字符串编码的数据，那么quicklistEntry.value
  和quicklistEntry.sz
  这两个字段用来标记这个字符串编码数据。

• 如果数据节点中存储的是整数编码的数据，那么会从对应的压缩链表中解码出这个整数数据，将之存储在quicklistEntry.longval
  字段中。

• quiclistEntry.offset
  的含义与quicklistIter.offset
  一致，都是表示当前数据节点在链表节点的压缩链表中的偏移。