dict字典--hashtable · 音視頻/C++/k8s/Docker等等學習筆記

[TOC] ## 概述 redis的哈希對象的底層存儲可以使用ziplist（壓縮列表）和hashtable。當hash對象可以同時滿足一下兩個條件時，哈希對象使用ziplist編碼。 * 哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于64字節 * 哈希對象保存的鍵值對數量小于512個當不滿足上述條件時，hash對象的底層數據為`hashtable` ## hashtable數據結構 ```c //節點 typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; /* 指向下一個節點, 鏈接表的方式解決Hash沖突*/ } dictEntry; typedef struct dictht { dictEntry **table; /* dictEntry*數組,Hash表 */ unsigned long size; /* Hash表總大小 */ unsigned long sizemask; /* 計算在table中索引的掩碼, 值是size-1 */ unsigned long used; /* Hash表已使用的大小 */ } dictht; typedef struct dict { dictType *type; void *privdata; dictht ht[2]; /* 兩個hash表,rehash時使用*/ long rehashidx; /* rehash的索引, -1表示沒有進行rehash */ unsigned long iterators; /* number of iterators currently running */ } dict; ``` redis的hash架構就是標準的hashtable的結構，通過掛鏈解決沖突問題。 ## hash存儲過程源碼分析以`hset`命令為例進行分析，整個過程如下： * 首先查看hset中key對應的value是否存在，`hashTypeLookupWriteOrCreate`。 * 判斷`key`和`value`的長度確定是否需要從`zipList`到`hashtable`轉換，`hashTypeTryConversion`。 * 對`key/value`進行`string`層面的編碼，解決內存效率問題。 * `hashTypeSet`,判斷是否使用ziplist或hashtable * 更新`hash`節點中`key/value`問題。 * 其他后續操作的問題判斷`key/value`的長度是否超過規定的長度64個字節，由`REDIS_HASH_MAX_ZIPLIST_VALUE`定義。如果超過64個字節那么久需要將`ziplist`轉成`hashtab`對象。 ``` void hashTypeTryConversion(robj *o, robj **argv, int start, int end) { int i; if (o->encoding != OBJ_ENCODING_ZIPLIST) return; for (i = start; i <= end; i++) { if (sdsEncodedObject(argv[i]) && // #define REDIS_HASH_MAX_ZIPLIST_VALUE 64 sdslen(argv[i]->ptr) > server.hash_max_ziplist_value) { //將對象的編碼轉換成 REDIS_ENCODING_HT hashTypeConvert(o, OBJ_ENCODING_HT); break; } } } ``` `hash`底層的更新操作函數`hashTypeSet`內部會根據是`ziplist`還是`hashtable`進行不同的處理邏輯，在`ziplist`當中會判斷`ziplist`存儲數據的長度來判斷是否需要轉為`hashtable`數據結構，其中長度判斷是通過`#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) { ... // 檢查在添加操作完成之后，是否需要將 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; } ``` ## 漸進式hash說明 * `dict`中`ht[2]`中有兩個`hash`表, 我們第一次存儲數據的數據時, `ht[0]`會創建一個最小為4的`hash`表, * 一旦`ht[0]`中的`size`和`used`相等, 則`dict`中會在`ht[1]`創建一個`size*2`大小的`hash`表, 此時并不會直接將`ht[0]`中的數據`copy`進`ht[0]`中, 執行的是漸進式`rehash` * 即在以后的操作(find, set, get等)中慢慢的`copy`進去, 以后新添加的元素會添加進`ht[0]`, 因此在`ht[1]`被占滿的時候定能確保`ht[0]`中所有的數據全部`copy`到`ht[1]`中.