Redis的六種底層數據結構(小結)
1、簡單動態字符串（SDS）
Redis 雖然是用 C 語言寫的，但Redis沒有直接使用C語言傳統的字符串表示（以空字符 ‘\0’ 結尾的字符數組），二是自己構建瞭一種名為簡單動態字符串（simple dynamic string，SDS）的抽象類型，並將 SDS 作為 Redis的默認字符串表示。
在Redis裡面，C字符串隻會作為字符串字面量（string literal）用在一些無須對字符串值進行修改的地方，比如打印日志。
SDS 的定義：
struct sdshdr{
//記錄buf數組中已使用字節的數量
//等於 SDS 所保存字符串的長度
int len;
//記錄 buf 數組中未使用字節的數量
int free;
//字節數組，用於保存字符串
char buf[];
}
① free 屬性的值為 0，表示這個SDS沒有分配任何未使用的空間。
② len 屬性的值為 5，表示這個SDS保存瞭一個五字節長的字符串。
③ buf 屬性是一個char 類型的數組，數組前五個字節分別保存瞭 ‘R’、‘e’、
‘d’、‘i’、‘s’ 五個字符，而最後一個字節則保存瞭空字符 ‘\0’ 。
（SDS遵循C字符串以空字符結尾的慣例，保存空字符的 1 字節空間不計算在SDS的 len屬性裡面，並且為空字符分配額外的 1 字節空間，以及添加空字符到字符串末尾等操作，都是由SDS 函數自動完成的，所有這個空字符對於SDS的使用者來說是完全透明的。遵循空字符結尾這一慣例的好處是，SDS可以直接重用C字符串函數庫裡面的函數。）
SDS 與 C 字浮串的區別：
（1）常數復雜度獲取字符串長度
因為 C 字符串並不記錄自身的長度信息， 所以為瞭獲取一個 C 字符串的長度， 程序必須遍歷整個字符串， 對遇到的每個字符進行計數， 直到遇到代表字符串結尾的空字符為止， 這個操作的復雜度為 O(N) 。
和 C 字符串不同， 因為 SDS 在 len 屬性中記錄瞭 SDS 本身的長度， 所以獲取一個 SDS 長度的復雜度僅為 O(1) 。
（2）杜絕緩沖區溢出
我們知道在 C 語言中使用 strcat 函數來進行兩個字符串的拼接，一旦沒有分配足夠長度的內存空間，就會造成緩沖區溢出。而對於 SDS 數據類型，在進行字符修改的時候，會首先根據記錄的 len 屬性檢查內存空間是否滿足需求，如果不滿足，會進行相應的空間擴展，然後在進行修改操作，所以不會出現緩沖區溢出。
（3）減少修改字符串的內存重新分配次數
C語言由於不記錄字符串的長度，所以如果要修改字符串，必須要重新分配內存（先釋放再申請），因為如果沒有重新分配，字符串長度增大時會造成內存緩沖區溢出，字符串長度減小時會造成內存泄露。
而對於SDS，由於len屬性和free屬性的存在，對於修改字符串SDS實現瞭空間預分配和惰性空間釋放兩種策略：
1、空間預分配：對字符串進行空間擴展的時候，擴展的內存比實際需要的多，這樣可以減少連續執行字符串增長操作所需的內存重分配次數。
2、惰性空間釋放：對字符串進行縮短操作時，程序不立即使用內存重新分配來回收縮短後多餘的字節，而是使用 free 屬性將這些字節的數量記錄下來，等待後續使用。（當然SDS也提供瞭相應的API，當我們有需要時，也可以手動釋放這些未使用的空間）。
（4）二進制安全
因為C字符串以空字符作為字符串結束的標識，而對於一些二進制文件（如圖片等），內容可能包括空字符串，因此C字符串無法正確存取；而所有 SDS 的API 都是以處理二進制的方式來處理 buf 裡面的元素，並且 SDS 不是以空字符串來判斷是否結束，而是以 len 屬性表示的長度來判斷字符串是否結束。
（5）兼容部分 C 字符串函數
雖然 SDS 的 API 都是二進制安全的， 但它們一樣遵循 C 字符串以空字符結尾的慣例： 這些 API 總會將 SDS 保存的數據的末尾設置為空字符， 並且總會在為 buf 數組分配空間時多分配一個字節來容納這個空字符， 這是為瞭讓那些保存文本數據的 SDS 可以重用一部分 <string.h> 庫定義的函數。
（6）總
2、鏈表
作為一種常用數據結構，鏈表內置在很多高級的編程語言裡面，因為Redis使用的 C 語言並沒有內置這種數據結構，所以 Redis 構建瞭自己的鏈表結構。
每個鏈表節點使用一個 adlist.h/listNode 結構來表示：
typedef struct listNode {
// 前置節點
struct listNode *prev;
// 後置節點
struct listNode *next;
// 節點的值
void *value;
} listNode;
多個 listNode 可以通過 prev 和 next 指針組成雙端鏈表， 如圖 3-1 所示。
雖然僅僅使用多個 listNode 結構就可以組成鏈表， 但使用 adlist.h/list 來持有鏈表的話， 操作起來會更方便：
typedef struct list {
// 表頭節點
listNode *head;
// 表尾節點
listNode *tail;
// 鏈表所包含的節點數量
unsigned long len;
// 節點值復制函數
void *(*dup)(void *ptr);
// 節點值釋放函數
void (*free)(void *ptr);
// 節點值對比函數
int (*match)(void *ptr, void *key);
} list;
list 結構為鏈表提供瞭表頭指針 head 、表尾指針 tail ， 以及鏈表長度計數器 len ， 而 dup 、 free 和 match 成員則是用於實現多態鏈表所需的類型特定函數：
① dup 函數用於復制鏈表節點所保存的值；
② free 函數用於釋放鏈表節點所保存的值；
③ match 函數則用於對比鏈表節點所保存的值和另一個輸入值是否相等。
圖 3-2 是由一個 list 結構和三個 listNode 結構組成的鏈表：
Redis 的鏈表實現的特性可以總結如下：
① 雙端： 鏈表節點帶有 prev 和 next 指針， 獲取某個節點的前置節點和後置節點的復雜度都是 O(1) 。
② 無環： 表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL ， 對鏈表的訪問以 NULL 為終點。
③ 帶表頭指針和表尾指針： 通過 list 結構的 head 指針和 tail 指針， 程序獲取鏈表的表頭節點和表尾節點的復雜度為 O(1) 。
④ 帶鏈表長度計數器： 程序使用 list 結構的 len 屬性來對 list 持有的鏈表節點進行計數， 程序獲取鏈表中節點數量的復雜度為 O(1) 。
⑤ 多態： 鏈表節點使用 void* 指針來保存節點值， 並且可以通過 list 結構的 dup 、 free 、 match 三個屬性為節點值設置類型特定函數， 所以鏈表可以用於保存各種不同類型的值。
3、字典
字典又稱為符號表或者關聯數組、或映射（map），是一種用於保存鍵值對的抽象數據結構。字典中的每一個鍵 key 都是唯一的，通過 key 可以對值來進行查找或修改。C 語言中沒有內置這種數據結構的實現，所以字典依然是 Redis 自己構建的。
Redis 的字典使用哈希表作為底層實現， 一個哈希表裡面可以有多個哈希表節點， 而每個哈希表節點就保存瞭字典中的一個鍵值對。
哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 結構定義：
typedef struct dictht {
// 哈希表數組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼，用於計算索引值
// 總是等於 size - 1
unsigned long sizemask;
// 該哈希表已有節點的數量
unsigned long used;
} dictht;
圖 4-1 展示瞭一個大小為 4 的空哈希表 （沒有包含任何鍵值對）。
哈希表節點
哈希表節點使用 dictEntry 結構表示， 每個 dictEntry 結構都保存著一個鍵值對：
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個哈希表節點，形成鏈表
struct dictEntry *next;
} dictEntry;
key 用來保存鍵，val 屬性用來保存值，值可以是一個指針，也可以是uint64_t 整數，也可以是 int64_t 整數。
註意這裡還有一個指向下一個哈希表節點的指針，我們知道哈希表最大的問題是存在哈希沖突，如何解決哈希沖突，有開放地址法和鏈地址法。這裡采用的便是鏈地址法，通過 next 這個指針可以將多個哈希值相同的鍵值對連接在一起，用來解決哈希沖突。
（因為 dictEntry 節點組成的鏈表沒有指向鏈表表尾的指針， 所以為瞭速度考慮， 程序總是將新節點添加到鏈表的表頭位置（復雜度為 O(1)）， 排在其他已有節點的前面。）
字典
Redis 中的字典由 dict.h/dict 結構表示：
typedef struct dict {
// 類型特定函數
dictType *type;
// 私有數據
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當 rehash 不在進行時，值為 -1
int rehashidx;
/* rehashing not in progress if rehashidx == -1 */
} dict;
type 屬性和 privdata 屬性是針對不同類型的鍵值對， 為創建多態字典而設置的：
● type 屬性是一個指向 dictType 結構的指針， 每個 dictType 結構保存瞭一簇用於操作特定類型鍵值對的函數， Redis 會為用途不同的字典設置不同的類型特定函數。
● 而 privdata 屬性則保存瞭需要傳給那些類型特定函數的可選參數。
typedef 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, void *key);
// 銷毀值的函數
void (*valDestructor)(void *privdata, void *obj);
} dictType;
ht 屬性是一個包含兩個項的數組， 數組中的每個項都是一個 dictht 哈希表， 一般情況下， 字典隻使用 ht[0] 哈希表， ht[1] 哈希表隻會在對 ht[0] 哈希表進行 rehash 時使用。
除瞭 ht[1] 之外， 另一個和 rehash 有關的屬性就是 rehashidx ： 它記錄瞭 rehash 目前的進度， 如果目前沒有在進行 rehash ， 那麼它的值為 -1 。
圖 4-3 展示瞭一個普通狀態下（沒有進行 rehash）的字典：
① 哈希算法：Redis計算哈希值和索引值方法如下：
# 使用字典設置的哈希函數，計算鍵 key 的哈希值 hash = dict->type->hashFunction(key); # 使用哈希表的 sizemask 屬性和哈希值，計算出索引值 # 根據情況不同， ht[x] 可以是 ht[0] 或者 ht[1] index = hash & dict->ht[x].sizemask;
②解決哈希沖突：這個問題上面我們介紹瞭，方法是鏈地址法。通過字典裡面的 *next 指針指向下一個具有相同索引值的哈希表節點。
③擴容和收縮(rehash)：當哈希表保存的鍵值對太多或者太少時，就要通過 rerehash(重新散列）來對哈希表進行相應的擴展或者收縮。具體步驟：
1、為字典的 ht[1] 哈希表分配空間， 這個哈希表的空間大小取決於要執行的操作， 以及 ht[0] 當前包含的鍵值對數量 （也即是 ht[0].used 屬性的值）
● 如果執行的是擴展操作， 那麼 ht[1] 的大小為第一個大於等於 ht[0].used * 2n； （也就是每次擴展都是根據原哈希表已使用的空間擴大一倍創建另一個哈希表）
● 如果執行的是收縮操作， 每次收縮是根據已使用空間縮小一倍創建一個新的哈希表。
2、將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面： rehash 指的是重新計算鍵的哈希值和索引值， 然後將鍵值對放置到 ht[1] 哈希表的指定位置上。
3、當 ht[0] 包含的所有鍵值對都遷移到瞭 ht[1] 之後 （ht[0] 變為空表）， 釋放 ht[0] ， 將 ht[1] 設置為 ht[0] ， 並在 ht[1] 新創建一個空白哈希表， 為下一次 rehash 做準備。
④觸發擴容與收縮的條件：
1、服務器目前沒有執行 BGSAVE 命令或者 BGREWRITEAOF 命令，並且負載因子大於等於1。
2、服務器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，並且負載因子大於等於5。
ps：負載因子 = 哈希表已保存節點數量 / 哈希表大小。
3、另一方面， 當哈希表的負載因子小於 0.1 時， 程序自動開始對哈希表執行收縮操作。
⑤漸近式 rehash
什麼叫漸進式 rehash？也就是說擴容和收縮操作不是一次性、集中式完成的，而是分多次、漸進式完成的。如果保存在Redis中的鍵值對隻有幾個幾十個，那麼 rehash 操作可以瞬間完成，但是如果鍵值對有幾百萬，幾千萬甚至幾億，那麼要一次性的進行 rehash，勢必會造成Redis一段時間內不能進行別的操作。所以Redis采用漸進式 rehash，這樣在進行漸進式rehash期間，字典的刪除查找更新等操作可能會在兩個哈希表上進行，第一個哈希表沒有找到，就會去第二個哈希表上進行查找。但是進行增加操作，一定是在新的哈希表上進行的。
4、跳躍表
跳躍表（skiplist）是一種有序數據結構，它通過在每個節點中維持多個指向其它節點的指針，從而達到快速訪問節點的目的。
具有如下性質：
1、由很多層結構組成；
2、每一層都是一個有序的鏈表，排列順序為由高層到底層，都至少包含兩個鏈表節點，分別是前面的head節點和後面的nil節點；
3、最底層的鏈表包含瞭所有的元素；
4、如果一個元素出現在某一層的鏈表中，那麼在該層之下的鏈表也全都會出現（上一層的元素是當前層的元素的子集）；
5、鏈表中的每個節點都包含兩個指針，一個指向同一層的下一個鏈表節點，另一個指向下一層的同一個鏈表節點；
和鏈表、字典等數據結構被廣泛地應用在 Redis 內部不同， Redis 隻在兩個地方用到瞭跳躍表， 一個是實現有序集合鍵， 另一個是在集群節點中用作內部數據結構， 除此之外， 跳躍表在 Redis 裡面沒有其他用途。
跳躍表節點（zskiplistNode）
該結構包含以下屬性：
①層（level）：節點中用 L1 、 L2 、 L3 等字樣標記節點的各個層， L1 代表第一層， L2 代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用於訪問位於表尾方向的其他節點，而跨度則記錄瞭前進指針所指向節點和當前節點的距離。在上面的圖片中，連線上帶有數字的箭頭就代表前進指針，而那個數字就是跨度。當程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。
每次創建一個新跳躍表節點的時候， 程序都根據冪次定律 （power law，越大的數出現的概率越小） 隨機生成一個介於 1 和 32 之間的值作為 level 數組的大小， 這個大小就是層的“高度”。（所以說表頭節點的高度就是32）
②後退（backward）指針：節點中用 BW 字樣標記節點的後退指針，它指向位於當前節點的前一個節點。後退指針在程序從表尾向表頭遍歷時使用。
③分值（score）：各個節點中的 1.0 、 2.0 和 3.0 是節點所保存的分值。在跳躍表中，節點按各自所保存的分值從小到大排列。
④成員對象（obj）：各個節點中的 o1 、 o2 和 o3 是節點所保存的成員對象。
註意表頭節點和其他節點的構造是一樣的： 表頭節點也有後退指針、分值和成員對象， 不過表頭節點的這些屬性都不會被用到， 所以圖中省略瞭這些部分， 隻顯示瞭表頭節點的各個層。
跳躍表（zskiplist）
① header ：指向跳躍表的表頭節點。
② tail ：指向跳躍表的表尾節點。
③ level ：記錄目前跳躍表內，層數最大的那個節點的層數（表頭節點的層數不計算在內）。
④ length ：記錄跳躍表的長度，也即是，跳躍表目前包含節點的數量（表頭節點不計算在內）。
5、整數集合
整數集合（intset）是集合鍵的底層實現之一，當一個集合隻包含整數值元素，並且這個集合的元素數量不多時，Redis就會使用集合作為集合鍵的底層實現。
整數集合（intset）是Redis用於保存整數值的集合抽象數據類型，它可以保存類型為int16_t、int32_t 或者int64_t 的整數值，並且保證集合中不會出現重復元素。
每個 intset.h/intset 結構表示一個整數集合：
typedef struct intset {
// 編碼方式
uint32_t encoding;
// 集合包含的元素數量
uint32_t length;
// 保存元素的數組
int8_t contents[];
} intset;
整數集合的每個元素都是 contents 數組的一個數據項，它們按照從小到大的順序排列，並且不包含任何重復項。
length 屬性記錄瞭 contents 數組的大小。
需要註意的是雖然 contents 數組聲明為 int8_t 類型，但是實際上contents 數組並不保存任何 int8_t 類型的值，其真正類型有 encoding 來決定。
① 升級（encoding int16_t -> int32_t -> int64_t）
當我們新增的元素類型比原集合元素類型的長度要大時，需要對整數集合進行升級，才能將新元素放入整數集合中。具體步驟：
1、根據新元素類型，擴展整數集合底層數組的大小，並為新元素分配空間。
2、將底層數組現有的所有元素都轉成與新元素相同類型的元素，並將轉換後的元素放到正確的位置，放置過程中，維持整個元素順序都是有序的。
3、將新元素添加到整數集合中（保證有序）。
升級能極大地節省內存。
② 降級
整數集合不支持降級操作，一旦對數組進行瞭升級，編碼就會一直保持升級後的狀態。
6、壓縮列表
壓縮列表（ziplist）是列表鍵和哈希鍵的底層實現之一。
當一個列表鍵隻包含少量列表項， 並且每個列表項要麼就是小整數值， 要麼就是長度比較短的字符串， 那麼 Redis 就會使用壓縮列表來做列表鍵的底層實現。
因為哈希鍵裡面包含的所有鍵和值都是小整數值或者短字符串。
壓縮列表是 Redis 為瞭節約內存而開發的， 由一系列特殊編碼的連續內存塊組成的順序型（sequential）數據結構。
一個壓縮列表可以包含任意多個節點（entry）， 每個節點可以保存一個字節數組或者一個整數值。
每個壓縮列表節點都由 previous_entry_length 、 encoding 、 content 三個部分組成
① previous_entry_ength：記錄壓縮列表前一個字節的長度。previous_entry_ength 的長度可能是1個字節或者是5個字節。如果上一個節點的長度小於254，則該節點隻需要一個字節就可以表示前一個節點的長度瞭。如果前一個節點的長度大於等於254，則屬性的第一個字節為254，後面用四個字節表示當前節點前一個節點的長度。利用此原理即當前節點位置減去上一個節點的長度即得到上一個節點的起始位置，壓縮列表可以從尾部向頭部遍歷。這麼做很有效地減少瞭內存的浪費。
② encoding：節點的encoding保存的是節點的content的內容類型以及長度，encoding類型一共有兩種，一種字節數組一種是整數，encoding區域長度為1字節、2字節或者5字節長。
③ content：content區域用於保存節點的內容，節點內容類型和長度由encoding決定。
連鎖更新問題
連鎖更新在最壞情況下需要對壓縮列表執行 N 次空間重分配操作， 而每次空間重分配的最壞復雜度為 O(N) ， 所以連鎖更新的最壞復雜度為 O(N^2) 。
要註意的是， 盡管連鎖更新的復雜度較高， 但它真正造成性能問題的幾率是很低的
到此這篇關於Redis的六種底層數據結構(小結)的文章就介紹到這瞭,更多相關Redis 底層數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！