1 字符串

redis并未使用傳統的c語言字符串表示，它自己構建了一種簡單的動態字符串抽象類型。

在redis里，c語言字符串只會作為字符串字面量出現，用在無需修改的地方。

當需要一個可以被修改的字符串時，redis就會使用自己實現的SDS（simple dynamic string）。比如在redis數據庫里，包含字符串的鍵值對底層都是SDS實現的，不止如此，SDS還被用作緩沖區（buffer）：比如AOF模塊中的AOF緩沖區以及客戶端狀態中的輸入緩沖區。

下面來具體看一下sds的實現：

struct sdshdr
{int len;//buf已使用字節數量（保存的字符串長度）int free;//未使用的字節數量char buf[];//用來保存字符串的字節數組
};

sds遵循c中字符串以'\0'結尾的慣例，這一字節的空間不算在len之內。

這樣的好處是，我們可以直接重用c中的一部分函數。比如printf；

? ? sds相對c的改進

? ? 獲取長度：c字符串并不記錄自身長度，所以獲取長度只能遍歷一遍字符串，redis直接讀取len即可。

? ? 緩沖區安全：c字符串容易造成緩沖區溢出，比如：程序員沒有分配足夠的空間就執行拼接操作。而redis會先檢查sds的空間是否滿足所需要求，如果不滿足會自動擴充。

? ? 內存分配：由于c不記錄字符串長度，對于包含了n個字符的字符串，底層總是一個長度n+1的數組，每一次長度變化，總是要對這個數組進行一次內存重新分配的操作。因為內存分配涉及復雜算法并且可能需要執行系統調用，所以它通常是比較耗時的操作。? ?

? ? redis內存分配：

1、空間預分配：如果修改后大小小于1MB，程序分配和len大小一樣的未使用空間，如果修改后大于1MB，程序分配? 1MB的未使用空間。修改長度時檢查，夠的話就直接使用未使用空間，不用再分配。?

2、惰性空間釋放：字符串縮短時不需要釋放空間，用free記錄即可，留作以后使用。

? ? 二進制安全

c字符串除了末尾外，不能包含空字符，否則程序讀到空字符會誤以為是結尾，這就限制了c字符串只能保存文本，二進制文件就不能保存了。

而redis字符串都是二進制安全的，因為有len來記錄長度。

2 鏈表

作為一種常用數據結構，鏈表內置在很多高級語言中，因為c并沒有，所以redis實現了自己的鏈表。

鏈表在redis也有一定的應用，比如列表鍵的底層實現之一就是鏈表。（當列表鍵包含大量元素或者元素都是很長的字符串時）

發布與訂閱、慢查詢、監視器等功能也用到了鏈表。

具體實現：

//redis的節點使用了雙向鏈表結構
typedef struct listNode {// 前置節點struct listNode *prev;// 后置節點struct listNode *next;// 節點的值void *value;
} listNode;

//其實學過數據結構的應該都實現過
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;

總結一下redis鏈表特性：

雙端、無環、帶長度記錄、

多態：使用?void*?指針來保存節點值， 可以通過?dup?、?free?、?match?為節點值設置類型特定函數， 可以保存不同類型的值。

3、字典

其實字典這種數據結構也內置在很多高級語言中，但是c語言沒有，所以redis自己實現了。

應用也比較廣泛，比如redis的數據庫就是字典實現的。不僅如此，當一個哈希鍵包含的鍵值對比較多，或者都是很長的字符串，redis就會用字典作為哈希鍵的底層實現。

來看看具體是實現：

//redis的字典使用哈希表作為底層實現
typedef struct dictht {// 哈希表數組dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩碼，用于計算索引值// 總是等于 size - 1unsigned long sizemask;// 該哈希表已有節點的數量unsigned long used;} dictht;

table?是一個數組， 數組中的每個元素都是一個指向dictEntry?結構的指針， 每個?dictEntry?結構保存著一個鍵值對。

圖為一個大小為4的空哈希表。

我們接著就來看dictEntry的實現：

typedef struct dictEntry {// 鍵void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下個哈希表節點，形成鏈表struct dictEntry *next;
} dictEntry;

（v可以是一個指針， 或者是一個?uint64_t?整數， 又或者是一個?int64_t?整數。）

next就是解決鍵沖突問題的，沖突了就掛后面，這個學過數據結構的應該都知道吧，不說了。

?

下面我們來說字典是怎么實現的了。

typedef struct dict {// 類型特定函數dictType *type;// 私有數據void *privdata;// 哈希表dictht ht[2];// rehash 索引int rehashidx; //* rehashing not in progress if rehashidx == -1 
} dict;

type?和?privdata?是對不同類型的鍵值對， 為創建多態字典而設置的：

type?指向?dictType?， 每個?dictType?保存了用于操作特定類型鍵值對的函數， 可以為用途不同的字典設置不同的類型特定函數。

而?privdata?屬性則保存了需要傳給那些類型特定函數的可選參數。

而dictType就暫時不展示了，不重要而且字有點多。。。還是講有意思的東西吧

? ? rehash（重新散列）

隨著我們不斷的操作，哈希表保存的鍵值可能會增多或者減少，為了讓哈希表的負載因子維持在合理的范圍內，有時需要對哈希表進行合理的擴展或者收縮。?一般情況下， 字典只使用?ht[0]?哈希表，?ht[1]?哈希表只會在對?ht[0]?哈希表進行 rehash 時使用。

redis字典哈希rehash的步驟如下：

1）為ht[1]分配合理空間：如果是擴展操作，大小為第一個大于等于ht[0]*used*2的，2的n次冪。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如果是收縮操作，大小為第一個大于等于ht[0]*used的，2的n次冪。

2）將ht[0]中的數據rehash到ht[1]上。

3）釋放ht[0]，將ht[1]設置為ht[0]，ht[1]創建空表，為下次做準備。

? ? 漸進rehash

數據量特別大時，rehash可能對服務器造成影響。為了避免，服務器不是一次性rehash的，而是分多次。

我們維持一個變量rehashidx，設置為0，代表rehash開始，然后開始rehash，在這期間，每個對字典的操作，程序都會把索引rehashidx上的數據移動到ht[1]。

隨著操作不斷執行，最終我們會完成rehash，設置rehashidx為-1.

需要注意：rehash過程中，每一次增刪改查也是在兩個表進行的。

?