[redis設計與實作][3]基本資料結構——字典

redis字典采用哈希表實作。

哈希表：

[cce lang=”c”]

typedef struct dictht {

//哈希表數組

dictentry **table;

//哈希表大小

unsigned long size;

//哈希表掩碼，用于計算索引值，總是等于size – 1

unsigned long size mask;

//已有的節點數量

unsigned long used;

} dictht;

[/cce]

哈希表節點：

typedef struct dictentry {

//鍵

void *key;

//值

union {

void *val;

uint64_t u64;

int64_t s64;

double d;

} v;

//下一個哈希表節點

struct dictentry *next;

} dictentry;

字典：

typedef struct dict {

//類型特定的函數

dicttype *type;

//私有資料

void *privdata;

//哈希表

dictht ht[2];

long rehashidx; /* rehashing not in progress if rehashidx == -1 */

int iterators; /* number of iterators currently running */

} dict;

* type屬性是一個指向dicttype結構的指針，每個dicttype結構儲存了一簇用于操作特定類型鍵值對的函數

* privdata儲存了需要傳給類型特定函數的可選參數

typedef struct dicttype {

//計算哈希值的函數

unsigned int (*hashfunction)(const void *key);

//複制鍵的函數

void *(*keydup)(void *privdata, const void *key);

//複制值的函數

void *(*valdup)(void *privdata, const void *obj);

//對比鍵的函數

int (*keycompare)(void *privdata, const void *key1, const void *key2);

//銷毀鍵的函數

void (*keydestructor)(void *privdata, void *key);

//銷毀值的函數

void (*valdestructor)(void *privdata, void *obj);

} dicttype;

ht屬性包含兩個項的數組。一般情況下隻使用ht[0]哈希表，ht[1]哈希表隻在對ht[0]進行rehash的時候才會使用。

雜湊演算法：

計算：

hash = dict->type->hashfunction(key)

index = hash & dict->ht[x].sizemask

當字典被用作資料庫的底層實作，或者哈希鍵的底層實作時，redis使用murmurhash2（https://code.google.com/p/smhasher/wiki/murmurhash2）算法計算鍵的哈希值。

int dictadd(dict *d, void *key, void *val);

int dictadd(dict *d, void *key, void *val)

{

dictentry *entry = dictaddraw(d,key);

if (!entry) return dict_err;

dictsetval(d, entry, val);

return dict_ok;

}

dictentry *dictaddraw(dict *d, void *key)

int index;

dictentry *entry;

dictht *ht;

//#define dictisrehashing(d) ((d)->rehashidx != -1)

if (dictisrehashing(d)) _dictrehashstep(d);

/* get the index of the new element, or -1 if

* the element already exists. */

if ((index = _dictkeyindex(d, key)) == -1)

return null;

/* allocate the memory and store the new entry */

ht = dictisrehashing(d) ? &d->ht[1] : &d->ht[0];

entry = zmalloc(sizeof(*entry));

entry->next = ht->table[index];

ht->table[index] = entry;

ht->used++;

/* set the hash entry fields. */

dictsetkey(d, entry, key);

return entry;

static int _dictkeyindex(dict *d, const void *key)

unsigned int h, idx, table;

dictentry *he;

/* expand the hash table if needed */

if (_dictexpandifneeded(d) == dict_err)

return -1;

/* compute the key hash value */

//#define dicthashkey(d, key) (d)->type->hashfunction(key)

h = dicthashkey(d, key);

for (table = 0; table <= 1; table++) {

idx = h & d->ht[table].sizemask;

/* search if this slot does not already contain the given key */

he = d->ht[table].table[idx];

while(he) {

//比較key是否已經存在，已經存在傳回-1

if (dictcomparekeys(d, key, he->key))

he = he->next;

if (!dictisrehashing(d)) break;

return idx;

static int _dictexpandifneeded(dict *d)

/* incremental rehashing already in progress. return. */

if (dictisrehashing(d)) return dict_ok;

/* if the hash table is empty expand it to the initial size. */

//#define dict_ht_initial_size 4

if (d->ht[0].size == 0) return dictexpand(d, dict_ht_initial_size);

/* if we reached the 1:1 ratio, and we are allowed to resize the hash

* table (global setting) or we should avoid it but the ratio between

* elements/buckets is over the “safe” threshold, we resize doubling

* the number of buckets. */

//static unsigned int dict_force_resize_ratio = 5;

/*

dict_can_resize設定：

void updatedictresizepolicy(void) {

if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)

dictenableresize();

else

dictdisableresize();

當有同步硬碟程序的時候改成不能擴充

*/

if (d->ht[0].used >= d->ht[0].size &&

(dict_can_resize ||

d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))

return dictexpand(d, d->ht[0].used*2);

int dictexpand(dict *d, unsigned long size)

dictht n; /* the new hash table */

unsigned long realsize = _dictnextpower(size);

/* the size is invalid if it is smaller than the number of

* elements already inside the hash table */

if (dictisrehashing(d) || d->ht[0].used > size)

return dict_err;

/* allocate the new hash table and initialize all pointers to null */

n.size = realsize;

n.sizemask = realsize-1;

n.table = zcalloc(realsize*sizeof(dictentry*));

n.used = 0;

/* is this the first initialization? if so it’s not really a rehashing

* we just set the first hash table so that it can accept keys. */

if (d->ht[0].table == null) {

d->ht[0] = n;

/* prepare a second hash table for incremental rehashing */

d->ht[1] = n;

d->rehashidx = 0;

int dictreplace(dict *d, void *key, void *val);

/* add an element, discarding the old if the key already exists.

* return 1 if the key was added from scratch, 0 if there was already an

* element with such key and dictreplace() just performed a value update

* operation. */

int dictreplace(dict *d, void *key, void *val)

dictentry *entry, auxentry;

/* try to add the element. if the key

* does not exists dictadd will suceed. */

if (dictadd(d, key, val) == dict_ok)

return 1;

/* it already exists, get the entry */

entry = dictfind(d, key);

/* set the new value and free the old one. note that it is important

* to do that in this order, as the value may just be exactly the same

* as the previous one. in this context, think to reference counting,

* you want to increment (set), and then decrement (free), and not the

* reverse. */

auxentry = *entry;

dictfreeval(d, &auxentry);

return 0;

dictentry *dictfind(dict *d, const void *key)

if (d->ht[0].size == 0) return null; /* we don’t have a table at all */

return he;

if (!dictisrehashing(d)) return null;

int dictrehash(dict *d, int n);

int dictrehash(dict *d, int n) {

if (!dictisrehashing(d)) return 0;

while(n–) {

dictentry *de, *nextde;

/* check if we already rehashed the whole table… */

//已經完成hash，釋放ht[0]。将ht[0]指向ht[1]

if (d->ht[0].used == 0) {

zfree(d->ht[0].table);

d->ht[0] = d->ht[1];

_dictreset(&d->ht[1]);

d->rehashidx = -1;

/* note that rehashidx can’t overflow as we are sure there are more

* elements because ht[0].used != 0 */

assert(d->ht[0].size > (unsigned long)d->rehashed);

//如果rehash索引為空，跳過

while(d->ht[0].table[d->rehashidx] == null) d->rehashidx++;

de = d->ht[0].table[d->rehashidx];

/* move all the keys in this bucket from the old to the new hash ht */

//移動一個桶裡面的所有key到新的哈希表

while(de) {

unsigned int 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++;

//為了防止占用太多的cpu時間，限制一次rehash的cpu時間

int dictrehashmilliseconds(dict *d, int ms) {

long long start = timeinmilliseconds();

int rehashes = 0;

while(dictrehash(d,100)) {

rehashes += 100;

if (timeinmilliseconds()-start > ms) break;

return rehashes;

調用者（redis.c）：每次嘗試漸進式rehash執行1ms

int incrementallyrehash(int dbid) {

/* keys dictionary */

if (dictisrehashing(server.db[dbid].dict)) {

dictrehashmilliseconds(server.db[dbid].dict,1);

return 1; /* already used our millisecond for this loop… */

/* expires */

if (dictisrehashing(server.db[dbid].expires)) {

dictrehashmilliseconds(server.db[dbid].expires,1);

轉載自：https://coolex.info/blog/439.html