redishash操作场景（阿里技术架构师总结）

redishash操作场景（阿里技术架构师总结）// 计算 key 的哈希值 h = dictHashKey(d key); idx = h & d->ht[table].sizemask; 复制代码 算出来的，同时我们也能看到，当存在键冲突时，查找键的成本static int _dictKeyIndex(dict *d const void *key) { unsigned int h idx table; dictEntry *he; /* Expand the hash table if needed */ // 单步 rehash // T = O(N) if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; /* Compute the key hash value */ // 计算 key 的哈希值 h = dictHashKey(

随着我们的redis操作不断执行，哈希表保存的键值对会逐渐地增多或者减少，当字典内数据过大时，会导致更多的键冲突，造成查询数据的成本增加。当数据减少时，已经分配的内存还在占用，会造成内存浪费。为了让哈希表的负载因子维持在一个合理的范围之内，程序需要对哈希表的大小进行相应的扩展或者收缩。

rehash的原理

• rehash：首先我们看下字典、跟哈希表的结构定义

/* * 字典 */ typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 目前正在运行的安全迭代器的数量 int iterators; /* number of iterators currently running */ } dict; 复制代码 // 哈希表 typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht; 复制代码

通过看结构定义我们先大概了解到，判断一个字段是否正在rehash通过判断 if rehashidx == -1 rehash是在 ht[1] 上从新分配内存，将 ht[0] 的数据迁移到 ht[1]

• 渐进式： rehash的过程不是一次完成的，而是在字典的读写操作，以及定时事件中每次完成一定量的迁移

扩容流程源码分析

因此是字典相关的操作，并且扩容一般存在于需要设置键值的时候，因此我们先直奔 dict.c文件看下是否有Add或者Set字符串内容的函数，通过搜索跟代码查看，我们发现有一个函数的逻辑还是挺像的。

int dictAdd(dict *d void *key void *val) { // 尝试添加键到字典，并返回包含了这个键的新哈希节点 // T = O(N) dictEntry *entry = dictAddRaw(d key); // todo ... } 复制代码

这个函数会调用 dictAddRaw(...) 方法给 dict 分配内存继续查看 dictAddRaw(...) 的代码

dictEntry *dictAddRaw(dict *d void *key) { int index; dictEntry *entry; dictht *ht; // 如果条件允许的话，进行单步 rehash // T = O(1) if (dictIsRehashing(d)) _dictRehashStep(d); /* Get the index of the new element or -1 if * the element already exists. */ // 计算键在哈希表中的索引值 // 如果值为 -1 ，那么表示键已经存在 // T = O(N) if ((index = _dictKeyIndex(d key)) == -1) return NULL; // T = O(1) /* Allocate the memory and store the new entry */ // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表 // 否则，将新键添加到 0 号哈希表 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. */ // 设置新节点的键 // T = O(1) dictSetKey(d entry key); return entry; } 复制代码

继续查看 _dictKeyIndex 内的代码

static int _dictKeyIndex(dict *d const void *key) { unsigned int h idx table; dictEntry *he; /* Expand the hash table if needed */ // 单步 rehash // T = O(N) if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; /* Compute the key hash value */ // 计算 key 的哈希值 h = dictHashKey(d key); // T = O(1) for (table = 0; table <= 1; table ) { // 计算索引值 idx = h & d->ht[table].sizemask; /* Search if this slot does not already contain the given key */ // 查找 key 是否存在 // T = O(1) he = d->ht[table].table[idx]; while(he) { if (dictCompareKeys(d key he->key)) return -1; he = he->next; } // 如果运行到这里时，说明 0 号哈希表中所有节点都不包含 key // 如果这时 rehahs 正在进行，那么继续对 1 号哈希表进行 rehash if (!dictIsRehashing(d)) break; } // 返回索引值 return idx; } 复制代码

通过查看上述代码，我们可以发现几处关键点，字典内索引值的计算时通过

// 计算 key 的哈希值 h = dictHashKey(d key); idx = h & d->ht[table].sizemask; 复制代码

算出来的，同时我们也能看到，当存在键冲突时，查找键的成本

he = d->ht[table].table[idx]; while(he) { if (dictCompareKeys(d key he->key)) return -1; he = he->next; } 复制代码

最关键的是 _dictExpandIfNeeded 通过函数名我们就觉得这个跟扩容有关

static int _dictExpandIfNeeded(dict *d) { /* Incremental rehashing already in progress. Return. */ // 渐进式 rehash 已经在进行了，直接返回 if (dictIsRehashing(d)) return DICT_OK; /* If the hash table is empty expand it to the initial size. */ // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表 // T = O(1) 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. */ // 一下两个条件之一为真时，对字典进行扩展 // 1）字典已使用节点数和字典大小之间的比率接近 1：1 // 并且 dict_can_resize 为真 // 2）已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { // 新哈希表的大小至少是目前已使用节点数的两倍 // T = O(N) return dictExpand(d d->ht[0].used*2); } return DICT_OK; } 复制代码

通过上述代码可以看到，最根本的内存分配操作是在 _dictExpandIfNeeded(...) 函数内执行的。该函数会判断当哈希表上已使用键值数比分配内存大 dict_force_resize_ratio (代表常量5)倍时 会重新分配内存，内存大小时原来已使用数的2倍。

总结

• 整个源码流程看完，我们发现在执行 dictAdd(...) 向字典内增加键值时，会调用 _dictExpandIfNeeded(...) 查看 ht[0].used/ht[0].size > 5 是否为 true 如果是则重新分配内存，大小为 ht[0].used * 2
• 在查看 dictAddRaw(...) 函数代码时，有一处命令

// 如果条件允许的话，进行单步 rehash // T = O(1) if (dictIsRehashing(d)) _dictRehashStep(d); 复制代码

_dictRehashStep 的作用是，执行一个键值从 h[0] 到 h[1] 的迁移，在 dict.c 内搜索该函数，会发现跟dict相关的读写操作都会调用该函数，这也验证rehahs的过程不是一步完成的，是渐进式的

收缩流程源码分析

字典内存的收缩主要是在定时事件内，定时检查，判断，相关代码如下

void databasesCron(void) { // todo ... // 在没有 BGSAVE 或者 BGREWRITEAOF 执行时，对哈希表进行 rehash if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) { /* We use global counters so if we stop the computation at a given * DB we'll be able to start from the successive in the next * cron loop iteration. */ static unsigned int resize_db = 0; static unsigned int rehash_db = 0; unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL; unsigned int j; /* Don't test more DBs than we have. */ // 设定要测试的数据库数量 if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum; /* Resize */ // 调整字典的大小 for (j = 0; j < dbs_per_call; j ) { tryResizeHashTables(resize_db % server.dbnum); resize_db ; } /* Rehash */ // 对字典进行渐进式 rehash if (server.activerehashing) { for (j = 0; j < dbs_per_call; j ) { int work_done = incrementallyRehash(rehash_db % server.dbnum); rehash_db ; if (work_done) { /* If the function did some work stop here we'll do * more at the next cron loop. */ break; } } } } } 复制代码

上述代码除了循环和判断外，有两个比较特别的函数

1. tryResizHashTables 相关源码

void tryResizeHashTables(int dbid) { if (htNeedsResize(server.db[dbid].dict)) dictResize(server.db[dbid].dict); if (htNeedsResize(server.db[dbid].expires)) dictResize(server.db[dbid].expires); } //htNeedsResize int htNeedsResize(dict *dict) { long long size used; size = dictSlots(dict); used = dictSize(dict); return (size && used && size > DICT_HT_INITIAL_SIZE && (used*100/size < REDIS_HT_MINFILL)); } 复制代码

通过分析源码，我们可以看到该函数会首先调用 htNeedsResize ，判断 used* 100 / size < REDIS_HT_MINFILL 如果是true则会调用 dictResize 重新分配内存

1. incrementallyRehash 相关源码

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); return 1; /* already used our millisecond for this loop... */ } return 0; } //dictRehashMillisecnods /* 在给定毫秒数内，以 100 步为单位，对字典进行 rehash 。 * * T = O(N) */ 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; } 复制代码

通过分析，可以看出该函数的作用，是对正在rehash的字典，每次执行1毫秒，每次循环100次的哈希表数据迁移。

总结

• 哈希表的收缩主要是在定时事件内执行
• 当已使用的键值占比不到分配内存的0.1时，就进行内存收缩
• 除了在上面扩容中说到的在进行读写时会进行数据迁移，在定时件事内也会进行数据迁移。同时可以避免，长时间没有读写操作，数据一直无法迁移的问题

需要的Java架构师方面的资料可以关注之后私信哈，回复“资料”领取免费架构视频资料，记得要点赞转发噢！！！