[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