Redis是C語(yǔ)言編寫的，沒(méi)有自帶的鏈表結(jié)構(gòu)，需要自己實(shí)現(xiàn)鏈表。鏈表被廣泛用于Redis的各種功能，比如客戶端狀態(tài)鏈表、客戶端輸出緩沖區(qū)、列表鍵、發(fā)布與訂閱、慢查詢、監(jiān)視器等。
列表鍵的底層實(shí)現(xiàn)之一就是鏈表（Redis3.2之前使用的是普通列表adlist.h/list，在Redis3.2 后被換成了快速列表quicklist.h/quicklist）。當(dāng)一個(gè)列表建包含了數(shù)量比較多的元素，又或者列表中包含的元素都是比較長(zhǎng)的字符串時(shí)，Reids會(huì)使用鏈表作為列表鍵的底層實(shí)現(xiàn)。
quicklist是由ziplist組成的雙向鏈表，鏈表中的每一個(gè)節(jié)點(diǎn)都以壓縮列表ziplist的結(jié)構(gòu)保存著數(shù)據(jù)，而ziplist有多個(gè)entry節(jié)點(diǎn)，保存著數(shù)據(jù)。相當(dāng)于一個(gè)quicklist節(jié)點(diǎn)保存的是一片數(shù)據(jù)，而不是一個(gè)數(shù)據(jù)。
例如：一個(gè)quicklist有4個(gè)quicklist節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都保存著1個(gè)ziplist結(jié)構(gòu)，每個(gè)ziplist的大小不超過(guò)8kb，ziplist的entry節(jié)點(diǎn)中的value成員保存著數(shù)據(jù)。
1 快速列表節(jié)點(diǎn)和快速列表的實(shí)現(xiàn)
快速列表的每個(gè)節(jié)點(diǎn)用一個(gè)quicklist.h/quicklist結(jié)構(gòu)來(lái)表示：
/* 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; /* ziplist的上一個(gè)節(jié)點(diǎn) */
struct quicklistNode *next; /* ziplist的下一個(gè)節(jié)點(diǎn) */
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;
多個(gè)quicklistNode可以通過(guò)prev和next指針組成雙端鏈表quicklist:
/* 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;
2 Redis鏈表的特性
Redis 的鏈表實(shí)現(xiàn)的特性可以總結(jié)如下：
- 雙向
quicklist宏觀上是一個(gè)雙向鏈表，因此具有一個(gè)雙向鏈表的優(yōu)點(diǎn)，進(jìn)行插入或刪除操作時(shí)非常方便，復(fù)雜度為O(n)，但是不需要內(nèi)存的復(fù)制，提高了效率。鏈表節(jié)點(diǎn)帶有 prev 和 next 指針， 獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的復(fù)雜度都是 O(1) 。 - 線性
表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的 next 指針都指向 NULL ， 對(duì)鏈表的訪問(wèn)以 NULL 為終點(diǎn)。 - 帶表頭指針和表尾指針
通過(guò)quicklist結(jié)構(gòu)的 head 指針和 tail 指針， 程序獲取鏈表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的復(fù)雜度為 O(1) 。 - 帶鏈表長(zhǎng)度計(jì)數(shù)器和數(shù)據(jù)項(xiàng)計(jì)數(shù)器
Redis使用 quicklist 結(jié)構(gòu)的 len 屬性來(lái)對(duì) quicklist 持有的quicklistNode(即ziplist)進(jìn)行計(jì)數(shù)，獲取鏈表中節(jié)點(diǎn)數(shù)量的復(fù)雜度為 O(1) 。
Redis使用 quicklist 結(jié)構(gòu)的 count 屬性來(lái)對(duì) quicklist 持有的數(shù)據(jù)項(xiàng)(即所有ziplist包含的數(shù)據(jù)項(xiàng)總數(shù))進(jìn)行計(jì)數(shù)，獲取鏈表中所有數(shù)據(jù)項(xiàng)總數(shù)量的復(fù)雜度為 O(1) 。 - 每個(gè)ziplist節(jié)點(diǎn)內(nèi)存連續(xù)
quicklist微觀上是一片片entry節(jié)點(diǎn)，每一片entry節(jié)點(diǎn)(即一個(gè)ziplist)內(nèi)存連續(xù)且順序存儲(chǔ)，可以通過(guò)二分查找以 log2(n) 的復(fù)雜度進(jìn)行定位，和B樹(shù)每個(gè)節(jié)點(diǎn)的存儲(chǔ)方式相似。
3 Redis快速鏈表相關(guān)結(jié)構(gòu)和常用API定義
#ifndef __QUICKLIST_H__
#define __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: 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;
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;
#define QUICKLIST_HEAD 0
#define QUICKLIST_TAIL -1
/* quicklist node encodings */
#define QUICKLIST_NODE_ENCODING_RAW 1
#define QUICKLIST_NODE_ENCODING_LZF 2
/* quicklist compression disable */
#define QUICKLIST_NOCOMPRESS 0
/* quicklist container formats */
#define QUICKLIST_NODE_CONTAINER_NONE 1
#define QUICKLIST_NODE_CONTAINER_ZIPLIST 2
#define quicklistNodeIsCompressed(node) \
((node)->encoding == QUICKLIST_NODE_ENCODING_LZF)
/* Prototypes */
quicklist *quicklistCreate(void);
quicklist *quicklistNew(int fill, int compress);
void quicklistSetCompressDepth(quicklist *quicklist, int depth);
void quicklistSetFill(quicklist *quicklist, int fill);
void quicklistSetOptions(quicklist *quicklist, int fill, int depth);
void quicklistRelease(quicklist *quicklist);
int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);
int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);
void quicklistPush(quicklist *quicklist, void *value, const size_t sz, int where);
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl);
quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist, unsigned char *zl);
quicklist *quicklistCreateFromZiplist(int fill, int compress, unsigned char *zl);
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node, void *value, const size_t sz);
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node, void *value, const size_t sz);
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data, int sz);
int quicklistDelRange(quicklist *quicklist, const long start, const long stop);
quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction);
quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist, int direction, const long long idx);
int quicklistNext(quicklistIter *iter, quicklistEntry *node);
void quicklistReleaseIterator(quicklistIter *iter);
quicklist *quicklistDup(quicklist *orig);
int quicklistIndex(const quicklist *quicklist, const long long index, quicklistEntry *entry);
void quicklistRewind(quicklist *quicklist, quicklistIter *li);
void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);
void quicklistRotate(quicklist *quicklist);
int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data, unsigned int *sz, long long *sval,
void *(*saver)(unsigned char *data, unsigned int sz));
int quicklistPop(quicklist *quicklist, int where, unsigned char **data, unsigned int *sz, long long *slong);
unsigned long quicklistCount(const quicklist *ql);
int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len);
size_t quicklistGetLzf(const quicklistNode *node, void **data);
#ifdef REDIS_TEST
int quicklistTest(int argc, char *argv[]);
#endif
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
#endif /* __QUICKLIST_H__ */
參考：
