<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • 【Redis 系列】redis 學習十五,redis sds數據結構和底層設計原理

    redis 是 C 語言寫的,那么我們思考一下 redis 是如何表示一個字符串的?redis 的數據結構和 C 語言的數據結構是一樣的嗎?

    我們可以看到 redis 源碼中的 sds 庫函數,和 sds 的具體實現,分別有如下 2 個文件:

    • sds.h
    • sds.c

    具體路徑是:deps/hiredis/sds.h , deps/hiredis/sds.c

    sds.h 中涉及如下數據結構:

    SDS

    redis 中 SDS simple Dynamic string

    簡單動態字符串

    C 語言中表示字符串的方式是字符數組,例如:

    char data[]="xiaomotong"
    

    如果 C 語言需要擴容的話需要重新分配一個再大一點的內存,存放新的字符串,若每次都要重新分配字符串,對于效率和性能必然會大大降低,并且若某一個字符串是 “xiaomo\0tong”

    這個時候,實際上 C 中 遇到 ‘\0’ 就結束了,因此實際 “xiaomo\0tong” 只會讀取到xiaomo ,字符串長度就是 6

    因此 redis 中的 sds 數據結構是這樣設計的,是通過一個成員來標志字符串的長度:

    SDS:
        free:0
        len:6
        char buf[]="xiaomo"
            
    若這個時候,我們需要在字符串后面追加字符串, sds 就會進行擴容,例如在后面加上 “tong” , 那么 sds 的數據結構中的值會變成如下:
        free:10
        len:10
        char buf[]="xiaomotong"      
    

    最后的 "xiaomotong" 也是帶有\0的,這也保持了 C 語言的標準,redis 中對于 sds 數據結構擴容是成倍增加的,但是到了一定的級別,例如 1M 的時候,就不會翻倍的擴容,而是做加法 例如 1M 變成 2M , 2M 變成 3M 等等

    SDS 的優勢:

    • 二進制安全的數據結構
    • 內存預分配機制,避免了頻繁的內存分配
    • 兼容 C 語言的庫函數

    redis 源碼 sds 數據結構

    現在我們看到的是 reids-6.2.5 sds 的數據結構,將以前的表示一個長度使用了 int 類型,是 32 字節的,能表示的長度可以達到 42 億,其實遠遠沒有必要使用 int32 ,太浪費資源了

    下面的數據結構,可以根據不同的需求,選取不同的數據結構進行使用

    struct __attribute__ ((__packed__)) hisdshdr5 {
        unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
        char buf[];
    };
    struct __attribute__ ((__packed__)) hisdshdr8 {
        uint8_t len; /* used */
        uint8_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) hisdshdr16 {
        uint16_t len; /* used */
        uint16_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) hisdshdr32 {
        uint32_t len; /* used */
        uint32_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) hisdshdr64 {
        uint64_t len; /* used */
        uint64_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    
    • hisdshdr5

    用于長度在 0 -- 2^5 - 1 范圍內

    • hisdshdr8

    用于長度在 2^5-- 2^8 - 1 范圍內

    • hisdshdr16

    用于長度在 2^8 -- 2^16 - 1 范圍內

    • hisdshdr32

    用于長度在 2^16 -- 2^32 - 1 范圍內

    • hisdshdr64

    用于長度在 2^32 -- 2^64 - 1 范圍內

    上述的 unsigned char flags 占用 1 個字節,8個 bit 位:

    • 其中 3 位 用于表示類型
    • 其中 5 位 用于表示字符串的長度

    前面 3 個 bit 位,能表示的數字范圍是 0 - 7 ,對于應到如下宏

    #define HI_SDS_TYPE_5  0
    #define HI_SDS_TYPE_8  1
    #define HI_SDS_TYPE_16 2
    #define HI_SDS_TYPE_32 3
    #define HI_SDS_TYPE_64 4
    #define HI_SDS_TYPE_MASK 7
    

    源碼實現是通過與操作來獲取到具體的數據結構類型的:

    咱們以 hisdshdr8 數據結構為例子,unsigned char flags 是這樣的

    • len

    表示已經使用的長度

    • alloc

    預分配的空間大小

    • flag

    表示使用哪一種數據結構(前 3 個 bit)

    • buf

    實際存儲的字符串

    那么,我們就能夠計算出來,該數據結構的空間剩余 free = alloc - len

    源碼中 sds.h 下的函數 hisds hi_sdsnewlen(const void *init, size_t initlen)

    使用 一個 init 指針和 initlen 長度,來創建一個字符串

    hisds hi_sdsnewlen(const void *init, size_t initlen) {
        void *sh;
        hisds s;
        // 計算type,獲取需要使用的數據結構類型
        char type = hi_sdsReqType(initlen);
        // 現在默認使用 HI_SDS_TYPE_8 了
        if (type == HI_SDS_TYPE_5 && initlen == 0) type = HI_SDS_TYPE_8;
        
        int hdrlen = hi_sdsHdrSize(type);
        unsigned char *fp; /* flags pointer. */
    	
        // 分配內存
        sh = hi_s_malloc(hdrlen+initlen+1);
        if (sh == NULL) return NULL;
        if (!init)
            memset(sh, 0, hdrlen+initlen+1);
        s = (char*)sh+hdrlen;
        fp = ((unsigned char*)s)-1;
        // 根據不同的類型對數據結構初始化
        switch(type) {
            case HI_SDS_TYPE_5: {
                *fp = type | (initlen << HI_SDS_TYPE_BITS);
                break;
            }
            case HI_SDS_TYPE_8: {
                HI_SDS_HDR_VAR(8,s);
                sh->len = initlen;
                sh->alloc = initlen;
                *fp = type;
                break;
            }
            case HI_SDS_TYPE_16: ...
            case HI_SDS_TYPE_32: ...
            case HI_SDS_TYPE_64: ...
        }
        if (initlen && init)
            memcpy(s, init, initlen);
        // 兼容 C 庫,字符串后面加上 \0
        s[initlen] = '\0';
        return s;
    }
    
    • hi_sdsReqType

    根據字符串的長度來計算所使用的數據類型

    • hi_sdsHdrSize

    根據不同的類型,獲取該類型需要分配的空間大小

    • hi_s_malloc

    開辟內存,調用的是alloc.h中的 hi_malloc,具體實現就看不到了

    • switch(type) …

    根據不同的類型,來將對應的數據結構做初始化

    • s[initlen] = '\0'

    兼容 C 庫,字符串后面加上 ’\0’

    redis k-v 底層設計原理

    redis 是如何存儲海量數據的?

    redis 中數據是以 key-value 的方式來存儲的,key 都是字符串,而 value 根據不同的數據結構表現形式也不太一樣

    他們的存儲方式是以 數組 + 鏈表的方式存儲的:

    • 數組

    數組中存放的是鏈表的地址

    • 鏈表

    鏈表中存儲的是具體的數據

    舉個例子:

    上面有說到 redis 里面的 key 都是字符串的方式,那么如何與數組和鏈表進行結合呢?

    具體邏輯是使用 hash 函數,將字符串 key 按照算法計算出一個索引值,這個值就是數組的索引,該索引對應的數組元素是指向一個鏈表的,鏈表中存放具體的數據

    • dict[10] 作為數組,每一個元素會指向一條鏈表

    • 現在我們要插入 k1 - v1 , k2 - v2 , k3 - v3

    通過 hash 函數進行計算:

    hash(k1) % 10 = 0
    
    hash(k2) % 10 = 1
    

    此處對 10 取模的原因是,整個數組就只能存放 10 個元素

    那么結果是這樣的

    dict[0] -> (k1,v1) -> null
    dict[1] -> (k2,v2) -> null
    

    若這個時候咱們插入的 (k3,v3) 計算出來的索引與前面已有數據的沖突了咋辦?

    hash(k3) % 10 = 1
    

    這就會出現 hash 沖突了,當 hash 沖突的時候,若 k3 與 k2 是相等了,那么就會直接更新 k2 對應的 value 值

    若 k3 與 k2 不同,則會通過鏈地址法來解決 hash 沖突,會把 (k3,v3) 通過頭插法來插入到原有的鏈表中,如:

    dict[0] -> (k1,v1) -> null
    dict[1] -> (k3,v3) -> (k2,v2) -> null
    

    小結

    • 對于上述的 hash ,相同的輸入,一定會有相同的輸出
    • 不同的輸入,也有可能有相同的輸出,此時就 hash 沖突了,是需要解決的

    參考資料:

    歡迎點贊,關注,收藏

    朋友們,你的支持和鼓勵,是我堅持分享,提高質量的動力

    歡迎大家對文章中的源碼細節進行討論和分享,不足之處還請多多指教,如果大佬們有更好的學習方法還請給予指導,謝謝

    1、評論區超過 10 人互動(不含作者本人),作者可以以自己的名義抽獎送出掘金徽章 2 枚(掘金官方承擔)

    好了,本次就到這里

    技術是開放的,我們的心態,更應是開放的。擁抱變化,向陽而生,努力向前行。

    我是小魔童哪吒,歡迎點贊關注收藏,下次見~

    posted @ 2022-05-06 21:16  小魔童哪吒  閱讀(20)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看