神刀安全网

Memcached的扩容源码分析

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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Memcached的扩容源码分析

分享到:更多 ()