回答

Redis 中的 List 數(shù)據(jù)結(jié)構(gòu)是一個雙向鏈表，用于存儲一個序列的數(shù)據(jù)，它類似于 Java 中的數(shù)組或列表，其底層實現(xiàn)分為兩個版本：

• 3.2 版本以前使用 linkedlist + ziplist

  • 當列表中元素的?度較?或者數(shù)量較少時，通常采?zipList來存儲。原因是因為 zipList 是一個緊湊的數(shù)據(jù)結(jié)構(gòu)，能夠有效地減少內(nèi)存占用。但是，在列表中元素較多或者元素較大時，zipList 的性能會下降，因為在列表的頭部或尾部添加或刪除元素時，可能需要重新分配并復(fù)制整個 ziplist。所以，zipList 非常適合少量的小數(shù)據(jù)存儲。同時 zipList 還有一個“連鎖更新”的問題，也會嚴重影響 ziplist 的性能。
  • 當列表元素大于 512 或者元素的長度大于 64 字節(jié)時，List 底層由 zipList 轉(zhuǎn)換為linkedlist。linkedlist 是一個雙向鏈表，能夠快速支持列表的刪除和插入操作，但是內(nèi)存利用率較低，因為它需要額外的內(nèi)存空間來維護鏈表結(jié)構(gòu)。

• 3.2 版本以后使用 quicklist

  • 從 3.2 版本開始后，List 的底層實現(xiàn)采用 quicklist。quicklist 是將 zipList 作為節(jié)點嵌入 linkedList 的節(jié)點中，它結(jié)合了兩者的優(yōu)點，也具備兩者的優(yōu)點。具體來說，quicklist 是由多個 ziplist 節(jié)點組成的 linkedList 鏈表，每個 ziplist 節(jié)點可以存儲多個列表元素。

擴展

List 介紹

List 的 Redis 中的 5 種主要數(shù)據(jù)結(jié)構(gòu)之一，它是一種序列集合，可以存儲一個有序的字符串列表，順序是插入的順序。我們可以使用相關(guān)命令添加一個字符串元素到 List 的頭部（左邊）或者尾部。

**List 的最大長度為 2^31 - 1，即每個 List 支持超過 40 億個元素。**主要特點如下：

• 有序性：List 中的元素按照插入順序排序，可以在列表的頭部或尾部添加元素。
• 雙向鏈表：List 內(nèi)部通過雙向鏈表實現(xiàn)，使得在列表的兩端操作（如插入和刪除）都非常快，時間復(fù)雜度為 O(1)。
• 元素重復(fù)性：List 允許重復(fù)的元素。
• 元素訪問：List 支持通過索引訪問元素（如 LINDEX 命令），但這是通過遍歷實現(xiàn)的，因此其時間復(fù)雜度為 O(N)。若 List 元素較多，則訪問效率較低

List 常用的命令如下：

• LPUSH key value1 [value2]：將一個或多個元素插入到列表頭部。如果 key 不存在，一個空列表會被創(chuàng)建并執(zhí)行 LPUSH 操作。返回值是操作后列表的長度。

• RPUSH key value1 [value2]：將一個或多個值插入到列表尾部。類似于 LPUSH

• LPOP key：移除并返回列表的第一個元素。如果列表為空，返回 nil。

• RPOP key：移除并返回列表的最后一個元素。如果列表為空，返回 nil。

• LLEN key：返回列表的長度，如果 key 不存在 返回 0。

• LINDEX key index：獲取列表在 index 位置的元素。index 是基于 0 的，也可以是負數(shù)，-1 表示最后一個元素，-2 表示倒數(shù)第二個元素等。

• LSET key index value：將列表的 index 位置的值設(shè)置為 value。如果 index 超出范圍，操作會返回一個錯誤。

• LRANGE key start stop：獲取列表指定范圍內(nèi)的元素。start 和 stop 都是基于 0 的索引，可以使用負數(shù)索引指定位置。

• LREM key count value：根據(jù)參數(shù) count 的值，移除與參數(shù) value 相等的元素。count 的值可以是以下幾種：

  • count > 0：從頭到尾，移除最多 count 個 value 相等的元素。
  • count < 0：從尾到頭，移除最多 -count 個 value 相等的元素。
  • count = 0：移除所有 value 相等的元素。

• LTRIM key start stop：對一個列表進行修剪(trim)，就是說，讓列表只保留指定區(qū)間內(nèi)的元素，不在指定區(qū)間之內(nèi)的元素都將被刪除。

下面是 List 常用命令的演示：

需要注意的是，List 設(shè)置過期時間，只能給整個 List 設(shè)置過期時間，不能單獨給某一個元素設(shè)置。

List 的底層實現(xiàn)

List 的底層實現(xiàn)有三種：zipList、linkedList 和 quickList。他們的使用情況如下：

• 當 List 存儲的元素較少且每個元素的大小也較小時，Redis 會選擇使用 zipList 來存儲數(shù)據(jù)，以節(jié)省內(nèi)存空間。
• 當列表元素大于 512 或者元素的長度大于 64 字節(jié)時，Redis 則轉(zhuǎn)換為使用 linkedList 來存儲數(shù)據(jù)，以優(yōu)化操作的性能。

zipList

當 List 中的元素比較少或者每個元素的大小也小時，Redis 選擇 zipList 來存儲數(shù)據(jù)。zipList 通過緊湊的內(nèi)存布局存儲一系列的 entry，每個 entry 可以代表一個字符串或者整數(shù)。

zipList 的內(nèi)部結(jié)構(gòu)主要分為三個部分：表頭（header）、條目（entries）和表尾（end），如下圖：

• 表頭（header）

  • zlbytes：4 個字節(jié)，記錄整個 ziplist 占用的總字節(jié)數(shù)。
  • zltail：4 個字節(jié)，記錄到 ziplist 最后一個元素的偏移量，這樣就可以快速定位到最后一個元素，提高從列表尾部添加或者訪問元素的效率。
  • zllen：2 個字節(jié)，記錄 ziplist 中元素的個數(shù)。

• 條目（entries）

  • 列表元素 entry。每個entry可以存儲字符串或者整數(shù)。entry 的結(jié)構(gòu)取決于它所存儲的數(shù)據(jù)類型和大小。

• 表尾（end）

  • 一個字節(jié)的特殊值0xFF，用于標記壓縮列表的結(jié)束。

entry 的結(jié)構(gòu)與其存儲的數(shù)據(jù)類型相關(guān)，如下：

存儲字符串時，有三個部分，而整數(shù)只有兩個部分，主要是因為整數(shù)是以最緊湊的格式存儲，沒有使用任何額外的標記或填充字節(jié)，所以在 zipList 中，整數(shù)值的編碼同時包含了類型信息和實際的整數(shù)值。

• prevlen

記錄前一個 entry 占用字節(jié)數(shù)，zipList 能實現(xiàn)逆序遍歷就是靠這個字段確定往前移動多少字節(jié)拿到上一個 entry 首地址。

若前一個 entry 長度小于 254 個字節(jié)時，則 prevlen 占用 1 個字節(jié)。若前一個 entry 長度大于等于 254 個字節(jié)，則 prevlen 占用 5 個字節(jié)，第一個字節(jié)設(shè)為0xFE，接下來的4字節(jié)用于存儲實際的長度值。

• encoding

用于表示當前 entry 的類型和長度，當前 entry 的長度和值是根據(jù)保存的是整數(shù)還是字符串以及數(shù)據(jù)的長度共同來決定。

前兩位用于表示類型，當前兩位值為 “11” 則表示 entry 存放的是整數(shù)類型數(shù)據(jù)，其他表示存儲的是字符串。

• entry-data

實際存儲數(shù)據(jù)的位置。如果 entry 存儲整數(shù)類型，則沒有這個 entry-data，它會合并到 encoding 中。

zipList 適合較少元素的存儲，如果元素過多的話，則查詢效率會大打折扣，時間復(fù)雜度為 O(N)。除了查詢效率較低外，zipList 還有一個問題：“連鎖更新問題”。那什么是連鎖更新問題呢？

zipList是一個緊湊的序列數(shù)據(jù)結(jié)構(gòu)，它每個 entry 都有一個 prevlen 字段來記錄前一個 entry 的大小，當我們插入一個較大元素或者修改一個元素較大時，會引發(fā)后續(xù) entry 的 prevlen 占用空間發(fā)生變化，從而導(dǎo)致該 entry 的存儲空間大小超過 254 bytes，進一步引發(fā)后續(xù) entry 的存儲空間，導(dǎo)致一連串的 entry 存儲空間發(fā)生變化，從而引發(fā)“連鎖更新”問題。

“連鎖更新”通常發(fā)生在以下情況：

• 當 zipList 中的一個 entry 被更新（或者插入一個新的 entry），導(dǎo)致該 entry 的存儲空間增加，并且這個存儲空間增加會導(dǎo)致后續(xù) entry 的存儲空間發(fā)生變化。
• 如果前一個 entry 的存儲空間需要使用更多的字節(jié)來表示（例如，從1字節(jié)增加到5字節(jié)），那么這種存儲空間的增加可能會影響到下一個 entry ，因為下一個 entry需要更新它存儲的前一個 entry 的存儲空間 prevlen 字段，它由1 字節(jié)變成 5 字節(jié)。
• 如果這個更新又導(dǎo)致下一個 entry的存儲空間表示也不足，那么這個過程就會繼續(xù)傳播，形成一個連鎖反應(yīng)，直到找到一個 entry，其長度表示不需要改變?yōu)橹埂?/li>

舉一個例子：假如我們有一個 zipList ，它有多個 entry 大小在 250~253字節(jié)之間，他們的 prevlen 都是 1 個字節(jié)：

現(xiàn)在我們插入一個新的 entry，長度為 260 bytes，則是 e1 的 prevlen 就會由 1 bytes 增加到 5 bytes，導(dǎo)致 e1 存儲空間由 252 bytes 增加到 256 bytes：

e1 由 252 bytes 增加到 256 bytes，那么 e2 的 prevlen 就會由 1 bytes 增加到 5 bytes，從而導(dǎo)致 e2 的存儲空間由 252 bytes 增加到 256 bytes：

e2 的存儲空間增加會導(dǎo)致 e3 的增加，e3 又會導(dǎo)致 e4，e4 又會延伸到 e5，但是 e5 的存儲空間由 100bytes 增加到 104 bytes，小于 254 bytes，所以不會導(dǎo)致 e6 的 prevlen 值增大，至此 “連鎖更新” 結(jié)束：

“連鎖更新”會對 zipList 的性能有影響，因為它會導(dǎo)致大量的內(nèi)存重新分配和數(shù)據(jù)復(fù)制。而且在極端情況下，即使只是修改了一個很小的 entry，也可能會導(dǎo)致整個 zipList 被復(fù)制和更新，嚴重影響 zipList 的性能。

總結(jié)：當列表中元素的?度較?或者數(shù)量較少時，通常采?zipList來存儲。原因是因為 zipList 是一個緊湊的數(shù)據(jù)結(jié)構(gòu)，能夠有效地減少內(nèi)存占用。但是，在列表中元素較多或者元素較大時，zipList 的性能會下降，因為在列表的頭部或尾部添加或刪除元素時，可能需要重新分配并復(fù)制整個 ziplist。所以，zipList 非常適合少量的小數(shù)據(jù)存儲。同時 zipList 還有一個“連鎖更新”的問題，也會嚴重影響 ziplist 的性能。

linkedList

linkedList 是一個由一個個節(jié)點組成的雙向鏈表，數(shù)據(jù)結(jié)構(gòu)定義如下：

typedef struct list {
    // 頭指針
    listNode *head;
    // 尾指針
    listNode *tail;
    // 節(jié)點值的復(fù)制函數(shù)
    void *(*dup)(void *ptr);
    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);
    // 節(jié)點值比對是否相等
    int (*match)(void *ptr, void *key);
    // 鏈表的節(jié)點數(shù)量
    unsigned long z;
} list;

list 結(jié)構(gòu)體代表整個鏈表，包含指向鏈表頭節(jié)點、尾節(jié)點的指針，以及鏈表的長度等信息。listNode 代表雙向鏈表的一個節(jié)點，定義如下：

typedef struct listNode {
    // 前驅(qū)節(jié)點指針
    struct listNode *prev;
    // 后驅(qū)節(jié)點指針
    struct listNode *next;
    // 指向節(jié)點的值
    void *value;
} listNode;

整體結(jié)構(gòu)如下：

linkedList 是一個雙向鏈表，所以在執(zhí)行兩端操作時（如 LPUSH、RPUSH、LPOP、RPOP），時間復(fù)雜度是 O(1)，效率非常快。但是如果它要執(zhí)行索引類操作（如 LINDEX、LSET ）時，則需要遍歷列表，所以效率會低些。同時，linkedList 與 zipList 相比，它的內(nèi)存使用率較高，每個節(jié)點除了存儲值本身外，還需要額外空間存儲前向和后向的指針。但是，對于大型列表，這種額外的內(nèi)存開銷是合理的，因為它提供了更佳的操作性能。所以 linkedList 比較適合列表元素數(shù)量較多，或者列表中包含大型元素的場景。

quicklist

在 quicklist 出現(xiàn)之前，List 使用 zipList 和 linkedList 來存儲數(shù)據(jù)。

• zipList：是一個緊湊的數(shù)據(jù)結(jié)構(gòu)，它能夠有效地減少內(nèi)存占用，但是當列表中元素較多或者元素本身較大時，zipList 的性能會下降，因為在列表的頭部或尾部添加或刪除元素時，可能需要重新分配并復(fù)制整個 ziplist。所以，zipList 非常適合少量的小數(shù)據(jù)存儲。
• linkedList：一個雙向鏈表，能夠快速支持插入和刪除操作，但是內(nèi)存利用率較低，因為它需要額外的內(nèi)存空間來維護鏈表結(jié)構(gòu)。

zipList 和 linkedList都存在這樣或那樣的缺陷，所以 Redis 在 3.2 版本采用 quicklist 來取代zipList 和 linkedList。

quicklist 是將 zipList 作為節(jié)點嵌入 linkedList 的節(jié)點中，它結(jié)合了兩者的優(yōu)點。具體來說，quicklist 是由多個 ziplist 節(jié)點組成的 linkedList 鏈表，每個 ziplist 節(jié)點可以存儲多個列表元素。

• 內(nèi)存利用率：通過使用 ziplist，quicklist 可以像使用 ziplist 那樣高效地存儲小數(shù)據(jù)元素，提供內(nèi)存利用率。
• 操作性能：由于 quicklist 是基于雙向鏈表的，它可以快速地在兩端添加或刪除元素，而不需要像單一 ziplist 那樣可能會發(fā)生重新分配和復(fù)制整個數(shù)據(jù)結(jié)構(gòu)的情況。對于列表中間的插入和刪除操作，Redis 會先找到對應(yīng)的 ziplist 節(jié)點，然后在這個 ziplist 中進行操作，這樣可以保持較高的操作效率。

quicklist 表頭結(jié)構(gòu)：

typedef struct quicklist {
    // 鏈表頭部節(jié)點指針
    quicklistNode *head;
    
    // 鏈表頭部節(jié)點指針
    quicklistNode *tail;
    
    // 所有 ziplist 的總 entry 個數(shù)
    unsigned long count;
    
    // quicklistNode 個數(shù)
    unsigned long len;          /* number of quicklistNodes */
    signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

quicklist節(jié)點結(jié)構(gòu)：

typedef struct quicklistNode {
    // 前驅(qū)節(jié)點指針
    struct quicklistNode *prev;
    // 后繼節(jié)點指針
    struct quicklistNode *next;
    // 指向 ziplist 的指針
    unsigned char *zl;
    // ziplist 字節(jié)大小
    unsigned int sz;
    // ziplst 元素個數(shù)
    unsigned int count : 16;
    // 編碼格式，1 = RAW 代表未壓縮原生ziplist，2=LZF 壓縮存儲
    unsigned int encoding : 2;
    // 節(jié)點持有的數(shù)據(jù)類型，默認值 = 2 表示是 ziplist
    unsigned int container : 2;
    // 節(jié)點持有的 ziplist 是否經(jīng)過解壓， 1 表示已經(jīng)解壓過，下一次操作需要重新壓縮。
    unsigned int recompress : 1;
    // ziplist 數(shù)據(jù)是否可壓縮，太小數(shù)據(jù)不需要壓縮
    unsigned int attempted_compress : 1;
    // 預(yù)留字段
    unsigned int extra : 10;
} quicklistNode;

結(jié)合 quicklist 和 quicklistNode，quicklist 的結(jié)構(gòu)如下圖：

使用 quicklist 關(guān)鍵點就在于我們?nèi)绾纹胶夂妹總€ ziplist 的大小或者元素個數(shù)，平衡內(nèi)存得使用和操作性能。

• quicklistNode的 ziplist 的越小，內(nèi)存使用率就會越低，極端情況下，每個 ziplist 只有一個元素，這樣quicklist 退化為了 linkedList。
• quicklistNode的 ziplist 的越大，內(nèi)存使用率就越高，但這樣就越不利于操作性能了，極端情況下，所有元素都幾種在 ziplist 中，quicklist 就退化為了 ziplist。

所以，我們需要通過配置來平衡每個 ziplist 的大小或者元素個數(shù)。Redis 提供了參數(shù) list-max-ziplist-size 和 list-compress-depth 來配置 quicklist。

list-max-ziplist-size

控制每個 quicklist 節(jié)點內(nèi)部的 ziplist 可以包含的最大元素數(shù)量或字節(jié)大小。

• 為負數(shù)時表示 ziplist 節(jié)點的字節(jié)大小上限。
• 為正數(shù)時表示ziplist 節(jié)點中元素的數(shù)量上限。

當一個 ziplist 中的元素達到配置的閾值時，如果有新元素添加到列表中時，Redis 會創(chuàng)建一個新的 ziplist 節(jié)點來存儲這個元素。該值較大（絕對值）時，單個 ziplist 存儲的元素就越多，內(nèi)存利用率就越高，但是會犧牲列表的操作性能，如果較小，則有利于列表的操作性能，但犧牲了內(nèi)存的利用率。所以，在實際生產(chǎn)情況下我們需要根據(jù)實際情況配置一個適中的值，來平衡列表操作的內(nèi)存效率和性能。

Redis 默認 list-max-ziplist-size 為 -2，限制 ziplist 節(jié)點大小為 2KB。

list-compress-depth

用于配置 quicklist 中節(jié)點的壓縮。list-compress-depth 決定了在 quicklist 中，距離首尾元素多遠的中間節(jié)點應(yīng)該被壓縮存儲，該參數(shù)影響著內(nèi)存使用和訪問這些被壓縮節(jié)點數(shù)據(jù)時的性能。注意，為了 push/pop 操作的高效性，quicklist 的頭和尾節(jié)點永遠都不會被壓縮。

• 0：表示不對 quicklist 中的任何節(jié)點進行壓縮。訪問性能最佳，但是內(nèi)存利用率最高。
• 1：表示對 quicklist 的首尾節(jié)點不之外的節(jié)點進行壓縮。這樣可以最大限度地提供內(nèi)存的利用率，但是不利于這些元素的訪問，因為需要進行解壓操作。
• > 1：指定了列表首尾節(jié)點各有多少個節(jié)點不被壓縮。如，list-compress-depth 2 表明 quicklist 的首尾各兩個節(jié)點不會被壓縮，其余中間的節(jié)點都會被壓縮。隨著這個值的增加，被壓縮的節(jié)點數(shù)量減少，內(nèi)存使用會增加，但訪問這些較靠近列表首尾的元素的速度會更快。

以上就是詳解Redis中的List是如何實現(xiàn)的的詳細內(nèi)容，更多關(guān)于Redis List實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論