天天看點
傳回

Redis核心原理與實踐--清單實作原理之quicklist結構

本文分析Redis中quicklist結構如何解決ziplist結構中的性能問題，并實作Redis的清單類型。本文内容摘自新書《Redis核心原理與實踐》。這本書深入地分析了Redis常用特性的内部機制與實作方式，内容源自對Redis源碼的分析，并從中總結出設計思路、實作原理。

在上一篇文章《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所示。

Redis核心原理與實踐--清單實作原理之quicklist結構

操作分析

插入元素到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)) 滿足以下條件：(1)待插入節點已滿 (2)尾插且後驅節點已滿，或者頭插且前驅節點已滿 建構一個新節點，将元素插入新節點，并根據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 6.0源碼，總結了Redis核心功能的設計與實作。通過閱讀本書，讀者可以深入了解Redis内部機制及最新特性，并學習到Redis相關的資料結構與算法、Unix程式設計、存儲系統設計，分布式系統架構等一系列知識。

經過該書編輯同意，我會繼續在個人技術公衆号（binecy）釋出書中部分章節内容，作為書的預覽内容，歡迎大家查閱，謝謝。

語雀平台預覽：《Redis核心原理與實踐》

京東連結

Redis核心原理與實踐
上一篇: mysql大小寫敏感配置
下一篇: The Rising Smart Logistics Industry: How to Use Big Data to Improve Efficiency and Save Costs

繼續閱讀