Redis 中 hash 數據類型的實現原理

hash 是 Redis 中基本數據結構之一，使用非常廣泛，這裏我們分析一下 hash 實現原理。

從宏觀看 Redis 數據結構

在分析哈希數據類型時，我們需要了解一下 redis 整體的組織。Redis 啓動會，會調用initServer函數初始化全局變量struct redisServer server;，其中保存了所有的數據庫信息，然後會調用aeMain(server.el);進入事件循環，不斷接收客戶端命令並執行。數據也是保存在redisServer中的redisDB中。redisDB中通過字典dict保存所有鍵值對數據。而字典dict是通過哈希表dictht實現的。

redisServer   // 全局變量server，保存了所有的數據庫信息
--> redisDB   // 數據庫信息，默認16個數據庫
    --> dict   // 字典，保存了所有的鍵值對
        --> dictht   // 哈希表，底層數據結構

重要的數據結構定義如下：

// redisServer保存了所有的數據庫信息
struct redisServer {
    redisDb *db;  // 數據庫數組，默認16個數據庫
    // ...
}
// redis數據庫，默認16個數據庫
typedefstruct redisDb {
    dict *dict;  // 字典，保存了所有的鍵值對
    // ...
    int id;    // 數據庫id
} redisDb;
// 字典，保存了所有的鍵值對
typedefstruct 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;

typedefstruct dictEntry {
    void *key;    // key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;    // value
    struct dictEntry *next;   // 指向下一個節點
} dictEntry;

在哈希表dictht中會通過dictEntry存儲 key-value 對，key 和 value 都是一個redisObject對象，key 總是一個字符串類型的對象，value 則根據具體數據類型底層數據結構的不同而不同，可以是字符串、哈希表等。

★

需要注意的是，這裏分析的是 redis-6.2.8 版本的源代碼，實現細節可能與最新代碼有所差異。

字典

字典是 redis 中用於存儲鍵值對數據的數據結構，字典的實現基於哈希表。可以看到字典結構中定義了dictht ht[2]，是通過兩個哈希表實現的字典。爲什麼是兩個哈希表呢？這是爲了解決字典擴縮容問題，實現漸進式 rehash，避免一次性 rehash 導致性能問題。

/* 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;

我們看一下dictRehash函數，這裏實現了遷移 n 個元素到新的表，遷移的過程就是找到下一個待遷移的元素，遷移到新表中，舊錶中的桶置爲 NULL，更新 rehashidx。

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    unsignedlong s0 = d->ht[0].size;
    unsignedlong s1 = d->ht[1].size;
    // 檢查是否允許rehash
    if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return0;
    if (dict_can_resize == DICT_RESIZE_AVOID && 
        ((s1 > s0 && s1 / s0 < dict_force_resize_ratio) ||
         (s1 < s0 && s0 / s1 < dict_force_resize_ratio)))
    {
        return0;
    }

    while(n-- && d->ht[0].used != 0) { // 執行n步，每步將一個節點從ht[0]遷移到ht[1]
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsignedlong)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return1; // 跳過空桶
        }
        de = d->ht[0].table[d->rehashidx]; // 獲取當前桶的元素
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;   // 將元素插入到新的哈希桶中
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;  // 將舊哈希桶置爲空
        d->rehashidx++;   // 下一個要處理的哈希桶索引
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {  // 如果ht[0]已經爲空，則rehash完成
        zfree(d->ht[0].table);  // 釋放ht[0]
        d->ht[0] = d->ht[1];  // 重置ht[0]
        _dictReset(&d->ht[1]);  // 重置ht[1]
        d->rehashidx = -1;   // rehashidx置爲-1，表示rehash完成
        return0;
    }

    /* More to rehash... */
    return1;
}

遷移過程是漸進式遷移，每次只遷移 n 個桶，通常會有兩個過程會進行遷移，一個是正常的命令請求過程中會遷移 1 個桶，另一個是定時任務serverCron，會定時調用incrementallyRehash進而調用dictRehashMilliseconds函數進而調用dictRehash進行遷移，每次遷移 100 個桶。

Hash 類型的實現

在介紹了從宏觀看 Redis 數據結構以及字典後，可以進入正題了，說明一下 Hash 類型的實現。

Hash 類型底層是通過壓縮列表 ziplist 以及字典 dict 實現的，因爲壓縮列表比字典更節省內存，所以程序在創建新 Hash 鍵時，默認使用壓縮列表作爲底層實現，當有需要時，程序纔會將底層實現從壓縮列表轉換到字典。

robj *createHashObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;   // 底層實現爲壓縮列表
    return o;
}

那麼什麼時候進行轉換呢？

元素個數超過一定閾值server.hash_max_ziplist_entries時，會進行轉換。
某個鍵或者某個值的長度超過一定閾值server.hash_max_ziplist_value時，也會進行轉換。

void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
    int i;
    size_t sum = 0;

    if (o->encoding != OBJ_ENCODING_ZIPLIST) return;

    for (i = start; i <= end; i++) {
        if (!sdsEncodedObject(argv[i]))
            continue;
        size_t len = sdslen(argv[i]->ptr);
        if (len > server.hash_max_ziplist_value) { // 當值長度大於這個值時，則進行轉換
            // 將壓縮列表轉爲哈希表
            // 轉換的具體過程就是創建哈希表，遍歷壓縮列表，獲取key,value，然後插入哈希表
            hashTypeConvert(o, OBJ_ENCODING_HT); 
            return;
        }
        sum += len;
    }
    if (!ziplistSafeToAdd(o->ptr, sum))
        hashTypeConvert(o, OBJ_ENCODING_HT);
}

我們看一下hset命令的實現，也就是向哈希類型的數據結構中添加數據：

void hsetCommand(client *c) {
    int i, created = 0;
    robj *o;

    if ((c->argc % 2) == 1) {  // 參數個數必須是偶數，放在field和value不成對
        addReplyErrorFormat(c,"wrong number of arguments for '%s' command",c->cmd->name);
        return;
    }

    // 檢查鍵空間中是否存在該鍵，如果不存在，則創建一個新的hash對象
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
    // 嘗試轉換類型，檢查key,value的長度，如果超過一定大小，需要將ziplist轉換爲哈希表
    hashTypeTryConversion(o,c->argv,2,c->argc-1); 

    // 遍歷所有field和value，插入到底層數據結構中
    // 具體插入時需要判斷是ziplist還是hash表
    for (i = 2; i < c->argc; i += 2)
        created += !hashTypeSet(o,c->argv[i]->ptr,c->argv[i+1]->ptr,HASH_SET_COPY);

    /* HMSET (deprecated) and HSET return value is different. */
    char *cmdname = c->argv[0]->ptr;
    if (cmdname[1] == 's' || cmdname[1] == 'S') {
        /* HSET */
        addReplyLongLong(c, created);
    } else {
        /* HMSET */
        addReply(c, shared.ok);
    }
    signalModifiedKey(c,c->db,c->argv[1]);  // 通知數據庫該鍵被修改
    // 發佈鍵空間通知
    notifyKeyspaceEvent(NOTIFY_HASH,"hset",c->argv[1],c->db->id);
    server.dirty += (c->argc - 2)/2;   // 增加數據庫的髒數據計數器
}

我們具體看一下壓縮列表數據結構，壓縮列表的佈局：<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

aigvM4

其中每個entry的佈局爲：<prevlen> <encoding> <entry-data>

prevlen：前一個entry的長度（動態編碼）
encoding：數據類型和編碼方式
entry-data：實際數據

這裏採用動態編碼是爲了節省存儲空間，與 protobuf 編碼中的 varint 原理類似。

具體的對應哈希類型的 field 和 value 在entry-data中存儲，相鄰節點交替存儲field和value，比如[field1,value1,field2,value2,field3,value3]，每個field或者value都是一個entry，依次排列。

核心操作：

hashTypeSet: 通過ziplistPush追加新元素
hashTypeGetFromZiplist：使用ziplistFind函數遍歷查找
自動轉換：當插入新元素導致長度 / 值超過閾值時，會調用hashTypeConvert進行轉換

壓縮列表比較適合數量量小的場景，每當插入一個新元素時，如果 ziplist 的容量不夠，則會重新分配內存空間，將原有數據拷貝到新空間中，並插入新元素。當數據量較大時，每次分配內存空間和拷貝數據都會產生較大的額外開銷，因此，當數據量較大時，會考慮將壓縮列表轉換爲哈希表存儲。實際上就是前面介紹的字典dict，這裏不再進行介紹。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/JgfWTQ7vtBKZ7fdDBtKKvg

從宏觀看 Redis 數據結構

字典

Hash 類型的實現

猜你喜歡