【Redis】內部數據結構自頂向下梳理

2020 年 12 月 31 日
筆記
Redis, 資料庫, 數據結構

本部落格將順著自頂向下的思路梳理一下Redis的數據結構體系，從資料庫到對象體系，再到底層數據結構。我將基於我的一個項目的程式碼來進行介紹：daredis。該項目中，使用Java實現了Redis中所有的數據結構，思想與Redis大致類似，各種變數的命名與Redis源碼基本一致，只是將結構體換成了類來實現。

Redis資料庫

Redis伺服器在初始化時，會創建一個db數組，大小默認是16，即創建16個資料庫。如下所示：

public class RedisServer {

    private static int dbNum = 16;
    public static RedisDB[] db;

    public static void init(){
        db = new RedisDB[dbNum];
    }

    public static void initDB(int index){
        db[index] = new RedisDB();
    }
}

實際上，每個客戶端都會擁有一個目標資料庫，默認情況下為db[0]。客戶端執行命令時，目標資料庫會成為其操作對象。

RedisDB類型包含一個字典，程式碼如下：

public class RedisDB {

    //資料庫的鍵空間
    Dict<SDS, RedisObject> dict;

    public RedisDB() {
        this.dict = new Dict<>();
    }
}

資料庫RedisDB實際上包含一個Dict類型，即字典（Redis中尤為關鍵的底層數據結構），是一個鍵值對集合，鍵名是SDS字元串，鍵值是RedisObject。Dict是後面要講的一種底層數據結構，在資料庫體系中也是用到了Dict。

可以這樣理解，Redis的所有對象體系都是掛在一個Dict字典下的。這也體現了Redis非關係型的特點。

Redis對象系統

繼續向下探索，看一看資料庫鍵值RedisObject是什麼。RedisObject表示Redis中的對象。Redis包含五種對象，統稱對象系統

RedisHash哈希對象
RedisList列表對象
RedisSet集合對象
RedisString字元串對象
RedisZSet有序集合對象

RedisObject包含一個類型欄位type和一個編碼欄位encoding，以及一個底層數據結構的引用ptr。如下所示：

public abstract class RedisObject {
    protected int type;
    protected int encoding;
    protected RedisObj ptr;
}

type的值由一個枚舉類型來維護，表示上述五種類型中的某種類型，如下所示

public enum RedisType {
    STRING(0),
    LIST(1),
    HASH(2),
    SET(3),
    ZSET(4);
    private final int val;
    RedisType(int VAL) {
        this.val = VAL;
    }
    public int VAL(){
        return val;
    }
}

encoding同樣由一個枚舉類型來維護，表示ptr指向的數據結構的類型，如下所示

public enum RedisEnc {
    RAW(0),
    INT(1),
    HT(2),
    LINKEDLIST(3),
    ZIPLIST(4),
    INTSET(5),
    SKIPLIST(6),
    EMBSTR(7);
    private final int val;
    RedisEnc(int VAL) {
        this.val = VAL;
    }
    public int VAL(){
        return val;
    }
}

RedisObject中的ptr引用的對象可以是多種類型。例如列表對象可由壓縮列表ziplist或者雙端鏈表linkedlist來編碼。兩種編碼可以轉換，當滿足以下兩個條件時，使用ziplist編碼

列表對象保存的所有字元串元素長度都小於64位元組；
列表對象保存的元素數量小於512個；

兩個條件有一項不滿足，會將壓縮列錶轉化為雙端鏈表。
其它Redis對象的數據結構編碼切換方式也與之類似。

Redis底層數據結構

底層數據結構指的是ptr指向的對象的內部結構，在Redis中，包含6種底層數據結構：

SDS動態字元串
ziplist壓縮列表
list鏈表
dict字典
skiplist跳躍表
intset整數集合

熟悉Redis的同學來說，這些都是耳熟能詳的數據結構，就不一一去介紹源碼了，項目daredis中都有具體實現。
之前寫過一篇介紹跳躍表的部落格，也可以看看：
【Redis】跳躍表原理分析與基本程式碼實現(java)

對象系統與各種底層數據結構映射關係如下：

Tags: Redis 資料庫數據結構