一口气读完了redis的基本类型相关代码，是时候好好静下心思来整理整理了。
字典在高级语言十分常见，C++有map类型，Python有dict类型等，C没有字典这种类型，因此Redis实现了字典。字典主要由值和键的映射组成，称为键值对，字典中的每个键都是独一无二的。字典在Redis中的应用十分广泛，后续将会体现出来。
涉及的主要代码
dict.hdict.c
dict的定义
//哈希表节点
typedef struct dictEntry {
void *key; //字典中的key
union { //union结构体，字典中的值，可以为一个void指针、无符号整型，有符号整型、浮点数
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; //键冲突的形成一个链表结构
} dictEntry;
//类型特定函数
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;
//hash table 哈希表
typedef struct dictht {
dictEntry **table; //哈希表节点指针数组
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表掩码，sizemask = size - 1
unsigned long used; //已有节点数量
} dictht;
//字典
typedef struct dict {
dictType *type; // 类型特定函数结构指针
void *privdata; // 私有数据，调用dictType中函数的时候需要传入
dictht ht[2]; // 哈希表，dictht[0]用来存储数据，dictht[1]用来rehash是重新使用
long rehashidx; /* rehashing not in progress if rehashidx == -1 */ //记录rehash到哪一个哈希表节点（类似于数组index）
int iterators; /* number of iterators currently running */ //正在运行的迭代器数量
} dict;
字典.png
如图所示，这个字典结构由多个层级组成，分别有哈希表节点、哈希表、字典组成。
哈希表节点
最底层的是哈希表节点dictEntry，dictEntry中保存着键值对，key属性保存着键，它是一个空类型指针，意味着可以使用任何类型作为键；v属性保存着值，它是一个结构体，可以是一个空类型指针，亦或者是一个无符号整型，亦或者是一个有符号整型，亦或者是一个浮点数。next属性是指向下一个dictEntry节点的值，可以将多个键冲突的键值对用next连接在一起，形成一个链表，以此来解决键冲突的问题。
哈希表
dictht表示哈希表，多个dictEntry链表由dictht中的table属性管理，dictht中size表示了table数组的大小，sizemask用来计算索引值，通常等于size-1；used属性记录该dictht包含的键值对数量，图中展示了table大小为4，键值对数量为3的dictht结构。
字典
图中总共有2个dictht结构，通常dict只是用其中一个dictht，另一个不使用；只有在进行rehash的时候，才会使用到另一个dictht结构，后面会讲到rehash的过程。dict表示字典，这个是我们所见到的字典对象，dict来管理dictht（属性ht），该结构还包含了关于字典的一些其他信息；type属性是一个dictType对象，它包含了一些关于键和值的操作，如复制、比较、销毁等，与private属性相结合就可以实现多态字典；rehashidx用来表示是否正在进行hash以及hash的进度；iterator表示当前正在运行的迭代器数量。
dict实现细节
哈希算法
要将一个键值对方到字典中，首先需要通过键算出一个hash值，然后再通过hash值算出一个索引值，接着根据索引，找到键值要插入对应的哈希表中。
对应的伪代码如下：
hash = dict->type-> hashFunction(key);
index = hash & dict->dictht[x].sizemask; //ht[x]根据是否在rehash，可能是ht[0]，也可能是ht[1]
根据key所指向的类型，redis提供了以下几种hash算法：
-
unsigned int dictIntHashFunction(unsigned int key)，不过该函数没有在源码看到有被调用； -
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len)； -
unsigned int dictGenHashFunction(const void *key, int len)。
其中，dictGenHashFunction函数使用了MurmurHash2算法，具体原来还没有详细研究，待整体代码看完后得空在来研究，若有兴趣可以看下MurmurHash，**该算法能够在有规律的输入情况下，仍然能够保持很好的随机分布性。
键冲突
键冲突是指不同的键算出了相同的索引。Redis使用链表来解决键冲突的问题，即算出同一个索引值的键值用next指针连接起来构成一个单向链表。当一个键值对进来时，先要计算出其索引，然后在dictht[0]（根据是否在rehash来决定是否需要在dictht[1]中寻找）中寻找该键是否存在，如果不存在，都将其插入到对应的链表头结点。
#define dictIsRehashing(d) ((d)->rehashidx != -1) //判断当前是否在hash阶段
/* Add an element to the target hash table */
//添加一个键值对
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节点，并返回其地址，上层来设置key
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d); //如果正在rehash中，那么rehash一个slot
/* 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]; //如果正在rehash，选择ht[1]插入
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;
}
//返回所在的slot
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 */
h = dictHashKey(d, key); //获取key的hash
for (table = 0; table <= 1; table++) { //两个ht都要寻找
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) {
if (dictCompareKeys(d, key, he->key)) //比较键值
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break; //如果不是在rehash过程中，ht[1]可以不用寻找
}
return idx;
}
哈希表的扩张和收缩
负载因子的计算：
factor = used/size，哈希表大小变化的最终是使得负载因子小于1。
哈希表大小的变化总是在dictht[1]上面进行操作的，其要变化后的大小与当前字典包含的键值对数量有关：
- 扩张操作：
dictht[1]的大小为第一个大于等于dict[0].used*2的2^n； - 收缩操作：
dictht[1]的大小为第一个大于等于dict[0].used的2^n；
//计算实际要创建的实际大小，添加键值对时会调用
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. */
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. */
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);
}
return DICT_OK;
}
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE; //4，也是table数组长度最小的值
if (size >= LONG_MAX) return LONG_MAX;
//以2的n次方倍扩张
while(1) {
if (i >= size)
return i;
i *= 2;
}
}
//重新设置table的大小，使得其负载因子小于1，通常在rehash之前调用，调整dictht[1]
//dictResize->dictExpand
int dictResize(dict *d)
{
int minimal;
if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
minimal = d->ht[0].used;
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE;
return dictExpand(d, minimal);
}
/* Expand or create the hash table */
//实际扩大dict的slot到指定大小
int dictExpand(dict *d, unsigned long size)
{
dictht n; /* the new hash table */
unsigned long realsize = _dictNextPower(size); //获得resize后实际的新大小，通常是2^n的大小
/* 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) //通常要求新的长度要比1已拥有的键值数量大并且该dict不能正在rehahs中
return DICT_ERR;
/* Rehashing to the same table size is not useful. */
if (realsize == d->ht[0].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*)); //分配slot
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. */
//如果ht[0]没有数据，则直接赋值给ht[0]
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
/* Prepare a second hash table for incremental rehashing */
d->ht[1] = n;
d->rehashidx = 0; //准备rehash
return DICT_OK;
}
rehash
当哈希表需要进行长度变化，首先设置dictht[1]到所需要的大小，然后将dictht[0]上的所有键值迁移到dictht[1]上，迁移完成之后，释放dictht[0]，将dictht[1]的值赋值给dictht[0]，然后为dictht[1]创建一个空白的哈希表。整个过程就是rehash。
//rehash 字典，n表示此处rehash的bucket，n表示最多可连续空转 n*10个bucket
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */ //最多轮过n*10个空bucket
if (!dictIsRehashing(d)) return 0;
//最多rehash n个bucket
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* 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->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++; //通过rehashidx来指定当前rehash的进度
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
//bucket上面的每个节点进行迁移
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++;
}
/* Check if we already rehashed the whole table... */
//已经迁移完成
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]); //重置ht[1]
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
rehash过程图解：
rehash之前
扩张长度
节点迁移完成
rehash完成
当dict中节点比较少时，进行rehash的速度是很快的，但如果dict中节点达到百万、千万、甚至亿的时候，如果只进行一次性rehash，会导致服务不可用一段时间（因为redis是单进程处理请求的）。因此，redis进行rehash并不是一次性集中完成，而是渐进式、逐步的地完成迁移。
渐进式rehash的过程：
- 在操作哈希表的过程中，发现需要扩大哈希表大小，因此计算要扩展的大小，分配空间给
dictht[1]; -
dictht[1]分配完毕后，设置dict->rehashidx为0，表示dict要开始rehash，rehash的过程中，dict->rehashidx表示当前rehash的进度（已经rehash到dictht[0]->table[rehashidx]）； - 在添加、删除、查询等操作的过程中，每次rehahs一个
dictEntry链表，新增的节点总是添加到dictht[1]哈希表中。 - 最终，
dictht[0]上的所有键值对都迁移到dictht[1]上，然后释放dictht[0]，将dict->ht[1]的值赋值给dict->ht[0]，重新申请空的hash表给dict->ht[1]，置dict->rehashidx=-1表示rehash完成。
可以看出，渐进式rehash将rehash过程分散到各种操作上，避免了一次性rehash带来的性能问题。
添加、删除、查找等都包含下面一段代码：
if (dictIsRehashing(d)) _dictRehashStep(d); //如果正在rehash中，那么rehash一个slot
删除键值对
如果在rehash过程中，需要寻找dictht[0]和dictht[1]，因为之前新添加的键值对是直接在dictht[1]中的。
/* Search and remove an element */
//删除键值对，nofree表示是否释放锁找到的key和value
static int dictGenericDelete(dict *d, const void *key, int nofree)
{
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
if (dictIsRehashing(d)) _dictRehashStep(d); //惰性hash
h = dictHashKey(d, key); //获取键的hash
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
while(he) {
if (dictCompareKeys(d, key, he->key)) { //比较键
/* Unlink the element from the list */
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
}
zfree(he);
d->ht[table].used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break; //如果不在hash中，就没有必要
}
return DICT_ERR; /* not found */
}
//从dict中提出并删除寻找到的键值
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0);
}
//从dict中剔除，但返回dictEntry
int dictDeleteNoFree(dict *ht, const void *key) {
return dictGenericDelete(ht,key,1);
}
查找键值对
如果在rehash过程中，需要在dictht[0]和dictht[1]中分别寻找，因为之前新添加的键值对是直接在dictht[1]中的。
//寻找key对应的dictEntry
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;
if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
if (dictIsRehashing(d)) _dictRehashStep(d); //惰性rehash
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
//获取键所对应的值
void *dictFetchValue(dict *d, const void *key) {
dictEntry *he;
he = dictFind(d,key);
return he ? dictGetVal(he) : NULL;
}
总结
- Redis的字典带有两个哈希表，另一个哈希表使用来做reahsh用；
- rehash不是一次性、集中式的，而是渐进的；
- Redis使用单链表来解决键冲突的问题。
字典主要API
| function | description | time complexity |
|---|---|---|
| dictCreate | 创建字典 | O(1) |
| dictAdd | 添加键值对 | O(1) |
| dictReplace | 如果存在键值对则更新，否则插入 | O(1) |
| dictDelete | 删除给定键值对 | O(1) |
| dictRelease | 释放给定字典 | O(N) |
| dictFind | 寻找键值对 | O(1) |
| dictGetRandomKey | 随机获取键值对 | O(1) |
网友评论