Redis 的哈希表 - rehash 详细讲解
Redis 的性能优越, 应用普遍, 可以存储的键值个数大到上亿条记录, 依然保持较高的效率. 作为一个内存数据库, Redis 内部采用了字典 (哈希表) 的数据结构实现了键值对的存储. 随着数据量的不断增加, 数据必然会产生 hash 碰撞, 而 Redis 采用链地址法解决 hash 冲突. 我们知道如果哈希表数据量达到了一个很大的量级, 那么冲突的链的元素数量就会很大, 这时查询效率就会变慢, 因为取值的时候 Redis 会遍历链表. 而随着数据量的缩减, 也会产生一定的内存浪费. Redis 在设计时充分考虑了字典的增加和缩减, 为了优化数据量增加时的查询效率和缩减时的内存利用率, Redis 进行了一系列操作, 而处理的这个过程被称作 rehash.Redis 是在插入新节点之前判断是否需要进行扩容, 如果不需要, 则直接插入, 否则需要先扩容, 再插入新节点.
为了避免对服务器性能造成影响, Redis 使用了一种渐进式哈希的机制来提高字典的缩放效率. 渐进式 rehash 的好处是它采取分而治之的方式, 将 rehash 键值所需的计算工作均摊到对字典的每个添加, 删除, 查找和更新操作上, 从而避免了集中式 rehash 带来的庞大计算量. 比如: 如果哈希表中的数据量达到上百万级别, 进行一次 rehash 会消耗大量的时间, 可能导致服务器在一段时间内停止服务.
存储结构
在 Redis 中, 键值对存储方式是由字典 (dict) 保存的, 而字典底层是通过哈希表来实现. 通过哈希表中的节点保存字典中的键值对.
hash 表的底层数据结构定义:
- // 字典定义
- typedef struct dict{
- dictType *type; //type 和 privdata 是针对不同类型的键值对, 为创建多态字典而设置的
- void *privdata;
- dictht ht[2]; // 两个 hashtable, 用于存储和 rehash
- long rehashidx; // 如果没有进行 rehash, 则值为 - 1, 否则, rehash 表示 rehash 进行到的索引位置
- unsigning long iterators;
- }dict;
- // 哈希表定义
- typedef struct dictht {
- dictEntry **table; // 指针, 指向一个哈希桶 bucket
- unsigning long size; // 哈希表的大小
- unsigning long sizemask; // 总是 size-1, 这个值和哈希值一起决定元素应该定位到桶中的什么位置
- unsigning long used; // 已使用的桶数量
- }dictht;
- // 具体键值对定义
- typedef struct dictEntry{
- void *key; // 键值
- union{
- void *val; //value 值
- unint64_tu64;
- int64_ts64;
- }v;
- struct dictEntry *next; // 指向下一个键值对的指针, 用于解决哈希冲突问题
- }dictEntry;
为什么每个字典中包含两个 hashtable?
首先 Redis 在正常读写时会用到一个 hashtable;
另一个 hashtable 的作用实际上是作为哈希表进行 rehash 时的一个临时载体.
当需要进行扩容时, Redis 会根据数据量和桶的个数初始化那个备用的 hashtable, 来使这个 hashtable 从容量上满足后续的使用, 并开始把之前的 hashtable 的数据迁移到这个新的 hashtable 上(重新计算哈希值), 等到数据全部迁移完毕, 再进行一次 HashTable 的地址更名, 把这个备用的 HashTable 更名为正式的 HashTable, 同时清空另一个 HashTable, 以供下一次 rehash 的使用. 然后将 rehashidx 赋值为 0, 打开渐进式 rehash 标志. 同时该值也标志渐进式 rehash 当前已经进行到哪个 hash 值.
扩容的条件
负载因子 = 哈希表保存的 key 的数量 / 哈希表的大小
当前哈希表中保存的 key 的数量超过了哈希表的大小 size, 并且 Redis 服务当前允许执行 rehash(指的是当前没有子进程在执行 AOF 文件重写或者生成 RDB 文件《持久化操作》);
或者保存的节点数与哈希表的大小的比例超过了安全阈值(默认为 5).
即, 当以下条件中的任意一个被满足时, 程序会自动开始对哈希表执行扩展操作:
服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAPF 命令, 并且哈希表的负载因子>=1;
服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAPF 命令, 并且哈希表的负载因子>=5;.
如果程序正在进行持久化, 这个时候进行 rehash 会导致数据不一致.
缩容的条件
元素个数低于数组长度的 10%.
缩容不会考虑 Redis 是否正在做 bgsave.
渐进式 rehash 初始化
不管是扩容 (包含初始化) 还是缩容, 最终都是调用 dictExpand 函数来完成.
这个函数完成的任务:
判断: 如果当前正在 rehash 或者传进来的扩容参数<当前哈希表中已使用的元素个数, 则返回错误;
计算新的 hash 表大小, 使得新的 hash 表的大小为一个 2 的 n 次方:>= size(传进来的参数)的第一个 2 的 n 次方;
判断: 如果扩容后的大小 == 原来表的大小, 则返回错误;
初始化 ht[1], 并且将 rehashidx 的值设置为 0, 返回正确;
操作辅助 rehash(每当客户端请求时, rehash 一个槽)
在 Redis 中, 每一个增, 删, 改, 查命令中都会判断哈希表是否正在进行扩容, 如果是则帮助执行一次, 调用_dictRehashStep(dict *d)函数.
此函数仅执行一步 hash 表的重散列, 并且仅当没有安全迭代器绑定到哈希表时. 这是因为当我们在重新散列中有迭代器时, 我们不能混淆打算两个哈希表的数据, 否则某些元素可能被遗漏或者重复遍历.
- static void _dictRehashStep(dict *d) {
- if (d->iterators == 0) dictRehash(d,1);
- }
定时辅助 rehash(每次 rehash100 个槽, 但是占用 CPU 的时间不能超过 1ms, 超过则直接退出)
虽然 Redis 实现了在读写操作时, 服务器辅助进行渐进式 rehash 操作, 但是如果服务器比较空闲, Redis 数据库将很长时间内都一直使用两个哈希表. 所以在 Redis 周期函数中, 如果发现有字典正在进行渐进式 rehash 操作, 则会花费 1 毫秒的时间, 帮助一起进行渐进式 rehash 操作.
- /* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
- 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 实现
不管是在操作中辅助 rehash 执行, 还是在周期函数中辅助执行, 最终都是在调用 dictRehash 函数:
- /* Performs N steps of incremental rehashing. Returns 1 if there are still
- * keys to move from the old to the new hash table, otherwise 0 is returned.
- *
- * Note that a rehashing step consists in moving a bucket (that may have more
- * than one key as we use chaining) from the old to the new hash table, however
- * since part of the hash table may be composed of empty spaces, it is not
- * guaranteed that this function will rehash even a single bucket, since it
- * will visit at max N*10 empty buckets in total, otherwise the amount of
- * work it does would be unbound and the function may block for a long time. */
- 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++;
- 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 */
- while(de) {
- uint64_t 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]);
- d->rehashidx = -1;
- return 0;
- }
- /* More to rehash... */
- return 1;
- }
rehash 的步骤
假设 ht[0]为正在使用的 hashtable,ht[1]为备用的 hashtable.
为字典的备用哈希表 ht[1]分配空间(初始化):
如果进行的是扩展操作, 那么 ht[1]的大小为第一个>= 已使用节点数 * 2 的 2^n(2 的 n 次方).
如果进行的收缩操作, 那么 ht[1]的大小为第一个>= 已使用节点数 * 2 的 2^n(2 的 n 次方).
在字典中维持一个索引计数器变量 rehashidx, 并将其值设置为 0, 表示 rehash 工作正式开始(为 - 1 时表示没有进行 rehash);
rehash 进行期间, 每次对字典进行添加, 删除, 查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0]哈希表在 rehashidx 索引上的所有键值对(这个桶中的链表)rehash 到 ht[1], 当一次 rehash 工作完成之后, 程序将 rehashidx 属性的值 + 1. 同时 Redis 会设置一个定时任务, 在 1ms 的时间内, 进行 rehash 处理, 每次仅仅处理少量的转移任务.
随着字典操作的不断执行, 最终在某个时间点上, ht[0]的所有键值对都会被 rehash 到 ht[1]上, 这时程序将 rehashidx 属性的值设置为 - 1, 表示 rehash 操作已经完成.
渐进式 rehash 执行期间的哈希表操作
因为在 rehash 的过程中, 字典会同时使用两个哈希表, 所以在 rehash 期间, 字典的删除, 查找, 更新, 增加等操作会在两个哈希表中进行. 比如:
要在字典中查找某一个键, 程序会现在 ht[0]里面进行查找, 如果没找到, 就会继续到 ht[1]里面进行查找.
如果是添加操作, 则新添加的键值对会一律被保存到 ht[1]中, 而 ht[0]不再进行任何添加操作: 这一措施保证 ht[0]中的键值对数量只减不增, 并且随着操作的执行, 最终变成空表.
渐进式 rehash 带来的问题
渐进式 rehash 避免了 Redis 阻塞(原来进行一次 put 操作, 要等到 rehash 全部结束, 这个操作才会返回, 现在则只需要辅助 rehash 一步), 但是由于在 rehash 时, 需要分配一个新的 hash 表, 在 rehash 期间, 同时有两个 hash 表在使用, 会使得 Redis 内存使用量瞬间突增, 在 Redis 满容状态下由于 Rehash 会导致大量 Key 驱逐.
与 HashMap 的扩容对比
HashMap 采用的不是渐进式扩容, 而是在哈希表插入元素之后, 检查哈希表是否需要扩容, 如果需要的话, 就进行扩容, 扩容完成之后, 返回;
HashMap 只有一个哈希表, 没有备用的;
HashMap 进行扩容的标准是: 当表中元素的总数量>哈希表的大小 * 负载因子 (默认 0.75) 时, 对表进行扩容, 扩容之后大小为原表大小的 2 倍;
HashMap 中引入了红黑树, 当链表长度大于 8 时, 将链表改为红黑树结构, 提高查找效率(从 O(n)->O(logn));
HashMap 是在加入新节点之后, 才判断是否需要扩容; 而 Redis 是在加入节点之前进行判断.
来源: http://www.jianshu.com/p/658365f0abfc