壓縮列表(ziplist)是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。

7.1 壓縮列表的構(gòu)成

壓縮列表是Redis為了節(jié)約內(nèi)存而開發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序性數(shù)據(jù)結(jié)構(gòu)。一個壓縮列表可以包含任意多個節(jié)點(diǎn),每個節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。

壓縮列表各個組成部分的詳細(xì)說明

7.2 壓縮列表節(jié)點(diǎn)的構(gòu)成

每個壓縮列表節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。

每個壓縮列表節(jié)點(diǎn)都由previous_entry_length、encoding、content三個部分組成

7.2.1 previous_entry_length

節(jié)點(diǎn)的previous_entry_length屬性以字節(jié)為單位，記錄了壓縮列表中前一個節(jié)點(diǎn)的長度。previous_entry_length屬性的長度可以是1字節(jié)或者5字節(jié)：

• 如果前一節(jié)點(diǎn)的長度小于254字節(jié)，那么previous_entry_length屬性的長度為1字節(jié)：前一節(jié)點(diǎn)的長度就保存在這一個字節(jié)里面
• 如果前一個節(jié)點(diǎn)的長度大于254字節(jié)，那么previous_entry_length屬性的長度為5字節(jié)：其中屬性的第一個字節(jié)會被設(shè)置為oxFE,而之后的四個字節(jié)則用于保存前一個節(jié)點(diǎn)的長度。
  因?yàn)楣?jié)點(diǎn)的previous_entry_length屬性記錄了前一個節(jié)點(diǎn)的長度，所以程序可以通過指針運(yùn)算，根據(jù)當(dāng)前節(jié)點(diǎn)的起始地址計(jì)算出前一個節(jié)點(diǎn)的起始地址。
  壓縮列表從表尾向表頭遍歷操作就是使用這一原理實(shí)現(xiàn)的，只要我們擁有一個指向某個節(jié)點(diǎn)起始地址的指針，那么通過這個指針以及這個節(jié)點(diǎn)的previous_entry_length屬性，程序就可以一直向前一個節(jié)點(diǎn)回溯，最終到達(dá)壓縮列表的表頭節(jié)點(diǎn)。

7.2.2 encoding

節(jié)點(diǎn)的encoding屬性記錄了節(jié)點(diǎn)的content屬性所保存數(shù)據(jù)的類型以及長度

7.2.3 content

節(jié)點(diǎn)的content屬性負(fù)責(zé)保存節(jié)點(diǎn)的值，節(jié)點(diǎn)值可以是一個字節(jié)數(shù)組或者整數(shù)，值的類型和長度由節(jié)點(diǎn)的encoding屬性決定。

7.3 連鎖更新

每個節(jié)點(diǎn)的previous_entry_length屬性都記錄了前一個節(jié)點(diǎn)的長度

• 如果前一個節(jié)點(diǎn)的長度小于254，那么previous_entry_length屬性需要用1字節(jié)長的空間來保存這個長度值
• 如果前一個節(jié)點(diǎn)的長度大于等于254，那么previous_entry_length屬性需要5字節(jié)長的空間來保存這個長度值
  考慮這樣一種情況：在一個壓縮列表中，有多個連續(xù)的、長度介于250字節(jié)到253字節(jié)之間的節(jié)點(diǎn)e1至eN
  |zlbytes|zltail|zllen|e1|e2|e3|...|eN|zlend|
  因?yàn)閑1至eN的所有節(jié)點(diǎn)的長度都小于254字節(jié)，所以記錄這些節(jié)點(diǎn)的長度只需要1字節(jié)長的previous_entry_length屬性，換句話說，e1至eN的所有節(jié)點(diǎn)的previous_entry_length屬性都是1字節(jié)長的。
  如果我們將一個長度大于等于254字節(jié)的新節(jié)點(diǎn)new設(shè)置到壓縮列表的表頭節(jié)點(diǎn)，那么new將成為e1的潛質(zhì)節(jié)點(diǎn)。
  此時e1到eN的每個節(jié)點(diǎn)的previous_entry_length屬性都要擴(kuò)展為5字節(jié)以符合壓縮列表對節(jié)點(diǎn)的要求，程序需要不斷的對壓縮列表進(jìn)行空間重分配操作。
  Redis將這種在特殊情況下產(chǎn)生的多次空間擴(kuò)展操作稱之為“連鎖更新”。
  除了添加新節(jié)點(diǎn)可能會引發(fā)連鎖更新之外，刪除節(jié)點(diǎn)也可能會連鎖更新。
  因?yàn)檫B鎖更新在最壞情況下需要對壓縮列表執(zhí)行N次空間重分配操作，而每次空間重分配的最壞復(fù)雜度為O(N)，所以連鎖更新的最壞復(fù)雜度為O(N²)。
  注意的是，盡管連鎖更新的復(fù)雜度較高，但它真正趙成性能問題的幾率是很低的：
• 首先，壓縮列表里要恰好有多個連續(xù)的、長度介于250字節(jié)至253字節(jié)之間的節(jié)點(diǎn)，連鎖更新才有可能被引發(fā)，在實(shí)際中，這種情況并不多見；
• 其次，即使出現(xiàn)連鎖更新，但只要更新的節(jié)點(diǎn)數(shù)量不多，就不會對性能造成任何影響：比如說，對三五個節(jié)點(diǎn)進(jìn)行連鎖更新是絕對不會影響性能的；