Redis壓縮表、跳躍表?拿來吧你

語言: CN / TW / HK

highlight: a11y-dark theme: channing-cyan


本文主要用來學習下,redis當中使用的壓縮表跳躍表,為什麼在諸多的資料結構中,redis要選擇他們作為自己的資料儲存結構。

什麼是壓縮表?

壓縮表是Redis為了節約記憶體而開發的,是由一系列特殊編碼的連續記憶體塊組成的順序型(sequential)資料結構。一個壓縮列表可以包含任意多個節點(entry),每個節點可以儲存一個位元組陣列或者一個整數值。

壓縮表的構成

壓縮表的構成如下所示:

未命名檔案 (24).png

壓縮表各構成部分的含義說明:

| 屬性 | 用途 | | --- | --- | | zlbytes | 記錄整個壓縮表佔用的位元組數;在對壓縮列表進行記憶體重分配或者計算zlend時使用 | | zltail | 記錄壓縮表尾結點距離起始節點的位元組距離 | | zllen | 記錄壓縮表包含的節點數量 | | entry | 壓縮表的節點,長度由其內容決定 | | zlend | 標記壓縮表末端 |

壓縮表節點(entry)的構成

每個節點由以下三個部分組成:

未命名檔案 (25).png

其中三個部分的含義分別是:

| 屬性 | 用途 | | --- | --- | | previous_entry_length | 以位元組為單位,記錄前一個節點的長度。程式可以通過指標運算,根據當前節點的起始地址來計算出前一個節點的起始地址。從表尾向表頭遍歷操作就是通過這樣原理實現的。 | | encoding | 記錄了節點的content屬性所儲存資料的型別以及長度 | | content | 儲存節點的值,節點值可以是一個位元組陣列或者整數,值的型別和長度由節點的encoding屬性決定 |

連鎖更新問題

在前面介紹previous_entry_length的時候,有一點沒有詳細說明:

  • 如果前一節點的長度小於254位元組,那麼previous_entry_length屬性需要用1位元組長的空間來儲存這個長度值。

  • 如果前一節點的長度大於等於254位元組,那麼previous_entry_length屬性需要用5位元組長的空間來儲存這個長度值。

正是由於這樣的設計,從而會導致連鎖更新問題。

假設有 entry1 到 entryN 個節點,每個節點的位元組長度都在 250 到 253 之間,則每個節點的previous_entry_length儲存的長度都是1。

如果此時 new 一個大於254的節點被壓入壓縮表的頭部,那麼這個 new 將成為 e1 前面的頭結點。此時e1的previous_entry_length只有1位元組,無法儲存前一節點new的5位元組長度,所以需要將e1的長度擴大為254 ~ 257

同樣的,對於e2來說,需要如e1一樣增加容量才行。直到eN,都需要重新分配空間,這一種連續擴充套件空間的操作被稱之為連鎖更新

其實連鎖更新造成的效能損耗的機率是很低的,實際使用過程中幾乎不會出現我們上面提到的極端環境,即使少量的連鎖更新,也可以忽略不計

什麼是跳躍表?

跳躍表(skiplist)是一種有序資料結構,它通過在每個節點中維持多個指向其他節點的指標,從而達到快速訪問節點的目的。

跳躍表的時間複雜度是平均O(logN)最壞O(N)

實現有序集合的方式有很多,為什麼redis選擇跳躍表?

  • 陣列:陣列元素插入、刪除不便
  • 連結串列:查詢元素效率低
  • 平衡樹:實現複雜

大多數情況下,跳躍表的效率可以和和平衡樹媲美,而其實現相對平衡樹要簡單,所以很多情況下用跳躍表去替代平衡樹

跳躍表的構成

跳躍表在redis當中由兩部分構成: * zskiplistNode:跳躍表節點 * zskiplist:儲存跳躍表節點資訊

跳躍表的模型如下所示:

跳躍表 (1).png

如上圖所示:

  • 藍色的是zskiplist結構
  • 其他四個綠色的是zskiplistNode結構

zskiplist結構介紹

在前面的圖上我們看到zskiplist包含四個部分:

  • header:指向跳躍表頭結點
  • tail:指向跳躍表的尾結點
  • level:記錄跳躍表中層數最大的節點層數。(注意:頭結點固定高度為32,初始全部指向NULL,且不被levle記錄層高)
  • length:記錄跳躍表長度,即包含幾個節點。(頭結點除外)

使用多個節點就可以作為跳躍表,那麼為什麼還需要zskiplist

實際通過zskiplist的結構就可以得出: * headertail:快速訪問跳躍表的頭或尾節點,且時間複雜度是O(1),否則可能需要遍歷至少大於等於1次。 * length:快速獲取長度(即節點數量),時間複雜度都O(1),否則需要遍歷整個跳躍表。 * level:用來快速獲取最高節點層數,時間複雜度是O(1)

可以幫助我們方便、快速的處理跳躍表。

zskiplistNode結構介紹

在前面的圖我們看到zskiplistNode包含四種部分: * Level:層,即以L開頭的部分。Level包含兩個部分前進指標跨度。表頭向表位遍歷時,會沿著前進指標前進。

* `前進指標`:指向表尾方向的其他節點
* `跨度`:當前節點距離指向節點的距離,即上圖箭頭上的數字。

每當有一個新的節點加入跳躍表,程式根據[冪次法則](https://baike.baidu.com/item/%E5%B9%82%E6%AC%A1%E6%B3%95%E5%88%99/8271554)生成一個介於1和32之間的值作為level的大小,即層的高度。
  • backward:後退指標,即BW。指向當前節點的前一個節點,當從表尾向表頭遍歷時被使用。
  • score:分值,即1.0、2.0、3.0。在跳躍表中會按照分值從小到大排列。
  • object:成員物件,即o1、o2、o3。當分值相同時,按照成員物件進行排序

表頭節點也有backward、score、object,但是不會使用。