Redis进阶-List底层数据结构精讲
文章目錄
- Pre
- list 列表
- 隊(duì)列 O(1)
- 棧 O(1)
- 查詢 O(n)
- 快速列表 quicklist
- 壓縮列表 ziplist
- ziplist 源碼
- entry
- 增加元素
- 快速列表 quicklist
- ziplist 存多少元素?
- 壓縮深度
- 延伸
Pre
Redis進(jìn)階-核心數(shù)據(jù)結(jié)構(gòu)進(jìn)階實(shí)戰(zhàn)
Algorithms_基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)(03)_線性表之鏈表_雙向鏈表
Redis 有 5 種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，分別為：string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合) 。
Redis 所有的數(shù)據(jù)結(jié)構(gòu)都是以唯一的key 字符串作為名稱，然后通過這個(gè)唯一 key 值來獲取相應(yīng)的 value 數(shù)據(jù)。不同類型的數(shù)據(jù)結(jié)構(gòu)的差異就在于 value 的結(jié)構(gòu)不一樣。
list 列表
-
Redis 的列表相當(dāng)于 Java 語言里面的 LinkedList，是鏈表而不是數(shù)組 。
這意味著list 的插入和刪除操作非常快，時(shí)間復(fù)雜度為 O(1)，但是查找數(shù)據(jù)很慢，時(shí)間復(fù)雜度為 O(n) 。
-
當(dāng)列表彈出了最后一個(gè)元素之后，該數(shù)據(jù)結(jié)構(gòu)自動(dòng)被刪除，內(nèi)存被回收。
-
Redis 的列表結(jié)構(gòu)常用來做異步隊(duì)列使用
將需要延后處理的任務(wù)結(jié)構(gòu)體序列化成字符串塞進(jìn) Redis 的列表，另一個(gè)線程從這個(gè)列表中輪詢數(shù)據(jù)進(jìn)行處理
隊(duì)列 O(1)
右邊進(jìn)左邊出：隊(duì)列
192.168.18.131:8001> rpush artisan art1 art2 art3 art4 (integer) 4 192.168.18.131:8001> llen artisan (integer) 4 192.168.18.131:8001> LRANGE artisan 0 999 1) "art1" 2) "art2" 3) "art3" 4) "art4" 192.168.18.131:8001> LPOP artisan "art1" 192.168.18.131:8001> LPOP artisan "art2" 192.168.18.131:8001> LPOP artisan "art3" 192.168.18.131:8001> LPOP artisan "art4" 192.168.18.131:8001> LPOP artisan (nil) 192.168.18.131:8001>當(dāng)然了，你也可以左邊進(jìn)，右邊出，保證FIFO就行。
除了rpush 和 lpop, 還可以使用 lpush 和 rpop 結(jié)合使用，效果是一樣的。
棧 O(1)
右邊進(jìn)右邊出：棧
192.168.18.131:8001> rpush artisan art1 art2 art3 art4 (integer) 4 192.168.18.131:8001> RPOP artisan "art4" 192.168.18.131:8001> RPOP artisan "art3" 192.168.18.131:8001> RPOP artisan "art2" 192.168.18.131:8001> RPOP artisan "art1" 192.168.18.131:8001> RPOP artisan (nil) 192.168.18.131:8001>查詢 O(n)
lindex & ltrim
-
lindex 相當(dāng)于 Java 鏈表的 get(int index)方法，它需要對(duì)鏈表進(jìn)行遍歷，性能隨著參數(shù)index 增大而變差.
-
ltrim : 兩個(gè)參數(shù) start_index 和 end_index 定義了一個(gè)區(qū)間，在這個(gè)區(qū)間內(nèi)的值， ltrim 要保留，區(qū)間之外統(tǒng)統(tǒng)砍掉。
-
我們可以通過 ltrim 來實(shí)現(xiàn)一個(gè)定長的鏈表，這一點(diǎn)非常有用。
-
index 可以為負(fù)數(shù)，index=-1 表示倒數(shù)第一個(gè)元素，同樣 index=-2 表示倒數(shù)第二個(gè)元素。
快速列表 quicklist
Redis 底層存儲(chǔ)的還不是一個(gè)簡單的 linkedlist，而是稱之為快速鏈表 quicklist 的一個(gè)結(jié)構(gòu)。
-
首先在列表元素較少的情況下會(huì)使用一塊連續(xù)的內(nèi)存存儲(chǔ)，這個(gè)結(jié)構(gòu)是 ziplist ，即壓縮列表 . 它將所有的元素緊挨著一起存儲(chǔ)，分配的是一塊連續(xù)的內(nèi)存
-
當(dāng)數(shù)據(jù)量比較多才會(huì)改成 quicklist.
因?yàn)槠胀ǖ逆湵硇枰母郊又羔樋臻g太大，會(huì)比較浪費(fèi)空間，而且會(huì)加重內(nèi)存的碎片化 .
比如這個(gè)列表里存的只是 int 類型的數(shù)據(jù)，結(jié)構(gòu)上還需要兩個(gè)額外的指針 prev 和 next 。所以 Redis 將鏈表和 ziplist 結(jié)合起來組成了 quicklist。也就是將多個(gè)ziplist 使用雙向指針串起來使用。這樣既滿足了快速的插入刪除性能，又不會(huì)出現(xiàn)太大的空間冗余。
壓縮列表 ziplist
Redis 為了節(jié)約內(nèi)存空間使用，zset 和 hash 容器對(duì)象在元素個(gè)數(shù)較少的時(shí)候，采用壓縮列表 (ziplist) 進(jìn)行存儲(chǔ)。
壓縮列表是一塊連續(xù)的內(nèi)存空間，元素之間緊挨著存儲(chǔ)，沒有任何冗余空隙。
使用DEBUG OBJECT 查看內(nèi)部存儲(chǔ)結(jié)構(gòu)
192.168.18.131:8001> ZADD artisan 1.0 java 2.0 go 3.0 python (integer) 3 192.168.18.131:8001> DEBUG OBJECT artisan # 查看內(nèi)部存儲(chǔ)結(jié)構(gòu) Value at:0x7f131e2ba5d0 refcount:1 encoding:ziplist serializedlength:36 lru:9895943 lru_seconds_idle:6 192.168.18.131:8001> 192.168.18.131:8001> HMSET artisan2 name ysw sex male -> Redirected to slot [6066] located at 192.168.18.132:8002 OK 192.168.18.132:8002> DEBUG OBJECT artisan2 Value at:0x7fb74eaba5f0 refcount:1 encoding:ziplist serializedlength:34 lru:9896028 lru_seconds_idle:9 192.168.18.132:8002>觀察 debug object 輸出的 encoding 字段都是 ziplist，這就表示內(nèi)部采用壓縮列表結(jié)構(gòu)進(jìn)行存儲(chǔ)。
ziplist 源碼
struct ziplist<T> {int32 zlbytes; // 整個(gè)壓縮列表占用字節(jié)數(shù)int32 zltail_offset; // 最后一個(gè)元素距離壓縮列表起始位置的偏移量，用于快速定位到最后一個(gè)節(jié)點(diǎn)int16 zllength; // 元素個(gè)數(shù)T[] entries; // 元素內(nèi)容列表，挨個(gè)挨個(gè)緊湊存儲(chǔ)int8 zlend; // 標(biāo)志壓縮列表的結(jié)束，值恒為 0xFF }壓縮列表為了支持雙向遍歷，所以才會(huì)有 ztail_offset 這個(gè)字段，用來快速定位到最后一 個(gè)元素，然后倒著遍歷。
entry
entry 塊隨著容納的元素類型不同，也會(huì)有不一樣的結(jié)構(gòu)
struct entry {int<var> prevlen; // 前一個(gè) entry 的字節(jié)長度int<var> encoding; // 元素類型編碼optional byte[] content; // 元素內(nèi)容 }它的 prevlen 字段表示前一個(gè) entry 的字節(jié)長度，當(dāng)壓縮列表倒著遍歷時(shí)，需要通過這個(gè)字段來快速定位到下一個(gè)元素的位置。
-
它是一個(gè)變長的整數(shù)，當(dāng)字符串長度小于254(0xFE) 時(shí)，使用一個(gè)字節(jié)表示；
-
如果達(dá)到或超出 254(0xFE) 那就使用 5 個(gè)字節(jié)來表示。
-
第一個(gè)字節(jié)是 0xFE(254)，剩余四個(gè)字節(jié)表示字符串長度。
用 5 個(gè)字節(jié)來表示字符串長度，是不是太浪費(fèi)了?
我們可以算一下，當(dāng)字符串長度比較長的時(shí)候，其實(shí) 5個(gè)字節(jié)也只占用了不到(5/(254+5))<2%的空間。
encoding 字段存儲(chǔ)了元素內(nèi)容的編碼類型信息，ziplist 通過這個(gè)字段來決定后面的content 內(nèi)容的形式。
增加元素
因?yàn)?ziplist 都是緊湊存儲(chǔ)，沒有冗余空間 (對(duì)比一下 Redis 的字符串結(jié)構(gòu))。意味著插入一個(gè)新的元素就需要調(diào)用 realloc 擴(kuò)展內(nèi)存。
取決于內(nèi)存分配器算法和當(dāng)前的 ziplist 內(nèi)存大小，realloc 可能會(huì)重新分配新的內(nèi)存空間，并將之前的內(nèi)容一次性拷貝到新的地址，也可能在原有的地址上進(jìn)行擴(kuò)展，這時(shí)就不需要進(jìn)行舊內(nèi)容的內(nèi)存拷貝。
如果 ziplist 占據(jù)內(nèi)存太大，重新分配內(nèi)存和拷貝內(nèi)存就會(huì)有很大的消耗。所以 ziplist不適合存儲(chǔ)大型字符串，存儲(chǔ)的元素也不宜過多。
快速列表 quicklist
Redis 早期版本存儲(chǔ) list 列表數(shù)據(jù)結(jié)構(gòu)使用的是壓縮列表 ziplist 和普通的雙向鏈表linkedlist，也就是元素少時(shí)用 ziplist，元素多時(shí)用 linkedlist。
// 鏈表的節(jié)點(diǎn) struct listNode<T> {listNode* prev;listNode* next;T value; } // 鏈表 struct list {listNode *head;listNode *tail;long length; }考慮到鏈表的附加空間相對(duì)太高，prev 和 next 指針就要占去 16 個(gè)字節(jié) (64bit 系統(tǒng)的指針是 8 個(gè)字節(jié))，另外每個(gè)節(jié)點(diǎn)的內(nèi)存都是單獨(dú)分配，會(huì)加劇內(nèi)存的碎片化，影響內(nèi)存管理效率。后續(xù)版本對(duì)列表數(shù)據(jù)結(jié)構(gòu)進(jìn)行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。
192.168.18.132:8002> RPUSH test artisan1 artisan2 artisan3 (integer) 3 192.168.18.132:8002> DEBUG OBJECT test Value at:0x7fb74eaba610 refcount:1 encoding:quicklist serializedlength:36 lru:9897276 lru_seconds_idle:4 ql_nodes:1 ql_avg_node:3.00 ql_ziplist_max:-2 ql_compressed:0 ql_uncompressed_size:41 192.168.18.132:8002>觀察上面輸出字段 encoding 的值。quicklist 是 ziplist 和 linkedlist 的混合體，它將 linkedlist 按段切分，每一段使用 ziplist 來緊湊存儲(chǔ)，多個(gè) ziplist 之間使用雙向指針串接起來。
struct ziplist {... } struct ziplist_compressed {int32 size;byte[] compressed_data; }struct quicklistNode {quicklistNode* prev;quicklistNode* next;ziplist* zl; // 指向壓縮列表int32 size; // ziplist 的字節(jié)總數(shù)int16 count; // ziplist 中的元素?cái)?shù)量int2 encoding; // 存儲(chǔ)形式 2bit，原生字節(jié)數(shù)組還是 LZF 壓縮存儲(chǔ)... } struct quicklist {quicklistNode* head;quicklistNode* tail;long count; // 元素總數(shù)int nodes; // ziplist 節(jié)點(diǎn)的個(gè)數(shù)int compressDepth; // LZF 算法壓縮深度... }上述代碼簡單地表示了 quicklist 的大致結(jié)構(gòu)。為了進(jìn)一步節(jié)約空間，Redis 還會(huì)對(duì)ziplist 進(jìn)行壓縮存儲(chǔ)，使用 LZF 算法壓縮，可以選擇壓縮深度。
ziplist 存多少元素?
quicklist 內(nèi)部默認(rèn)單個(gè) ziplist 長度為 8k 字節(jié)，超出了這個(gè)字節(jié)數(shù)，就會(huì)新起一個(gè)ziplist。
ziplist 的長度由配置參數(shù) list-max-ziplist-size 決定。
壓縮深度
quicklist 默認(rèn)的壓縮深度是 0，也就是不壓縮。壓縮的實(shí)際深度由配置參數(shù) list-compress-depth 決定.
為了支持快速的 push/pop 操作，quicklist 的首尾兩個(gè) ziplist 不壓縮，此時(shí)深度就是 1。
如果深度為 2，就表示 quicklist 的首尾第一個(gè) ziplist 以及首尾第二個(gè) ziplist 都不壓縮。
延伸
參考：《Redis深度歷險(xiǎn)：核心原理和應(yīng)用實(shí)踐》
ziplist、linkedlist 和 quicklist 的性能對(duì)比
總結(jié)
以上是生活随笔為你收集整理的Redis进阶-List底层数据结构精讲的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Redis进阶-JedisCluster
- 下一篇： Redis进阶-string底层数据结构