回答

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

• 3.2 版本以前使用 linkedlist + ziplist

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

• 3.2 版本以后使用 quicklist

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

擴(kuò)展

List 介紹

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

**List 的最大長(zhǎng)度為 2^31 - 1，即每個(gè) List 支持超過(guò) 40 億個(gè)元素。**主要特點(diǎn)如下：

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

List 常用的命令如下：

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

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

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

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

• LLEN key：返回列表的長(zhǎng)度，如果 key 不存在 返回 0。

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

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

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

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

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

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

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

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

List 的底層實(shí)現(xiàn)

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

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

zipList

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

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

• 表頭（header）

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

• 條目（entries）

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

• 表尾（end）

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

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

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

• prevlen

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

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

• encoding

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

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

• entry-data

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

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

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

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

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

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

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

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

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

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

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

linkedList

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

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

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

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

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

linkedList 是一個(gè)雙向鏈表，所以在執(zhí)行兩端操作時(shí)（如 LPUSH、RPUSH、LPOP、RPOP），時(shí)間復(fù)雜度是 O(1)，效率非常快。但是如果它要執(zhí)行索引類操作（如 LINDEX、LSET ）時(shí)，則需要遍歷列表，所以效率會(huì)低些。同時(shí)，linkedList 與 zipList 相比，它的內(nèi)存使用率較高，每個(gè)節(jié)點(diǎn)除了存儲(chǔ)值本身外，還需要額外空間存儲(chǔ)前向和后向的指針。但是，對(duì)于大型列表，這種額外的內(nèi)存開銷是合理的，因?yàn)樗峁┝烁训牟僮餍阅?。所?linkedList 比較適合列表元素?cái)?shù)量較多，或者列表中包含大型元素的場(chǎng)景。

quicklist

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

• zipList：是一個(gè)緊湊的數(shù)據(jù)結(jié)構(gòu)，它能夠有效地減少內(nèi)存占用，但是當(dāng)列表中元素較多或者元素本身較大時(shí)，zipList 的性能會(huì)下降，因?yàn)樵诹斜淼念^部或尾部添加或刪除元素時(shí)，可能需要重新分配并復(fù)制整個(gè) ziplist。所以，zipList 非常適合少量的小數(shù)據(jù)存儲(chǔ)。
• linkedList：一個(gè)雙向鏈表，能夠快速支持插入和刪除操作，但是內(nèi)存利用率較低，因?yàn)樗枰~外的內(nèi)存空間來(lái)維護(hù)鏈表結(jié)構(gòu)。

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

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

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

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

typedef struct quicklist {
    // 鏈表頭部節(jié)點(diǎn)指針
    quicklistNode *head;
    
    // 鏈表頭部節(jié)點(diǎn)指針
    quicklistNode *tail;
    
    // 所有 ziplist 的總 entry 個(gè)數(shù)
    unsigned long count;
    
    // quicklistNode 個(gè)數(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é)點(diǎn)結(jié)構(gòu)：

typedef struct quicklistNode {
    // 前驅(qū)節(jié)點(diǎn)指針
    struct quicklistNode *prev;
    // 后繼節(jié)點(diǎn)指針
    struct quicklistNode *next;
    // 指向 ziplist 的指針
    unsigned char *zl;
    // ziplist 字節(jié)大小
    unsigned int sz;
    // ziplst 元素個(gè)數(shù)
    unsigned int count : 16;
    // 編碼格式，1 = RAW 代表未壓縮原生ziplist，2=LZF 壓縮存儲(chǔ)
    unsigned int encoding : 2;
    // 節(jié)點(diǎn)持有的數(shù)據(jù)類型，默認(rèn)值 = 2 表示是 ziplist
    unsigned int container : 2;
    // 節(jié)點(diǎn)持有的 ziplist 是否經(jīng)過(guò)解壓， 1 表示已經(jīng)解壓過(guò)，下一次操作需要重新壓縮。
    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)鍵點(diǎn)就在于我們?nèi)绾纹胶夂妹總€(gè) ziplist 的大小或者元素個(gè)數(shù)，平衡內(nèi)存得使用和操作性能。

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

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

list-max-ziplist-size

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

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

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

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

list-compress-depth

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

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

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

最新評(píng)論