redis-哈希表自动扩容

@(架构说)[redis]

为了回答上次遗留问题 哈希表如何扩容问题? 重点内容: 1 注释代码:最新版本 https://github.com/aleafboat/redis.git 2 扩容函数

结构定义

typedef struct dict 
{
    dictType *type;
    void *privdata;
    dictht ht[2];//哈希表 
    long rehashidx;  /* rehashing not in progress if rehashidx == -1 */
    int iterators;  /* number of iterators currently running */
} dict;

typedef struct dictht 
{ //字典hash table  
    dictEntry **table;
    //可以看做字典数组,俗称桶bucket  
    unsigned long size; 
    //指针数组的大小,即桶的层数  
    unsigned long sizemask;  
    unsigned long used; 
    //字典中当前的节点数目  
} dictht;  

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

扩容过程

何时需要扩容 --触发的条件很多

每次增加dictEntry时,都会调用一次_dictExpandIfNeeded()这个函数。

1.如果dict正在扩容,则返回正常DICT_OK

2.如果dict刚刚初始化,也就是两个dictht都为NULL,则调用dictExpand()函数初始化。dictExpand()同样会做一次判断两个dictht都为NULL,然后直接赋给ht[0]。

3.如果可以扩容(dict_can_resize=1),那么只要现在表中键总数大于表的长度就开始扩容。如果不能扩容(也就是dict_can_resize=0), 但是如果表中键总数与表的长度的比值大于某一个阀值(由dict_force_resize_ratio静态变量决定),那么就强制扩容。

扩容是怎么进行的?

之前所说的每个dict中都有两个哈希表结构dictht *ht[2]。 当开始扩容时,把第一个ht作为原始表, 第二个作为扩容后的表

dict中rehashidx决定了目前扩容的进度。

扩容过程什么时候执行? 当决定开始扩容后

int dictRehash(dict d, int n); int dictRehashMilliseconds(dict d, int ms);

第一个函数中n决定每次rehash(也就是转移dictEntry)的次数, 第二个函数决定调用rehash函数的时间。 每次执行查找,增加,删除操作都会执行一次dictRehash(1)(如果正在扩容),使得整个漫长的扩容过程隐含在每一次简单的操作中。

函数:可以跳过不看

int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;
    //超过1ms刷新一次
    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}
int dictRehash(dict *d, int n) 
{   //移动n*10层(buckets)从d->ht[0] 到d->ht[1]
    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) 
        {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            //前插 例如head -- B -C--D  insert A A->B-C>D, head-A
            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;//第rehashidx层移动完毕
        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;
}

总结:

扩容步骤

  • 业务操作触发扩容 计算扩容大小,然后申请table[1]空间
  • 后台进程,间隔时间移动数据,从old-->new table[0]-->table[1]

QA

1 在扩容期间如果有新元素插入进来怎么办?

插入扩容的的哈希表 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

2 每次扩容多少?什么时候扩容

如果原数组大小为零 扩容:dictExpand(d, DICT_HT_INITIAL_SIZE) 默认为4 如果原来数组的个数大于数组的大小 扩容: dictExpand(d, d->ht[0].used*2) 记录个数的倍数 当以下条件中的任意一个被满足时,程序会自动开始对哈希表执行扩展操作: 1)服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于1。 2)服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于5。 load_factor = ht[0].used / ht[0].size

3 如何实现慢慢扩容 ?

解决办法通过开辟一个新的线程来处理,Rehash 在1ms内。 serverCron函数来调度

原文发布于微信公众号 - 架构说(JiaGouS)

原文发表时间:2015-12-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逸鹏说道

C# 温故而知新:Stream篇(六)

BufferedStream 目录: 简单介绍一下BufferedStream 如何理解缓冲区? BufferedStream的优势 从BufferedStre...

34750
来自专栏大内老A

ASP.NET MVC的Model元数据提供机制的实现

在前面的介绍中我们已经提到过表示Model元数据的ModelMetadata对象最终是通过一个名为ModelMetadataProvider的组件提供的,接下来...

22860
来自专栏用户2442861的专栏

网易2013校园招聘笔试题详解

http://blog.csdn.net/silangquan/article/details/18142651

15420
来自专栏葡萄城控件技术团队

C#:异步编程和线程的使用(.NET 4.5 )

异步编程和线程处理是并发或并行编程非常重要的功能特征。为了实现异步编程,可使用线程也可以不用。将异步与线程同时讲,将有助于我们更好的理解它们的特征。 本文中涉及...

23550
来自专栏JavaEdge

JedisSentinelPool源码分析

1. 概述 Redis-Sentinel作为官方推荐的HA解决方案,Jedis也在客户端角度实现了对Sentinel的支持,主要实现在JedisSentinel...

39440
来自专栏瓜大三哥

文件地址映射之yaffs_GetTnode

yaffs文件系统在更新文件数据的时候,会分配一块新的chunk,也就是说,同样的文件偏移地址,在该地址上的数据更新前和更新后,其对应的flash上的存储地址是...

20760
来自专栏Danny的专栏

探秘BOF 和EOF

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

12530
来自专栏Java学习网

Java中使用栈实现一个队列,实用代码

本功能提供下面四个方法: push(x) ——添加元素x到队列。 pop()——从队列中删除前面的元素。 peek()——得到前面的元素。 empty()——返...

27790
来自专栏Linyb极客之路

并发编程之同步容器类和并发容器类

一、fail-fast机制 快速报错机制(fail-fast)能够防止多个进程同时修改同一个容器的内容。如果在你迭代遍历某个容器的过程中,另一个进程接入其中,...

30590
来自专栏数据结构与算法

2039. 树的统计

输入文件:counttree.in   输出文件:counttree.out 简单对比 时间限制:1 s   内存限制:128 MB 【题目描述】 关于...

350100

扫码关注云+社区

领取腾讯云代金券