簡介
Redis 的底層資料結構主要以下幾種：
- SDS(Simple Dynamic String, 簡單動態字串)
- ZipList(壓縮串列)
- QuickList(快表)
- Dict(字典)
- IntSet(整數集合)
- ZSkipList(跳躍表)
簡單動態字串
在 Redis 中，并不會直接使用 C 語言自帶的字串結構作為實際的存盤結構，而只是將字串作為字面量使用，大多數情況使用自定義的 SDS 來表示字串，
SDS 主要用于儲存 Redis 的默認字串表示、AOF 模塊中的 AOF 緩沖區、客戶端狀態輸入緩沖區，它的定義如下：
struct sdshdr {
int len; // 記錄 buf 陣列中已使用位元組的數量，等于 SDS 所保存的字串的長度
int alloc; // 記錄 buf 陣列中未使用位元組的數量
char buf[]; // 位元組陣列，用于保存字串
};
優點
相對于 C 語言的字串實作，Redis 實作的 SDS 有以下優點：
- 通過記錄
len屬性，實作常數級時間復雜度獲取字串長度 - 通過檢查
len屬性，避免字串在修改時出現緩沖區溢位的情況 - 通過記錄
len屬性和alloc屬性，對于修改字串實作了空間預分配和惰性空間釋放 - 實際存盤的
buf是一個位元組陣列，可以實作 SDS 安全操作二進制資料 - SDS 仍然以
\0作為字串結尾的標識，這樣可以重用 C 語言字串的部分函式
空間預分配
當 SDS 修改時需要擴展空間大小，程式不僅會為 SDS 擴展修改所需的空間，還會為 SDS 分配額外的未使用空間，這額外空間一般是 len 的大小，最大不超過 1MB，
這樣可以減少連續執行字串增長操作所需的記憶體重分配次數，
惰性空間釋放
當 SDS 修改時需要縮短空間大小，程式并不會立即將多出來的空間進行空間重分配，而是使用 alloc 屬性將這些空間大小記錄下來，以待后續使用，
而且 SDS 也提供手動釋放未使用空間的方法，這樣可以避免浪費記憶體，
壓縮串列
ZipList 實際是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構，是 Hash 型別底層實作的一種方式，
結構
一個 ZipList 結構由 zlbytes、zltail、zllen、entries、zlend 這些屬性組成，這些屬性順序連接在一起組成了 ZipList：
zlbytes 用于記錄 ZipList 占用的記憶體位元組數，在對 ZipList 進行記憶體重分配或者計算 zlend 的位置時使用，
zltail 記錄了 ZipList 表尾結點距離 ZipList 的起始地址有多少個位元組，Redis 可以通過這個屬性快速確定表尾結點的地址，
zllen 記錄了 ZipList 包含的結點數量，當這個屬性小于 UINT16_MAX(65535) 時，這個值就是 ZipList 包含的結點數量；這個屬性大于 UINT16_MAX 時，則需要遍歷整個 ZipList 才能計算得出結點數量，一個 ZipList 可以包含任意多個結點，每個結點可以保存一個位元組陣列或者一個整數值，
zlend 定義了特殊值 OxFF 用于標記 ZipList 的末端，
優點
ZipList 是一種節省記憶體的串列結構，對于普通的陣列來說，其中每個元素占用的空間大小取決于最大的元素，而 ZipList 解決了這個問題，
因此，ZipList 在設計的時候，盡量讓每個元素按照實際的內容大小存盤，所以增加了 encoding 屬性，使得程式可以根據不同的 encoding 屬性來細化存盤大小，
由于陣列每個元素都占用相同的記憶體空間，在遍歷陣列時非常方便，
而 ZipList 每個元素存盤的記憶體空間不一樣，為了解決倒序遍歷的問題，增加了 prevlen 屬性來定位上一個元素的起始位置，
缺點
ZipList 內部的資料存盤是一段連續的空間，并且沒有預留記憶體空間，在移除結點時也是立即縮容，這表示每次寫操作都會進行記憶體分配操作，
第二個缺點就是，在某種情況下，ZipList 會出現連鎖更新的問題，
連鎖更新
ZipList 存盤了 prevlen 屬性表示前一個元素的長度，如果前一個元素長度小于 254 個位元組，則 prevlen 使用 1 個位元組保存這個長度值，如果前一個結點大于 254 個位元組，則 prevlen 使用 5 個位元組保存這個長度值，
如果 ZipList 中正好存在連續多個長度介于 250~253 個位元組的結點，這時需要在 ZipList 前面插入一個大于等于 254 個位元組的新結點，后一個結點的 prevlen 需要從 1 個位元組轉換成 5 個位元組，則后一個結點也會大于等于 254 個位元組，后續的結點以此類推，將會造成這部分結點出現連續更新，
快表
Redis 在 3.2 版本之后新增了快表資料結構，它是一種以 ZipList 為結點的雙端鏈表結構，可以理解成分段的 ZipList 鏈接在一起，
在 3.2 版本之前，Redis 使用 ZipList 或 LinkedList 來實作 List 型別，并且有一個選擇的標準：
- 保存的所有字串元素的長度都小于 64 位元組，且保存的元素數量小于 512 個，選擇使用 ZipList
- 否則使用 LinkedList 資料結構替代 ZipList
ZipList 要求有一段連續的記憶體空間，而使用 LinkedList 分配記憶體又會出現大量的記憶體碎片，因此 QuickList 對此做了優化，既避免出現大量的記憶體碎片，又避免一次性占用記憶體過大，
字典
字典在 Redis 中的應用非常廣泛，比如 Redis 的資料庫就是使用字典來作為底層實作的，對資料庫的增、刪、改、查操作都是構建在對字典的操作之上的，
哈希表結點
字典存盤資料的最小結構就是哈希表結點，Redis 中的哈希表結點使用 dictEntry 結構表示，每個 dictEntry 都保存著一個鍵值對：
typedef struct dictEntry {
void *key; // 鍵值對的鍵
union { // 鍵值對的值
void *val; // 可以是一個指標
uint64_t u64; // 可以是一個 uint64_t 整數
int64_t s64; // 可以是一個 int64_t 整數
} v;
struct dictEntry *next; // 指向下個哈希表節點，形成鏈表
} dictEntry;
這里值得注意的就是，next 指標會指向下一個哈希表結點，而它的功能就是用于解決哈希沖突，由此可見 Redis 的哈希表解決哈希沖突的方法是鏈地址法，
哈希表
哈希表是由多個哈希表結點組成的，Redis 中自定義的哈希表結構如下：
typedef struct dictht {
dictEntry **table; // 哈希表陣列
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表大小掩碼，用于計算索引值，總是等于 size - 1
unsigned long used; // 該哈希表已有節點的數量
} dictht;
一般的，哈希表的物理存盤結構都是陣列，Redis 的哈希表結構也是如此，而這個結點陣列中的每個元素都是一個指向 dictEntry 結構的指標，
字典結構
Redis 為了使哈希表結構更加具有通用性，最后是在自定義的 dictht 哈希表結構外層再包一層字典結構，即是 dict 結構：
typedef struct dict {
dictType *type; // 型別特定函式
void *privdata; // 私有資料
dictht ht[2]; // 哈希表
int rehashidx; // rehash 索引，當 rehash 不在進行時，值為 -1
} dict;
這里展示了另一個 dictType 的結構，其實這個結構保存了一簇用于操作特定型別鍵值對的函式，Redis 會為用途不同的字典設定不同的型別特定函式，以下是 dictType 的結構定義：
typedof struct dictType {
unsigned int (*hashFunction)(const void *key); // 計算哈希值的函式
void *(*keyDup)(void *privData, const void *key); // 復制鍵的函式
void *(*valDup)(void *privData, const void *obj); // 復制值的函式
int (*keyCompare)(void *privData, const void *key1, const void *key2); // 對比鍵的函式
void *(*keyDestructor)(void *privData, const void *key); // 銷毀鍵的函式
void *(*keyDestructor)(void *privData, const void *obj); // 銷毀值的函式
} dictType;
其實 dict 結構的 type 屬性和 privdata 屬性是針對不同型別的鍵值對，為創建多型字典而設定的，其中 privData 屬性保存了需要傳給那些型別特定函式的可選引數，
需要注意一下，字典結構的 ht 屬性是一個長度為 2 的陣列，也就是說，這個字典結構存盤了兩個 dictType 結構，其中一個用于存盤實際使用的哈希表，另一個用于存盤重新哈希的臨時哈希表，
這個重新哈希還涉及到了 rehashidx 屬性，表示的是重新哈希當前的進度，
哈希演算法
當要將一個新的鍵值對添加到字典里面時，程式會先根據鍵值對的鍵計算出哈希值和索引值，然后再根據索引值，將包含新鍵值對的哈希表結點放到哈希表陣列的指定索引上，
Redis 計算哈希值和索引值的流程是：通過 dict 中的 type 屬性找到計算哈希值的函式，然后通過函式計算出對應的哈希值；確定對應的 dictht 結構之后，再根據 sizemask 和哈希值計算出索引值，
Redis 使用 MurmurHash2 演算法計算鍵的哈希值，其優點就是對于有規律的輸入值也能給出很好的隨機分布性，并且演算法的計算速度也非常快，
哈希沖突
相同的哈希值會計算出相同的索引值，這就會導致哈希沖突，
Redis 使用了鏈地址法解決哈希沖突，每一個哈希表結點都有一個 next 指標，多個沖突的哈希表結點就會使用這個 next 指標構成一個單向鏈表，這就解決了鍵沖突的問題，
這里需要注意一點，由于哈希表結點不存盤鏈表的尾結點，為了速度考慮，哈希沖突時構建的單向鏈表使用頭插法插入一個鏈表結點，
重新哈希
隨著操作不斷執行，哈希表保存的資料會逐漸增多或減少，為了讓哈希表的負載因子維持在一個合理的范圍內，Redis 會在必要的時候進行重新哈希的操作，
重新哈希指的是重新計算哈希表結點的哈希值和索引值，然后將鍵值對放到 ht 陣列的另一個哈希表中，
Redis 對哈希表進行擴展操作的兩個條件如下：
- 服務器目前沒有正在執行
BGSAVE命令或BGREWRITEAOF命令，并且哈希表的負載因子大于等于 1， - 服務器目前正在執行
BGSAVE命令或BGREWRITEAOF命令，并且哈希表的負載因子大于等于 5，
其中負載因子 = 哈希表已保存結點數量 / 哈希表大小，
另一方面，當哈希表的負載因子小于 0.1 時，Redis 會自動開始對哈希表進行收縮操作，
Redis 做自動擴展的條件包含兩種情況的原因是，執行
BGSAVE和BGREWRITEAOF命令的是服務器的子行程，而大多數作業系統都采用寫時復制技術以優化子行程的使用效率，所以在子行程存在期間，服務器會提高執行擴展操作所需的負載因子，
漸進式重新哈希
為了避免因為重新哈希導致停止服務的情況，Redis 做重新哈希不是一次性完成的，而是分多次、漸進式地完成的，這也是 dict 結構中存在 ht 陣列的原因，
漸進式重新哈希的好處在于它采取了分而治之的方式，將重新哈希所需的計算作業均攤到對字典的每個添加、洗掉、查找和更新操作上，從而避免集中式重新哈希而帶來的龐大計算量，
整數集合
整數集合被 Redis 用于保存整數值的不重復集合，以下是整數集合的實作：
typedef struct intset {
uint32_t encoding; // 編碼方式
uint32_t length; // 集合包含的元素數量
int8_t contents[]; // 保存元素的陣列
} intset;
其中 contents 陣列中存盤的是整數集合中的元素，各個項按照從小到大進行排列，且陣列中不包含任何重復值，
length 屬性記錄了整數集合包含的元素個數，也相當于 contents 的陣列長度，
encoding 記錄著整數集合的編碼方式，雖然 contents 的定義是 int8_t 型別，但實際上 contents 陣列存盤元素的真正型別取決于 encoding 的值，
升級
整數集合的 contents 屬性可以存盤 int16、int32 或 int64 三種型別之一的數值，如果原本只存盤了 int16 型別的 contents 陣列插入一個 int32 型別的數值，這時就涉及到整數集合的升級操作，
每當要將一個整數插入到整機集合中時，Redis 都會先判斷新元素的型別是否會比已存在的元素型別長，如果存在這種情況，整數集合需要先進行升級，才能將新元素添加到整數集合里面，具體的步驟如下：
- 根據新元素的型別，擴展整數集合底層陣列的空間大小，并為新元素分配空間；
- 將現有元素都轉換成與新元素的型別相同，并將轉換型別后的數值放置到正確的位上，并保持原陣列的順序不變；
- 最后改變
encoding的值，并將length加1，
整數集合的升級操作是不可逆的，一旦對陣列進行了升級，編碼就會一直保持升級后的狀態，
升級的好處
整數集合的升級策略有兩個好處，一個是提升整數集合的靈活性，另一個是盡可能地節約記憶體，
因為 C 語言是靜態型別語言，不同型別的整數值需要用不同的陣列存盤，而整數集合通過升級策略將有原本不同型別的整數添加到同一個陣列中，減少了型別錯誤的情況，
同樣的，整數集合通過使用一個陣列存盤了三種不同型別的整數，又確保升級操作只會在有需要的時候進行，這可以盡量節省記憶體，
跳表
跳表是一種有序的資料結構，它通過在每個結點中維持多個指向其他結點的指標，從而達到快速訪問結點的目的，
Redis 的跳表包括了兩個結構，一個是跳表結點的結構，另一個是存盤跳表結點的外部結構，
跳表結點
以下是跳表結點的結構定義：
typedef struct zskiplistNode {
struct zskiplistLevel { // 索引層
struct zskiplistNode *forward; // 前進指標
unsigned int span; // 跨度
} level[];
robj *obj; // 成員物件
double score; // 分值
struct zskiplistNode *backward; // 后退指標
} zskiplistNode;
這里只是一個跳表結點的結構，概念比較多，
跳表的 zskiplistLevel 是一個陣列，陣列的長度表示結點有多少層索引，其中每個元素都包含一個指向其他結點的指標，程式可以通過這些指標加快訪問其他結點的速度，每次創建一個新的跳表結點的時候，程式都會根據冪次定律隨機生成一個介于 1 和 32 之間的值作為陣列的大小，
forward 是指每個索引層都包含指向下一個具有相同高度索引層的結點，也可以將前進指標理解成鏈表的 next 指標，從相同層級的角度上看，每一個相同層級的結點都組成了類似于鏈表的結構，
span 記錄了兩個結點之間的距離，實際上是用來計算排位的：在查找某個結點的程序中，將沿途訪問過的所有層的跨度累積起來，得到的結果就是目標結點在跳躍表的排位，
backward 用于從表尾向表頭訪問結點，對于最底層的鏈表來說，前進指標和后退指標使得這個鏈表成為一個雙向鏈表，
結點的 score 即是 Redis 的有序集合中的分值，結點的成員是一個指向 SDS 物件的指標，這個 SDS 物件存盤當前結點的值，對于相同分值的成員，Redis 會按照成員物件在字典序中的大小來進行排序，成員物件較小的結點會排在前面，而成員物件較大的結點會排在后面，
跳表
僅使用多個跳表結點就可以實作跳表，但是新增外部跳表結構可以使得程式更方便處理跳表，Redis 的跳表結構如下：
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 頭節點，尾節點
unsigned long length; // 節點數量
int level; // 目前表內節點的最大層數
} zskiplist;
其中 head 指標和 tail 指標分別指向跳表的表頭和表尾，通過這兩個指標，Redis 定位跳表表頭結點和表尾結點的時間復雜度為 \(O(1)\)，
通過記錄 length 屬性，Redis 可以在 \(O(1)\) 的時間復雜度內回傳跳表的長度，
跳表使用 level 屬性記錄了表內結點的最大層數，但這個是不包含表頭結點的層高的，
首發于「程式員翔仔」，點擊查看更多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/549802.html
標籤：其他