Redis 中的 List,底層采用了什么數(shù)據(jù)結(jié)構(gòu)?
這篇文章,我們將從 Redis List 的基本原理出發(fā),深入分析其內(nèi)部實(shí)現(xiàn)機(jī)制、源碼層面的細(xì)節(jié),并結(jié)合實(shí)際示例,全面解析 Redis List 的工作原理。
一、Redis List 概述
Redis 的 List 是一個(gè)簡(jiǎn)單的字符串列表,按照插入順序排序。它支持在列表的兩端插入或刪除元素,具有以下特點(diǎn):
- 有序:元素按照插入順序排列,可以通過(guò)索引訪問(wè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 的大小和元素的長(zhǎng)度,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 版本開(kāi)始,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ì):
- 高效插入與刪除:在兩端插入和刪除元素時(shí),只需要操作鏈表的頭部或尾部節(jié)點(diǎn),時(shí)間復(fù)雜度為 O(1)。
- 節(jié)省空間:每個(gè)節(jié)點(diǎn)內(nèi)部仍然使用壓縮列表存儲(chǔ)元素,節(jié)省內(nèi)存。
靈活性:適用于包含大量元素的 List。
三、源碼分析
下面將通過(guò)源碼分析 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 等命令為例,分析它們?cè)谠创a中的實(shí)現(xiàn)。
3. LPUSH 和 RPUSH
LPUSH 和 RPUSH 用于在 List 的左端和右端插入元素。它們?cè)?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ù)索引(從尾部開(kāi)始計(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è)迭代器,從頭部或尾部開(kāi)始遍歷 quicklist
}
int quicklistNext(quicklistIter *i, quicklistEntry *entry) {
// 通過(guò)迭代器遍歷 quicklist 中的元素
}
核心邏輯:
- 創(chuàng)建一個(gè)迭代器,指定遍歷方向(從頭到尾或從尾到頭)。
- 遍歷 quicklist 的節(jié)點(diǎn)和節(jié)點(diǎn)內(nèi)的 ziplist,收集指定范圍的元素。
- 返回結(jié)果集合。
四、性能優(yōu)化與選擇
Redis 在 List 的內(nèi)部實(shí)現(xiàn)中,通過(guò) quicklist 結(jié)構(gòu)在節(jié)省內(nèi)存和提高操作效率之間取得了平衡。以下是一些性能優(yōu)化的考慮:
- 節(jié)點(diǎn)大?。╢ill 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 支持多種壓縮算法,通過(guò)配置可以進(jìn)一步優(yōu)化內(nèi)存使用。
- 迭代器機(jī)制:通過(guò)迭代器遍歷 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é)?。簤嚎s列表是一種為節(jié)省內(nèi)存而設(shè)計(jì)的緊湊數(shù)據(jù)結(jié)構(gòu)。它將多個(gè)元素緊密存儲(chǔ)在一個(gè)連續(xù)的內(nèi)存塊中,避免了傳統(tǒng)鏈表中每個(gè)節(jié)點(diǎn)需要額外指針(如前驅(qū)和后繼指針)帶來(lái)的內(nèi)存開(kāi)銷。對(duì)于包含少量元素且每個(gè)元素較短的小型列表,壓縮列表能夠顯著減少內(nèi)存使用量。
緩存友好性:由于壓縮列表將所有元素存儲(chǔ)在一個(gè)連續(xù)的內(nèi)存區(qū)域中,這種布局有助于提升緩存命中率。CPU 在訪問(wèn)數(shù)據(jù)時(shí),能夠更高效地預(yù)取和緩存數(shù)據(jù),從而提高訪問(wèn)速度。
簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu):壓縮列表的實(shí)現(xiàn)相對(duì)簡(jiǎn)單,適用于不需要頻繁插入和刪除操作的場(chǎng)景。對(duì)于靜態(tài)或變化不大的小型列表,壓縮列表提供了足夠的性能和內(nèi)存效率。
2. 雙端鏈表
高效的兩端操作:雙端鏈表允許在列表的頭部和尾部進(jìn)行高效的插入和刪除操作,時(shí)間復(fù)雜度為 O(1)。這對(duì)于需要頻繁在兩端進(jìn)行操作的應(yīng)用場(chǎng)景(如隊(duì)列和棧)尤為重要。
動(dòng)態(tài)擴(kuò)展能力:與壓縮列表相比,雙端鏈表更適合處理動(dòng)態(tài)變化較大的列表。它能夠靈活地在任意位置插入和刪除元素,而不會(huì)像壓縮列表那樣需要整體移動(dòng)內(nèi)存塊。
分段存儲(chǔ)與性能優(yōu)化:Quicklist 通過(guò)將列表分段存儲(chǔ),每個(gè)段使用壓縮列表(ziplist)作為節(jié)點(diǎn),實(shí)現(xiàn)了分塊管理。這種設(shè)計(jì)兼具了壓縮列表的內(nèi)存效率和雙端鏈表的操作性能。具體來(lái)說(shuō),每個(gè) quicklist 節(jié)點(diǎn)內(nèi)部是一個(gè)壓縮列表,多個(gè)節(jié)點(diǎn)通過(guò)雙端鏈表連接起來(lái)。這樣,在需要進(jìn)行插入或刪除操作時(shí),僅需操作相關(guān)的節(jié)點(diǎn),而不影響整個(gè)列表結(jié)構(gòu)。
Redis 會(huì)根據(jù)列表的長(zhǎng)度和元素的大小,自動(dòng)決定使用壓縮列表還是雙端鏈表。這種智能選擇機(jī)制確保了在不同場(chǎng)景下都能獲得最佳的性能和內(nèi)存使用率。例如:
- 小型列表:當(dāng)列表較小且元素較短時(shí),Redis 會(huì)選擇壓縮列表,最大化內(nèi)存節(jié)省和緩存效率。
- 大型列表:當(dāng)列表變得較大或元素較長(zhǎng)時(shí),Redis 會(huì)轉(zhuǎn)而使用 quicklist,以提升操作性能和擴(kuò)展能力。
六、總結(jié)
本文,我們從源碼角度分析了 Redis 的 List 數(shù)據(jù)結(jié)構(gòu),它是一個(gè)高效、靈活的數(shù)據(jù)結(jié)構(gòu),適用于多種應(yīng)用場(chǎng)景,如消息隊(duì)列、任務(wù)管理等。通過(guò)內(nèi)部的 quicklist 結(jié)構(gòu),Redis 在節(jié)省內(nèi)存和優(yōu)化操作效率方面做出了平衡。通過(guò)學(xué)習(xí)本文,我們也可以發(fā)現(xiàn) Redis 對(duì)性能的追求。