Redis?ziplist?壓縮列表的源碼解析
前言
相信對(duì)使用過(guò) Redis 的人來(lái)說(shuō)，數(shù)據(jù)類型 List 是不會(huì)陌生的吧。大多數(shù)人需要實(shí)現(xiàn)一個(gè)隊(duì)列時(shí)候，首選的就是 List 了。但是其實(shí) Redis 的 List 類型有多種實(shí)現(xiàn)方式。這篇文章就是介紹其中一種實(shí)現(xiàn) ziplist - 壓縮列表。
源碼解讀
一如既往，關(guān)于 ziplist 的定義和實(shí)現(xiàn)還是放在一對(duì)文件中，分別是 ziplist.h 和 ziplist.c。在 ziplist.c 文件的頭部有著這么一段注釋介紹什么是 ziplist。
ziplist 是一個(gè)經(jīng)過(guò)特殊編碼的雙向鏈表，旨在提高內(nèi)存效率。 它存儲(chǔ)字符串和整數(shù)值，其中整數(shù)被編碼為實(shí)際整數(shù)而不是一系列字符。 它允許在 O(1) 時(shí)間內(nèi)在列表的任一側(cè)進(jìn)行推送和彈出操作。 但是，由于每個(gè)操作都需要重新分配 ziplist 使用的內(nèi)存，因此實(shí)際復(fù)雜性與 ziplist 使用的內(nèi)存量有關(guān)。
從這段話得到：對(duì)于不同的數(shù)據(jù)類型有著不同的編碼方式，理解為會(huì)對(duì)數(shù)據(jù)進(jìn)行壓縮，從而達(dá)到減少內(nèi)存使用的目的。但是隨著存儲(chǔ)的 value 數(shù)據(jù)級(jí)增加，使用 ziplist 所付出的代價(jià)也隨之增加。
ziplist 布局
ziplist 是一個(gè)特殊雙向鏈表，不像普通的鏈表使用前后指針關(guān)聯(lián)在一起，它是存儲(chǔ)在連續(xù)內(nèi)存上的。整體的結(jié)構(gòu)布局如下圖：
- zlbytes: 32 位無(wú)符號(hào)整型，記錄 ziplist 整個(gè)結(jié)構(gòu)體的占用空間大小。當(dāng)然了也包括 zlbytes 本身。這個(gè)結(jié)構(gòu)有個(gè)很大的用處，就是當(dāng)需要修改 ziplist 時(shí)候不需要遍歷即可知道其本身的大小。 這個(gè) SDS 中記錄字符串的長(zhǎng)度有相似之處，這些好的設(shè)計(jì)往往在平時(shí)的開(kāi)發(fā)中可以采納一下。
- zltail: 32 位無(wú)符號(hào)整型, 記錄整個(gè) ziplist 中最后一個(gè) entry 的偏移量。所以在尾部進(jìn)行 POP 操作時(shí)候不需要先遍歷一次。
- zllen: 16 位無(wú)符號(hào)整型, 記錄 entry 的數(shù)量， 所以只能表示 2^16。但是 Redis 作了特殊的處理：當(dāng)實(shí)體數(shù)超過(guò) 2^16 ,該值被固定為 2^16 - 1。 所以這種時(shí)候要知道所有實(shí)體的數(shù)量就必須要遍歷整個(gè)結(jié)構(gòu)了。
- entry: 真正存數(shù)據(jù)的結(jié)構(gòu)。
- zlend: 8 位無(wú)符號(hào)整型, 固定為 255 。為 ziplist 的結(jié)束標(biāo)識(shí)。
entry 節(jié)點(diǎn)
每個(gè) entry 都包含兩條信息的元數(shù)據(jù)為前綴。 第一元數(shù)據(jù)用來(lái)存儲(chǔ)前一個(gè) entry 的長(zhǎng)度，以便能夠從后向前遍歷列表。 第二元數(shù)據(jù)是表示 entry 的編碼形式。 用來(lái)表示 entry 類型，整數(shù)或字符串，在字符串的情況下，它還表示字符串有效的長(zhǎng)度。
所以一個(gè)完整的 ziplist 是這樣存儲(chǔ)的：
prelen
記錄前一個(gè) entry 的長(zhǎng)度。若前一個(gè) entry 的長(zhǎng)度小于 254 , 則使用 1 個(gè)字節(jié)的 8 位無(wú)符號(hào)整數(shù)來(lái)表示。
若前一個(gè) entry 長(zhǎng)度大于等于 254，則使用 5 個(gè)字節(jié)來(lái)表示。第 1 個(gè)字節(jié)固定為 254 (FE) 作為標(biāo)識(shí)，剩余 4 字節(jié)則用來(lái)表示前一個(gè) entry 的實(shí)際大小。
所以兩種情況下的 entry 結(jié)構(gòu)如下所示：
1. 前一個(gè) entry 大小不超過(guò) 253。 <prevlen from 0 to 253> <encoding> <entry> 2. 前一個(gè) entry 大小超過(guò) 253。 0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>
encoding 編碼
entry 的編碼字段取決于具體值的內(nèi)容，分為字符串、數(shù)字兩種類型單獨(dú)處理。
一、當(dāng) entry 是字符串時(shí)，有 3 種編碼方式。編碼第 1 個(gè)字節(jié)的前 2 位將保存用于存儲(chǔ)字符串長(zhǎng)度的編碼類型，后面是字符串的實(shí)際長(zhǎng)度。
1. 長(zhǎng)度小于或等于 63 字節(jié)（6 位）的字符串值。 “pppppp”表示無(wú)符號(hào)的 6 位數(shù)據(jù)長(zhǎng)度。 |00pppppp| - 1 byte 2. 長(zhǎng)度小于或等于 16383 字節(jié)（14 位）的字符串值。14 位的數(shù)據(jù)采用 big endian 存儲(chǔ)。 big endian 是一種字節(jié)序方式，有Little-Endian、Big-Endian兩種。 |01pppppp|qqqqqqqq| - 2 bytes 3. 長(zhǎng)度大于或等于 16384 字節(jié)的字符串值。 采用 big endian 存儲(chǔ)且可表示的字符串長(zhǎng)度最大2^32-1，所以第一個(gè)字節(jié)沒(méi)有用到，所以低6位沒(méi)有用，所以都是0。 |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
二、當(dāng) entry 是整數(shù)時(shí)，有 6 種編碼方式。前 2 位都固定為 1，接下來(lái)的 2 位用于指定將在此標(biāo)頭后存儲(chǔ)哪種類型的整數(shù)。
與 ziplist 標(biāo)頭一樣，所有整數(shù)都以 Little-Endian 序表示，即使此代碼是在 Big-Endian 系統(tǒng)中編譯的。
1. 整數(shù)編碼為 int16_t（2 字節(jié)）。 |11000000| - 3 bytes 2. 整數(shù)編碼為int32_t（4個(gè)字節(jié)）。 |11010000| - 5 bytes 3. 整數(shù)編碼為 int64_t（8 字節(jié)）。 |11100000| - 9 bytes 4. 整數(shù)編碼為24位帶符號(hào)（3個(gè)字節(jié)）。 |11110000| - 4 bytes 5. 整數(shù)編碼為 8 位有符號(hào)（1 字節(jié)）。 |11111110| - 2 bytes 6. 0到12的無(wú)符號(hào)整數(shù)。編碼后的值實(shí)際上是1到13，因?yàn)?000和1111不能用，所以要從編碼后的4位值中減去1才能得到正確的值。 |1111xxxx| - (with xxxx between 0001 and 1101) immediate 4 bit integer
三、結(jié)尾編碼標(biāo)識(shí)
1. 表示 ziplist 結(jié)尾的標(biāo)識(shí)。 |11111111|
總結(jié)
- ziplist 為了節(jié)省內(nèi)存，采用了緊湊的連續(xù)存儲(chǔ)。所以在修改操作下并不能像一般的鏈表那么容易，需要從新分配新的內(nèi)存，然后復(fù)制到新的空間。
- ziplist 是一個(gè)雙向鏈表，可以在時(shí)間復(fù)雜度為O(1)從下頭部、尾部進(jìn)行pop或push。
- 可能會(huì)出現(xiàn)連鎖更新現(xiàn)象。
其實(shí)使用中并沒(méi)有直接操作這種數(shù)據(jù)結(jié)構(gòu)，但是可以設(shè)置何種情況下使用它。可以在 Redis 的配置文件中進(jìn)行設(shè)置。
如有以下可選設(shè)置項(xiàng)：
- hash-max-ziplist-entries：hash 類型元素?cái)?shù)量超過(guò)指定數(shù)據(jù)后時(shí)候。使用 hash 存儲(chǔ)， 否則使用壓縮表。
- hash-max-ziplist-value： hash 類型元素長(zhǎng)度超過(guò)指定數(shù)據(jù)后時(shí)候。 使用 hash 存儲(chǔ)，否則使用壓縮鏈表。
- zset-max-ziplist-entries：zset 類型 壓縮列表 ziplist 最大限制元素?cái)?shù)。超過(guò)指定值將會(huì)使用跳表 skiplist + dict 來(lái)存儲(chǔ)。
- zset-max-ziplist-value：set 類型 壓縮列表 ziplist 最大限制大小。超過(guò)指定將會(huì)使用跳表 skiplist+dict 來(lái)存儲(chǔ)。
到此這篇關(guān)于Redis ziplist 壓縮列表的源碼解析的文章就介紹到這了,更多相關(guān)Redis ziplist 壓縮列表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Redis為什么選擇單線程？Redis為什么這么快？的相關(guān)資料,需要的朋友可以參考下2023-03-03
這篇文章主要為大家介紹了Redis異常測(cè)試盤(pán)點(diǎn)分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
本文主要介紹了Redis整合MySQL主從集群的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
redis 過(guò)期策略是定期刪除+惰性刪除,下面這篇文章主要給大家介紹了關(guān)于Redis過(guò)期策略的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-01-01
Redis實(shí)現(xiàn)排行榜及相同積分按時(shí)間排序功能的實(shí)現(xiàn)
這篇文章主要介紹了Redis實(shí)現(xiàn)排行榜及相同積分按時(shí)間排序,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-08-08
本文主要介紹了Redis如何正確關(guān)閉和開(kāi)啟持久化，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
Redis拓展之定時(shí)消息通知實(shí)現(xiàn)詳解
這篇文章主要為大家介紹了Redis拓展之定時(shí)消息通知實(shí)現(xiàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-07-07
Java實(shí)現(xiàn)多級(jí)緩存的方法詳解
對(duì)于高并發(fā)系統(tǒng)來(lái)說(shuō),有三個(gè)重要的機(jī)制來(lái)保障其高效運(yùn)行,它們分別是：緩存、限流和熔斷,所以本文就來(lái)和大家探討一下多級(jí)緩存的實(shí)現(xiàn)方法,希望對(duì)大家有所幫助2024-02-02
這篇文章主要為大家介紹了redis分布式鎖解決緩存雙寫(xiě)一致性示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
Redis在2.6推出了腳本功能，允許開(kāi)發(fā)者使用Lua語(yǔ)言編寫(xiě)腳本傳到Redis中執(zhí)行。下面這篇文章主要給大家介紹了關(guān)于Redis執(zhí)行Lua腳本的好處與示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-10-10