<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 字典(map) 及其核心編碼結構

    redis 是使用 C 語言編寫的,但是 C 語言是沒有字典這個數據結構的,因此 C 語言自己使用結構體來自定義一個字典結構

    typedef struct redisDb

    src\server.h 中的 redis 數據庫 數據結構

    /* Redis database representation. There are multiple databases identified
     * by integers from 0 (the default database) up to the max configured
     * database. The database number is the 'id' field in the structure. */
    typedef struct redisDb {
        dict *dict;                 /* The keyspace for this DB */
        dict *expires;              /* Timeout of keys with a timeout set */
        dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
        dict *ready_keys;           /* Blocked keys that received a PUSH */
        dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
        int id;                     /* Database ID */
        long long avg_ttl;          /* Average TTL, just for stats */
        unsigned long expires_cursor; /* Cursor of the active expire cycle. */
        list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
    } redisDb;
    

    redisDb 存放了 redis 數據庫底層的數據結構:

    • dict

    字典類型

    • expires

    過期時間

    • blocking_keys

    客戶端等待數據的鍵 (BLPOP)

    • ready_keys

    收到PUSH的鍵被阻塞

    • watched_keys

    監控 MULTI/EXEC CAS 的鍵,例如事務的時候就會使用到

    • id

    數據庫的 id, 0 – 15

    • avg_ttl

    統計平均的 ttl

    • expires_cursor

    記錄過期周期

    • defrag_later

    存放 key 的列表

    typedef struct dict

    src\dict.h 字典的數據結構

    typedef struct dict {
        dictType *type;
        void *privdata;
        dictht ht[2];
        long rehashidx; /* rehashing not in progress if rehashidx == -1 */
        int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    } dict;
    

    dict 存放字典的數據結構

    • type

    字典的類型

    • privdata

    私有數據

    • ht

    hash 表, 一個舊表,一個新表,是有當 hash 表擴容的時候,新表才會被使用到,也就是 ht[1]

    typedef struct dictType

    typedef struct dictType {
        uint64_t (*hashFunction)(const void *key);
        void *(*keyDup)(void *privdata, const void *key);
        void *(*valDup)(void *privdata, const void *obj);
        int (*keyCompare)(void *privdata, const void *key1, const void *key2);
        void (*keyDestructor)(void *privdata, void *key);
        void (*valDestructor)(void *privdata, void *obj);
        int (*expandAllowed)(size_t moreMem, double usedRatio);
    } dictType;
    

    dictType 定義了多個函數指針,便于后續進行方法的實現和調用

    例如 keyCompare 函數指針,他是一個指針,指向的是一個函數,這個函數有 3 個參數,和 1 個返回值:

    3 個參數

    • privdata

    具體的數據

    • key1

    key1 這個鍵具體的值

    • key2

    key2 這個鍵具體的值

    這個指針 keyCompare 指向的函數作用是比較兩個 key 的大小

    typedef struct dictht

    /* This is our hash table structure. Every dictionary has two of this as we
     * implement incremental rehashing, for the old to the new table. */
    typedef struct dictht {
        dictEntry **table;
        unsigned long size;
        unsigned long sizemask;
        unsigned long used;
    } dictht;
    

    dictht 存放的是 hash 表使用到的數據結構

    • table

    實際的 key-value 鍵值對

    • size

    hashtable 的容量

    • sizemask

    等于 size -1

    • used

    hashtable 元素的個數

    typedef struct dictEntry

    typedef struct dictEntry {
        void *key;
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        struct dictEntry *next;
    } dictEntry;
    

    dictEntry 為鍵值對的實際數據結構

    • key

    key 值,實際上是一個 sds 類型的

    • v

    value 值,是一個聯合體

    • next

    dictEntry 指針,指向下一個數據,主要是解決 hash 沖突的

    例如上一篇我們介紹到的 hash,如下圖中,key 就是 1,v 就是 (k3,v3) ,next 指向的就是 (k2,v2),一般默認情況 next 指向 NULL

    上述聯合體 v ,里面第 1 個元素是, void *val;

    實際上這個元素才是指向真正的值,這個元素是一個指針,實際的數據結構是這個樣子的

    typedef struct redisObject {
        unsigned type:4;
        unsigned encoding:4;
        unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                                * LFU data (least significant 8 bits frequency
                                * and most significant 16 bits access time). */
        int refcount;
        void *ptr;
    } robj;
    
    • type

    類型,占 4 個 bit ,是用來約束客戶端 api 的,例如 string 類型,embstr,hash,zset 等等

    • encoding

    編碼類型,占 4 個bit ,使用到的數字有 0 - 10,分別表示不同的數據類型

    • lru

    lru 占 24 個bit ,3 個字節 , 內存淘汰算法

    • refcount

    引用計數 , int 類型,占 4 個字節

    • ptr

    實際的數據指針 , 64 位操作系統中, ptr 占 8個字節

    bitmap 的小案例

    設置一個 bitmap 的 key,作用為標記 11 號的在線用戶

    127.0.0.1:6379> SETBIT login:9:11 25 1
    (integer) 0
    127.0.0.1:6379> SETBIT login:9:11 26 1
    (integer) 0
    127.0.0.1:6379> SETBIT login:9:11 27 1
    (integer) 0
    127.0.0.1:6379> BITCOUNT login:9:11
    (integer) 3
    127.0.0.1:6379> strlen login:9:11
    (integer) 4
    
    • BITCOUNT key [start end]

    通過 BITCOUNT 可以看出 11 號在線人數 3 個人,login:9:11 占用字節數位 4 字節

    127.0.0.1:6379> SETBIT login:9:12 26 1
    (integer) 0
    127.0.0.1:6379> SETBIT login:9:12 25 0
    (integer) 0
    127.0.0.1:6379> SETBIT login:9:12 27 1
    (integer) 0
    127.0.0.1:6379> STRLEN login:9:12
    (integer) 4
    

    通過 BITCOUNT 可以看出 12 號在線人數 2 個人,login:9:12 占用字節數位 4 字節

    下面我們將取 login:9:11 和 login:9:12 的 與操作,來計算 11 號 和 12 號兩天來都在線的人數

    127.0.0.1:6379> BITOP and login:and login:9:11 login:9:12
    (integer) 4
    127.0.0.1:6379> BITCOUNT login:and
    (integer) 2
    
    • BITOP operation destkey key [key ...]

    根據上述結果我們可以看出,11 號 和 12 號兩天來都在線的人數為 2 人,驗證 ok

    我們再來看看11 號 和 12 號任意一天在線的人數

    127.0.0.1:6379> BITOP or login:or login:9:11 login:9:12
    (integer) 4
    127.0.0.1:6379> BITCOUNT login:or
    (integer) 3
    

    根據上述結果我們可以看出,11 號 和 12 號任意一天在線的人數為 3 人,驗證 ok

    127.0.0.1:6379> type login:or
    string
    127.0.0.1:6379> OBJECT encoding login:or
    "raw"
    127.0.0.1:6379> OBJECT encoding login:9:12
    "raw"
    127.0.0.1:6379> OBJECT encoding login:and
    "raw"
    

    咱們來看看上述用到的 key ,在 redis 里面實際是什么數據類型吧,

    • OBJECT encoding [arguments [arguments ...]]

    可以看出上述都是 “raw” 類型, 也就是 redis 的 sds 類型

    緩存行

    咱們再來看一個小例子,redis 中設置一個字符串 key

    127.0.0.1:6379> set name xiaoming
    OK
    127.0.0.1:6379> OBJECT encoding name
    "embstr"
    

    我們可以看出 name 的類型是 “embstr”,那么 “embstr” 底層是如何實現的呢?“embstr” 有能承載多少個字節的數據呢?

    上述我們有說到 redis 里面存放鍵值對的地方在 dictEntry 結構體中,dictEntry 結構體中的val 指針指向的是一個 redisObject 結構體,是這樣的

    我們在一個 64 位的機器中,CPU 在內存中讀取數據的是通過讀取緩存行的方式來實現的

    一個緩存行有 64 字節

    一個 redisObject 結構體占 16 字節

    那么就還剩 48 字節 可以使用,那么使用 redis 里面 哪一個 sds 數據結構來存放數據數據呢?

    使用 hisdshdr8 類型,hisdshdr8 類型 sds 的前 3 個元素占用 3 個字節,那么剩下的 buf 存放數據就可以存放 45個字節(64 - 16 - 3)的數據了

    如果你這么認為了,那么就有點粗心哦,因為 redis 為了兼容 C 語言的標準,會在字符串的后面加上 1 個 ‘\0’ ,他是占一個字節的因此最終“embstr” 實際能存放的字節數是:

    44 字節

    來回顧上一篇文章,可以看出

    當數據占用空間在 0 - - 2^5-1 , 使用 hisdshdr5 數據類型

    2^5 – 2^8-1 的占用空間的時候,使用 hisdshdr8 數據類型

    小小的實踐

    我們在 redis 中設置一個 test 的值為一個 44字節 的內容,查看這個 key 的類型,是 embstr

    127.0.0.1:6379> set test 99999999991111111111222222222233333333334444
    OK
    127.0.0.1:6379> OBJECT encoding test
    "embstr"
    127.0.0.1:6379> STRLEN test
    (integer) 44
    

    再來設置 test2 為 大于 44 字節的內容,再查看他的內容是 raw

    127.0.0.1:6379> set test2 999999999911111111112222222222333333333344449
    OK
    127.0.0.1:6379> OBJECT encoding test2
    "raw"
    

    最后送上一張上述數據結構的關系圖

    參考資料:

    歡-迎點贊,關注,收藏

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

    好了,本次就到這里

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

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

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