【Redis原始碼系列】Redis6.0資料結構詳解--ziplist篇

語言: CN / TW / HK

highlight: tomorrow-night theme: fancy


前言

上篇文章我們研究了Redis SDS資料結構的實現原理, 並深入分析了其針對性的優化手段。本篇我們研究一下另一個數據結構ziplist。

前期回顧: 【Redis原始碼系列】Redis6.0資料結構詳解--SDS篇

資料結構

整體佈局

ziplist沒有結構體定義, 官方文件描述其為: 一種特殊結構的雙向連結串列。其特殊之處在, 沒有使用雙向指標(prev, next)去連線前後的元素, 而是通過計算元素中特定編碼的字長偏移量來訪問不同的元素, 藉助原始碼src/ziplist.c 中的註釋描述:

image.png

我們可以瞭解到典型的壓縮列表佈局為:

image.png

由如下部分組成: - zlbytes: uint32_t型別, 表示整個ziplist所佔用記憶體的位元組數, 在執行記憶體分配時會被使用。 - zltail: uint32_t型別, 即上圖到達zlend節點的偏移量, 通過此偏移量可以快速定位到zlend節點。 - zllen: uint16_t型別, ziplist 中節點的數量。 當這個值小於 UINT16_MAX (65535)時,這個值就是 ziplist 中節點的數量; 當這個值等於 UINT16_MAX 時,節點的數量需要遍歷整個 ziplist 才能計算得出。 - entry: ziplist 所儲存的節點,各個節點的長度根據內容而定。
- zlend: uint8_t型別, 255 的二進位制值 1111 1111 (UINT8_MAX) ,用於標記 ziplist 的末端。

entry組成

entry的邏輯定義如下:

image.png

其並非實際儲存結構, 只是輔助結構, 可以通過一些巨集定義更方便的展開, 簡化為更容易理解的記憶體佈局如下:

image.png

pre_entry_length

pre_entry_length記錄了前一個節點的長度, 可佔用 1 或者 5個位元組, 語句 #define ZIP_BIG_PREVLEN 254 定義當前一個節點的字長小於254時, 使用一個位元組儲存其值, 超過254, 則第一個位元組被設定為254, 剩下位元組儲存其實際長度。可以通過次記錄作指標偏移量計算跳轉到上一個節點,如上圖, 當前指標位置為 curptr,則 preptr = curptr-pre_entry_length,這樣可以快速定位到上一個節點。參見原始碼如下:

image.png

len

len字長有 encoding & len 兩部分組成, 長度可能為 1,2,5個位元組。其中encoding佔用兩個位元組, 其值有如下兩種情況: - 00,01,10: 表示儲存的是字元陣列 - 11: 表示儲存的是整數 其值在不同情況子長下的儲存示例為:

| 位元組長 | 編碼 | content值 | | :---: | :--- | :--- | | 1 byte | 00bbbbbb | 長度小於等於 63 位元組的字元陣列 | | 2 byte | 01bbbbbb xxxxxxxx | 長度小於等於 16383 位元組的字元陣列 | | 5 byte | 10____ aaaaaaaa bbbbbbbb cccccccc dddddddd | 長度小於等於 16383 位元組的字元陣列 | | 1 byte | 11000000 | int16_t 型別的整數 | | 1 byte | 11010000 | int32_t 型別的整數 | | 1 byte | 11100000 | int64_t 型別的整數 | | 1 byte | 11110000 | 24 bit 有符號整數 | | 1 byte | 11111110 | 8 bit 有符號整數 | | 1 byte | 1111xxxx | 4 bit 無符號整數,介於 0 至 12 之間 |

content

通過以上的結構分析我們已經能夠了解entry佈局的基本組成, 關於content的內容我們從一個例項入手來進行了解, 老規矩, 有請萬能的 hello world 登場:

image.png 一個儲存hello world的ziplist節點如圖所示, 其中encoding佔用兩位, 00 標識內容型別為字元陣列, length 佔用6位, 為二進位制的11, 表示 content 位元組長度, encoding & length整體佔用一個位元組。

資料操作

建立ziplist

image.png

建立的方法比較簡單, 可以看到ziplist本質上是一個位元組陣列, 初始化記憶體為: ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE=11個位元組, 巨集定義如下: - ZIPLIST_HEADER_SIZE: (sizeof(uint32_t)*2+sizeof(uint16_t)) 共10個位元組。 - ZIPLIST_END_SIZE: (sizeof(uint8_t)) 一個位元組, 表示尾部節點。 建立完成後結構如下:

image.png

插入元素

__ziplistInsert 方法上游有ziplistInsertziplistPush方法呼叫核心都是執行__ziplistInsert方法,原始碼分析如下:

image.png

查詢元素

基於我們如上的分析, 可以比較清除的理解ziplist的查詢操作, 原始碼解析如下:

image.png

連鎖更新

前面我們分析過entryprevious_entry_length屬性儲存了前一個節點的長度, 為 1 或 5 個位元組長度,當前一個節點長度在 254 以下時,使用一個位元組儲存其長度, 長度在 254 以上時, 使用5個位元組儲存其長度, 事項如下例項: 在ziplist中連續儲存著長度為 250 - 253 長度的節點 e1,e2...eN, 此時每個節點的previous_entry_length屬性長度都為 1, 當我們在頭結點插入一個長度超過254的entry後, 第二個節點e1需要修改自己的屬性previous_entry_length, 增加4個位元組, 依此類推, 直到後面的每一個節點執行類似的操作, 我們將這種情況命名為: 連鎖更新, 在原始碼src/ziplist.c__ziplistCascadeUpdate方法實現了這樣的操作邏輯。原始碼解析如下:

image.png

基於原始碼有如下思考, 在連鎖更新的最壞的情況下需要執行N次空間重新分配操作, 而每次空間分配最壞複雜度為O(N), 所以連鎖更新最壞的複雜度為O(N^2),看起來是一個非常危險的存在, 儘管如此, 實際使用起來要達到最壞情況條件相對比較苛刻, 要滿足所有節點長度介於250-253之間。同時在實際情況中, 更新的節點仍在小範圍內, 不會對效能造成明顯可見的影響。

此類操作可類比到PHP7的zend_hash原始碼實現, PHP7使用連結串列來處理hash衝突, 同時使用開源的time33演算法做hash值計算, 當我們使用惡意資料構造zend_hash的資料結構, 就是得原本連續儲存的bucket陣列轉化為基於bucket的連結串列, 我們很容易實現這樣的入侵: ```php <?php echo "開始新增元素" . PHP_EOL;

$a = ["cooper" => "cooper_key"];

$size = pow(2, 16); $startTime = microtime(true); $array = array(); for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) { $array[$key] = 0; } $endTime = microtime(true); echo '插入 ', $size, ' 個惡意的元素需要 ', $endTime - $startTime, ' 秒', "\n"; $startTime = microtime(true); $array = array(); for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) { $array[$key] = 0; } $endTime = microtime(true); echo '插入 ', $size, ' 個普通元素需要 ', $endTime - $startTime, ' 秒', "\n"; 執行結果如下: 開始新增元素 插入 65536 個惡意的元素需要 8.8367640972137 秒 插入 65536 個普通元素需要 0.0045688152313232 秒 ``` 儘管如此, 我們仍然大規模的使用PHP做web服務的實現, 不過我們需要注意防範此類的攻擊。

總結

本篇我們分析了redis ziplist的原始碼實現, 可以看到ziplist本質記憶體結構是一個位元組陣列, 作者通過相對複雜的指標偏移規則做結構的邏輯模擬, 這樣帶來的好處是極大的提高的了記憶體的使用率, 整體實現幾乎是不浪費任何一個可儲存的位元組, 也體現了作者對於設計一個記憶體型資料庫的極致追求。 關於ziplist個人認為需要重點理解其編碼的實現規則, 以及這些規則背後存在的意義。同時對於基於此規則引起的可能存在的複雜度較高的操作我們也做了詳細的解析, 並且舉一反三類比PHP原始碼的實現做了分解。複雜事物背後很難有100%完美的解法, 使用空間換取時間也是很多優秀作品的共同選擇, 同時能夠將複雜邏輯做嚴謹的設計與實現, 也使得我們可以站在巨人的肩膀上更好的充實自己。