Redis核心原理與實踐--列錶實現原理之quicklist結構

binecy 2021-09-19 08:50:39 阅读数:744

redis 核心 原理 原理 quicklist

在上一篇文章《Redis列錶實現原理之ziplist結構》,我們分析了ziplist結構如何使用一塊完整的內存存儲列錶數據。
同時也提出了一個問題:如果鏈錶很長,ziplist中每次插入或删除節點時都需要進行大量的內存拷貝,這個性能是無法接受的。
本文分析quicklist結構如何解决這個問題,並實現Redis的列錶類型。

quicklist的設計思想很簡單,將一個長ziplist拆分為多個短ziplist,避免插入或删除元素時導致大量的內存拷貝。
ziplist存儲數據的形式更類似於數組,而quicklist是真正意義上的鏈錶結構,它由quicklistNode節點鏈接而成,在quicklistNode中使用ziplist存儲數據。

提示:本文以下代碼如無特殊說明,均比特於quicklist.h/quicklist.c中。
本文以下說的“節點”,如無特殊說明,都指quicklistNode節點,而不是ziplist中的節點。

定義

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_compress : 1;
unsigned int extra : 10;
} quicklistNode;
  • prev、next:指向前驅節點,後驅節點。
  • zl:ziplist,負責存儲數據。
  • sz:ziplist占用的字節數。
  • count:ziplist的元素數量。
  • encoding:2代錶節點已壓縮,1代錶沒有壓縮。
  • container:目前固定為2,代錶使用ziplist存儲數據。
  • recompress:1代錶暫時解壓(用於讀取數據等),後續需要時再將其壓縮。
  • extra:預留屬性,暫未使用。

當鏈錶很長時,中間節點數據訪問頻率較低。這時Redis會將中間節點數據進行壓縮,進一步節省內存空間。Redis采用是無損壓縮算法—LZF算法。
壓縮後的節點定義如下:

typedef struct quicklistLZF {
unsigned int sz;
char compressed[];
} quicklistLZF;
  • sz:壓縮後的ziplist大小。
  • compressed:存放壓縮後的ziplist字節數組。

quicklist的定義如下:

typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count;
unsigned long len;
int fill : QL_FILL_BITS;
unsigned int compress : QL_COMP_BITS;
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
  • head、tail:指向頭節點、尾節點。
  • count:所有節點的ziplist的元素數量總和。
  • len:節點數量。
  • fill:16bit,用於判斷節點ziplist是否已滿。
  • compress:16bit,存放節點壓縮配置。

quicklist的結構如圖2-5所示。
圖2-5

操作分析

插入元素到quicklist頭部:

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
// [1]
if (likely(
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
// [2]
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
// [3]
quicklistNodeUpdateSz(quicklist->head);
} else {
// [4]
quicklistNode *node = quicklistCreateNode();
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
quicklistNodeUpdateSz(node);
_quicklistInsertNodeBefore(quicklist, quicklist->head, node);
}
quicklist->count++;
quicklist->head->count++;
return (orig_head != quicklist->head);
}

參數說明:

  • value、sz:插入元素的內容與大小。

【1】判斷head節點ziplist是否已滿,_quicklistNodeAllowInsert函數中根據quicklist.fill屬性判斷節點是否已滿。
【2】head節點未滿,直接調用ziplistPush函數,插入元素到ziplist中。
【3】更新quicklistNode.sz屬性。
【4】head節點已滿,創建一個新節點,將元素插入新節點的ziplist中,再將該節點頭插入quicklist中。

也可以在quicklist的指定比特置插入元素:

REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
void *value, const size_t sz, int after) {
int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
int fill = quicklist->fill;
quicklistNode *node = entry->node;
quicklistNode *new_node = NULL;
...
// [1]
if (!_quicklistNodeAllowInsert(node, fill, sz)) {
full = 1;
}
if (after && (entry->offset == node->count)) {
at_tail = 1;
if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
full_next = 1;
}
}
if (!after && (entry->offset == 0)) {
at_head = 1;
if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
full_prev = 1;
}
}
// [2]
...
}

參數說明:

  • entry:quicklistEntry結構,quicklistEntry.node指定元素插入的quicklistNode節點,quicklistEntry.offset指定插入ziplist的索引比特置。
  • after:是否在quicklistEntry.offset之後插入。

【1】根據參數設置以下標志。

  • full:待插入節點ziplist是否已滿。
  • at_tail:是否ziplist尾插。
  • at_head:是否ziplist頭插。
  • full_next:後驅節點是否已滿。
  • full_prev:前驅節點是否已滿。

提示:頭插指插入鏈錶頭部,尾插指插入鏈錶尾部。

【2】根據上面的標志進行處理,代碼較煩瑣,這裏不再列出。
這裏的執行邏輯如錶2-2所示。

條件 條件說明 處理方式
!full && after 待插入節點未滿,ziplist尾插 再次檢查ziplist插入比特置是否存在後驅元素,如果不存在則調用ziplistPush函數插入元素(更快),否則調用ziplistInsert插入元素
!full && !after 待插入節點未滿,非ziplist尾插 調用ziplistInsert函數插入元素
full && at_tail && node -> next && !full_next && after 待插入節點已滿,尾插,後驅節點未滿 將元素插入後驅節點ziplist中
full && at_head && node -> prev && !full_prev && !after 待插入節點已滿,ziplist頭插,前驅節點未滿 將元素插入前驅節點ziplist中
full && ((at_tail && node -> next && full_next && after) ||(at_head && node->prev && full_prev && !after)) 待插入節點已滿,尾插且後驅節點已滿,或者頭插且前驅節點已滿 構建一個新節點,將元素插入新節點,並根據after參數將新節點插入quicklist中
full 待插入節點已滿,並且在節點ziplist中間插入 將插入節點的數據拆分到兩個節點中,再插入拆分後的新節點中

我們只看最後一種場景的實現:

 // [1]
quicklistDecompressNodeForUse(node);
// [2]
new_node = _quicklistSplitNode(node, entry->offset, after);
new_node->zl = ziplistPush(new_node->zl, value, sz,
after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
new_node->count++;
quicklistNodeUpdateSz(new_node);
// [3]
__quicklistInsertNode(quicklist, node, new_node, after);
// [4]
_quicklistMergeNodes(quicklist, node);

【1】如果節點已壓縮,則解壓節點。
【2】從插入節點中拆分出一個新節點,並將元素插入新節點中。
【3】將新節點插入quicklist中。
【4】嘗試合並節點。_quicklistMergeNodes嘗試執行以下操作:

  • 將node->prev->prev合並到node->prev。
  • 將node->next合並到node->next->next。
  • 將node->prev合並到node。
  • 將node合並到node->next。
    合並條件:如果合並後節點大小仍滿足quicklist.fill參數要求,則合並節點。
    這個場景處理與B+樹的節點分裂合並有點相似。

quicklist常用的函數如錶2-3所示。

函數 作用
quicklistCreate、quicklistNew 創建一個空的quicklist
quicklistPushHead,quicklistPushTail 在quicklist頭部、尾部插入元素
quicklistIndex 查找給定索引的quicklistEntry節點
quicklistDelEntry 删除給定的元素

配置說明

  • list-max-ziplist-size:配置server.list_max_ziplist_size屬性,該值會賦值給quicklist.fill。取正值,錶示quicklist節點的ziplist最多可以存放多少個元素。例如,配置為5,錶示每個quicklist節點的ziplist最多包含5個元素。取負值,錶示quicklist節點的ziplist最多占用字節數。這時,它只能取-1到-5這五個值(默認值為-2),每個值的含義如下:
    -5:每個quicklist節點上的ziplist大小不能超過64 KB。
    -4:每個quicklist節點上的ziplist大小不能超過32 KB。
    -3:每個quicklist節點上的ziplist大小不能超過16 KB。
    -2:每個quicklist節點上的ziplist大小不能超過8 KB。
    -1:每個quicklist節點上的ziplist大小不能超過4 KB。
  • list-compress-depth:配置server.list_compress_depth屬性,該值會賦值給quicklist.compress。
    0:錶示節點都不壓縮,Redis的默認配置。
    1:錶示quicklist兩端各有1個節點不壓縮,中間的節點壓縮。
    2:錶示quicklist兩端各有2個節點不壓縮,中間的節點壓縮。
    3:錶示quicklist兩端各有3個節點不壓縮,中間的節點壓縮。
    以此類推。

編碼

ziplist由於結構緊凑,能高效使用內存,所以在Redis中被廣泛使用,可用於保存用戶列錶、散列、有序集合等數據。
列錶類型只有一種編碼格式OBJ_ENCODING_QUICKLIST,使用quicklist存儲數據(redisObject.ptr指向quicklist結構)。列錶類型的實現代碼在t_list.c中,讀者可以查看源碼了解實現更多細節。

總結

  • ziplist是一種結構緊凑的數據結構,使用一塊完整內存存儲鏈錶的所有數據。
  • ziplist內的元素支持不同的編碼格式,以最大限度地節省內存。
  • quicklist通過切分ziplist來提高插入、删除元素等操作的性能。
  • 鏈錶的編碼格式只有OBJ_ENCODING_QUICKLIST。

本文內容摘自作者新書《Redis核心原理與實踐》,這本書深入地分析了Redis常用特性的內部機制與實現方式,大部分內容源自對Redis源碼的分析,並從中總結出設計思路、實現原理。通過閱讀本書,讀者可以快速、輕松地了解Redis的內部運行機制。
經過該書編輯同意,我會繼續在個人技術公眾號(binecy)發布書中部分章節內容,作為書的預覽內容,歡迎大家查閱,謝謝。

版权声明:本文为[binecy]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919085039112N.html