redis數(shù)據(jù)結構和對象一

小樣樣樣樣樣樣 2022-02-10

展開全文

1. SDS:簡單動態(tài)字符串（simple dynamic string)

Redis沒有直接使用C語言的字符串，而是自己構建了一種名為簡單動態(tài)字符串類型，并將SDS用作Redis的默認字符串。

SDS的定義

struct sdshdr {

    // buf 中已占用空間的長度
    int len;

    // buf 中剩余可用空間的長度
    int free;

    // 字節(jié)數(shù)組
    char buf[];
};

SDS與C字符串的區(qū)別

SDS獲取字符串長度復雜度為O(1), C字符串獲取字符串長度復雜度為O(N)；
因為C字符串獲取字符串并不記錄自身長度，程序必須遍歷整個字符串對每個字符串計數(shù)。這個操作的復雜度為O(N)
SDS在len屬性中記錄了SDS本身長度，所以獲取字符串長度復雜度為O(1)
API是安全的，不會造成緩沖區(qū)溢出；
C字符串不記錄自身長度，如果忘了給字符串擴容執(zhí)行字符串拼接就會造成溢出
SDS拼接字符串之前會先通過free字段檢測剩余空間能否滿足需求，不能滿足需求的就會擴容。
減少修改字符串帶來的內(nèi)存重分配次數(shù)；
C字符串底層總是一個N+1個字符數(shù)組，所以每次增長或縮短一個字符串，程序總要對這個C字符串進行一次內(nèi)存重分配。
SDS實現(xiàn)空間預分配和惰性空間釋放兩種優(yōu)化策略.
二進制安全
C字符串只能保存文本數(shù)據(jù)
SDS可以保存文本或者二進制數(shù)據(jù)

** 2. 鏈表 **

Redis的List（列表）和發(fā)布訂閱，慢查詢，監(jiān)視器等功能都用到了鏈表

鏈表節(jié)點實現(xiàn) adlist.h/listNode結構表示

    // listNode 雙端鏈表節(jié)點
    typedef struct listNode {

        // 前置節(jié)點
        struct listNode *prev;

        // 后置節(jié)點
        struct listNode *next;

        // 節(jié)點的值
        void *value;

    } listNode;

該鏈表為雙向鏈表，由多個listNode結點組成的鏈表結構圖如下：

鏈表實現(xiàn) adlist.h/list結構表示


    // list 雙端鏈表
    typedef struct list { // 在c語言中,用結構體的方式來模擬對象是一種常見的手法

        // 表頭節(jié)點
        listNode *head;

        // 表尾節(jié)點
        listNode *tail;

        // 節(jié)點值復制函數(shù)
        void *(*dup)(void *ptr);

        // 節(jié)點值釋放函數(shù)
        void(*free)(void *ptr);

        // 節(jié)點值對比函數(shù)
        int(*match)(void *ptr, void *key);

        // 鏈表所包含的節(jié)點數(shù)量
        unsigned long len;

    } list;

例：由一個list結構和三個listNode結構組成的鏈表
![](https://img2020.cnblogs.com/blog/1186190/202102/1186190-20210227163531303-2083424534.jpg)

鏈表提供表頭指針head，表尾指針tail，以及鏈表長度計數(shù)器len，和封裝了3個內(nèi)置函數(shù)
1.dup函數(shù)：復制鏈表結點所保存的值
2.free函數(shù)：釋放鏈表結點所保存的值
3.match函數(shù)：對比鏈表結點所保存的值和另一個輸入值是否相等
這三個函數(shù)是用于實現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)。

Redis鏈表實現(xiàn)特征總結
1.雙端：獲取某個結點的前驅和后繼結點都是O(1)
2.無環(huán)：表頭的prev指針和表尾的next指針都指向NULL，對鏈表的訪問都是以NULL為終點
3.帶表頭指針和表尾指針：獲取表頭和表尾的復雜度都是O(1)
4.帶鏈表長度計數(shù)器：len屬性記錄，獲取鏈表長度O(1)
5.多態(tài)：鏈表結點使用void*指針來保存結點的值，并且可以通過鏈表結構的三個函數(shù)為結點值設置類型特定函數(shù)，所以鏈表可以保存各種不同類型的值

字典
1. 字典的實現(xiàn)
哈希節(jié)點使用dictEntry結構表示，每個dictEntry結構都保存著一個鍵值對。

    // dictEntry 哈希表節(jié)點
    typedef struct dictEntry {
        // 鍵
        void *key;

        // 值
        union {//值v的類型可以是以下三種類型
            void *val;
            uint64_t u64;
            int64_t s64;
        } v;

        // 指向下個哈希表節(jié)點，形成鏈表
        struct dictEntry *next;

    } dictEntry;

Redis字典使用哈希表有dictht.h/dictht結構定義


    typedef struct dictht { 
        // 哈希表數(shù)組, 每個元素都是一條鏈表
        dictEntry **table;

        // 哈希表大小
        unsigned long size;

        // 哈希表大小掩碼，用于計算索引值
        // 總是等于 size - 1
        unsigned long sizemask;

        // 該哈希表已有節(jié)點的數(shù)量
        unsigned long used;

    } dictht;

![](https://img2020.cnblogs.com/blog/1186190/202102/1186190-20210227171229827-765330912.png)

    // dict 字典
    typedef struct dict {
        
        // 類型特定函數(shù)
        dictType *type; // type里面主要記錄了一系列的函數(shù),可以說是規(guī)定了一系列的接口

        // 私有數(shù)據(jù)
        void *privdata; // privdata保存了需要傳遞給那些類型特定函數(shù)的可選參數(shù)

        //兩張哈希表
        dictht ht[2];//便于漸進式rehash

        //rehash 索引，并沒有rehash時，值為 -1
        int rehashidx;
        
        //目前正在運行的安全迭代器的數(shù)量
        int iterators;

    } dict;

* type 屬性是一個指向dictType結構的指針，每個dictType結構保存了一族用于操作特定類型鍵值對的函數(shù)，Redis為用途不同的字典設置不同的類型特定函數(shù)。
* privdata 屬性則保存了需要傳遞給那些類型特定函數(shù)的可選參數(shù)。
* ht是一個包含兩個項的數(shù)組，數(shù)組每個項都是一個dictht哈希表，一般情況下只使用ht[0]哈希表，ht[1]只會對ht[0]哈希表進行rehash時使用。
* rehashidx它記錄了rehash目前的進度，如果目前沒有進行rehash，那么他的值為-1.

    // dictType 用于操作字典類型函數(shù)
    typedef struct dictType {

        // 計算哈希值的函數(shù)
        unsigned int(*hashFunction)(const void *key);

        // 復制鍵的函數(shù)
        void *(*keyDup)(void *privdata, const void *key);

        // 復制值的函數(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;

![](https://img2020.cnblogs.com/blog/1186190/202102/1186190-20210227171242872-913327145.png)

哈希算法
使用字典類型設置的哈希函數(shù)擊視鍵key的哈希值
int hash = dict->type->hashFunction(key)
使用哈希表的sizemask的屬性和哈希值計算出索引值
index = hash & dict->ht[0].sizemask;
使用哈希表節(jié)點next指針構成單向鏈表解決哈希沖突。
擴展和收縮哈希表的恭祝通過執(zhí)行rehash操作來完成步驟如下
如果執(zhí)行的是擴展操作，那么擴展ht[1]的大小為第一個大于等于ht[0].used*2的2的n此冪
如果執(zhí)行的是收縮操作，那么收縮ht[1]的大小為第一個大于等于ht[0].used的2的n此冪
將保存在ht[0]中的所有鍵值對rehash到ht[1]上面：rehash指的是重新計算鍵的哈希值和索引值，然后將鍵值對放置到ht[1]哈希表的指點位置。
當ht[0]包含的所有鍵值對都遷移到ht[1]之后，釋放ht[0]，將ht[1]設置為ht[0]，并在ht[1]重新創(chuàng)建一個空哈希表，為下一次rehash做準備。
當以下條件中的任意一個被滿足時，程序會自動開始對哈希表進行擴展操作
1）服務器目前沒有執(zhí)行BGSAVE命令或者BGREWRITEOF命令，并且哈希表的負載因子大于等于1.
2）服務器目前正在執(zhí)行BGSAVE命令或者BGREWRITEOF命令，并且哈希表的負載因子大于等于5.
3) 哈希表的負載因子可以通過公式：load_factor = ht[0].used / ht[0].size;
4) 哈希表的負載因子小于0.1時，自動執(zhí)行哈希表收縮操作；
如果哈希表中有成千上萬個鍵值對，那么要一次性rehash到ht[1]的話，可能會導致服務器一段時間內(nèi)停止服務。為了避免rehash對服務器性能影響，服務器二十分多次，漸進性的將ht[0]里面的鍵值對漸進性的rehash。詳細步驟：
1）為ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表。
2）在字典中維持一個索引計數(shù)器變量rehashidx，并將它的值設置為0，表示rehash工作正式開始。
3) 在rehash進行期間，每次對字典執(zhí)行添加，刪除，查找或者更新操作時，程序除了執(zhí)行指定的操作外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1],完成順帶操作后，程序將rehashidx屬性的值加一.
4) 隨著字典操作的不斷執(zhí)行，最終在某個時間點，ht[0]的所有鍵值對會被rehash至ht[1]。這是將rehashidx設置為-1.表示rehash操作已執(zhí)行完。