写在前面
以下内容是基于Redis 6.2.6 版本整理总结
一、Redis 数据结构hash的编码格式
Redis中hash数据类型使用了两种编码格式:ziplist(压缩列表)、hashtable(哈希表)
在redis.conf配置文件中,有以下两个参数,意思为:当节点数量小于512并且字符串的长度小于等于64时,会使用ziplist编码。
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
二、压缩链表(ziplist)
ziplist 我们整理在下一篇文章。
三、哈希表(hashtable)
Redis中的字典(dict)使用哈希表作为的底层实现,一个哈希表里可以有多个哈希表的节点,每个节点保存字典中的一个键值对。
哈希表结构定义如下:
typedef struct dictht {
dictEntry **table; // 哈希表数组 每个元素都是 dictEntry 的指针,指向 dictEntry;
unsigned long size; // 哈希表大小
unsigned long sizemask; // 用来计算索引值 always: sizemask = size - 1
unsigned long used; // 哈希表已有节点的数量
} dictht;
哈希表节点定义如下:
哈希表节点使用 dictEntry 结构表示,每个 dictEntry 结构都保存着一个键值对和冲突后的链表的下一个节点。
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 保存下一个 dictEntry 的地址,形成链表
} dictEntry;
其中,value 是一个联合体,可以保存多种数据类型。当value类型为 uint64_t 、int64_t 或 double时可以直接存储。其他类型需要在其他位置申请一段空间来存放,并用val指向这段空间来使用。
字典结构定义如下:
// location: dict.h
typedef struct dict {
dictType *type; // 指向 dictType 结构的指针
void *privdata; // 存储私有数据的指针,在 dictType 里面的函数会用到
dictht ht[2]; // 两个哈希表,扩容时使用,后面会结合源码详细说明
long rehashidx; // 值为-1时,表示没有进行rehash,否则保存rehash执行到那个元素的数组下标
int16_t pauserehash; // >0 表示rehash暂停,<0 表示编码错误
} dict;
dictType 结构定义如下
dictType 结构体定义了一系列操作key-value键值对的方法的函数指针,在实际运行时传入指定函数,就能实现预期的功能,有点运行时多态绑定的味道。
// 操作特性键值对的函数簇
typedef struct dictType {
uint64_t (*hashFunction)(const void *key); // 计算哈希值的函数
void *(*keyDup)(void *privdata, const void *key); // 复制key的函数
void *(*valDup)(void *privdata, const void *obj); // 复制value的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 对比key的函数
void (*keyDestructor)(void *privdata, void *key); // 销毁key的函数
void (*valDestructor)(void *privdata, void *obj); // 销毁value的函数
int (*expandAllowed)(size_t moreMem, double usedRatio); // 扩容
} dictType;
字典整体结构可以用下图来描述:
3.1 hash冲突
当两个或两个以上的键被分配到哈希数组的同一个索引上面时,我们称这些键发生了冲突。Redis的哈希表使用拉链法解决hash冲突。
3.2 负载因子
负载因子 = used / size ; used 是哈希数组存储的元素个数,size 是哈希数组的长度。
负载因子越小,冲突越小;负载因子越大,冲突越大。
3.3 rehash
随着命令的不断执行,哈希表保存的减值对会逐渐增加或者减少,为了让哈希表的负载因子维持在一个合理的范围内,当哈希表中的键值对过多或过少时,需要对哈希表的大小进行相应的扩展和收缩。而哈希表的扩展和收缩可以通过rehash来执行。rehash 就是将 ht[0] 中的节点,通过重新计算哈希值和索引值放到 ht[1] 哈希表指定的位置上。
扩容
- 如果负载因子大于1,就会触发扩容,扩容的规则是每次翻倍;
- 如果正在fork,执行持久化则不会扩容,但是,如果负载因子大于5,会立马扩容。
缩容
如果负载因子小于0.1,就会触发缩容。缩容的规则是:恰好包含used的2^n。
3.4 渐进式rehash
当哈希表中的元素过多时,如果一次性rehash到ht[1],庞大的计算量,可能导致redis服务在一段时间不可用。为了避免rehash对服务器带来的影响,redis分多次、慢慢的将ht[0]哈希表中的键值对rehash到ht[1]哈希表,这就是渐进式rehash。
核心思想:将整个rehash过程均摊到每次命令的执行中。
rehash的详细步骤:
- 为 ht[1] 哈希表分配空间,此时字典同时拥有ht[0] 和 ht[1] 两个字典
- 将字典中的rehashidx设置为0,表示开始rehash
- 在rehash期间,每次对字典的增删改查,除了执行指定的命令外,还会顺带将ht[0] 中 rehashidx 索引上的所有键值对都rehash到ht[1]中,执行完rehash,rehashidx属性加一。注意:新增的键值对只能插入到ht[1]哈希表中,保证ht[0]的键值对只减不增。
- 随着操作的不断进行,最终ht[0]哈希表中的所有键值对都被rehash到ht[1]中。此时,将ht[0]释放掉,让ht[0] 指向ht[1],并设置rehashidx 为 -1,表示rehash完成。
四、字典常用 API
// 创建字典
dict *dictCreate(dictType *type, void *privDataPtr);
// 将键值对 key-val 插入到字典
int dictAdd(dict *d, void *key, void *val);
// 删除字典中指定 key 的键值对
int dictDelete(dict *d, const void *key);
// 获取指定key的value值
void *dictFetchValue(dict *d, const void *key);
// 将键值对 key-val 插入到字典,如果该key已经存在,则只更新val
int dictReplace(dict *d, void *key, void *val);
五、Rehash源码分析
5.1 添加元素步骤
// 1. 通过hash函数得到hash值
hash = dict->type->hashFunction(key);
// 2. 将hash值与对应哈希表的sizemask 进行 & 操作得到index
index= hash & d->ht[x].sizemask; // x = 0 or 1
// 3. 创建 dictEntry 节点,头插法插入到对应哈希表的index的位置
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
添加元素源码分析
redis使用 dictAdd() 方法往哈希表中添加元素。dictAdd 调用的是 dictAddRaw 方法,它会先通过_dictKeyIndex() 函数计算出table的index;再通过头插法将该节点插入到目标位置。
dictAdd() 函数
/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
// 将 val 保存到 entry 节点
dictSetVal(d, entry, val);
return DICT_OK;
}
dictAddRaw() 函数
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. */
// 计算index
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
/* Allocate the memory and store the new entry.
* Insert the element in top, with the assumption that in a database
* system it is more likely that recently added entries are accessed
* more frequently. */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
// 头插法 最快
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
// 将 key 保存在 entry 节点中
dictSetKey(d, entry, key);
return entry;
}
其中,在_dictKeyIndex() 函数计算index的时候,会调用 _dictExpandIfNeeded() 函数判断是否满足扩容的条件。其中有个条件是依赖于 dictTypeExpandAllowed(d) 的返回值。
_dictKeyIndex() 函数
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
/* Expand the hash table if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
for (table = 0; table <= 1; table++) {
idx = hash & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (existing) *existing = he;
return -1;
}
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
_dictExpandIfNeeded() 函数
/* Expand the hash table if needed */
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) &&
dictTypeExpandAllowed(d))
{
return dictExpand(d, d->ht[0].used + 1);
}
return DICT_OK;
}
dictTypeExpandAllowed() 函数
static int dictTypeExpandAllowed(dict *d) {
if (d->type->expandAllowed == NULL) return 1;
return d->type->expandAllowed(
_dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),
(double)d->ht[0].used / d->ht[0].size);
}
可以看到,如果 dictType 中没有设置 expandAllowed 函数,则直接返回真;如果设置了expandAllowed 函数,就需要执行完相应的函数才能确定是否可以扩缩容。这就是 dictType 的一个典型的应用场景。
5.2 rehash 源码分析
该函数每次从rehashidx开始的位置,固定扫描 10 个bucket,如果对应的bucket中有数据就 rehash 到 ht[1]中。文章来源:https://www.toymoban.com/news/detail-425469.html
static void _dictRehashStep(dict *d) {
if (d->pauserehash == 0) dictRehash(d,1);
}
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
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++;
// 如果 经过 n*10 次,还是为空,本次rehash结束
if (--empty_visits == 0) return 1;
}
// 找到要rehash的bucket
de = d->ht[0].table[d->rehashidx];
// 遍历该bucket对应的dictEntry链表
while(de) {
uint64_t h;
nextde = de->next;
// 为该dictEntry 获取在ht[1]中的index
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 头插法 de->next 指向 ht[1].table[h]的第一个元素 (可能为NULL,可能有元素)
de->next = d->ht[1].table[h];
// 更新ht[1].table[h]的值指向该 dictEntry
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde; // 更新de,继续遍历,直至为空
}
// 将ht[0]中 d->rehashidx 对应的bucket清空
d->ht[0].table[d->rehashidx] = NULL;
// 更新rehashidx
d->rehashidx++;
}
// 检查整个ht[0]表,rehash是否完成
if (d->ht[0].used == 0) {
zfree(d->ht[0].table); // 释放ht[0]
d->ht[0] = d->ht[1]; // 让ht[0] 指向 rehash后的 ht[1]
_dictReset(&d->ht[1]); // 重置 ht[0], 以备下次rehash
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
文章参考与<零声教育>的C/C++linux服务期高级架构系统教程学习文章来源地址https://www.toymoban.com/news/detail-425469.html
到了这里,关于Redis数据结构之——hash的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!