Hash 數據結構 使用 ziplist 當同時滿足下麵兩個條件時,使用 ziplist 存儲數據 元素個數少於512個 (hash-max-ziplist-entries: 512) 每個元素長度小於64位元組 (hash-max-ziplist-value: 64) 不滿足上面的條件, 使用 ha ...
Hash 數據結構
- 使用 ziplist
當同時滿足下麵兩個條件時,使用 ziplist 存儲數據- 元素個數少於512個 (hash-max-ziplist-entries: 512)
- 每個元素長度小於64位元組 (hash-max-ziplist-value: 64)
- 不滿足上面的條件, 使用 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
- 為ht[1]分配空間，此時字典同時持有ht[0]和ht[1]
- 將rehashidx設為0，表示rehash正式開始
- 在rehash期間，每次對字典執行任意操作時，程式除了執行對應操作之外，還會順帶將ht[0]在rehashidx索引上的所有鍵值對rehash到ht[1]，操作完後將rehashidx的值 + 1
- Redis本身也會有事件輪詢，哪怕沒有命令訪問，也會通過輪詢事件逐漸完成數據遷移
- 當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 不存在時才會執行
