注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

偶有所得,记录在此

有分享交流才有进步,永远不要固步自封

 
 
 

日志

 
 

Redis Dict 分析  

2011-02-21 17:08:30|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
非常普通的 Hash 算法,无特别之处。

如何解决 Hash 冲突
Hash Table 的每一个 Entry 是一个链表,Hash 值相同的 Entry 放在这个链表内;查询时,先用 Hash Key 定位到链表头,然后遍历这个链表执行查找或者插入操作。

Hash 表扩容方案
1) 新 Hash Table Size 的计算
每次执行 add Entry 操作时,先进行 Hash 表的扩容检测,算法如下:
/* 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))
{
    return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
                                d->ht[0].size : d->ht[0].used)*2);
}
return DICT_OK;

如果 Entry 的数量超过了 Hash Size,并且允许扩容(dict_can_resize == 1),则会执行扩容。

即便不允许扩容(dict_can_resize == 0),如果 Entry 的数量超过 Hash Size 的 5 倍(dict_force_resize_ratio 的值为 5),会被强制扩容。

新的 Hash Size 为原来 Entry 数量 的 2 倍。

当 Hash Table 使用率低于 10%,同样会执行 resize 操作以节省内存。

#define REDIS_HT_MINFILL        10

static 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));
}

2)  扩容过程
执行
dictExpand 时,会先创建新的 Hash Table,然后设置 d->rehashidx = 0  结束,不立即执行数据转移 rehash。

此时,系统存在两个 Hash table,新的 Hash Table 为空,等待 rehash 将数据从旧 Hash Table 转移出来。

rehash 是由 Redis Server 是在 main loop 里面执行的。在每个 loop 里面,对于每个 dict,每次执行 1 millisecond rehash 操作;如果未完成 rehash,会在下一个 loop 里面继续执行。

 3) 查找时,如果 rehash 未完成,会同时查找两个 Hash 表。
  评论这张
 
阅读(1419)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017