Redis 中的 List，底層采用了什么數(shù)據(jù)結(jié)構(gòu)？

作者：猿java 2025-01-14 08:00:00

本文我們從源碼角度分析了 Redis 的 List 數(shù)據(jù)結(jié)構(gòu)，它是一個(gè)高效、靈活的數(shù)據(jù)結(jié)構(gòu)，適用于多種應(yīng)用場景，如消息隊(duì)列、任務(wù)管理等。

這篇文章，我們將從 Redis List 的基本原理出發(fā)，深入分析其內(nèi)部實(shí)現(xiàn)機(jī)制、源碼層面的細(xì)節(jié)，并結(jié)合實(shí)際示例，全面解析 Redis List 的工作原理。

一、Redis List 概述

Redis 的 List 是一個(gè)簡單的字符串列表，按照插入順序排序。它支持在列表的兩端插入或刪除元素，具有以下特點(diǎn)：

有序：元素按照插入順序排列，可以通過索引訪問。
雙端操作：支持從左端（頭部）和右端（尾部）進(jìn)行插入和刪除操作。
高效：在兩端插入和刪除的時(shí)間復(fù)雜度為 O(1)。

常用的 List 命令包括 LPUSH、RPUSH、LPOP、RPOP、LINDEX、LRANGE 等。

二、Redis List 的內(nèi)部實(shí)現(xiàn)

Redis 的 List 數(shù)據(jù)結(jié)構(gòu)內(nèi)部實(shí)現(xiàn)主要依賴于兩個(gè)數(shù)據(jù)結(jié)構(gòu)：壓縮列表（ziplist）和雙端鏈表（quicklist）。根據(jù) List 的大小和元素的長度，Redis 會(huì)自動(dòng)選擇合適的數(shù)據(jù)結(jié)構(gòu)，以優(yōu)化存儲(chǔ)空間和操作效率。

1. 壓縮列表

壓縮列表是一種為節(jié)省內(nèi)存而設(shè)計(jì)的緊湊數(shù)據(jù)結(jié)構(gòu)。它將多個(gè)元素緊密存儲(chǔ)在一個(gè)連續(xù)的內(nèi)存塊中，適用于小型的 List。

結(jié)構(gòu)：壓縮列表由三個(gè)部分組成：ziplist header、entry list 和 ziplist end。
性能：適用于含有少量元素且每個(gè)元素較短的 List，節(jié)省內(nèi)存但在頻繁插入和刪除時(shí)性能較低。

2. 雙端鏈表

從 Redis 3.2 版本開始，List 的內(nèi)部實(shí)現(xiàn)改為使用 quicklist，它結(jié)合了壓縮列表和雙向鏈表的優(yōu)點(diǎn)。

結(jié)構(gòu)：quicklist 是由多個(gè)壓縮列表（ziplist）組成的雙向鏈表，每個(gè)壓縮列表稱為一個(gè)節(jié)點(diǎn)（node）。

優(yōu)勢：

高效插入與刪除：在兩端插入和刪除元素時(shí)，只需要操作鏈表的頭部或尾部節(jié)點(diǎn)，時(shí)間復(fù)雜度為 O(1)。
節(jié)省空間：每個(gè)節(jié)點(diǎn)內(nèi)部仍然使用壓縮列表存儲(chǔ)元素，節(jié)省內(nèi)存。

靈活性：適用于包含大量元素的 List。

三、源碼分析

下面將通過源碼分析 Redis List 的實(shí)現(xiàn)機(jī)制，重點(diǎn)關(guān)注 quicklist 相關(guān)的代碼部分。

1. 數(shù)據(jù)結(jié)構(gòu)定義

Redis 在 src/quicklist.h 文件中定義了 quicklist 相關(guān)的數(shù)據(jù)結(jié)構(gòu)。

// quicklist.h

typedefstruct quicklistEntry {
    unsignedchar *value; /* value of the entry */
    unsignedint sz;      /* length of the value */
    longlong longval;    /* long representation, if applicable */
    unsignedint encoding:4;
    unsignedint attempted_float_conversion:1;
} quicklistEntry;

typedefstruct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsignedchar *zl;     /* ziplist containing some entries */
    unsignedint sz;       /* byte size of ziplist */
    unsignedint count:16;
    unsignedint encoding:4;
    unsignedint container:4;
    unsignedint recompress:1;
} quicklistNode;

typedefstruct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    const quicklistCompress *compress;
    unsignedint count;    /* total count of all entries in all the nodes */
    unsignedlong len;    /* count of all elements */
    unsignedlong maxlevel;
    unsignedint fill:16;
    unsignedint compress_depth:4;
    unsignedint mem_compressed:1;
} quicklist;

主要的數(shù)據(jù)結(jié)構(gòu)包括：

quicklistEntry：表示 quicklist 中的一個(gè)條目（entry）。
quicklistNode：表示 quicklist 中的一個(gè)節(jié)點(diǎn)，包含一個(gè) ziplist。
quicklist：整個(gè) quicklist 結(jié)構(gòu)，包含頭尾節(jié)點(diǎn)、統(tǒng)計(jì)信息等。

2. 常用命令的實(shí)現(xiàn)

以下將以 LPUSH、RPUSH、LPOP、RPOP、LINDEX、LRANGE 等命令為例，分析它們在源碼中的實(shí)現(xiàn)。

3. LPUSH 和 RPUSH

LPUSH 和 RPUSH 用于在 List 的左端和右端插入元素。它們在 quicklist 中的實(shí)現(xiàn)主要涉及調(diào)用 quicklistPush 函數(shù)。

// listOp.c

void quicklistPush(quicklist *quicklist, void *value, size_t sz, int where) {
    // 省略參數(shù)檢查和類型轉(zhuǎn)換

    if (where == QUICKLIST_HEAD) {
        // 插入到鏈表頭部
        // 如果頭節(jié)點(diǎn)已滿，創(chuàng)建新節(jié)點(diǎn)
    } else {
        // 插入到鏈表尾部
        // 如果尾節(jié)點(diǎn)已滿，創(chuàng)建新節(jié)點(diǎn)
    }

    // 使用 ziplist 插入元素
    // 更新統(tǒng)計(jì)信息
}

核心邏輯：

判斷插入的位置（頭部或尾部）。
檢查對(duì)應(yīng)位置的節(jié)點(diǎn)是否有足夠空間插入新元素。
如果節(jié)點(diǎn)已滿，創(chuàng)建一個(gè)新的節(jié)點(diǎn)并插入。
在對(duì)應(yīng)節(jié)點(diǎn)的 ziplist 中插入新元素。
更新 quicklist 的統(tǒng)計(jì)信息。

4. LPOP 和 RPOP

LPOP 和 RPOP 用于從 List 的左端和右端彈出元素。它們主要調(diào)用 quicklistPopCustom 函數(shù)。

// listPop.c

int quicklistPopCustom(quicklist *quicklist, int where, long long *v, unsigned char **sval, unsigned int *slen) {
    if (where == QUICKLIST_HEAD) {
        // 從頭部節(jié)點(diǎn)的 ziplist 彈出元素
        // 如果節(jié)點(diǎn)為空，刪除節(jié)點(diǎn)并移動(dòng)到下一個(gè)節(jié)點(diǎn)
    } else {
        // 從尾部節(jié)點(diǎn)的 ziplist 彈出元素
        // 如果節(jié)點(diǎn)為空，刪除節(jié)點(diǎn)并移動(dòng)到前一個(gè)節(jié)點(diǎn)
    }

    // 更新統(tǒng)計(jì)信息和 quicklist 結(jié)構(gòu)
}

核心邏輯：

根據(jù)彈出的位置，選擇頭部或尾部節(jié)點(diǎn)。
從對(duì)應(yīng)節(jié)點(diǎn)的 ziplist 中彈出元素。
如果節(jié)點(diǎn)為空，刪除節(jié)點(diǎn)并更新鏈表指針。
更新 quicklist 的統(tǒng)計(jì)信息。

5. LINDEX

LINDEX 用于獲取 List 中指定索引的元素。它調(diào)用 quicklistIndex 函數(shù)。

// listIndex.c

quicklistEntry *quicklistIndex(quicklist *quicklist, long index) {
    // 處理負(fù)索引
    // 遍歷 quicklist 中的節(jié)點(diǎn)，累加節(jié)點(diǎn)中元素的數(shù)量
    // 找到包含目標(biāo)索引的節(jié)點(diǎn)
    // 在節(jié)點(diǎn)的 ziplist 中查找具體的元素
}

核心邏輯：

處理負(fù)索引（從尾部開始計(jì)數(shù)）。
遍歷 quicklist 的節(jié)點(diǎn)，累加每個(gè)節(jié)點(diǎn)的元素?cái)?shù)量。
確定目標(biāo)索引所在的節(jié)點(diǎn)。
在該節(jié)點(diǎn)的 ziplist 中查找目標(biāo)元素。

6. LRANGE

LRANGE 用于獲取 List 中指定范圍的元素。它調(diào)用 quicklistGetRange 函數(shù)。

// listRange.c

quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction) {
    // 創(chuàng)建一個(gè)迭代器，從頭部或尾部開始遍歷 quicklist
}

int quicklistNext(quicklistIter *i, quicklistEntry *entry) {
    // 通過迭代器遍歷 quicklist 中的元素
}

核心邏輯：

創(chuàng)建一個(gè)迭代器，指定遍歷方向（從頭到尾或從尾到頭）。
遍歷 quicklist 的節(jié)點(diǎn)和節(jié)點(diǎn)內(nèi)的 ziplist，收集指定范圍的元素。
返回結(jié)果集合。

四、性能優(yōu)化與選擇

Redis 在 List 的內(nèi)部實(shí)現(xiàn)中，通過 quicklist 結(jié)構(gòu)在節(jié)省內(nèi)存和提高操作效率之間取得了平衡。以下是一些性能優(yōu)化的考慮：

節(jié)點(diǎn)大小（fill factor）：quicklist 中每個(gè)節(jié)點(diǎn)的 ziplist 有一個(gè)填充因子（默認(rèn)是 4），決定了多少元素被存儲(chǔ)在一個(gè)節(jié)點(diǎn)中。適當(dāng)?shù)奶畛湟蜃涌梢詼p少節(jié)點(diǎn)數(shù)量，提高遍歷效率。
壓縮算法：quicklist 支持多種壓縮算法，通過配置可以進(jìn)一步優(yōu)化內(nèi)存使用。
迭代器機(jī)制：通過迭代器遍歷 quicklist，提高了操作的靈活性和效率。

在選擇使用 List 時(shí)，應(yīng)根據(jù)實(shí)際需求和數(shù)據(jù)規(guī)模合理設(shè)計(jì)，避免在極大的 List 上進(jìn)行頻繁的中間位置插入和刪除操作，因?yàn)檫@可能導(dǎo)致性能下降。

五、為什么List底層有兩種實(shí)現(xiàn)

List 數(shù)據(jù)結(jié)構(gòu)的底層采用了壓縮列表（ziplist）和雙端鏈表（quicklist），其實(shí)是內(nèi)存效率與操作性能之間取得最佳平衡。主要原因如下：

1. 壓縮列表

內(nèi)存節(jié)省：壓縮列表是一種為節(jié)省內(nèi)存而設(shè)計(jì)的緊湊數(shù)據(jù)結(jié)構(gòu)。它將多個(gè)元素緊密存儲(chǔ)在一個(gè)連續(xù)的內(nèi)存塊中，避免了傳統(tǒng)鏈表中每個(gè)節(jié)點(diǎn)需要額外指針（如前驅(qū)和后繼指針）帶來的內(nèi)存開銷。對(duì)于包含少量元素且每個(gè)元素較短的小型列表，壓縮列表能夠顯著減少內(nèi)存使用量。

緩存友好性：由于壓縮列表將所有元素存儲(chǔ)在一個(gè)連續(xù)的內(nèi)存區(qū)域中，這種布局有助于提升緩存命中率。CPU 在訪問數(shù)據(jù)時(shí)，能夠更高效地預(yù)取和緩存數(shù)據(jù)，從而提高訪問速度。

簡單數(shù)據(jù)結(jié)構(gòu)：壓縮列表的實(shí)現(xiàn)相對(duì)簡單，適用于不需要頻繁插入和刪除操作的場景。對(duì)于靜態(tài)或變化不大的小型列表，壓縮列表提供了足夠的性能和內(nèi)存效率。

2. 雙端鏈表

高效的兩端操作：雙端鏈表允許在列表的頭部和尾部進(jìn)行高效的插入和刪除操作，時(shí)間復(fù)雜度為 O(1)。這對(duì)于需要頻繁在兩端進(jìn)行操作的應(yīng)用場景（如隊(duì)列和棧）尤為重要。

動(dòng)態(tài)擴(kuò)展能力：與壓縮列表相比，雙端鏈表更適合處理動(dòng)態(tài)變化較大的列表。它能夠靈活地在任意位置插入和刪除元素，而不會(huì)像壓縮列表那樣需要整體移動(dòng)內(nèi)存塊。

分段存儲(chǔ)與性能優(yōu)化：Quicklist 通過將列表分段存儲(chǔ)，每個(gè)段使用壓縮列表（ziplist）作為節(jié)點(diǎn)，實(shí)現(xiàn)了分塊管理。這種設(shè)計(jì)兼具了壓縮列表的內(nèi)存效率和雙端鏈表的操作性能。具體來說，每個(gè) quicklist 節(jié)點(diǎn)內(nèi)部是一個(gè)壓縮列表，多個(gè)節(jié)點(diǎn)通過雙端鏈表連接起來。這樣，在需要進(jìn)行插入或刪除操作時(shí)，僅需操作相關(guān)的節(jié)點(diǎn)，而不影響整個(gè)列表結(jié)構(gòu)。

Redis 會(huì)根據(jù)列表的長度和元素的大小，自動(dòng)決定使用壓縮列表還是雙端鏈表。這種智能選擇機(jī)制確保了在不同場景下都能獲得最佳的性能和內(nèi)存使用率。例如：

小型列表：當(dāng)列表較小且元素較短時(shí)，Redis 會(huì)選擇壓縮列表，最大化內(nèi)存節(jié)省和緩存效率。
大型列表：當(dāng)列表變得較大或元素較長時(shí)，Redis 會(huì)轉(zhuǎn)而使用 quicklist，以提升操作性能和擴(kuò)展能力。

六、總結(jié)

本文，我們從源碼角度分析了 Redis 的 List 數(shù)據(jù)結(jié)構(gòu)，它是一個(gè)高效、靈活的數(shù)據(jù)結(jié)構(gòu)，適用于多種應(yīng)用場景，如消息隊(duì)列、任務(wù)管理等。通過內(nèi)部的 quicklist 結(jié)構(gòu)，Redis 在節(jié)省內(nèi)存和優(yōu)化操作效率方面做出了平衡。通過學(xué)習(xí)本文，我們也可以發(fā)現(xiàn) Redis 對(duì)性能的追求。

責(zé)任編輯：趙寧寧來源：猿java