Redis实现原理(2)--字典
1、 Dict2.1 数据结构定义dict.h
// 哈希表结构
typedef struct dictht {
dictEntry **table; //哈希表数组指针
unsigned long size;//哈希表大小
unsigned long sizemask; //掩码，hash时用到
unsigned long used; //已有节点的数量
} dictht;
//哈希表节点结构
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
} v;// 值，可以是指针类型、uint64和int64
struct dictEntry *next;//指向下一节点形成一个单链表
} dictEntry;
//字典定义
typedef struct dict {
dictType *type;
void *privdata;
dictht ht;
int rehashidx; // 重分布标示-1标示正在重分布中
int iterators; // 重分布进度
} dict;
// 字典类型
// 每个dictType保存了一系列用于操作特定字典的函数，不同用途的字典type不同
typedef struct dictType {
// hash函数
unsigned int (*hashFunction)(const void *key);
// key的复制
void *(*keyDup)(void *privdata, const void *key);
// value的复制
void *(*valDup)(void *privdata, const void *obj);
// key的比较
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// key的销毁
void (*keyDestructor)(void *privdata, void *key);
// value的销毁
void (*valDestructor)(void *privdata, void *obj);
} dictType;
2.2 hash
调用type中得hashFunction方法计算key的hash值，redis内部使用的hash算法为Austin Appleby开发的MurmurHash2算法
h = d->type->hashFunction(key)
计算key的索引值，先在ht中查找，如果没有找到并且在rehash的过程中，则继续在ht中找
idx = h & d->ht.sizemask
对于哈希冲突的解决，redis采取的拉链法，相同索引值的key会存储在一个单链表中，所以确定了索引值以后还需要在对应的单链表中进行搜索
while(he) {
if (dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
2.3 rehash
为了保证字典的使用效率，redis对字典结构采取了定期rehash的机制，因为rehash是重CPU的操作，为了避免过程中出现对外无响应的情况，这里做了一种增量rehash的优化
rehash的流程如下：
1) 新建一个空得hash表，size为第一个大于等于2n的整数
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size)
return i;
i *= 2;
}
2) 将ht中的key重新计算hash和index，索引到ht中，并将ht中相应的索引值置为空
3) 待ht中的数据全部rehash到ht中之后将ht设置为ht，并创建一个新的ht
增量rehash是对步骤2进行优化，每次只rehash一个index的key，并且在rehash过程中对读写操作做限制：
1) 读：先查ht，如果没有再在ht上查找
2) 写：rehash过程中，新的key只向ht中写，并且会将索引所对应的所有key重新hash到ht中。
最终会在某个时间点ht中所有的key重新hash到ht中。
http://www.yancey.info/?p=180
页:
[1]