Hash 數據結構

1. 使用 ziplist
   當同時滿足下面兩個條件時,使用 ziplist 存儲數據
   • 元素個數少于512個 (hash-max-ziplist-entries: 512)
   • 每個元素長度小于64字節 (hash-max-ziplist-value: 64)
2. 不滿足上面的條件, 使用 hashtable

Hash使用 ziplist 圖解

可以看到, 當hash以ziplist編碼存儲時,鍵值對依次按順序存放在ziplist中,key在前,value在后.

Hash使用 hashtable 圖解

哈希表相關的數據結構

//字典
typedef struct dict {
    dictType *type; // 類型特定函數
    void *privdata; // 私有數據
    dictht ht[2]; // 每個字典使用兩個哈希表，實現漸進式 rehash
    int rehashidx;   // rehash 索引,當 rehash 不在進行時，值為 -1
    int iterators; // 目前正在運行的安全迭代器的數量
} dict;

//哈希表
typedef struct dictht {
    dictEntry **table; // 哈希表數組
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩碼，用于計算索引值, 總是等于 size - 1
    unsigned long used; // 該哈希表已有節點的數量
} dictht;

//哈希表節點
typedef struct dictEntry {
    void *key; // 鍵
    union {
        void *val; // 值, 正常是指向一個 redisObject
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next; // 指向下個哈希表節點，形成鏈表 (拉鏈法解決hash沖突)
} dictEntry;

哈希表圖解

漸進式rehash流程

當hashtable需要擴容時,redis使用漸進式rehash

1. 為ht[1]分配空間，此時字典同時持有ht[0]和ht[1]
2. 將rehashidx設為0，表示rehash正式開始
3. 在rehash期間，每次對字典執行任意操作時，程序除了執行對應操作之外，還會順帶將ht[0]在rehashidx索引上的所有鍵值對rehash到ht[1]，操作完后將rehashidx的值 + 1
4. Redis本身也會有事件輪詢，哪怕沒有命令訪問，也會通過輪詢事件逐漸完成數據遷移
5. 當rehashidx的值增加到 ht[0].size，此時ht[0]的所有鍵值對都已經遷移到ht[1]了。程序會把ht[1]賦值給ht[0]，并重新在ht[1]上新建一個空表。將rehashidx重新置為-1，以此表示rehash完成

Redis為什么需要漸進式rehash？

當存在超大的hashTable進行擴容時，如果不去漸進式擴容，單次擴容時間太長,擴容期間Redis服務不可用，將導致線程阻塞

Hash的常用命令

• HSET key field value 將一個或多個field/value插入到哈希表中
• HGET key field 返回key中指定 field 的 value 值
• HKEYS key 返回哈希表 key 中的所有field
• HGETALL key 返回哈希表 key 中，所有的field和value
• HVALS key 返回哈希表 key 中的所有value
• HEXISTS key field 檢查哈希表 key 中，field 是否存在
• HDEL key field 刪除哈希表 key 中的一個或多個field
• HLEN key 返回哈希表 key 中field的數量
• HSETNX key field value ：將哈希表 key 中的 field 的值設置為 value , 僅當 field 不存在時才會執行