《redis設(shè)計與實現(xiàn)》——數(shù)據(jù)結(jié)構(gòu)

一爽醋、SDS

Redis自己構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string, SDS）的抽象類型，將SDS用作Redis的默認(rèn)字符串表示雷逆。而沒有直接使用C語言傳統(tǒng)的字符串表示富拗。

每個sds.h/shshdr結(jié)構(gòu)表示一個SDS值：

struct sdshdr{
    // 記錄buf數(shù)組中已使用字節(jié)的數(shù)量
    // 等于SDS所保存字符串的長度
    int len;
    
    // 記錄buf數(shù)組中未使用字節(jié)的數(shù)量
    int free;
    
    // 字節(jié)數(shù)組
    char buf[]; 
};

要點：

Redis 只會使用C字符串作為字面量喇肋，在大多數(shù)情況下，Redis使用SDS作為字符串表示档桃。
比起C字符串枪孩，SDS具有以下優(yōu)點：
- 常數(shù)復(fù)雜度獲取字符串長度。
- 杜絕緩沖區(qū)溢出藻肄。
- 減少修改字符串長度時所需的內(nèi)存重分配次數(shù)蔑舞。
- 二進制安全：不以空字符作為字符串結(jié)尾。
- 兼容部分C字符串函數(shù)嘹屯。

二攻询、鏈表

鏈表節(jié)點：adlist.h/listNode

typedef struct listNode {
    // 前置節(jié)點
    struct listNode *prev;
    
    // 后置節(jié)點
    struct listNode *next;
    
    // 節(jié)點的值
    void *value;
} listNode;

鏈表：adlist.h/list

typedef struct list {
    // 表頭節(jié)點
    listNode *head;
    
    // 表尾節(jié)點
    listNode tail;
    
    // 鏈表所包含的節(jié)點數(shù)量
    unsigned long len;
    
    // 節(jié)點值復(fù)制函數(shù)
    void *(*dup)(void *ptr);
    
    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);
    
    // 節(jié)點值對比函數(shù)
    int (*match)(void *ptr, void *key)
} list;

要點：

鏈表被廣泛用于實現(xiàn)Redis的各種功能，比如列表鍵州弟、發(fā)布與訂閱钧栖、慢查詢低零、監(jiān)視器等。
每一個鏈表節(jié)點有一個listNode結(jié)構(gòu)表示拯杠，每一個節(jié)點都有一個指向前置節(jié)點和后直接點的指針掏婶，所以Redis的鏈表實現(xiàn)時雙端鏈表。
每一個鏈表使用一個list結(jié)構(gòu)來表示潭陪，這個結(jié)構(gòu)帶有表頭節(jié)點指針雄妥、表尾節(jié)點指針，以及鏈表長度等信息依溯。
因為鏈表表頭節(jié)點和前置節(jié)點和表尾節(jié)點的后置節(jié)點都指向NULL茎芭，所以Redis的鏈表實現(xiàn)是無環(huán)鏈表。
通過為鏈表設(shè)置不同的類型特定函數(shù)誓沸，Redis的鏈表可以用于保存各種不同類型的值梅桩。

三、字典

哈希表：dict.h/dictht

typedef struct dictht {
    // 哈希表數(shù)組
    dictEntry **table;
    
    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩碼拜隧，用于計算索引值
    // 總是等于size - 1
    unsigned long sizemask;
    
    // 該哈希表已有節(jié)點的數(shù)量
    unsigned long used;
} dictht;

哈希表節(jié)點：

typedef struct dictEntry {
    // 鍵
    void *key;
    
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t 64;
    } v;
    
    // 指向下個哈希表節(jié)點宿百，形成鏈表, 以此解決沖突
    struct dictEntry *next;
    
} dictEntry;

字典：dict.h/dict

typedef struct dict {
    // 類型特定函數(shù)
    dictType *type;
    
    // 私有數(shù)據(jù)
    void *privdata;
    
    // 哈希表
    dictht ht[2];
    
    // rehash索引
    // 當(dāng)rehash不在進行時，值為-1
    int trehashidx;  // rehashing not in progress if rehashidx == -1
}

dictType：

typedef struct dictType {
    // 計算哈希值的函數(shù)
    unsigned int (*hashFunction)(const void *key);
    
    // 復(fù)制鍵的函數(shù)
    void *(*keyDup)(void *privdata, const void *key);
    
    // 復(fù)制值的函數(shù)
    void *(*valDup)(void *privdata, const void *obj);
    
    // 對比鍵的函數(shù)
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    
    // 銷毀鍵的函數(shù)
    void (*keyDestructor)(void *privdata, void *key);
    
    // 銷毀值的函數(shù)
    void (*valDestructor)(void *privdata, void *obj);
}dictType;

要點：

字典被廣泛用于實現(xiàn)redis的各項功能洪添，其中包括數(shù)據(jù)庫和哈希鍵垦页。
Redis中的字典使用哈希表作為底層實現(xiàn)，每個字典帶有兩個哈希表干奢，一個平時使用痊焊，另一個僅在進行rehash時使用。
當(dāng)字典被用作數(shù)據(jù)庫的底層實現(xiàn)忿峻，或者哈希鍵的底層實現(xiàn)時薄啥，Redis使用MurmurHash2算法來計算哈希鍵的哈希值（優(yōu)點：即使輸入的鍵是有規(guī)律的，算法仍能給出一個很好的隨機分布性逛尚，并且算法的計算速度也非陈⒕澹快）。
哈希表使用鏈地址法來解決鍵沖突绰寞，被分配到同一個索引上的多個鍵值會連成一個單項鏈表（速度考慮到逊，采用頭插法）。
在對哈希表進行擴展或者收縮操作時滤钱，程序需要將現(xiàn)有哈希表包含的所有鍵值對rehash到新哈希表里面觉壶，并且這個rehash過程并不是一次性地完成，而是漸進式的完成的（每次更新更新新哈希表件缸，刪除舊哈希表節(jié)點铜靶，插入只插入新哈希表，保證ht[0]包含的鍵值對數(shù)量只減不增停团，最終為空表）旷坦。

四掏熬、跳躍表

跳躍表節(jié)點：redis.h/zskiplistNode

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

zskiplist 結(jié)構(gòu)定義：

typedef strut zskiplist {
    // 表頭節(jié)點和表尾節(jié)點
    structz skiplistNode *header, *tail;
    
    // 表中節(jié)點的數(shù)量
    unsigned long length;
    
    // 表中層數(shù)最大的節(jié)點的層數(shù)
    int level;
} zskiplist;

要點：

跳躍表是有序集合的底層實現(xiàn)之一。
Redis的跳躍表實現(xiàn)由zskiplist和zskiplistNode兩個結(jié)構(gòu)組成秒梅，其中zskiplist用于保存跳躍表信息（比如表頭節(jié)點旗芬、表尾節(jié)點、長度）捆蜀，而zskiplistNde則用于表示跳躍表節(jié)點疮丛。
每個跳躍表節(jié)點的層高都是1至32之間的隨機數(shù)。
在同一個跳躍表中辆它，多個節(jié)點可以包含相同的分值誊薄，但每個節(jié)點的成員對象必須是唯一的。
跳躍表中的節(jié)點按照分值大小進行排序锰茉，當(dāng)分值相同時呢蔫，節(jié)點按照成員對象的大小進行排序。

六飒筑、整數(shù)集合

整數(shù)集合：intset.h/intset

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    
    // 集合包含的元素數(shù)量
    uint32_t length;
    
    // 保存元素的數(shù)組
    int8_t contents[];
} intset;

要點：

整數(shù)集合是集合鍵的底層實現(xiàn)之一片吊。
整數(shù)集合的底層實現(xiàn)為數(shù)組，這個數(shù)組以有序协屡、無重復(fù)的方式保存集合元素俏脊，在有需要時，程序會根據(jù)新添加元素的類型肤晓，改變這個數(shù)組的類型爷贫。
升級操作為整數(shù)集合帶來了操作上的靈活性，并且盡可能地節(jié)約了內(nèi)存补憾。
整數(shù)集合只支持升級操作漫萄，不支持降級操作。

七余蟹、壓縮列表

zlbytes	zltail	zllen	entry1	entry2	...	entryN	zlend

要點：

壓縮列表是一種為節(jié)約內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)卷胯。
壓縮列表被用作列表鍵和哈希鍵的底層實現(xiàn)之一。
壓縮列表可以包含多個節(jié)點威酒，每一個節(jié)點可以保存一個字節(jié)數(shù)組或者整數(shù)值。
添加新節(jié)點到壓縮列表挺峡，或者從壓縮列表刪除節(jié)點葵孤，可能會引發(fā)連鎖更新操作，但這種操作出現(xiàn)的機率并不高橱赠。