redis底層資料結構深入介紹

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、物件

##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 总结

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

我们现在要插入k2，通过hash 算法计算到k2 的hash 值为2，即我们需要将k2 插入到dictEntry[2]中：

在插入后我们可以看到，dictEntry指向了k2，k2的next 指向了k1，从而完成了一次插入操作（这里选择表头插入是因为哈希表节点中没有记录链表尾节点位置）

4.4 Rehash

随着对哈希表的不断操作，哈希表保存的键值对会逐渐的发生改变，为了让哈希表的负载因子维持在一个合理的范围之内，我们需要对哈希表的大小进行相应的扩展或者压缩，这时候，我们可以通过 rehash（重新散列）操作来完成。

4.4.1 目前的哈希表状态：

我们可以看到，哈希表中的每个节点都已经使用到了，这时候我们需要对哈希表进行拓展。

4.4.2 为哈希表分配空间

哈希表空间分配规则：

如果执行的是拓展操作，那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂

如果执行的是收缩操作，那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂

因此这里我们为ht[1] 分配 空间为8，

4.4.3 数据转移

將ht[0]中的資料轉移到ht[1]中，在轉移的過程中，需要對雜湊表節點的資料重新進行雜湊值計算

資料轉移後的結果：

4.4.4 釋放ht[0]

將ht[0]釋放，然後將ht[1]設為ht[0]，最後為ht[1]分配一個空白哈希表：

4.4.5 漸進式rehash

上面我們說到，在進行拓展或壓縮的時候，可以直接將所有的鍵值對rehash 到ht[1]中，這是因為資料量比較小。在實際開發過程中，這個rehash 的操作並不是一次性、集中式完成的，而是分多次、漸進式地完成。

漸進式rehash 的詳細步驟：

1、為ht[1] 分配空間，讓字典同時持有ht[0]和ht[1]兩個雜湊表

2、在幾點維持一個索引計數器變數rehashidx，並將它的值設為0，表示rehash 開始

3、在rehash 進行期間，每次對字典執行CRUD操作時，程式除了執行指定的操作以外，還會將ht[0]中的資料rehash 到ht[1]表中，並且將rehashidx加一

4、當ht[0]中所有資料轉移到ht[1]中時，將rehashidx 設定成-1，表示rehash 結束

採用漸進式rehash 的好處在於它採取分而治之的方式，避免了集中式rehash 帶來的龐大計算量。

以上是redis底層資料結構深入介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！