本文首發于公眾號：Hunter后端
原文鏈接：Redis資料結構三之壓縮串列
本篇筆記介紹壓縮串列，
在 Redis 3.2 版本之前，壓縮串列是串列物件、哈希物件、有序集合物件的的底層實作之一，
因為壓縮串列本身結構上的一些缺陷，壓縮串列這個結構被替換了，但是壓縮串列結構本身有一些可取之處，并且替換它的新結構 listpack 與之很相似，所以我們這里還是介紹一下壓縮串列的結構和存盤
1、壓縮串列的結構
壓縮串列是 Redis 為了節約記憶體而開發的，由一個連續記憶體塊組成的順序型資料結構，
它的組成結構如下：
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
壓縮串列的英文名是 ziplist，所以它的屬性都是 zl 開頭，
1. 串列屬性介紹
zlbytes
zlbytes 長度為 4 位元組，記錄整個壓縮串列占用的記憶體位元組數
zltail
zltail 長度為 4 位元組，記錄壓縮串列最后一個節點，也就是我們結構示例中的 entryN 到 zlbytes 的地址之間的偏移量，
zllen
zllen 長度為 2 位元組，記錄的是壓縮串列包含的節點數量，也就是結構中的 N，
zlend
zlend 長度為 1 位元組，它的值為 0xFF（十進制 255），用于標記壓縮串列的末端，
2. 壓縮串列節點屬性介紹
對于每一個 entry 節點，也就是壓縮串列中的元素節點，它的結構示意如下：
| previous_entry_length | encoding | content |
previous_entry_length
previous_entry_length 屬性記錄的是壓縮串列中前一個節點的長度
previous_entry_length 屬性本身的長度可以是 1 位元組或者 5 位元組
如果前一節點的長度小于 254 位元組，那么 previous_entry_length 屬性的長度為 1 位元組，前一個節點的長度保存在這個位元組里
如果前一節點的長度大于等于 254 位元組，那么 previous_entry_length 屬性的長度為 5 位元組，第一個位元組被設定成 0xFE（也就是 254），之后的四個位元組用于前一節點的長度，
通過 previous_entry_length 屬性，我們可以通過當前節點的地址和 previous_entry_length 屬性，計算出前一個節點的起始地址，壓縮串列的從表尾到表頭的遍歷操作就是使用這個原理一個節點一個節點往前回溯實作的，
encoding
encoding 屬性記錄了節點的 content 屬性所保存資料的型別以及長度，
encoding 的值如果是一位元組長，且值的最高位以 11 開頭，那么表示是整數編碼，表示 content 屬性保存著整數值，
encoding 的值為 一位元組、兩位元組、五位元組長，且值的最高位為 00、01、10 則表示是位元組陣列編碼
content
content 屬性保存的是節點的值，可以是一個位元組陣列或者整數，值的型別和長度由節點的 encoding 屬性決定，
2、 連鎖更新
在壓縮串列的節點屬性中，previous_entry_length 屬性的長度是根據前一節點的長度來進行賦值的，如果前一節點的長度小于 254 位元組，那么下一節點的 previous_entry_length 屬性長度為 1 位元組，如果前一節點的長度大于等于 254 位元組，那么下一節點的 previous_entry_length 屬性為 5 位元組，
那么在這種情況下，就存在一種較為極端的情況，那就是壓縮串列中每個節點的長度都在 250 - 253 位元組之間，這時候，如果在表頭插入一個長度大于等于 254 位元組的節點，那么相對應的第二個節點的 previous_entry_length 的長度就要從 1 位元組變為 4 位元組，那么該節點的整體長度就大于等于 254 位元組，
依此類推，壓縮串列的每一個節點的長度都會產生連鎖反應，長度都會逐個變成大于等于 254 位元組長度，程式就需要不斷地對壓縮串列執行空間重分配的操作，
Redis 將這種在特殊情況下產生的連續多次空間擴展操作稱為連鎖更新，
除了新增節點這種情況，還有一種洗掉節點也可能造成連鎖更新的情況，比如有這么幾個節點，big 節點的長度大于等于 254 位元組，small 節點長度小于254 位元組，e1 到 eN 的節點長度都在 250-253 位元組之間，
| zlbytes | zltail | zllen | big | small | entry1 | entry2 | ... | entryN | zlend |
這時候，洗掉 small 節點，entry1 節點的前節點的長度就會從 250-253 變成大于等于 254，因此 entry1 節點的 previous_entry_length 長度就會變成 5 位元組，entry1 整體長度就會大于等于 254 位元組，依次之后每個節點都會這樣產生連鎖更新，
盡管連鎖更新的復雜度較高，但它真正造成性能問題的幾率是很低的：
首先，壓縮串列里要恰好有多個連續的、長度介于 250-253 位元組之間的節點，連鎖反應才有可能被引發
其次，即使出現連鎖更新，但只要被更新的節點數量不多，就不會對性能造成任何影響，比如對只擁有三五個節點的壓縮串列進行連鎖更新，
3、壓縮串列缺點
壓縮串列雖然能節約記憶體，但仍然存在一些缺點：
- 需要通過遍歷操作來查找節點，元素過多時會造成查詢效率低下
- 對壓縮串列節點進行新增或者修改時，可能會造成連鎖更新的問題
如果想獲取更多后端相關文章，可掃碼關注閱讀：
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/552751.html
標籤：NoSQL
上一篇：多圖詳解：不停機分庫分表五個步驟
下一篇：返回列表