本文共 4283 字，大约阅读时间需要 14 分钟。
Hash表是Memcached里面最重要的结构之一，其采用链接法来处理Hash冲突，当Hash表中的项太多时，也就是Hash冲突比较高的时候，Hash表的遍历就脱变成单链表，此时为了提供Hash的性能，Hash表需要扩容，Memcached的扩容条件是当表中元素个数超过Hash容量的1.5倍时就进行扩容，扩容过程由独立的线程来完成，扩容过程中会采用2个Hash表，将老表中的数据通过Hash算法映射到新表中，每次移动的桶的数目可以配置，默认是每次移动老表中的1个桶。
//hash表中增加元素 int assoc_insert(item *it, const uint32_t hv) { unsigned int oldbucket; //如果已经进行扩容且目前进行扩容还没到需要插入元素的桶，则将元素添加到旧桶中 if (expanding &&(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) { it->h_next = old_hashtable[oldbucket];//添加元素 old_hashtable[oldbucket] = it; } else {//如果没扩容，或者扩容已经到了新的桶中，则添加元素到新表中 it->h_next = primary_hashtable[hv & hashmask(hashpower)];//添加元素 primary_hashtable[hv & hashmask(hashpower)] = it; } hash_items++;//元素数目+1 //还没开始扩容，且表中元素个数已经超过Hash表容量的1.5倍 if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) { assoc_start_expand();//唤醒扩容线程 } MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items); return 1; } //唤醒扩容线程 static void assoc_start_expand(void) { if (started_expanding) return; started_expanding = true; pthread_cond_signal(&maintenance_cond);//唤醒信号量 } //启动扩容线程，扩容线程在main函数中会启动，启动运行一遍之后会阻塞在条件变量maintenance_cond上面，插入元素超过规定，唤醒条件变量 static void *assoc_maintenance_thread(void *arg) { //do_run_maintenance_thread的值为1，即该线程持续运行 while (do_run_maintenance_thread) { int ii = 0; item_lock_global();//加Hash表的全局锁 mutex_lock(&cache_lock);//加cache_lock锁 //执行扩容时，每次按hash_bulk_move个桶来扩容 for (ii = 0; ii < hash_bulk_move && expanding; ++ii) { item *it, *next; int bucket; //老表每次移动一个桶中的一个元素 for (it = old_hashtable[expand_bucket]; NULL != it; it = next) { next = it->h_next;//要移动的下一个元素 bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower);//按新的Hash规则进行定位 it->h_next = primary_hashtable[bucket];//挂载到新的Hash表中 primary_hashtable[bucket] = it; } old_hashtable[expand_bucket] = NULL;//旧表中的这个Hash桶已经按新规则完成了扩容 expand_bucket++;//老表中的桶计数+1 if (expand_bucket == hashsize(hashpower - 1)) {//hash表扩容结束,expand_bucket从0开始,一直递增 expanding = false;//修改扩容标志 free(old_hashtable);//释放老的表结构 STATS_LOCK();//更新一些统计信息 stats.hash_bytes -= hashsize(hashpower - 1) * sizeof(void *); stats.hash_is_expanding = 0; STATS_UNLOCK(); if (settings.verbose > 1) fprintf(stderr, "Hash table expansion done\n"); } } mutex_unlock(&cache_lock);//释放cache_lock锁 item_unlock_global();//释放Hash表的全局锁 if (!expanding) {//完成扩容 //修改Hash表的锁类型，此时锁类型更新为分段锁，默认是分段锁，在进行扩容时，改为全局锁 switch_item_lock_type(ITEM_LOCK_GRANULAR); slabs_rebalancer_resume();//释放用于扩容的锁 /* We are done expanding.. just wait for next invocation */ mutex_lock(&cache_lock);//加cache_lock锁，保护条件变量 started_expanding = false;//修改扩容标识 pthread_cond_wait(&maintenance_cond, &cache_lock);//阻塞扩容线程 mutex_unlock(&cache_lock); slabs_rebalancer_pause();//加用于扩容的锁 switch_item_lock_type(ITEM_LOCK_GLOBAL);//修改锁类型为全局锁 mutex_lock(&cache_lock);//临时用来实现临界区 assoc_expand();//执行扩容 mutex_unlock(&cache_lock); } } return NULL; } //按2倍容量扩容Hash表 static void assoc_expand(void) { old_hashtable = primary_hashtable;//old_hashtable指向主Hash表 primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));//申请新的空间 if (primary_hashtable) {//空间申请成功 if (settings.verbose > 1) fprintf(stderr, "Hash table expansion starting\n"); hashpower++;//hash等级+1 expanding = true;//扩容标识打开 expand_bucket = 0; STATS_LOCK();//更新全局统计信息 stats.hash_power_level = hashpower; stats.hash_bytes += hashsize(hashpower) * sizeof(void *); stats.hash_is_expanding = 1; STATS_UNLOCK(); } else {//空间事情失败 primary_hashtable = old_hashtable; } } 转载地址：http://ptfbm.baihongyu.com/