首頁 >資料庫 >Redis >redis底層資料結構深入介紹

redis底層資料結構深入介紹

尚轉載: 2019-11-28 16:23:252479瀏覽

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[];  
};

redis底層資料結構深入介紹

#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 屬性的值，直接知道字串長度。

redis底層資料結構深入介紹

2.3.2 杜絕緩衝區溢位

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

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

redis底層資料結構深入介紹

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

redis底層資料結構深入介紹

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

Redis 中SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：

当我们需要对一个SDS 进行修改的时候，redis 会在执行拼接操作之前，预先检查给定SDS 空间是否足够，如果不够，会先拓展SDS 的空间，然后再执行拼接操作

redis底層資料結構深入介紹

2.3.3 减少修改字符串时带来的内存重分配次数　　　

C语言字符串在进行字符串的扩充和收缩的时候，都会面临着内存空间的重新分配问题。

1. 字符串拼接会产生字符串的内存空间的扩充，在拼接的过程中，原来的字符串的大小很可能小于拼接后的字符串的大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。

2. 字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出来的空间就成为了内存泄露。

举个例子：我们需要对下面的SDS进行拓展，则需要进行空间的拓展，这时候redis 会将SDS的长度修改为13字节，并且将未使用空间同样修改为1字节

redis底層資料結構深入介紹

因为在上一次修改字符串的时候已经拓展了空间，再次进行修改字符串的时候会发现空间足够使用，因此无须进行空间拓展

redis底層資料結構深入介紹

通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次

2.3.4 惰性空间释放

我们在观察SDS 的结构的时候可以看到里面的free 属性，是用于记录空余空间的。我们除了在拓展字符串的时候会使用到free 来进行记录空余空间以外，在对字符串进行收缩的时候，我们也可以使用free 属性来进行记录剩余空间，这样做的好处就是避免下次对字符串进行再次修改的时候，需要对字符串的空间进行拓展。

然而，我们并不是说不能释放SDS 中空余的空间，SDS 提供了相应的API，让我们可以在有需要的时候，自行释放SDS 的空余空间。

通过惰性空间释放，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能有的增长操作提供了优化

2.3.5 二进制安全

C 字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。

但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。

例如：

redis底層資料結構深入介紹

2.3.6 兼容部分C字符串函数

虽然SDS 的API 都是二进制安全的，但他们一样遵循C字符串以空字符串结尾的惯例。

2.3.7 总结

redis底層資料結構深入介紹

3、链表

3.1 概述

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

链表在Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。　

3.2 链表的数据结构

每个链表节点使用一个 listNode结构表示（adlist.h/listNode）：

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

多个链表节点组成的双端链表：

1redis底層資料結構深入介紹

我们可以通过直接操作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 组成的结构图：

1redis底層資料結構深入介紹

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;
}

一个空的字典的结构图如下：

1redis底層資料結構深入介紹

我们可以看到，在结构中存有指向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 采用了链地址法：

1redis底層資料結構深入介紹

当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 属性是一个包含两个项（两个哈希表）的数组

普通状态下的字典：

redis底層資料結構深入介紹