深入淺出Redis-redis底層數據結構（上）

redis是一個key-value存儲系統。和Memcached類似，它支持存儲的value類型相對更多，包括string(字元串)、list(鏈表)、set(集合)、zset(sorted set --有序集合)和hash（哈希類型）。這些數據類型都支持push/pop、add/remove及取交... ...

1、概述

　　　　相信使用過Redis 的各位同學都很清楚，Redis 是一個基於鍵值對（key-value）的分散式存儲系統，與Memcached類似，卻優於Memcached的一個高性能的key-value資料庫。

　　　　在《Redis設計與實現》這樣描述：

　　　　Redis 資料庫裡面的每個鍵值對（key-value） 都是由對象（object）組成的：

　　　　　　資料庫鍵總是一個字元串對象（string object）;

　　　　　　資料庫的值則可以是字元串對象、列表對象（list）、哈希對象（hash）、集合對象（set）、有序集合（sort set）對象這五種對象中的其中一種。

　　　　我們為什麼會說Redis 優於Memcached 呢，因為Redis 的出現，豐富了memcached 中key-value的存儲不足，在部分場合可以對關係資料庫起到很好的補充作用，而且這些數據類型都支持push/pop、add/remove及取交集並集和差集及更豐富的操作，而且這些操作都是原子性的。

　　　　我們今天探討的並不是Redis 中value 的數據類型，而是他們的具體實現——底層數據類型。

　　　　Redis 底層數據結構有一下數據類型：

1. 　簡單動態字元串
2. 鏈表
3. 字典
4. 跳躍表
5. 整數集合
6. 壓縮列表
7. 對象

　　　　我們接下來會一步一步的探討這些數據結構有什麼特點，已經他們是如何構成我們所使用的value 數據類型。

2、簡單動態字元串（simple dynamic string）SDS

2.1 概述

　　　Redis 是一個開源的使用ANSI C語言編寫的key-value 資料庫，我們可能會較為主觀的認為 Redis 中的字元串就是採用了C語言中的傳統字元串表示，但其實不然，Redis 沒有直接使用C語言傳統的字元串表示，而是自己構建了一種名為簡單動態字元串（simple dynamic string SDS）的抽象類型，並將SDS用作Redis 的預設字元串表示：

redis>SET msg "hello world"
OK

　　　設置一個key= msg，value = hello world 的新鍵值對，他們底層是數據結構將會是：

　　　　　鍵（key）是一個字元串對象，對象的底層實現是一個保存著字元串“msg” 的SDS；

　　　　　值（value）也是一個字元串對象，對象的底層實現是一個保存著字元串“hello world” 的SDS

　　　從上述例子，我們可以很直觀的看到我們在平常使用redis 的時候，創建的字元串到底是一個什麼樣子的數據類型。除了用來保存字元串以外，SDS還被用作緩衝區（buffer）AOF模塊中的AOF緩衝區。

2.2 SDS 的定義

　　Redis 中定義動態字元串的結構：

/*  
 * 保存字元串對象的結構  
 */  
struct sdshdr {  
      
    // buf 中已占用空間的長度  
    int len;  
  
    // buf 中剩餘可用空間的長度  
    int free;  
  
    // 數據空間  
    char buf[];  
};

　　　1、len 變數，用於記錄buf 中已經使用的空間長度（這裡指出Redis 的長度為5）

　　　2、free 變數，用於記錄buf 中還空餘的空間（初次分配空間，一般沒有空餘，在對字元串修改的時候，會有剩餘空間出現）

　　 3、buf 字元數組，用於記錄我們的字元串（記錄Redis）

2.3 SDS 與 C 字元串的區別

　　　　傳統的C 字元串使用長度為N+1 的字元串數組來表示長度為N 的字元串，這樣做在獲取字元串長度，字元串擴展等操作的時候效率低下。C 語言使用這種簡單的字元串表示方式，並不能滿足Redis 對字元串在安全性、效率以及功能方面的要求

2.3.1 獲取字元串長度（SDS O（1）/C 字元串 O(n)）

　　　　傳統的C 字元串使用長度為N+1 的字元串數組來表示長度為N 的字元串，所以為了獲取一個長度為C字元串的長度，必須遍歷整個字元串。

　　　　和C 字元串不同，SDS 的數據結構中，有專門用於保存字元串長度的變數，我們可以通過獲取len 屬性的值，直接知道字元串長度。

2.3.2 杜絕緩衝區溢出

　　　　C 字元串 不記錄字元串長度，除了獲取的時候複雜度高以外，還容易導致緩衝區溢出。

　　　　假設程式中有兩個在記憶體中緊鄰著的字元串 s1 和 s2，其中s1 保存了字元串“redis”，二s2 則保存了字元串“MongoDb”：

　　　　如果我們現在將s1 的內容修改為redis cluster，但是又忘了重新為s1 分配足夠的空間，這時候就會出現以下問題：

　　　　我們可以看到，原本s2 中的內容已經被S1的內容給占領了，s2 現在為 cluster，而不是“Mongodb”。

　　　　 Redis 中SDS 的空間分配策略完全杜絕了發生緩衝區溢出的可能性：

　　　　當我們需要對一個SDS 進行修改的時候，redis 會在執行拼接操作之前，預先檢查給定SDS 空間是否足夠，如果不夠，會先拓展SDS 的空間，然後再執行拼接操作

2.3.3 減少修改字元串時帶來的記憶體重分配次數　　　

　　C語言字元串在進行字元串的擴充和收縮的時候，都會面臨著記憶體空間的重新分配問題。

　　　1. 字元串拼接會產生字元串的記憶體空間的擴充，在拼接的過程中，原來的字元串的大小很可能小於拼接後的字元串的大小，那麼這樣的話，就會導致一旦忘記申請分配空間，就會導致記憶體的溢出。

　　　2. 字元串在進行收縮的時候，記憶體空間會相應的收縮，而如果在進行字元串的切割的時候，沒有對記憶體的空間進行一個重新分配，那麼這部分多出來的空間就成為了記憶體泄露。

　　舉個例子：我們需要對下麵的SDS進行拓展，則需要進行空間的拓展，這時候redis 會將SDS的長度修改為13位元組，並且將未使用空間同樣修改為1位元組

　　　因為在上一次修改字元串的時候已經拓展了空間，再次進行修改字元串的時候會發現空間足夠使用，因此無須進行空間拓展

　　通過這種預分配策略，SDS將連續增長N次字元串所需的記憶體重分配次數從必定N次降低為最多N次

2.3.4 惰性空間釋放

　　　　我們在觀察SDS 的結構的時候可以看到裡面的free 屬性，是用於記錄空餘空間的。我們除了在拓展字元串的時候會使用到free 來進行記錄空餘空間以外，在對字元串進行收縮的時候，我們也可以使用free 屬性來進行記錄剩餘空間，這樣做的好處就是避免下次對字元串進行再次修改的時候，需要對字元串的空間進行拓展。

　　　　然而，我們並不是說不能釋放SDS 中空餘的空間，SDS 提供了相應的API，讓我們可以在有需要的時候，自行釋放SDS 的空餘空間。

　　　　通過惰性空間釋放，SDS 避免了縮短字元串時所需的記憶體重分配操作，並未將來可能有的增長操作提供了優化

2.3.5 二進位安全

　　　　C 字元串中的字元必須符合某種編碼，並且除了字元串的末尾之外，字元串裡面不能包含空字元，否則最先被程式讀入的空字元將被誤認為是字元串結尾，這些限制使得C字元串只能保存文本數據，而不能保存想圖片，音頻，視頻，壓縮文件這樣的二進位數據。

　　　　但是在Redis中，不是靠空字元來判斷字元串的結束的，而是通過len這個屬性。那麼，即便是中間出現了空字元對於SDS來說，讀取該字元仍然是可以的。

　　　　例如：

2.3.6 相容部分C字元串函數

　　　　雖然SDS 的API 都是二進位安全的，但他們一樣遵循C字元串以空字元串結尾的慣例。

2.3.7 總結

C 字元串	SDS
獲取字元串長度的複雜度為O（N)	獲取字元串長度的複雜度為O(1)
API 是不安全的，可能會造成緩衝區溢出	API 是安全的，不會造成緩衝區溢出
修改字元串長度N次必然需要執行N次記憶體重分配	修改字元串長度N次最多執行N次記憶體重分配
只能保存文本數據	可以保存二進位數據和文本文數據
可以使用所有<String.h>庫中的函數	可以使用一部分<string.h>庫中的函數

3、鏈表

3.1 概述

　　鏈表提供了高效的節點重排能力，以及順序性的節點訪問方式，並且可以通過增刪節點來靈活地調整鏈表的長度。

　　鏈表在Redis 中的應用非常廣泛，比如列表鍵的底層實現之一就是鏈表。當一個列表鍵包含了數量較多的元素，又或者列表中包含的元素都是比較長的字元串時，Redis 就會使用鏈表作為列表鍵的底層實現。

3.2 鏈表的數據結構

　　　每個鏈表節點使用一個 listNode結構表示（adlist.h/listNode）：

typedef struct listNode{
      struct listNode *prev;
      struct listNode * next;
      void * value;  
}

　　　多個鏈表節點組成的雙端鏈表：

　　　　我們可以通過直接操作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 組成的結構圖：

3.3 鏈表的特性

雙端：鏈表節點帶有prev 和next 指針，獲取某個節點的前置節點和後置節點的時間複雜度都是O（N）
無環：表頭節點的 prev 指針和表尾節點的next 都指向NULL，對立案表的訪問時以NULL為截止
表頭和表尾：因為鏈錶帶有head指針和tail 指針，程式獲取鏈表頭結點和尾節點的時間複雜度為O(1)
長度計數器：鏈表中存有記錄鏈表長度的屬性 len
多態：鏈表節點使用 void* 指針來保存節點值，並且可以通過list 結構的dup 、 free、 match三個屬性為節點值設置類型特定函數。

4、字典

4.1 概述

　　　字典，又稱為符號表（symbol table）、關聯數組（associative array）或映射（map），是一種用於保存鍵值對的抽象數據結構。　

　　　在字典中，一個鍵（key）可以和一個值（value）進行關聯，字典中的每個鍵都是獨一無二的。在C語言中，並沒有這種數據結構，但是Redis 中構建了自己的字典實現。

　　　舉個簡單的例子：

redis > SET msg "hello world"
OK

　　　創建這樣的鍵值對（“msg”，“hello world”）在資料庫中就是以字典的形式存儲

4.2 字典的定義

　　　4.2.1 哈希表

　　　Redis 字典所使用的哈希表由 dict.h/dictht 結構定義：

typedef struct dictht {
   //哈希表數組
   dictEntry **table;
   //哈希表大小
   unsigned long size;

   //哈希表大小掩碼，用於計算索引值
   unsigned long sizemask;
   //該哈希表已有節點的數量
   unsigned long used;
}

　　　一個空的字典的結構圖如下：

　　　我們可以看到，在結構中存有指向dictEntry 數組的指針，而我們用來存儲數據的空間既是dictEntry

4.2.2 哈希表節點（ dictEntry ）

　　　dictEntry 結構定義：

typeof struct dictEntry{
   //鍵
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;

}

　　　在數據結構中，我們清楚key 是唯一的，但是我們存入裡面的key 並不是直接的字元串，而是一個hash 值，通過hash 演算法，將字元串轉換成對應的hash 值，然後在dictEntry 中找到對應的位置。

這時候我們會發現一個問題，如果出現hash 值相同的情況怎麼辦？Redis 採用了鏈地址法：

　　　當k1 和k0 的hash 值相同時，將k1中的next 指向k0 想成一個鏈表。

　　　4.2.3 字典

typedef struct dict {
    // 類型特定函數
    dictType *type;
    // 私有數據
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in trehashidx;

}

　　　　type 屬性和privdata 屬性是針對不同類型的鍵值對，為創建多態字典而設置的。

　　　　ht 屬性是一個包含兩個項（兩個哈希表）的數組

　　　　普通狀態下的字典：

4.3 解決哈希衝突

　　在上述分析哈希節點的時候我們有講到：在插入一條新的數據時，會進行哈希值的計算，如果出現了hash值相同的情況，Redis 中採用了連地址法（separate chaining）來解決鍵衝突。每個哈希表節點都有一個next 指針，多個哈希表節點可以使用next 構成一個單向鏈表，被分配到同一個索引上的多個節點可以使用這個單向鏈表連接起來解決hash值衝突的問題。

　　舉個例子：

　　現在哈希表中有以下的數據：k0 和k1