點(diǎn)擊下方“JavaEdge”，選擇“設(shè)為星標(biāo)”

第一時(shí)間關(guān)注技術(shù)干貨！

免責(zé)聲明~ 任何文章不要過(guò)度深思！萬(wàn)事萬(wàn)物都經(jīng)不起審視，因?yàn)槭郎蠜](méi)有同樣的成長(zhǎng)環(huán)境，也沒(méi)有同樣的認(rèn)知水平，更「沒(méi)有適用于所有人的解決方案」； 別急著評(píng)判文章列出的觀點(diǎn)，只需代入其中，適度審視一番自己即可，能「跳脫出來(lái)從外人的角度看看現(xiàn)在的自己處在什么樣的階段」才不為俗人。 怎么想、怎么做，全在乎自己「不斷實(shí)踐中尋找適合自己的大道」

0 引言

Redis 作為一種高效的內(nèi)存型鍵值數(shù)據(jù)庫(kù)，得益于其底層數(shù)據(jù)結(jié)構(gòu)的精妙設(shè)計(jì)。對(duì)于 List 類(lèi)型的數(shù)據(jù)，Redis 從早期的簡(jiǎn)單鏈表（linkedlist），到壓縮列表（ziplist），再到如今的quicklist和listpack，不斷優(yōu)化以平衡內(nèi)存利用率和性能。這篇文章將深入剖析 Redis 的 quicklist 和 listpack 數(shù)據(jù)結(jié)構(gòu)，幫助 Java 技術(shù)專(zhuān)家理解其背后的設(shè)計(jì)思想與使用場(chǎng)景。

Redis List 結(jié)構(gòu)的演進(jìn)

在 Redis 早期的版本中，List 類(lèi)型的數(shù)據(jù)主要通過(guò)鏈表（LinkedList）實(shí)現(xiàn)，雖然鏈表在插入和刪除操作上有較高的效率，但鏈表的節(jié)點(diǎn)分散存儲(chǔ)，不利于內(nèi)存的連續(xù)性，也會(huì)帶來(lái)較高的內(nèi)存消耗。為了解決這些問(wèn)題，Redis 引入了壓縮列表（ziplist），一個(gè)將所有元素緊湊存儲(chǔ)在一塊連續(xù)內(nèi)存空間中的結(jié)構(gòu)，極大地提升了內(nèi)存利用率。

然而，隨著數(shù)據(jù)量的增加，ziplist 也暴露出了其操作上的性能瓶頸。為此，Redis 開(kāi)發(fā)了 quicklist，將鏈表和壓縮列表的優(yōu)勢(shì)結(jié)合。Redis 5.0 引入了 listpack，作為壓縮列表的替代方案，進(jìn)一步優(yōu)化內(nèi)存利用率和性能。

1 Quicklist：鏈表與壓縮列表的結(jié)合1.1 結(jié)構(gòu)概覽

Quicklist是一個(gè)結(jié)合了雙向鏈表和壓縮列表的混合結(jié)構(gòu)。它將鏈表的每一個(gè)節(jié)點(diǎn)設(shè)計(jì)為一個(gè)壓縮列表（ziplist），這樣既保持了鏈表的插入和刪除優(yōu)勢(shì)，又通過(guò)壓縮列表提高了內(nèi)存利用率。

struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* List element count */
unsigned int len; /* Number of quicklistNodes */
int fill : 16; /* fill factor for individual nodes */
unsigned int compress : 16; /* depth of end nodes not to compress */
};

每個(gè)quicklistNode包含一個(gè)ziplist，它們之間通過(guò)雙向鏈表連接。fill參數(shù)控制每個(gè)節(jié)點(diǎn)中可以容納的元素?cái)?shù)量，compress參數(shù)決定了 quicklist 在兩端保留多少未壓縮的節(jié)點(diǎn)，用于提高頻繁訪問(wèn)區(qū)域的性能。

1.2 操作原理

• 插入操作：當(dāng)一個(gè)元素被插入到 List 中時(shí)，Redis 會(huì)首先檢查目標(biāo) quicklistNode 中的壓縮列表是否有空間。如果空間足夠，則直接在對(duì)應(yīng)的 ziplist 中進(jìn)行插入操作；否則，會(huì)在當(dāng)前鏈表節(jié)點(diǎn)之前或之后創(chuàng)建一個(gè)新的 quicklistNode，并將元素插入其中。

• 刪除操作：類(lèi)似于插入，刪除操作會(huì)定位到元素所在的壓縮列表進(jìn)行刪除操作。如果一個(gè) ziplist 中的元素被全部刪除，整個(gè) quicklistNode 也會(huì)被釋放。

Quicklist 的最大優(yōu)勢(shì)在于其內(nèi)存與性能的靈活平衡。通過(guò)將元素存儲(chǔ)在緊湊的壓縮列表中，減少了內(nèi)存碎片問(wèn)題，而雙向鏈表結(jié)構(gòu)則確保了較高效的插入和刪除性能。需要注意的是，quicklist 中的壓縮列表數(shù)量受fill參數(shù)影響，填充因子的調(diào)優(yōu)在性能和內(nèi)存占用之間找到平衡尤為關(guān)鍵。

2. Listpack：壓縮列表的繼任者

Redis 5.0 引入了Listpack，一種類(lèi)似于壓縮列表的數(shù)據(jù)結(jié)構(gòu)，但它相比 ziplist 在設(shè)計(jì)上有更多的改進(jìn)，主要用于實(shí)現(xiàn) Redis 的 Sorted Set 和 Hash 中的小對(duì)象集合。

2.1 結(jié)構(gòu)概覽

Listpack是一種緊湊的、連續(xù)的內(nèi)存存儲(chǔ)結(jié)構(gòu)，用來(lái)存放一系列長(zhǎng)度不固定的字符串或整數(shù)。與 ziplist 類(lèi)似，Listpack 也在一塊連續(xù)的內(nèi)存中存儲(chǔ)數(shù)據(jù)，但其更簡(jiǎn)化的結(jié)構(gòu)設(shè)計(jì)帶來(lái)了更高的性能和更低的內(nèi)存開(kāi)銷(xiāo)。

struct listpack {
unsigned char *entry_start; // Listpack entries start here
unsigned int total_bytes; // Total size of the listpack
unsigned int num_entries; // Number of entries in the listpack
};

Listpack 采用變長(zhǎng)編碼的方式來(lái)存儲(chǔ)每個(gè)元素，并且每個(gè) entry 的開(kāi)銷(xiāo)比 ziplist 更低。其設(shè)計(jì)目標(biāo)是確保在存儲(chǔ)小型數(shù)據(jù)集合時(shí)，比 ziplist 更加高效。

2.2 優(yōu)化細(xì)節(jié)

• 內(nèi)存優(yōu)化：Listpack 采用了更加緊湊的編碼方式，減少了元素的元數(shù)據(jù)開(kāi)銷(xiāo)。例如，Listpack 使用一個(gè)字節(jié)來(lái)表示整數(shù)，而 ziplist 則可能需要額外的元數(shù)據(jù)。

• 性能優(yōu)化：Listpack 的簡(jiǎn)單結(jié)構(gòu)使其在插入和刪除操作上比 ziplist 更高效，特別是在遍歷整個(gè) Listpack 的時(shí)候，性能表現(xiàn)更為優(yōu)異。

Listpack 主要用于 Redis 的 Sorted Set、Hash 和 Stream 的實(shí)現(xiàn)中。當(dāng)數(shù)據(jù)量較少時(shí)，Listpack 能夠提供優(yōu)秀的內(nèi)存利用率；當(dāng)數(shù)據(jù)量增多時(shí)，Redis 會(huì)自動(dòng)將其轉(zhuǎn)換為其他數(shù)據(jù)結(jié)構(gòu)（如 skiplist 或 hash 表）。

3 Quicklist 與 Listpack 的對(duì)比特性 Quicklist Listpack 結(jié)構(gòu)類(lèi)型 鏈表 + 壓縮列表 緊湊型連續(xù)內(nèi)存結(jié)構(gòu) 主要應(yīng)用場(chǎng)景 Redis List Redis Sorted Set, Hash 內(nèi)存占用 中等，可調(diào)優(yōu) 極低 插入/刪除性能 較好，鏈表提供快速操作 較好，適合小型集合 數(shù)據(jù)量增加時(shí)的行為 自動(dòng)分裂為多個(gè) ziplist 轉(zhuǎn)換為復(fù)雜結(jié)構(gòu)（如 skiplist）4 Java 開(kāi)發(fā)者的思考：數(shù)據(jù)結(jié)構(gòu)選擇的啟示

對(duì)于 Java 開(kāi)發(fā)者來(lái)說(shuō)，Redis 的 quicklist 和 listpack 設(shè)計(jì)提供了許多數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)上的啟發(fā)：

• 內(nèi)存與性能的平衡：Redis 的 quicklist 通過(guò)結(jié)合鏈表與緊湊列表實(shí)現(xiàn)了內(nèi)存利用率與操作性能之間的平衡。在 Java 開(kāi)發(fā)中，類(lèi)似的權(quán)衡也可以用于選擇合適的數(shù)據(jù)結(jié)構(gòu)。對(duì)于小型集合，緊湊存儲(chǔ)能夠有效降低內(nèi)存占用；而對(duì)于大型集合或頻繁插入/刪除的場(chǎng)景，鏈表或其他高效的數(shù)據(jù)結(jié)構(gòu)則更加適合。

• 優(yōu)化緩存命中率：quicklist 通過(guò)緊湊存儲(chǔ)元素，提升了 CPU 緩存的利用率。這種思想在 Java 應(yīng)用中也可以借鑒，尤其是在對(duì)性能要求較高的系統(tǒng)中，合理設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)以最大化利用 CPU 緩存是提升性能的關(guān)鍵。

• 變長(zhǎng)編碼的高效性：Listpack 采用變長(zhǎng)編碼方式存儲(chǔ)數(shù)據(jù)，減少了存儲(chǔ)小型整數(shù)或短字符串的開(kāi)銷(xiāo)。在 Java 開(kāi)發(fā)中，類(lèi)似的思想也可以通過(guò)使用合適的序列化策略或者優(yōu)化對(duì)象的存儲(chǔ)格式來(lái)實(shí)現(xiàn)。

Redis 的 quicklist 和 listpack 通過(guò)不同的設(shè)計(jì)策略，分別在內(nèi)存利用和性能優(yōu)化上提供了獨(dú)特的解決方案。對(duì)于 Java 技術(shù)專(zhuān)家來(lái)說(shuō)，理解這些底層數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)不僅有助于更好地使用 Redis，也為開(kāi)發(fā)高性能應(yīng)用提供了寶貴的借鑒。通過(guò)學(xué)習(xí)這些優(yōu)化思路，我們可以在自己的系統(tǒng)設(shè)計(jì)中更好地權(quán)衡內(nèi)存與性能，選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)滿(mǎn)足不同場(chǎng)景的需求。

關(guān)注我，緊跟本系列專(zhuān)欄文章，咱們下篇再續(xù)！

★ 作者簡(jiǎn)介：魔都架構(gòu)師，多家大廠后端一線研發(fā)經(jīng)驗(yàn)，在分布式系統(tǒng)設(shè)計(jì)、數(shù)據(jù)平臺(tái)架構(gòu)和AI應(yīng)用開(kāi)發(fā)等領(lǐng)域都有豐富實(shí)踐經(jīng)驗(yàn)。 各大技術(shù)社區(qū)頭部專(zhuān)家博主。具有豐富的引領(lǐng)團(tuán)隊(duì)經(jīng)驗(yàn)，深厚業(yè)務(wù)架構(gòu)和解決方案的積累。 負(fù)責(zé)： 中央/分銷(xiāo)預(yù)訂系統(tǒng)性能優(yōu)化 活動(dòng)&券等營(yíng)銷(xiāo)中臺(tái)建設(shè) 交易平臺(tái)及數(shù)據(jù)中臺(tái)等架構(gòu)和開(kāi)發(fā)設(shè)計(jì) 車(chē)聯(lián)網(wǎng)核心平臺(tái)-物聯(lián)網(wǎng)連接平臺(tái)、大數(shù)據(jù)平臺(tái)架構(gòu)設(shè)計(jì)及優(yōu)化 LLM Agent應(yīng)用開(kāi)發(fā) 區(qū)塊鏈應(yīng)用開(kāi)發(fā) 大數(shù)據(jù)開(kāi)發(fā)挖掘經(jīng)驗(yàn) 推薦系統(tǒng)項(xiàng)目 目前主攻市級(jí)軟件項(xiàng)目設(shè)計(jì)、構(gòu)建服務(wù)全社會(huì)的應(yīng)用系統(tǒng)。 ”

參考：

• 編程嚴(yán)選網(wǎng)

編程嚴(yán)選網(wǎng)：http://www.javaedge.cn/ 專(zhuān)注分享軟件開(kāi)發(fā)全生態(tài)相關(guān)技術(shù)文章、視頻教程資源、熱點(diǎn)資訊等，全站資源免費(fèi)學(xué)習(xí)，快來(lái)看看吧~ 【編程嚴(yán)選】星球

歡迎長(zhǎng)按圖片加好友，我會(huì)第一時(shí)間和你分享軟件行業(yè)趨勢(shì)，面試資源，學(xué)習(xí)方法等等。

公眾號(hào)后臺(tái)私信：

• 更多教程資源應(yīng)有盡有

想先人一步獲取以上所有資源？加入《編程嚴(yán)選》星球一鍵獲??！