共讀《redis設計與實現》-數據結構篇

2022 年 4 月 14 日
筆記
中間件, 數據庫

準備將之前攢下的書先看一遍，主要是有個大概的了解，以後用的時候也知道在哪裡找。所以準備開幾篇共讀的帖子，激勵自己多看一些書。

Redis 基於 簡單動態字符串（SDS）、雙端鏈表、字典、壓縮列表、整數集合等基礎的數據結構，創建了一個對象系統，這個對象系統包含：字符串對象（String）、列表對象（List）、集合對象（Set）、有序集合對象（Zset）、哈希對象（Hash） 5種數據對象類型。但是這5種對象類型，其內部的基礎的存儲結構並不是一對一的一種，而是每一種包含了至少兩種數據結構。

我們這篇主要用來說一下其基礎的存儲結構

前提條件

redis 底層是使用C語言編寫的，所以很多函數直接使用的C庫。

一、SDS（簡單動態字符串）

我們知道C語言中字符串是以字符數組char[]進行存儲的，字符串的結束是以 空字符『/0』 來進行標識的，也就是字符串的實際長度比我們看見的字符串都會多1 byte(位元組)。
如果我們想要查看一下字符串的長度，那麼就需要遍歷一下字符數組，時間複雜度為O(n)。

1.1 結構說明：

redis中使用結構體SDS用來存儲字符串類型，同樣的使用字符數組進行存儲也自帶空字符『/0』，從而可以使用C語言中字符串相關的特性/函數。
len：數組已用長度記錄，就是說字符串的真實長度（不算『/0』）
free：數組中剩餘可用長度，也就是數組中還有多少長度使用的。

1.2 內存預分配

我們從SDS結構圖可以知道SDS中字符數組的長度是和字符串長度不一樣的，那麼這個長度是如何分配的？

首先如果是創建/擴展：
1. 小於1M，分配的未使用內存是使用內存的2倍
2. 大於1M，那麼每次擴展未使用內存為 1M
如果是收縮：

並不會立即真正釋放，會留下未使用的內存，可以通過Api來進行釋放，從而避免內存泄漏。

1.3 二進制

由於C語言中字符串以『/0』標識結尾，所以C語言中字符串不能存儲圖片、音視頻的二進制數據，但是redis 中字符串以len來做為結尾的判斷，所以可以使用字符串來存儲二進制的數據。
當然對於文本類型的本身結束就是『/0』結尾的，所以我們可以直接使用C的字符串特性。

1.4 特性(總結)：

自帶空格，從而可以使用C語言字符串相關特性
存儲 使用空間和未使用空間這樣長度可以快速得出（時間複雜度O(1)），不用遍曆數組(時間複雜度O(n))
由2我們可以杜絕 C語言中緩存溢出的問題
節省了避免緩存溢出而帶來內存重分配的系統開銷
空間預分配
1. 擴展：小於1M 預分配未使用空間為使用空間的2倍，大於1M，預分配未使用空間為1M；
2. 收縮：惰性空間釋放
可以存儲圖片和音視頻二進制數據。

關於 C語言緩存溢出：
我們知道數組是一塊內存挨着的存儲空間，C語言中，如果我們直接對字符串增加，會有如下這種情況的發生：

現在給hello 尾部添加「-wi」字符串

“字符串「hello」添加 “-wi” 字符串之後內存快照”

所以C語言中我們為了防止這種情況，每次擴展的時候都會進行 內存重分配，使得空餘的字符數組可以容得下我們新加的字符串。但是 內存重分配會導致系統調用，對於redis這種頻繁增加刪除的數據庫來說，這種肯定要儘可能的減少系統性能的浪費。

二、鏈表

其實就是一個結構體持有雙向鏈表

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;

特性

雙向連表，這樣查找前（或者後）一個節點，複雜度為O(1)
有頭尾指針，查找第一個節點、最後一個節點複雜度為O(1)
帶鏈表長度計數器，返回長度複雜度為O(1)
無環（⚠️）
void* 存儲節點的值,可以使用dup\free\match 等特定函數。

三、字典

C語言本身沒有 字典類型，但是對於key-vale 這種映射的關係在redis是常用的，所以redis 自己構建了一個結構體，本身使用的是 hash 結構

typedef struct dict {
    dictType *type;     //dictType也是一種數據結構，dictType結構中包含了一些函數，這些函數用來計算key的哈希值，進而用這個哈希值計算key在dictEntry型table數組中的下標
    void *privdata;     //私有數據，保存着dictType結構中函數的參數
    dictht ht[2];       //兩張哈希表：一張用來正常存儲節點，一張用來在rehash時臨時存儲節點
    long rehashidx;     //rehash的標記：默認-1，當table數組中已有元素個數增加/減少到一定量時，整個字典結構將進行rehash給每個table元素重新分配位置，rehashidx代表rehash過程的進度，rehashidx==-1代表字典沒有在進行rehash，rehashidx>-1代表該字典結構正在對進行rehash
} dict;

3.1 字典結構體

dictType：也是一種數據結構，dictType結構中包含了一些函數（dup\free等），這些函數用來計算key的哈希值，進而用這個哈希值計算key在dictEntry型table數組中的下標。

說白了，也就是redis 的字典為每種基礎類型都創建了一個dictType，使得可以使用類型特定的函數

privdata：私有數據，存儲dictType構造參數，不同的類型傳不同的參數
ht[]：哈希表，真正存儲數據的地方。其中ht[0]是使用的表，ht[1]是沒有分配內存空間，只有在rehash的時候會分配內存，用到。
rehashidx：在rehash的時候才會使用。

3.1.1 redis 哈希表結構體：

typedef struct dictht { //哈希表
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask; 
    unsigned long used;
} dictht;

說明：

table 是hash 存儲的桶數組地址
size 是桶的大小，也就是數組的容量
sizemask，進行hash 運算的時候會使用到，一般為 size-1;(用於計算每個key在table中的下標位置=hash(key)&sizemask)
記錄哈希表的table中已有的節點數量（節點=dictEntry=鍵值對）。

3.1.2 redis的hash節點結構體

typedef struct dictEntry {
    void *key;//鍵
    union{     //值
        void *val;//值可以是指針
        uint64_tu64;//值可以是無符號整數
        int64_ts64;//值可以是帶符號整數
    } v;
    struct dicEntry *next;//指向下個dictEntry節點：redis的字典結構採用鏈表法解決hash衝突,當table數組某個位置處已有元素時，該位置採用頭插法形成鏈表解決hash衝突
} dictEntry;

3.2 結構圖

3.3 hash 步驟

算出key 的hash 值（通過key 自身的函數）
使用 步驟1得到的哈希值和 sizemask進行運算 index = hash & dict->ht[x].sizemask;得到要存儲的索引位置。

其實和java 的hashmap 運算過程一樣
當然這種肯定會遇到hash 衝突，這時候就是用 鏈地址法解決衝突
也為了插入效率問題（插入的話還需要遍歷在數組後面的鏈表），採用頭插法

3.4 rehash 步驟

所謂的rehash 就是當前hash 結構（主要是 桶數組）已經低於某種效率了，需要進行優化，從而 再次進行hash運算

給ht[1]分配內存，具體的分配規則：
1. 如果是擴展(增加值)導致的rehash，分配的ht[1]內存為：h[0].user*2的2^n(2的n次冪)
2. 如果是收縮導致的rehash，分配的ht[1]內存為：h[0].user的2^n(2的n次冪)
將rehashidx賦值0
將ht[0]的值 重新hash 運算到ht[1]中去，運行一次 rehashidx值 +1
將 ht[0]釋放，將ht[1]改為ht[0]，新建一個ht[1]

3.5 rehash 觸發條件

沒有在執行BGSAVE命令或者BGREWRITEAOF命令，並且哈希表的負載因子 大於或等於1。
目前正在執行BGSAVE命令或者BGREWRITEAOF命令，並且哈希表的負載因子大於或等於5。
當哈希表的負載因子``小於``0.1時，redis會自動開始對哈希表進行縮容操作。

說一下負載因子：節點數/桶大小

3.6 漸進rehash

對於數量小的hash表進行 reash 一次執行就ok ,但是數據量特別大的呢？那種成千上萬幾億的數據，這種如果進行一次性的rehash的話佔用資源是非常大的，此時redis 就要處於不可用的狀態了，這種是絕對不允許的，所以這種是需要分批次來進行rehash,就是漸進rehash。

對於這種有個注意點：
如果在rehash 的時候寫入數據，那麼我們直接寫到ht[1]上，
但是如果是讀、更新、刪除操作則是兩個ht[]都要用

3.7 特性

ht[0] 為一般存儲，ht[1] 為rehash時使用的存儲
rehashidx 開始為 -1 ，開始rehash的時候會變成0
hash 算法是MurMurHash
通過鏈地址法解決衝突
採用頭插法
使用漸進rehash
觸發條件

四、跳躍表

對於一個有序數組，我們想要快速訪問，並且頻繁的更新數據，那麼我們會使用什麼樣的存儲操作呢？對於 有序這兩個字我們快速訪問肯定想到的是二分表，樹形結構，尤其是 二叉平衡樹 最為可靠，但是二叉平衡樹 以及它的簡易替代 紅黑樹在數據庫這種 更新比較頻繁的應用中，維持他們的平衡是很耗費性能的。所以redis 採用了相似的 跳躍表 這種結構。

不同於前面幾種結構，跳躍表只是在存儲大量的有序數組中或者 redis 內部結構中使用到了。
本意是減少複雜度，替代平衡樹，並且因為跳躍表的實現比平衡樹要來得更為簡單，所以有不少程序都使用跳躍表來代替平衡樹。
結構圖：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    //header指向跳躍表的表頭節點，tail指向跳躍表的表尾節點
    unsigned long length;   //記錄跳躍表的長度，也即是，跳躍表目前包含節點的數量(表頭節點不計算在內)
    int level;  //記錄目前跳躍表內，層數最大的那個節點的層數(表頭節點的層數不計算在內)
} zskiplist;

typedef struct zskiplistNode {
    robj *obj;  /*成員對象*/
    double score;   /*分值*/
    struct zskiplistNode *backward; /*後退指針*/
    struct zskiplistLevel { /*層*/
        struct zskiplistNode *forward;  /*前進指針*/
        unsigned int span;  /*跨度*/
    } level[];
} zskiplistNode;

說明：

這裡說一下跳躍表的思想：
我們在有序列表中查找一個數，

對於**數組**那麼我們就可以使用二分法去查找，以此來提高查找效率，但是如果我們要頻繁的插入新數據，那就要不斷的去移動這個數組的數據，這樣來說數據如果特別大性能並沒有得到很大的提升（移動數據數據相比查找來說是更耗時的）

對於**鏈表**來說，我們的插入和刪除就比較方便了，畢竟只有指針之間引用的修改，這不提高效率了么？但是鏈表是不可以用二分法的（中間元素需要遍歷才能找到O(n)，數據可以直接訪問O(1)），我們有沒有辦法去提高鏈表的查找效率呢？
我們可以每隔一個節點在上面建立一個節點，也就是新的鏈表是之前鏈表的一半的數量，查找的時候以新鏈表為起點，遇到比當前節點大（小）比後一節點小（大）的就移動到之前節點去查找，這樣查找的效率可以得到很大的提升，當然，我們可以在新鏈表上在建立一層，查找速度比之前的在提高一些，然後在新建一層……這樣最終就是一個建立索引的過程。

對於 二分規則（每隔一個節點建立上一層索引）是否要完美``執行？
當最後我們建立好之後是不是發現，每隔一個建立這種索引的過程是不是和平衡二叉樹有點像啊？而且有個最重要的是，當我們插入新數據的時候，為了維持每隔一個建立上一層索引的概念，我們不得不更新索引。。這樣當索引數量大的時候不又產生效率問題么，似乎也沒辦法解決了？？
既然有這種問題，我們就沒必要嚴格執行二分不就行了么。關注一下我們的目的只在於讓查找的效率提升，那麼我們按照這種方法提升查找效率，既然不能達到百分百完美，那我們就盡量的靠近實現二分就行。
用數學統計學中的概率問題去解決，也就是實現平均的二分其實查找效率就能夠得到提升，所以並不是嚴格執行每隔一個進行一次建立索引。

特性：

同樣的，跳躍表也是redis 建立了一個結構體來持有節點對象，這樣我們使用的時候可以使用 length來獲取長度，level 獲取最大層數、以及頭節點、尾節點，這些獲取的時候複雜度都是O(1)
然後每個 listnode 節點都有多個``前進指針和一個``後退指針
前進指針 指向比節點大（或者小）的下個節點；（也就是指向尾部元素的方向）
後退指針 指向當前節點的上一層級（只有一個，並且指向上一層級，不能跨級）
我們訪問或者查找元素時通過前進指針就可以查找到。
隨機層數：對於每一個新插入的節點，都需要調用一個隨機算法給它分配一個合理的層數，Redis 跳躍表默認允許最大的層數是 32

五、整數集合

5.1 結構體

//每個intset結構表示一個整數集合
typedef struct intset{
    //編碼方式
    uint32_t encoding;
    //集合中包含的元素數量
    uint32_t length;
    //保存元素的數組
    int8_t contents[];
} intset;

整數集合也是一樣的持有一個整數數組的結構體，結構體中存儲數組長度、數組類型

contents[]：是整數集合的底層實現，整數集合的每個元素都是 contents數組的個數組項(item),各個項在數組中按值的大小從小到大有序地排列,並且數組中不包含任何重複項。
length：屬性記錄了數組的長度。
encoding：intset結構體將contents屬性聲明為int8_t類型的數組,但實際上 contents數組並不保存任何int8t類型的值, contents數組的真正類型取決於encoding屬性的值。encoding屬性的值為INTSET_ENC_INT16則數組就是uint16_t類型，數組中的每一個元素都是int16_t類型的整數值(-32768——32767)，encoding屬性的值為INTSET_ENC_INT32則數組就是uint32_t類型，數組中的每一個元素都是int16_t類型的整數值(-2147483648——2147483647)。

5.2 升級

C語言中，內存是需要我們自己行進管理的。其實我們可以知道我們儲存的時候並不是一次性存儲的，可能之前儲存的是 int8 類型的，後來數據發生變化，我們儲存int16甚至int32\int64類型的，為了防止這種情況發生，我們一般一開始就進行 int64的定義存儲，這樣我們就不用擔心後面使用的時候發生內存溢出問題。但是有個問題是：我們這樣做的話，假如前面的都是int8的，後面int64 最後很晚才入庫或者直接不入庫了，這樣我們用int64存儲的int8數據，這不是內存浪費么？所以，redis 為了這種情況，對沒有超過當前存儲的情況使用當前結構進行存儲，也就是開始就是 int8，等到進來一個數發現存儲不夠，需要int16\int32 那麼我在升級整個集合的類型。從而避免了資源的浪費。
升級首先要做的就是空間重分配。
只有升級操作，沒有``降級操作。

5.3 優點

靈活性：就是我的存儲可以更加的靈活，不必擔心類型轉換的問題。
節約內存：不必一開始就建立大容量的數據。

六、壓縮列表

它是我們常用的 zset ，list 和 hash 結構的底層實現之一

和其他類型一樣，壓縮列表也是由一個結構體來持有存儲的數據數據，然後存儲了數組中節點的數量，節點的偏移量，節點的存儲大小。
其中，entry[] 存儲的是有序的數組序列。

entry[]

我們重點看一下entry[]的結構體

為什麼小數據量使用

我們知道，對於內存的讀取來說順序讀取是比隨機讀取效率要高很多的所以對於讀取的操作，我們常常會將其設置為數組，提高其讀取效率。但是如果是更新來說，大數據量的數組往往是效率不可靠的。所以，我們也就明白為什麼對於壓縮列表來說，只有小數據量的才會使用。

encoding

——解決空間浪費問題
對於數據存儲也有一個問題：就是我們在整數集合中說的，如果前面的數據是int8 的後面的是int64的，這樣我們的存儲空間就要設置成64的，前面不就浪費了很多內存么，如何解決這個問題？
我們可以存儲成不同結構類型的啊，比如entry 結構體，我的content 就是不同數據類型的，這樣存儲的時候小的存儲成int8 大的存儲成int64,但是這樣會有個問題：我們在遍歷它的時候由於不知道每個元素的大小是多少，因此也就無法計算出下一個節點的具體位置，如果前面讀取的是in8 後面讀取的int64 我怎麼分開呢？
這個時候我們可以給每個節點增加一個encoding的屬性，我們就可以知道這個**content**中記錄數據的格式，也就是內存的大小了。

一位元組、兩位元組或者五位元組長，值的最高位為 00 、 01 或者 10 的是位元組數組編碼：這種編碼表示節點的 content 屬性保存着位元組數組，數組的長度由編碼除去最高兩位之後的其他位記錄；
一位元組長，值的最高位以 11 開頭的是整數編碼：這種編碼表示節點的 content 屬性保存着整數值，整數值的類型和長度由編碼除去最高兩位之後的其他位記錄；

如此。我們在遍歷節點的之後就知道每個節點的長度(佔用內存的大小)，就可以很容易計算出下一個節點再內存中的位置。這種結構就像一個簡單的壓縮列表了。

previous_entry_length

我們知道如何順序讀取了，但是如果我想後退讀取數據呢？我們不知道前面數據的類型大小，怎麼取截取內存讀取呢？
和encoding 一樣，我們記錄一下上一個entry的大小，然後用當前內存地址-**previous_entry_length** 如此就能計算出上一個內存地址，然後按照相應規則讀取了。

這個屬性記錄了壓縮列表前一個節點的長度，該屬性根據前一個節點的大小不同可以是1個位元組或者5個位元組。
如果前一個節點的長度小於254個位元組，那麼previous_entry_length的大小為1個位元組，即前一個節點的長度可以使用1個位元組表示
如果前一個節點的長度大於等於254個位元組，那麼previous_entry_length的大小為5個位元組，第一個位元組會被設置為0xFE(十進制的254），之後的四個位元組則用於保存前一個節點的長度。

連鎖更新

由上述我們知道，下一個節點存儲上一個節點的大小，如果我們添加節點或者刪除節點的時候，節點的大小發生了變化：

考慮下這種情況：
比如多個連續節點長度都是小於254 位元組的，都處於 250 和253 位元組之間，現在我們在前面插入一個大於254 位元組長度的節點，那麼後一節點之前的 1位元組顯然不能滿足，只能更改為 5 位元組來盡心存儲大於254 位元組的長度，我們在看後面，麻煩的事情來了：我們將previous_entry_length 改成5位元組的長度，那麼我們當前節點就超過了254節點，顯然下一節點的previous_entry_length也不滿足了，然後我們就又要改，這樣一系列的問題就出現了。這樣的問題稱為連鎖更新。
儘管連鎖更新的複雜度較高，但是它真正造成性能問題的幾率是很低的：

要很多連續的，長度介於 250和253 之間的節點
即使出現連鎖更新，但是如果只是小範圍，節點數量不多，就不會造成性能影響。

所以在實際中我們可以放心的使用這個函數。

對象系統

到這裡我們已經將redis 的存儲結構講完了，但是對象系統和存儲結構之間具體的關係，或者說聯繫是什麼呢？
首先我們明白，在對象系統中，redis 有五大對象：STRING、LIST、SET、ZSET、HASH
然後每個對象的底層存儲是我們上面說的哪幾種類型，
說白了就是說的 java中的基本類型 和對象之間的關係。

從上面我們知道每種對象都至少有兩種基本類型，那麼他們之間的劃分或者說界限是什麼呢？

1. 界限

2. 各種對象API

STRING API

LIST API

SET API

ZSET API

HASH API

3. 公共Api

4. 類型檢查

我們知道對於redis 來說，每個對象都使用了至少兩種基本類型，但是C 語言中，如果類型不一樣，常常會出現類型錯誤的問題。我們怎麼解決呢？
這裡我們看一下對象的儲存結構：

struct redisObject {

    unsigned type:4; // 類型

    unsigned encoding:4; // 編碼 

    void *ptr; //執行底層實現數據結構的指針

    int refcount; //引用計數，用於內存回收

    unsigned lru:22; // 記錄最近一次訪問這個對象的時間

}

通過這個我們可以看到，其實redis 對象存儲了使用的基本結構，這樣我們使用api的時候，都會進行一個類型檢查然後再去進行使用，對於非本類型的 api 返回錯誤信息。

其實每個對象內部基本類型的轉換也是需要注意一下的，就是邊界。

5. 多態性

我們可以從公共api 中可以看到 redis 對象的多態性，就是不同的類型執行的方法結果是一樣的，只不過對於不同的類型都有自己特殊的處理
其實這裡的多態性在我們同一個類型中不同基礎結構的 API 中也是有體現的。

6. 內存回收/引用計數器

C語言中，內存是交給我們自己來進行管理的，所以當我們不使用這塊內存的時候就要就行內存釋放。我們怎麼知道內存是否還在使用呢？從之前我們對象結構中可以看到，redis 維護了一個引用計數器，這樣我們每次引用的時候都會使得 refcount+1。其實引用計數器在很多語言中都有使用java中也使用過，這裏面有個比較難受的點：如果兩個對象之間相互引用，但是兩個都是沒有用的，這種永遠不會是0，也就就釋放不了拉。在redis 中還維護了一個lru就是說設置一個時間，超過這個時間的，那麼就強制釋放它，這樣就避免了相互引用導致的內存釋放問題。

7. 對象共享

redis 大量用到了sds 這種結構，而且可以在其他基本結構中嵌套使用。例如鏈表的節點的值可以使用 sds 。我們如果有很多一樣的數據，如果在內存中分配一個空間，少量的還行如果數量多了豈不會「浪費」？
所以redis 採用了對象共享，也就是這個類型的數據如果在內存中已經有了，那麼我們再次創建的時候不會開闢新的空間，直接使用對象的引用，此時引用計數器+1，那麼數據量大的時候就會節省很多內存。
redis 服務器啟動的時候會創建一萬個字符串對象，這些對象包含0-9999字符串對象，以後使用的時候不在創建新的而是使用這個對象。

參考資料

《Redis設計與實現》-黃健宏
部分圖片來與百度搜索

Tags: 中間件數據庫