當前位置:網站首頁>Redis源碼與設計剖析 -- 7.快速列錶

Redis源碼與設計剖析 -- 7.快速列錶

2022-07-23 10:49:22JunesFour

Redis 快速列錶



1. 介紹

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

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

2. quicklist實現

quicklist實際上是zipListlinkedList的混合體,它把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;

其中fillcompress屬性是可以配置的,在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是quicklistPushHeadquicklistPushTail

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源碼剖析和注釋

版權聲明
本文為[JunesFour]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/204/202207230451475746.html

隨機推薦