Chanler

Redis 底層 C 語言

數據結構#

動態字符串 SDS#

Redis 並沒有使用 C 語言的 String，因為它實際上是字符數組

例子:
char* s="hello" 為 {'h', 'e', 'l', 'l', 'o', '\0'}

所以 Redis 構建了一種新的字符串結構，稱為簡單動態字符串 Simple Dynamic String，簡稱 SDS

這裡讀取不根據 '\0' 只是為了符合 C 語言，實際用的是 len

小於 1M 時快速增加分配內存，之後 1M 為間隔申請，注申請內存消耗十分大

二進制安全是指根據 len 讀取，不會因為中間出現 '\0' 而突然停止

IntSet#

IntSet 是 Redis 中 set 集合的一種實現方式，基於整數數組實現，長度可變、有序等特徵

encoding 決定每個元素佔據的大小，此處 16 位 即 2 字節，length 決定數組內存儲元素個數

假如是 16 的編碼方式，卻加入了一個超過編碼方式的元素，則倒序拷貝元素到正確位置（倒序是為了不覆蓋），然後添加新元素，最後修改 Hearder 中的 encoding、length

IntSet 可以看做是特殊的整數數組，具備一些特點：

1. Redis 會確保 IntSet 中的元素唯一、有序
2. 具備類型升級機制，可以節省內存空間
3. 底層採用二分查找方式來查詢

Dict#

Dict 鍵值關係對，哈希表的大小總是為 $2^n$，used 有可能超過 size，此時一定會有個桶退化成鏈表

union 指其中任意一個

sizemask = size - 1，二進制為 n 個 1

實際組成

擴容

Dict 中的 HashTable 是數組結合鏈表，所以考慮數據過多解決數據衝突，擴大到上取 $2^n$

收縮

每次刪除時也會檢查 loadFactor < 0.1 就會收縮到 used 上取 $2^n$ 最小為 4

重建

不管是擴容還是收縮都會涉及到重建，改變 size、sizemask，所以要 rehash，這就是為什麼 dict 要有 ht [2]，一份用，一份空

擴容重建示例

當數據量十分大時，無法一次性重建完成，所以實際是漸進式 hash，慢慢遷移，以前的數據可能在 ht [0]/ht [1]，所以新增放在 ht [1]，ht [0] 只減不增

ZipList#

ZipList 是一種特殊的 “双端鏈表”，由一系列特殊編碼的連續內存塊組成。可以在任意一端進行壓入 / 彈出操作，時間複雜度為 O (1)

大小

可以通過前一個 entry 占用長度得到上個 entry 起始地址進行逆序遍歷，可以通過計算結構中長度得到下個 entry 起始地址進行正序遍歷

注意 Redis 這裡用小端字節序
字符串類型

整數類型 0-12 可以省去 content 直接在 encoding 的後 4 bit 中保存數值

ZipList 的連鎖更新問題#

主要問題在於：記錄前一個 entry 長度的 prevlen 字段會在長度大於等於 254 字節時由 1 字節變為 5 字節，導致下個 entry 的 prevlen 可能發生連鎖更新

在 ZipList 中插入或修改一個 entry1，使之大於等於 254 字節，此時這個 entry1 後面的 entry2 中 prevlen 字段就需要從 1 字節變為 5 字節去記錄 entry1 的新長度

這個改變導致 entry2 後面的 entry3 也需要修改 prevlen3 字段去記錄 entry2 變化後的新長度，一旦極端些，每個 entry 在 prevlen 字段由 1 字節變為 5 字節時都大於等於 254 字節，那會有一系列連鎖更新，導致插入 O (1) 退化成 O (n)

為什麼是大於等於 254 而不是 255 字節時 prevlen 采用 5 字節？
prevlen 有 8 位，可以表示 0~255，但是 255 即 0xff 被 zlend 特殊標記占據，標記壓縮列表 ZipList 末端，而 prevlen 恰好又是一個 entry 的起始，用 255 分界會與 zlend 結束符衝突

ZipList 特性

1. 壓縮列表的可以看做一種連續內存空間的 “双向鏈表 "
2. 列表的節點之間不是通過指針連接，而是記錄上一節點和本節點長度來尋址，內存占用較低
3. 如果列表數據過多，導致鏈表過長，可能影響查詢性能
4. 增或刪較大數據時有可能發生連續更新問題

QuickList#

ZipList 問題：

1. 保存前後鏈表指針需要足足 16 字節，ZipList 節省了非常多內存，但卻要求使用連續內存空間，申請內存效率比較低；限制 ZipList 長度以及 entry 大小
2. 要存儲大量數據，超過了 ZipList 最佳存儲上限；創建多個 ZipList 分片存儲
3. 數據拆分後過於分散，不便管理查找；引入 QuickList 雙端鏈表，節點記錄 ZipList

配置項 list-max-ziplist-szie=-2 默認一個 ZipList 內存占用不超過 8kb

配置項是否壓縮節點，即首尾各不壓縮節點個數，解釋為經常使用首尾節點，中間節點不怎麼用的到

這裡即首尾各 1 個節點不壓縮，所以中間的兩個 ZipList 被重編碼

QuickList 特性：

1. 是一個節點為 ZipList 的雙端鏈表；內存碎片多，連續占用少
2. 節點採用 ZipList，解決了傳統鏈表的內存占用問題；ZipList 節省內存
3. 控制了 ZipList 大小，解決連續內存空間申請效率問題；分片 ZipList，不必要連續大內存
4. 中間節點可以壓縮，進一步節省了內存；

SkipList#

跳表 SkipList 首先是鏈表
1. 元素按升序排列
2. 節點可能包含多個指針，指針跨度不同；這樣起碼比一個一個遍歷快，最高允許 32 個

向後指針 backward，向前指針採用 level [] 數組，最起碼有一個跨度指針，可以快速向前跨然後一步一步往後摸索到正確的節點

在查找時從高層級往下檢索，類似於二分，空間換時間，提前存儲了某跨度後的節點

SkipList 特性：

1. 跳表 SkipList 是一個雙向鏈表，每個節點都包含 score 和 element
2. 節點按照 score 值排序，score 值一樣則按照 element 字典排序
3. 每個節點都可以包含多層指針，層數是 1 到 32 之間的隨機數
4. 不同層指針到下個節點的跨度不同，層級越高，跨度越大
5. 增刪改查效率與紅黑樹基本一致，實現卻更簡單

RedisObject#

Redis 中的任意數據類型的鍵和值都會被封裝為 RedisObject，也叫做 Redis 對象

type、encoding、lru 共 32 bit，4 字節；refcount 4 字節；*ptr 8 字節，RedisObject 頭部占 16 字節

如 String 類型，一個 key-value 就消耗一個 RedisObject 頭，確實蠻占空間

編碼方式 encoding

五種數據類型#

那 BitMap、HyperLogLog 呢？
這些衍生出來的數據結構實際上基於 String 這個數據結構實現，並不是新類型
還有 GEO 基於 SortedSet

String#

String 是 Redis 最常見的數據存儲類型

String RAW 編碼#

String 基本編碼方式是 RAW，基於簡單動態字符串 SDS 實現，存儲上限為 512mb

String EmbStr 編碼#

如果存儲的 SDS 長度小於等於 44 字節，則會採用 EMBSTR 編碼，此時 RedisObject Head 與 SDS 是一段連續空間；申請內存時只需要調用一次內存分配函數，效率更高；與 Redis 申請內存算法有關，總之就是如果 SDS 長度為 44 字節，Head + SDS 剛好 64 字節，不會產生內存碎片

String INT 編碼#

如果存儲的字符串是整數值，並且大小在 LONG_MAX 範圍內，則會採用 INT 編碼，直接將數據保存在 RedisObject 的 ptr 指針位置，剛好 8 字節，不再需要 SDS

String raw、embstr、int 編碼#

List#

List 數據類型可以操作首尾兩端的元素，底層使用 LinkedList + ZipList 結合起來的 QuickList 數據結構

List 結構

Set#

Set 數據類型是單列集合，不保證有序，保證元素唯一，可求交、並、差；對查也就是 SISMEMBER 非常頻繁，所以選用 HashTable

採用 HT 編碼 Dict，用 key 存元素，value 統一為 null
當存儲全是整數，且元素數量不超過 set-max-intset-entries 時，Set 採用 IntSet 編碼，節省內存

如果使用 IntSet 超過最大數或加入非整數，則轉換成 HT 編碼 Dict

IntSet 編碼的 Set

HashTable 編碼的 Set

ZSET#

ZSet 也就是 SortedSet，每一個元素都有一個 score 值和 member 值，可以根據 score 值排序，member 唯一性，可以查詢 member 分數；member 和 score 類鍵值對關係，即 ZSet 要求鍵值存儲、鍵唯一、可排序，所以可選 SkipList、HashTable

SkipList 根據 score 排序，滿足鍵值存儲和可排序，但是當根據 member 查 score 就退化成鏈表，並且 member 唯一也不方便

HashTable 設置 key-value 為 member-score 即可，但是無法滿足根據 score 排序的功能

所以兩個數據結構都使用，Dict 保證 member 唯一，ZSet 保證可排序、範圍查詢

ZSet 使用 Dict 和 SkipList 結合，編碼設置為 SKIPLIST

但是當元素不多時選用 Dict + ZipList 結合非常占用內存而且又是不怎麼明顯，因此在滿足以下條件時 ZSet 會選用 ZipList 結構節省內存

1. 元素數量小於 zset_max_ziplist_entries，默認值 128
2. 每個元素都小於 zset_max_ziplist_value 字節，默認值 64

在初始化創建時，如果初始值兩個條件都同時滿足，那麼就使用 ZipList

在添加元素時如果是 ZipList 則會判斷要不要轉換成 SkipList + HashTable 結構

但是 ZipList 不滿足 ZSet 的三個要求，為什麼在小數據、小數量下可以用 ZipList ？
可以用業務邏輯模擬支持排序、鍵值對排序，並且連續內存空間，element/member 在前 value/score 在後

Hash#

Hash 結構與 ZSet 結構類似，要求鍵值存儲，鍵唯一，可以根據鍵獲取值；必然是 hashTable 啊

和 ZSet 區別

1. ZSet 的鍵是 member，值是 score；hash 的鍵和值都是任意值
2. ZSet 要根據 score 排序；Hash 則無需排序

Hash 結構默認採用 ZipList 編碼，用以節省內存，ZipList 中相鄰的兩個 entry 分別保存 field 和 value
當數據量較大時，Hash 結構會轉為 HT 編碼即 Dict，觸發條件有兩個

1. zipList 中的元素數量超過了 hash-max-ziplist-entries 默認 512
2. ZipList 中的任意 entry 大小超過了 hash-max-ziplist-value 默認 64 字節

打破了任意一個條件就轉換成 HT 編碼

Hash 源碼，可以看到初始化時默認初始化成 ZipList

然後在嘗試添加時判斷要不要轉換 HT 編碼，根據元素大小進行判斷

最後進行添加，添加時會判斷有沒有等，如果是 ZipList 再插入後檢查長度，超過就轉換成 HT 編碼

此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://blog.0xling.cyou/posts/redis/redis-3