redis hash底層資料結構

hash底層存儲結構

redis的哈希對象的底層存儲可以使用ziplist（壓縮清單）和hashtable。當hash對象可以同時滿足一下兩個條件時，哈希對象使用ziplist編碼。

• 哈希對象儲存的所有鍵值對的鍵和值的字元串長度都小于64位元組
• 哈希對象儲存的鍵值對數量小于512個

redis hash資料結構

redis的hash架構就是标準的hashtab的結構，通過挂鍊解決沖突問題。

hashtab.png

redis ziplist資料結構

ziplist的資料結構主要包括兩層，ziplist和zipEntry。

• ziplist包括zip header、zip entry、zip end三個子產品。
• zip entry由prevlen、encoding&length、value三部分組成。
• prevlen主要是指前面zipEntry的長度，coding&length是指編碼字段長度和實際- 存儲value的長度，value是指真正的内容。
• 每個key/value存儲結果中key用一個zipEntry存儲，value用一個zipEntry存儲。

ziplist

zipEntry

redis hash存儲過程源碼分析

以hset指令為例進行分析，整個過程如下：

• 首先檢視hset中key對應的value是否存在，hashTypeLookupWriteOrCreate。
• 判斷key和value的長度确定是否需要從zipList到hashtab轉換，hashTypeTryConversion。
• 對key/value進行string層面的編碼，解決記憶體效率問題。
• 更新hash節點中key/value問題。
• 其他後續操作的問題

void hsetCommand(redisClient *c) {
    int update;
    robj *o;

    // 取出或新建立哈希對象
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;

    // 如果需要的話，轉換哈希對象的編碼
    hashTypeTryConversion(o,c->argv,2,3);

    // 編碼 field 和 value 對象以節約空間
    hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);

    // 設定 field 和 value 到 hash
    update = hashTypeSet(o,c->argv[2],c->argv[3]);

    // 傳回狀态：顯示 field-value 對是新添加還是更新
    addReply(c, update ? shared.czero : shared.cone);

    // 發送鍵修改信号
    signalModifiedKey(c->db,c->argv[1]);

    // 發送事件通知
    notifyKeyspaceEvent(REDIS_NOTIFY_HASH,"hset",c->argv[1],c->db->id);

    // 将伺服器設為髒
    server.dirty++;
}
           

判斷key/value的長度是否超過規定的長度64個位元組，由REDIS_HASH_MAX_ZIPLIST_VALUE定義。如果超過64個位元組那麼久需要将ziplist轉成hashtab對象。

/* 
 * 對 argv 數組中的多個對象進行檢查，
 * 看是否需要将對象的編碼從 REDIS_ENCODING_ZIPLIST 轉換成 REDIS_ENCODING_HT

 * 注意程式隻檢查字元串值，因為它們的長度可以在常數時間内取得。
 */
void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
    int i;

    // 如果對象不是 ziplist 編碼，那麼直接傳回
    if (o->encoding != REDIS_ENCODING_ZIPLIST) return;

    // 檢查所有輸入對象，看它們的字元串值是否超過了指定長度
    for (i = start; i <= end; i++) {
        // #define REDIS_HASH_MAX_ZIPLIST_VALUE 64
        if (sdsEncodedObject(argv[i]) &&
            sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
        {
            // 将對象的編碼轉換成 REDIS_ENCODING_HT
            hashTypeConvert(o, REDIS_ENCODING_HT);
            break;
        }
    }
}
           

hash底層的更新操作函數hashTypeSet内部會根據是ziplist還是hashtab進行不同的處理邏輯，在ziplist當中會判斷ziplist存儲資料的長度來判斷是否需要轉為hashtab資料結構，其中長度判斷是通過#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512定義的。

/* 
 * 将給定的 field-value 對添加到 hash 中，
 * 如果 field 已經存在，那麼删除舊的值，并關聯新值。
 *
 * 這個函數負責對 field 和 value 參數進行引用計數自增。
 *
 * 傳回 0 表示元素已經存在，這次函數調用執行的是更新操作。
 *
 * 傳回 1 則表示函數執行的是新添加操作。
 */
int hashTypeSet(robj *o, robj *field, robj *value) {
    int update = 0;

    // 添加到 ziplist
    if (o->encoding == REDIS_ENCODING_ZIPLIST) {
        unsigned char *zl, *fptr, *vptr;

        // 解碼成字元串或者數字
        field = getDecodedObject(field);
        value = getDecodedObject(value);

        // 周遊整個 ziplist ，嘗試查找并更新 field （如果它已經存在的話）
        zl = o->ptr;
        fptr = ziplistIndex(zl, ZIPLIST_HEAD);
        if (fptr != NULL) {
            // 定位到域 field
            fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1);
            if (fptr != NULL) {
                /* Grab pointer to the value (fptr points to the field) */
                // 定位到域的值
                vptr = ziplistNext(zl, fptr);
                redisAssert(vptr != NULL);

                // 辨別這次操作為更新操作
                update = 1;

                /* Delete value */
                // 删除舊的鍵值對
                zl = ziplistDelete(zl, &vptr);

                /* Insert new value */
                // 添加新的鍵值對
                zl = ziplistInsert(zl, vptr, value->ptr, sdslen(value->ptr));
            }
        }

        // 如果這不是更新操作，那麼這就是一個添加操作
        if (!update) {
            /* Push new field/value pair onto the tail of the ziplist */
            // 将新的 field-value 對推入到 ziplist 的末尾
            zl = ziplistPush(zl, field->ptr, sdslen(field->ptr), ZIPLIST_TAIL);
            zl = ziplistPush(zl, value->ptr, sdslen(value->ptr), ZIPLIST_TAIL);
        }
        
        // 更新對象指針
        o->ptr = zl;

        // 釋放臨時對象
        decrRefCount(field);
        decrRefCount(value);

        // 檢查在添加操作完成之後，是否需要将 ZIPLIST 編碼轉換成 HT 編碼
        // #define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512
        if (hashTypeLength(o) > server.hash_max_ziplist_entries)
            hashTypeConvert(o, REDIS_ENCODING_HT);

    // 添加到字典
    } else if (o->encoding == REDIS_ENCODING_HT) {

        // 添加或替換鍵值對到字典
        // 添加傳回 1 ，替換傳回 0
        if (dictReplace(o->ptr, field, value)) { /* Insert */
            incrRefCount(field);
        } else { /* Update */
            update = 1;
        }

        incrRefCount(value);
    } else {
        redisPanic("Unknown hash encoding");
    }

    // 更新/添加訓示變量
    return update;
}