Redis壓縮列表的設(shè)計(jì)與實(shí)現(xiàn)
壓縮列表(Ziplist)其應(yīng)用場(chǎng)景主要包括以下幾個(gè)方面:
1. 哈希表(Hash)
在 Redis 中,當(dāng)哈希表(Hash)的鍵值對(duì)數(shù)量較少且每個(gè)鍵和值的長(zhǎng)度較短時(shí),Redis 會(huì)使用壓縮列表作為哈希表的底層實(shí)現(xiàn)。這種方式可以大幅度減少內(nèi)存開銷,提高存儲(chǔ)效率。
使用條件
- 鍵值對(duì)數(shù)量較少(默認(rèn)不超過(guò) 512 個(gè),可以通過(guò)配置參數(shù)
hash-max-ziplist-entries
調(diào)整)。 - 每個(gè)鍵和值的字符串長(zhǎng)度較短(默認(rèn)不超過(guò) 64 字節(jié),可以通過(guò)配置參數(shù)
hash-max-ziplist-value
調(diào)整)。
2. 列表(List)
當(dāng) Redis 列表中的元素?cái)?shù)量較少且每個(gè)元素的長(zhǎng)度較短時(shí),壓縮列表會(huì)被用作列表的底層實(shí)現(xiàn),以節(jié)省內(nèi)存。
使用條件
- 列表的元素?cái)?shù)量較少(默認(rèn)不超過(guò) 512 個(gè),可以通過(guò)配置參數(shù)
list-max-ziplist-entries
調(diào)整)。 - 每個(gè)元素的字符串長(zhǎng)度較短(默認(rèn)不超過(guò) 64 字節(jié),可以通過(guò)配置參數(shù)
list-max-ziplist-value
調(diào)整)。
3. 有序集合(Sorted Set)
在有序集合中,當(dāng)成員數(shù)量較少且成員和分?jǐn)?shù)的長(zhǎng)度較短時(shí),壓縮列表會(huì)被用作有序集合的底層實(shí)現(xiàn)之一,以提高存儲(chǔ)效率。
使用條件
- 成員數(shù)量較少(默認(rèn)不超過(guò) 128 個(gè),可以通過(guò)配置參數(shù)
zset-max-ziplist-entries
調(diào)整)。 - 每個(gè)成員和分?jǐn)?shù)的字符串長(zhǎng)度較短(默認(rèn)不超過(guò) 64 字節(jié),可以通過(guò)配置參數(shù)
zset-max-ziplist-value
調(diào)整)。
優(yōu)點(diǎn)與缺點(diǎn)
優(yōu)點(diǎn):
- 高效內(nèi)存利用:通過(guò)緊湊的存儲(chǔ)結(jié)構(gòu),大幅減少內(nèi)存占用。
- 適合小數(shù)據(jù)量:在存儲(chǔ)小規(guī)模數(shù)據(jù)時(shí),能夠提供良好的性能和內(nèi)存效率。
缺點(diǎn):
- 操作代價(jià)較高:由于壓縮列表是連續(xù)存儲(chǔ)結(jié)構(gòu),插入和刪除操作可能需要移動(dòng)大量數(shù)據(jù),性能相對(duì)較低。
- 不適合大數(shù)據(jù)量:壓縮列表更適合小規(guī)模的數(shù)據(jù)存儲(chǔ),當(dāng)數(shù)據(jù)量變大時(shí),操作效率會(huì)顯著下降。
示例及實(shí)際應(yīng)用
假設(shè)我們有一個(gè)包含用戶屬性的哈希表結(jié)構(gòu),并且用戶屬性數(shù)量較少,屬性值也較短,這樣的哈希表會(huì)被存儲(chǔ)為壓縮列表:
# 創(chuàng)建一個(gè)包含用戶屬性的哈希表 HSET user:1000 name "Alice" HSET user:1000 age "30" HSET user:1000 city "New York" # 獲取用戶屬性 HGETALL user:1000 # 返回 ["name", "Alice", "age", "30", "city", "New York"]
當(dāng)滿足壓縮列表的使用條件時(shí),上述哈希表將以壓縮列表的形式存儲(chǔ),從而節(jié)省內(nèi)存開銷。
同樣地,對(duì)于一個(gè)短列表和一個(gè)小規(guī)模有序集合,它們也可以被存儲(chǔ)為壓縮列表:
# 創(chuàng)建一個(gè)短列表 LPUSH mylist "element1" LPUSH mylist "element2" LPUSH mylist "element3" # 獲取列表所有元素 LRANGE mylist 0 -1 # 返回 ["element3", "element2", "element1"] # 創(chuàng)建一個(gè)小規(guī)模有序集合 ZADD myzset 1 "member1" ZADD myzset 2 "member2" ZADD myzset 3 "member3" # 獲取有序集合所有成員 ZRANGE myzset 0 -1 WITHSCORES # 返回 ["member1", "1", "member2", "2", "member3", "3"]
底層實(shí)現(xiàn)
1. 整體結(jié)構(gòu)
壓縮列表由一系列按順序排列的節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)可以存儲(chǔ)一個(gè)整數(shù)或一個(gè)字節(jié)數(shù)組。所有數(shù)據(jù)都存儲(chǔ)在連續(xù)的內(nèi)存塊中。整體結(jié)構(gòu)如下:
- zlbytes:4 字節(jié),記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)。
- zltail:4 字節(jié),指向壓縮列表尾部節(jié)點(diǎn)的偏移量,便于快速定位最后一個(gè)節(jié)點(diǎn)。
- zllen:2 字節(jié),記錄壓縮列表中的節(jié)點(diǎn)數(shù)量。如果超過(guò) 65535,則需要遍歷整個(gè)列表來(lái)計(jì)算節(jié)點(diǎn)數(shù)量。
- entryX:一個(gè)或多個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)實(shí)際數(shù)據(jù)。
- zlend:1 字節(jié),特殊標(biāo)志符,值固定為 0xFF,標(biāo)記壓縮列表的結(jié)束。
2. 節(jié)點(diǎn)結(jié)構(gòu)
每個(gè)節(jié)點(diǎn)由以下部分組成:
- previous_entry_length:存儲(chǔ)前一個(gè)節(jié)點(diǎn)的長(zhǎng)度,以便支持反向遍歷。當(dāng)前一個(gè)節(jié)點(diǎn)長(zhǎng)度小于 254 字節(jié)時(shí),該字段占 1 字節(jié);否則,該字段占 5 字節(jié)。
- encoding:編碼類型和長(zhǎng)度信息,用于標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)類型及其長(zhǎng)度。該字段的長(zhǎng)度取決于實(shí)際編碼方式。
- content:實(shí)際存儲(chǔ)的數(shù)據(jù),可以是整數(shù)或字節(jié)數(shù)組。
3. 編碼方式
壓縮列表支持多種編碼方式,根據(jù)數(shù)據(jù)類型和長(zhǎng)度選擇最合適的編碼方式。常見(jiàn)的編碼方式包括:
字符串編碼:
- 長(zhǎng)度小于或等于 63 字節(jié):6 位表示長(zhǎng)度
- 長(zhǎng)度小于或等于 16383 字節(jié):14 位表示長(zhǎng)度
- 長(zhǎng)度大于 16383 字節(jié):32 位表示長(zhǎng)度
整數(shù)編碼:
- 1 字節(jié)整數(shù):表示范圍為 [-128, 127]
- 3 字節(jié)整數(shù):表示范圍為 [-2^23, 2^23-1]
- 5 字節(jié)整數(shù):表示范圍為 [-2^39, 2^39-1]
4. 操作
壓縮列表支持多種操作,包括插入、刪除、查找等。這些操作通過(guò)調(diào)整節(jié)點(diǎn)結(jié)構(gòu)和更新相關(guān)元數(shù)據(jù)來(lái)實(shí)現(xiàn)。
插入
插入一個(gè)新節(jié)點(diǎn),需要找到插入位置,調(diào)整后續(xù)節(jié)點(diǎn)的 previous_entry_length
字段,并可能觸發(fā)內(nèi)存重分配。例如:
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { // step 1: 找到插入位置 // step 2: 擴(kuò)展內(nèi)存以容納新節(jié)點(diǎn) // step 3: 調(diào)整其他節(jié)點(diǎn)的 previous_entry_length 字段 // step 4: 將新節(jié)點(diǎn)寫入壓縮列表 }
刪除
刪除一個(gè)節(jié)點(diǎn),需要調(diào)整前后節(jié)點(diǎn)的連接關(guān)系,并可能觸發(fā)內(nèi)存收縮。例如:
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) { // step 1: 找到要?jiǎng)h除的節(jié)點(diǎn) // step 2: 釋放節(jié)點(diǎn)占用的空間 // step 3: 調(diào)整其他節(jié)點(diǎn)的 previous_entry_length 字段 // step 4: 縮減內(nèi)存 }
查找
遍歷壓縮列表,查找滿足條件的節(jié)點(diǎn)。例如:
unsigned char *ziplistFind(unsigned char *zl, unsigned char *s, unsigned int slen, unsigned int skip) { // step 1: 遍歷壓縮列表 // step 2: 比較節(jié)點(diǎn)內(nèi)容 // step 3: 返回匹配的節(jié)點(diǎn) }
擴(kuò)容機(jī)制
壓縮列表(Ziplist)的主要設(shè)計(jì)目標(biāo)之一是節(jié)省內(nèi)存。為了保持?jǐn)?shù)據(jù)緊湊存儲(chǔ),壓縮列表使用連續(xù)的內(nèi)存塊。因此,當(dāng)需要插入新的數(shù)據(jù)時(shí),如果現(xiàn)有內(nèi)存塊空間不足,就需要進(jìn)行擴(kuò)容操作。
1. 擴(kuò)容觸發(fā)條件
當(dāng)需要在壓縮列表中插入新節(jié)點(diǎn),但當(dāng)前內(nèi)存空間不足以容納該新節(jié)點(diǎn)時(shí),會(huì)觸發(fā)擴(kuò)容操作。這是為了確保壓縮列表能夠繼續(xù)正常存儲(chǔ)新增的數(shù)據(jù)。
2. 擴(kuò)容步驟
步驟1:計(jì)算新長(zhǎng)度
首先,根據(jù)當(dāng)前壓縮列表的總長(zhǎng)度和新節(jié)點(diǎn)的大小,計(jì)算出擴(kuò)容后所需的總長(zhǎng)度。
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)); // 當(dāng)前壓縮列表的總長(zhǎng)度 size_t reqlen = zipRawEntryLength(p); // 新節(jié)點(diǎn)所需的長(zhǎng)度 size_t newlen = curlen + reqlen; // 新的總長(zhǎng)度
步驟2:分配新內(nèi)存
根據(jù)計(jì)算出的新長(zhǎng)度,為壓縮列表分配一個(gè)更大的內(nèi)存塊。這個(gè)過(guò)程通常使用 zrealloc
函數(shù),該函數(shù)不僅會(huì)增加所需的最小容量,還會(huì)多分配一些額外的空間,以減少頻繁的內(nèi)存重分配操作,從而提高性能。
if (newlen > curlen) { zl = zrealloc(zl, newlen); // 分配新的內(nèi)存塊 ZIPLIST_BYTES(zl) = intrev32ifbe(newlen); // 更新 zlbytes 字段 }
步驟3:復(fù)制舊數(shù)據(jù)
在分配了新的內(nèi)存塊之后,將舊的壓縮列表數(shù)據(jù)復(fù)制到新的內(nèi)存塊中。這是由 zrealloc
自動(dòng)處理的,程序員無(wú)需手動(dòng)干預(yù)。
步驟4:更新元數(shù)據(jù)
擴(kuò)容后,需要更新壓縮列表的元數(shù)據(jù)字段,包括 zlbytes
、zltail
等,以反映新的內(nèi)存布局。
ZIPLIST_BYTES(zl) = intrev32ifbe(newlen); // 更新 zlbytes // 如果插入點(diǎn)在尾部,需要更新 zltail if (tail_pos == curlen) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(new_tail_offset); }
步驟5:插入新節(jié)點(diǎn)
在更新完元數(shù)據(jù)之后,在適當(dāng)?shù)奈恢貌迦胄鹿?jié)點(diǎn),并調(diào)整相關(guān)的 previous_entry_length
和其他必要的字段。
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { // ... 前面部分略 ... // 插入新節(jié)點(diǎn) memmove(p + reqlen, p, curlen - (p - zl)); zipSetEntry(zl, p, s, slen); // 更新 zlend 標(biāo)志 ZIPLIST_END(zl) = 0xFF; return zl; }
3. 內(nèi)存分配策略
Redis 使用 Jemalloc 或者系統(tǒng)默認(rèn)的內(nèi)存分配器來(lái)進(jìn)行內(nèi)存管理。內(nèi)存擴(kuò)展時(shí),通常會(huì)分配比實(shí)際需求更多的內(nèi)存,以減少未來(lái)再次擴(kuò)容的次數(shù)。這種策略稱為“緩沖區(qū)增長(zhǎng)”,可以顯著提升性能,避免頻繁的內(nèi)存分配和數(shù)據(jù)拷貝。
4. 內(nèi)存收縮
除了擴(kuò)容,壓縮列表還可能進(jìn)行收縮操作。當(dāng)刪除大量節(jié)點(diǎn)或者節(jié)點(diǎn)內(nèi)容縮小時(shí),壓縮列表可能會(huì)釋放不再需要的內(nèi)存空間。這通常發(fā)生在內(nèi)存非常緊張或者節(jié)點(diǎn)刪除操作非常頻繁的情況下。
收縮示例
假設(shè)刪除操作導(dǎo)致壓縮列表變得非常稀疏,可以通過(guò)重新分配較小的內(nèi)存空間來(lái)實(shí)現(xiàn)收縮:
unsigned char *ziplistShrink(unsigned char *zl) { size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)); size_t newlen = calculateNewLengthAfterDeletion(zl); if (newlen < curlen) { zl = zrealloc(zl, newlen); ZIPLIST_BYTES(zl) = intrev32ifbe(newlen); } return zl; }
以上就是Redis壓縮列表的設(shè)計(jì)與實(shí)現(xiàn)的詳細(xì)內(nèi)容,更多關(guān)于Redis壓縮列表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Redis源碼解析sds字符串實(shí)現(xiàn)示例
這篇文章主要為大家介紹了Redis源碼解析sds字符串實(shí)現(xiàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08SpringMVC集成redis配置的多種實(shí)現(xiàn)方法
這篇文章主要介紹了SpringMVC集成redis配置的多種實(shí)現(xiàn)方法,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-03-03Redis常用數(shù)據(jù)類型命令實(shí)例匯總
這篇文章主要介紹了Redis常用數(shù)據(jù)類型命令實(shí)例匯總,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10Springboot/Springcloud項(xiàng)目集成redis進(jìn)行存取的過(guò)程解析
大家都知道Redis支持五種數(shù)據(jù)類型:string(字符串),hash(哈希),list(列表),set(集合),zset(sorted set:有序集合),本文重點(diǎn)給大家介紹Springboot/Springcloud項(xiàng)目集成redis進(jìn)行存取的過(guò)程,需要的朋友參考下吧2021-12-12Ubuntu下Redis密碼設(shè)置問(wèn)題及其解決過(guò)程
這篇文章主要介紹了Ubuntu下Redis密碼設(shè)置問(wèn)題及其解決過(guò)程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-06-06Redis不同數(shù)據(jù)類型使用場(chǎng)景代碼實(shí)例
這篇文章主要介紹了Redis不同數(shù)據(jù)類型使用場(chǎng)景代碼實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-12-12Redis Cluster集群動(dòng)態(tài)擴(kuò)容的實(shí)現(xiàn)
本文主要介紹了Redis Cluster集群動(dòng)態(tài)擴(kuò)容的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-07-07Redis大key多key拆分實(shí)現(xiàn)方法解析
這篇文章主要介紹了Redis大key多key拆分實(shí)現(xiàn)方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11