redis的rehash

redis的rehashredis支持的数据结构有: 

  1. string 字符串(可以为整形、浮点型和字符串,统称为元素),String类型是二进制安全的,意思是 redis 的 string 可以包含任何数据。
  2. List  链表(redis 使用双端链表实现的 List),是有序的,value可以重复,可以通过下标取出对应的value值,左右两边都能进行插入和删除数据。
  3. set 集合保存多个字符串的元素,但和列表不同的是集合中  1. 不允许有重复的元素,2.集合中的元素是无序的,不能通过索引下标获取元素,3.支持集合间的操作,可以取多个集合取交集、并集、差集。
  4. dict 散列值(hash map的key必须是唯一的)
  5. zset 有序集合,保留了集合不能有重复成员的特性,区别是,有序集合中的元素是可以排序的,它给每个元素设置一个分数,作为排序的依据。

其中dict是使用频率相当高,也是非常实用的一种结构,使用哈希表作为底层实现, 一个哈希表里面可以有多个哈希表节点, 而每个哈希表节点就保存了字典中的一个键值对,哈希表中的键值对随着不断进行的操作增加或减少,为了将哈希表的负载因子维持在较为合理的范围内,程序需对哈希表的大小进行相应的扩展或者收缩。在redis的具体实现中,使用了一种叫做渐进式哈希(rehashing)的机制来提高dict的缩放效率。

源码解说

dict的数据结构定义:


/* 哈希表节点 */
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;
} dictEntry;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
/* 哈希表
 * 每个字典都使用两个哈希表,以实现渐进式 rehash 。
 */
typedef struct dictht {
    // 哈希表数组
    // 可以看作是:一个哈希表数组,数组的每个项是entry链表的头结点(链地址法解决哈希冲突)
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;
/* 字典 */
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;

dict的结构大致如上,接下来分析一下其中最重要的几个数据成员:

  1. dictht::table:哈希表内部的table结构使用了链地址法来解决哈希冲突,刚开始看的时候我很奇怪,这怎么是个二维数组?这其实是一个指向数组的指针,数组中的每一项都是entry链表的头结点。
  2. dictht ht[2]:在dict的内部,维护了两张哈希表,作用等同于是一对滚动数组,一张表是旧表,一张表是新表,当hashtable的大小需要动态改变的时候,旧表中的元素就往新开辟的新表中迁移,当下一次变动大小,当前的新表又变成了旧表,以此达到资源的复用和效率的提升。
  3. rehashidx:因为是渐进式的哈希,数据的迁移并不是一步完成的,所以需要有一个索引来指示当前的rehash进度。当rehashidx为-1时,代表没有哈希操作。
     

rehash的主体部分:

/* 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是以bucket(桶)为基本单位进行渐进式的数据迁移的,每步完成一个bucket的迁移,直至所有数据迁移完毕。一个bucket对应哈希表数组中的一条entry链表。新版本的dictRehash()还加入了一个最大访问空桶数(empty_visits)的限制来进一步减小可能引起阻塞的时间。

深扒一下这个函数的具体实现。

  1. 判断dict是否正在rehashing,只有是,才能继续往下进行,否则已经结束哈希过程,直接返回。
  2. 接着是分n步进行的渐进式哈希主体部分(n由函数参数传入),在while的条件里面加入对.used旧表中剩余元素数目的观察,增加安全性。
  3. 一个runtime的断言保证一下渐进式哈希的索引没有越界。
  4. 接下来一个小while是为了跳过空桶,同时更新剩余可以访问的空桶数,empty_visits这个变量的作用之前已经说过了。
  5. 现在我们来到了当前的bucket,在下一个while(de)中把其中的所有元素都迁移到ht[1]中,索引值是辅助了哈希表的大小掩码计算出来的,可以保证不会越界。同时更新了两张表的当前元素数目。
  6. 每一步rehash结束,都要增加索引值,并且把旧表中已经迁移完毕的bucket置为空指针。
  7. 最后判断一下旧表是否全部迁移完毕,若是,则回收空间,重置旧表,重置渐进式哈希的索引,否则用返回值告诉调用方,dict内仍然有数据未迁移。

渐进式哈希的精髓:数据的迁移不是一次性完成的,而是可以通过dictRehash()这个函数分步规划的,并且调用方可以及时知道是否需要继续进行渐进式哈希操作。如果dict数据结构中存储了海量的数据,那么一次性迁移势必带来redis性能的下降,别忘了redis是单线程模型,在实时性要求高的场景下这可能是致命的。而渐进式哈希则将这种代价可控地分摊了,调用方可以在dict做插入,删除,更新的时候执行dictRehash(),最小化数据迁移的代价。
在迁移的过程中,数据是在新表还是旧表中并不是一个非常急迫的需求,迁移的过程并不会丢失数据,在旧表中找不到再到新表中寻找就是了。

参考:浅谈Redis中的Rehash机制_Coding_QK-CSDN博客_redis rehash

rehash过程

触发rehash的机制:

  1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 1 ,执行扩展操作;
  2. 服务器目前正在执行BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 5,执行扩展操作 ;
  3. 当哈希表的负载因子小于 0.1 时, 程序自动开始对哈希表执行收缩操作。

   其中哈希表的负载因子可以通过公式:负载因子 = 哈希表已保存节点数量 / 哈希表大小load_factor = ht[0].used / ht[0].size计算得出。
   比如说, 对于一个大小为 4 , 包含 4 个键值对的哈希表来说, 这个哈希表的负载因子为:load_factor = 4 / 4 = 1
   又比如说, 对于一个大小为 512 , 包含 256 个键值对的哈希表来说, 这个哈希表的负载因子为:load_factor = 256 / 512 = 0.5

   根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行, 服务器执行扩展操作所需的负载因子并不相同,这是因为在执行 BGSAVE 命令或BGREWRITEAOF 命令的过程中, Redis 需要创建当前服务器进程的子进程。 而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程的使用效率, 所以在子进程存在期间, 服务器会提高执行扩展操作所需的负载因子, 从而尽可能地避免在子进程存在期间进行哈希表扩展操作, 这可以避免不必要的内存写入操作, 最大限度地节约内存。

rehash过程:

  1. ht[1] 分配空间, 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 表示 rehash 工作正式开始。
  3. 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行, 最终在某个时间点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成。

关于rehash过程中ht数组的变化:

为字典的 ht[1] 哈希表分配空间, 这个哈希表的空间大小取决于要执行的操作, 以及 ht[0]当前包含的键值对数量(也即是ht[0].used 属性的值):

  • 如果执行的是扩展操作, 那么 ht[1] 的大小为第一个大于等于ht[0].used * 2 的 2^n (2 的 n 次方幂);
  • 如果执行的是收缩操作, 那么 ht[1]的大小为第一个大于等于 ht[0].used 的 2^n。

将保存在 ht[0] 中的所有键值对 rehash 到 ht[1]上面:rehash指的是重新计算键的哈希值和索引值,然后将键值对放置到 ht[1] 哈希表的指定位置上。

当 ht[0]包含的所有键值对都迁移到了ht[1] 之后 (ht[0] 变为空表),释放 ht[0] ,将 ht[1] 设置为 ht[0] , 并在 ht[1] 新创建一个空白哈希表,为下一次rehash做准备。

参考《Redis设计与实现》图解 :

  • 准备开始rehashredis的rehash
  • rehash索引0上的键值对redis的rehash 

  • rehash索引1上的键值对redis的rehash
  • ehash索引2上的键值对redis的rehash

  • rehash索引3上的键值对redis的rehash

  • rehash执行完毕

redis的rehash

渐进式rehash执行期间的哈希表操作

因为在进行渐进式rehash的过程中,字典会同时使用ht[0]和ht[1]两个哈希表,所以在渐进式rehash进行期间,字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行。例如,要在字典里面查找一个键的话,程序会先在ht[0]里面进行查找,如果没找到的话,就会继续到ht[1]里面进行查找,诸如此类。

另外,在渐进式rehash执行期间,新添加到字典的键值对一律会被保存到ht[1]里面,而ht[0]则不再进行任何添加操作,这一措施保证了ht[0]包含的键值对数量会只减不增,并随着rehash操作的执行而最终变成空表。

《Redis设计与实现》

上一篇:【Tokio】非阻塞关闭运行时


下一篇:sql server数据库的带返回值的存储和函数的基础使用