Redis 快速列錶

1. 介紹

之前我們介紹了鏈錶結構和壓縮列錶結構，它們是列錶鍵的底層實現方式，但是鏈錶的附加空間有點高，因為prev和next指針會占掉一部分的空間（64比特系統占用8 + 8 = 16字節）.而且鏈錶的每個節點都是單獨分配內存，會加劇內存的碎片化.

所以在redis-3.2版本開始，Redis使用quicklist作為列錶鍵的底層實現.

2. quicklist實現

quicklist實際上是zipList和linkedList的混合體，它把zipList放在linkedList的每個結點中，實現緊凑存儲.

2.1 quicklist錶頭結構

typedef struct quicklist {
    
    // 指向頭部(最左邊)quicklist節點的指針
    quicklistNode *head;
    // 指向尾部(最右邊)quicklist節點的指針
    quicklistNode *tail;
    // ziplist節點計數器
    unsigned long count;
    // quicklist節點計數器
    unsigned int len;
    // 保存ziplist的大小，配置文件設定，占16bits
    int fill : 16;
    // 節點壓縮程度，配置文件設定，占16bits，0錶示不壓縮
    unsigned int compress : 16;
} quicklist;

其中fill和compress屬性是可以配置的，在redis.conf文件中.

• fill屬性對應的配置：list-max-ziplist-size -2
  • 當數字為負數時，錶示下列含義：
    • -1錶示每個quicklistNode節點的ziplist字節大小不能超過4kb.
    • -2錶示每個quicklistNode節點的ziplist字節大小不能超過8kb（默認）.
    • -3錶示每個quicklistNode節點的ziplist字節大小不能超過16kb.
    • -4錶示每個quicklistNode節點的ziplist字節大小不能超過32kb.
    • -5錶示每個quicklistNode節點的ziplist字節大小不能超過64kb.
  • 當數字為正數時，錶示下列含義：
    • 錶示ziplist結構能包含的entry的最大個數，最大值為2 ^ 15.
  • compress屬性對應的配置：list-compress-depth 0
  • 0錶示不壓縮（默認）.
  • 1錶示quicklist列錶的兩端各有1個節點不壓縮，中間的節點壓縮.
  • 2錶示quicklist列錶的兩端各有2個節點不壓縮，中間的節點壓縮.
  • 3錶示quicklist列錶的兩端各有3個節點不壓縮，中間的節點壓縮.
  • 最大值為2 ^ 16.

2.2 quicklist節點結構

typedef struct quicklistNode {
    
    struct quicklistNode *prev;     //前驅節點指針
    struct quicklistNode *next;     //後繼節點指針
    // 不設置壓縮數據參數時指向一個ziplist結構，設置壓縮數據參數指向quicklistLZF結構
    unsigned char *zl;
    // 壓縮列錶ziplist的總長度
    unsigned int sz;
    // ziplist中的節點數，占16 bits長度
    unsigned int count : 16;
    // 錶示是否采用LZF壓縮算法壓縮quicklist節點，1錶示不采用，2錶示采用，占2 bits長度
    unsigned int encoding : 2;
    // 錶示一個quicklistNode節點是否采用ziplist結構保存數據，2錶示采用，1錶示不采用，默認是2，占2bits長度
    unsigned int container : 2;
    // 標記quicklist是否壓縮過，占1bit長度
    // 如果recompress為1，則等待被再次壓縮
    unsigned int recompress : 1;
    // 測試時使用
    unsigned int attempted_compress : 1;
    // 額外擴展比特，占10bits長度
    unsigned int extra : 10;
} quicklistNode;

2.3 被壓縮過的ziplist

typedef struct quicklistLZF {
    
    // 錶示被LZF算法壓縮後的ziplist的大小
    unsigned int sz;
    // 保存壓縮後的ziplist的數組，柔性數組
    char compressed[];
} quicklistLZF;

2.4 quicklistEntry

// 管理quicklist中quicklistNode節點中ziplist信息的結構
typedef struct quicklistEntry {
    
	// 指向所屬的quicklist的指針
    const quicklist *quicklist;
    // 指向所屬的quicklistNode節點的指針
    quicklistNode *node;
    // 指向當前ziplist結構的指針 
    unsigned char *zi;
     // 指向當前ziplist結構的字符串vlaue成員 
    unsigned char *value;
    // 指向當前ziplist結構的整數value成員 
    long long longval;            
    // 保存當前ziplist結構的字節數大小
    unsigned int sz;
    // 保存相對ziplist的偏移量
    int offset;
} quicklistEntry;

3. 常用操作

3.1 插入

quicklist可以選擇在頭部或者尾部進行插入，對應的API是quicklistPushHead和quicklistPushTail：

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    
	// 備份頭結點地址
    quicklistNode *orig_head = quicklist->head;
    // 如果ziplist可以插入entry節點
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
    
        quicklist->head->zl =
        	// 將節點push到頭部
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        // 更新quicklistNode記錄ziplist大小的sz
        quicklistNodeUpdateSz(quicklist->head);
    } else {
    
    	// 如果不能插入entry節點到ziplist
    	// 新創建一個quicklistNode節點
        quicklistNode *node = quicklistCreateNode();
        //將entry節點push到新創建的quicklistNode節點中
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
		// 更新ziplist的大小sz
        quicklistNodeUpdateSz(node);
        // 將新創建的節點插入到頭節點前
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    // 更新quicklistNode計數器
    quicklist->count++;
    // 更新entry計數器
    quicklist->head->count++;
    // 如果改變頭節點指針則返回1，否則返回0
    return (orig_head != quicklist->head);
}

int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
    
    quicklistNode *orig_tail = quicklist->tail;
    // 如果ziplist可以插入entry節點
    if (likely(
            _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
    
        quicklist->tail->zl =
       		// 將節點push到尾部
            ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
        // 更新quicklistNode記錄ziplist大小的sz
        quicklistNodeUpdateSz(quicklist->tail);
    } else {
    
    	// 新創建一個quicklistNode節點
        quicklistNode *node = quicklistCreateNode();
        // 將entry節點push到新創建的quicklistNode節點中
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
		// 更新ziplist的大小sz
        quicklistNodeUpdateSz(node);
        // 將新創建的節點插入到尾節點後
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    // 更新quicklistNode計數器
    quicklist->count++;
    // 更新entry計數器
    quicklist->tail->count++;
    // 如果改變尾節點指針則返回1，否則返回0
    return (orig_tail != quicklist->tail);
}

參考資料：

《Redis設計與實現》

Redis源碼剖析和注釋