一、背景 — 為什么要有多種“列表（List）”編碼

• 在內(nèi)存數(shù)據(jù)庫(kù) Redis 中，列表（List）是常用數(shù)據(jù)類型之一，用于實(shí)現(xiàn)隊(duì)列、堆棧、消息隊(duì)列、任務(wù)隊(duì)列等場(chǎng)景。
• 不同場(chǎng)景對(duì)內(nèi)存使用與訪問(wèn)效率有不同要求：少量元素 → 希望節(jié)省內(nèi)存；大量元素或頻繁插入/刪除 → 需要高性能操作。
• 因此Redis 設(shè)計(jì)者提供了不同的“編碼方式”（encoding）來(lái)存儲(chǔ) List 對(duì)象，以兼顧 空間效率 與 操作效率。

在歷史發(fā)展中，Redis 對(duì) List 的編碼方式經(jīng)歷了如下階段：

• 早期：使用 雙向鏈表（linkedlist） 或 壓縮列表（ziplist），兩種可選。
• 從 Redis 3.2 版本起，引入 quicklist，作為新的默認(rèn)結(jié)構(gòu)，取代了 ziplist + linkedlist 的混合策略。

下面分別介紹 ziplist 和 quicklist 的結(jié)構(gòu)與特性，然后比較優(yōu)缺點(diǎn)。

二、ziplist —— 壓縮列表（compact list）

2.1 ziplist 是什么

• ziplist 是 Redis 提供的一種“緊湊型列表結(jié)構(gòu)（compact list）”。它將多個(gè) list 元素連續(xù)地存放在一塊 連續(xù)內(nèi)存（contiguous memory block） 中。
• 每個(gè) entry（元素）包含必要的 metadata（如前一個(gè) entry 長(zhǎng)度、當(dāng)前 entry 長(zhǎng)度、數(shù)據(jù)內(nèi)容等），因此 ziplist 可以存放不同長(zhǎng)度的數(shù)據(jù)項(xiàng)（字符串、整數(shù)等），而不需要為每個(gè)元素單獨(dú)分配內(nèi)存。
• 因?yàn)閮?nèi)存連續(xù)、元素緊湊，ziplist 在內(nèi)存占用上非常高效 — 對(duì)于存儲(chǔ)少量、短字符串／整數(shù)列表時(shí)，能節(jié)省大量?jī)?nèi)存。

ziplist結(jié)構(gòu)如圖所示，參考Redis面試題：

下邊的圖也可加深理解

ziplist的各字段含義如下。

• zlbytes：壓縮列表的字節(jié)長(zhǎng)度，占4B，因此壓縮列表最長(zhǎng) 2³²?1B。
• zltail：壓縮列表尾元素相對(duì)于壓縮列表起始地址的偏移量，占4B。
• zllen：壓縮列表的元素?cái)?shù)目，占2B；當(dāng)壓縮列表的元素?cái)?shù)目超過(guò)65535（2¹??1）時(shí)，zllen 無(wú)法存儲(chǔ)，此時(shí)必須遍歷整個(gè)壓縮列表才能獲取元素?cái)?shù)目。
• entry1、entr2y：壓縮列表存儲(chǔ)的若干個(gè)元素，可以是字節(jié)數(shù)組或者整數(shù)，長(zhǎng)度不限；
• zlend：壓縮列表的結(jié)尾，占1B，固定為0xFF。

對(duì)于每一個(gè)entry元素來(lái)講

entry 結(jié)構(gòu)包含三個(gè)字段：

1. prelen
   • 記錄前一個(gè)元素的長(zhǎng)度，用于從后向前遍歷。
   • 前一個(gè)元素長(zhǎng)度 < 254B → 占 1B。
   • 前一個(gè)元素長(zhǎng)度 ≥ 254B → 占 5B（首字節(jié)為 0xFE，后 4B 為實(shí)際長(zhǎng)度）。
2. encoding
   • 表示 data 的數(shù)據(jù)類型（整數(shù)或字節(jié)數(shù)組）。
   • 長(zhǎng)度可變（1B、2B 或 5B），通過(guò)開(kāi)頭的比特區(qū)分。
   • 同時(shí)可包含字節(jié)數(shù)組的長(zhǎng)度信息（如 6bit、14bit 或 32bit 表示長(zhǎng)度）。

以下是encoding字段的元素編碼

3. data
   • 實(shí)際存儲(chǔ)的數(shù)據(jù)，可以是整數(shù)或字節(jié)數(shù)組，長(zhǎng)度由 encoding 決定。

2.2 ziplist 的適用條件（默認(rèn)策略）

在 Redis 配置文件（或編譯時(shí)默認(rèn)）中，對(duì)于 LIST、HASH、ZSET 等類型，會(huì)設(shè)置參數(shù)來(lái)決定是否使用 ziplist，例如：

• list-max-ziplist-entries：限制 ziplist 中元素（entry）個(gè)數(shù)
• list-max-ziplist-value：限制每個(gè) entry 的最大字節(jié)數(shù)（value 大?。?/li>

當(dāng)元素?cái)?shù)量或元素大小超過(guò)這些限制時(shí)，Redis 會(huì)放棄 ziplist 編碼，轉(zhuǎn)為其他更適合的編碼方式（在老版本可能是 linkedlist，現(xiàn)在是 quicklist）。

2.3 ziplist 的優(yōu)點(diǎn)與缺點(diǎn)

優(yōu)點(diǎn)：

• 內(nèi)存利用率高 — 非常節(jié)省內(nèi)存空間，適合存儲(chǔ)少量、小數(shù)據(jù)。
• 內(nèi)存連續(xù)，有利于 CPU 緩存和遍歷效率。

缺點(diǎn) / 缺陷：

• 對(duì)修改操作（插入 / 刪除 / 更新）不友好 — 因?yàn)橐３诌B續(xù)內(nèi)存，一旦中間插入或刪除，就可能觸發(fā)內(nèi)存重新分配和數(shù)據(jù)搬移（realloc + memcpy），代價(jià)高昂。這里會(huì)涉及連鎖更新問(wèn)題。
• 當(dāng)元素較多或較大時(shí)，ziplist 會(huì)非常臃腫或重復(fù) realloc，性能和穩(wěn)定性都不理想。
• 因此，ziplist 更適合“短小、穩(wěn)定、不頻繁變更”的列表數(shù)據(jù)，不適合大數(shù)據(jù)量或高頻寫入場(chǎng)景。

三、quicklist —— 快速列表（QuickList）

3.1 quicklist 是什么

• quicklist 是從 Redis 3.2 開(kāi)始引入的 List 編碼方式，用于替代早期的 ziplist /adlist 編碼。
• 它本質(zhì)上是 雙向鏈表 + 壓縮子列表 的混合結(jié)構(gòu)：一個(gè) quicklist 是一個(gè)雙向鏈表，而鏈表的每個(gè)節(jié)點(diǎn)（quicklistNode）內(nèi)部持有一個(gè) ziplist來(lái)存儲(chǔ)一段連續(xù)的元素。
• 這樣的設(shè)計(jì)兼顧了鏈表和 ziplist 各自的優(yōu)點(diǎn)。

3.2 quicklist 的結(jié)構(gòu)與配置參數(shù)

quicklist 的主要結(jié)構(gòu)由 quicklist 和 quicklistNode 兩個(gè) C 結(jié)構(gòu)體定義，在 Redis 源碼中（例如 quicklist.h / quicklist.c）可以查看。

結(jié)構(gòu)圖

在quicklist中，關(guān)鍵字段包括：

• head / tail：指向鏈表頭尾節(jié)點(diǎn)。
• count：List 中所有元素entry的總數(shù)。
• len：quicklistNode 節(jié)點(diǎn)數(shù)量。
• fill：用于控制每個(gè) ziplist 容量上限entry 數(shù)量 或 字節(jié)大小，通過(guò) list-max-ziplist-size 配置項(xiàng)設(shè)定。
• compress：用于控制壓縮深度，即鏈表兩端多少個(gè)節(jié)點(diǎn)不壓縮，中間節(jié)點(diǎn)可被壓縮以節(jié)省內(nèi)存，通過(guò) list-compress-depth 配置項(xiàng)控制。
• 每個(gè) quicklistNode 包含指向內(nèi)部 ziplist（或 listpack）的指針 zl，大小 sz，元素計(jì)數(shù) count 等信息。

?? 注意：在 Redis 最新版本中（例如 7.x），listpack 已經(jīng)逐步取代 ziplist 作為內(nèi)部壓縮子列表結(jié)構(gòu)，但 quicklist 的設(shè)計(jì)思想不變 —— 分段 + 鏈表 + 壓縮子列表。

3.3 quicklist 的優(yōu)點(diǎn)

• 兼顧空間與效率：通過(guò)將列表拆成多個(gè)小段（ziplist），既避免了大型鏈表帶來(lái)的內(nèi)存碎片和高 overhead，也避免了大型 ziplist 帶來(lái)的頻繁 realloc 問(wèn)題。
• 快速頭尾操作（push/pop）：因?yàn)?quicklist 是鏈表結(jié)構(gòu)，在頭尾插入刪除是 O(1) 操作，非常高效，適合隊(duì)列／棧等操作頻繁場(chǎng)景。
• 壓縮可選：中間節(jié)點(diǎn)可以壓縮（LZF 等算法／listpack 壓縮），節(jié)省內(nèi)存；而頭尾保留原始以保證訪問(wèn)性能。
• 靈活適應(yīng)不同場(chǎng)景：既適合存儲(chǔ)小量短元素，也適合存儲(chǔ)大量元素或長(zhǎng)列表。

3.4 quicklist 的限制與注意事項(xiàng)

• 如果配置不當(dāng)（ziplist 內(nèi)部過(guò)大、壓縮設(shè)置不合理），可能出現(xiàn)性能開(kāi)銷過(guò)重，或內(nèi)存碎片／壓縮開(kāi)銷問(wèn)題。
• quicklist 內(nèi)部實(shí)現(xiàn)比簡(jiǎn)單鏈表或數(shù)組復(fù)雜，對(duì)于某些極端訪問(wèn)模式（大量隨機(jī)訪問(wèn)中間、頻繁跨節(jié)點(diǎn)訪問(wèn)）可能不如純數(shù)組或其他結(jié)構(gòu)高效。

quicklist 的兩種極端情況如下：

1. 當(dāng) ziplist 節(jié)點(diǎn)過(guò)多時(shí)，quicklist 退化為雙向鏈表。最極端的情況是每個(gè) ziplist 節(jié)點(diǎn)只包含一個(gè) entry，即一個(gè)元素對(duì)應(yīng)一個(gè)節(jié)點(diǎn)。
2. 當(dāng) ziplist 節(jié)點(diǎn)過(guò)少時(shí)，quicklist 退化為 ziplist。最極端的情況是整個(gè) quicklist 中只含有一個(gè) ziplist 節(jié)點(diǎn)。

• 對(duì)于非常頻繁的隨機(jī)訪問(wèn)或修改，可能需要謹(jǐn)慎評(píng)估是否適合使用列表結(jié)構(gòu)。

四、ziplist vs quicklist —— 對(duì)比總結(jié)

Redis 之所以在內(nèi)存數(shù)據(jù)庫(kù) / 緩存系統(tǒng)中表現(xiàn)出色，很大程度上是因?yàn)樗鼮椴煌瑘?chǎng)景提供了優(yōu)化良好的底層數(shù)據(jù)結(jié)構(gòu)。ziplist 與 quicklist 是 Redis List 類型在歷史與現(xiàn)在對(duì)空間與時(shí)間折中的經(jīng)典設(shè)計(jì)。

• ziplist：為“少量、小數(shù)據(jù)、節(jié)省內(nèi)存”而生。
• quicklist：為“高性能、靈活、適應(yīng)大/變動(dòng)列表”而設(shè)計(jì)。

到此這篇關(guān)于Redis中ziplist與quicklist解析與對(duì)比小結(jié)的文章就介紹到這了,更多相關(guān)Redis ziplist與quicklist內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論