设为首页 收藏本站
查看: 1528|回复: 0

[经验分享] memcache研究笔记 之 hashtable

[复制链接]
累计签到:1 天
连续签到:1 天
发表于 2014-3-19 13:26:26 | 显示全部楼层 |阅读模式
查找过程中与关键字进行比较的次数通常取决于三个因素:哈希函数,解决冲突的方法和哈希表的填装因子。处理冲突方法相同的hashtable,其平均查找长度依赖于哈希表的装填因子:
装填因子a = 表中填入的记录数/哈希表长度

memcached 采用的hash 函数是Bob Jenkins 先生在1996 创立的一个算法,复杂度为O(6n+35),而且冲突率极低,该算法具体过程可以参阅这里。冲突处理的方法为开链法。

memcached 中实际有两个hash 表,一个是“主hash 表”(primary_hashtable),另外一个是“原有hash 表”(old_hashtable)。每次操作的时候,先会检测表是否正处于扩展(expanding)状态,如果扩展还没完成时,先在原有hash 表中操作数据。 向primary_hashtable插入数据assoc_insert,会检查primary_hashtable中数据项的数量,如果(K-V数量) > (primary_hashtable哈希桶数量 * 3  / 2),则将primary_hashtable扩大一倍,这项工作是由assoc维护线程负责。所以memcache可以避免由于哈希桶太深导致hash table性能下降。值得学习的时,在扩展primary_hashtable时,memcache作者先将primary_hashtable备份到old_hashtable, 然后将old_hashtable的哈希桶一个一个重新插入primary_hashtalbe。这样就避免了长久占用cache lock导致其它工作线程过久等待,影响请求响应时间。

main中启动维护线程assoc_maintenance_thread,然后等待条件变量进行hash长度扩容。在assoc_insert达到条件*3/2*的时候触发条件变量后assoc_maintenance_thread进行扩容。

涉及到的变量:
static unsigned int hashpower = 16;         
#define hashsize(n) ((ub4)1<<(n))              //hashtable初始化大小设置为2^16
#define hashmask(n) (hashsize(n)-1)         // 初始hashmask=0x1111 1111 1111 1111,用来将哈希函数计算的结果映射到hashsize域内,hashmask二进制值永远是hashpower位1的串
static unsigned int hash_items = 0;            // hashtable中存在的item数量
static unsigned int expand_bucket = 0;      // 当前扩展的位置(old_hashtable中的索引)大于等于expand_bucket表示还在old_hashtable中  

总结:
1、当无需扩容,直接操作primary_hashtable
2、待primary_hashtable正在扩容,指定了hash_bulk_move,然后指定了expand_bucket在当前bucket里面的位置,
     1)如果新操作位置<expand_bucket,  直接操作primary_hashtable
     2)如果新操作位置>=expand_bucket,直接操作old_hashtable
3、锁的数据同步保证cache_lock
思考:
影响mc_hash的性能的因素:1、散列函数 2、表自然增长  


运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址:https://www.yunweiku.com/thread-15971-1-1.html 上篇帖子: Memcached源码阅读之服务器资源调整 下篇帖子: memcached缓存批量更新解决方案探讨
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群,最新一手资源尽在官方微信交流群!快快加入我们吧...

扫描微信二维码查看详情

客服E-mail:kefu@iyunv.com 客服QQ:1061981298


QQ群⑦:运维网交流群⑦ QQ群⑧:运维网交流群⑧ k8s群:运维网kubernetes交流群


提醒:禁止发布任何违反国家法律、法规的言论与图片等内容;本站内容均来自个人观点与网络等信息,非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来,其版权均归原作者及其网站所有,我们尊重他人的合法权益,如有内容侵犯您的合法权益,请及时与我们联系进行核实删除!



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表