最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • memcached源码分析—–哈希表基本操作以及扩容过程


            转载请注明出处:http://blog.csdn.net/luotuo44/article/details/42773231

            温馨提示:本文用到了1些可以在启动memcached设置的全局变量。关于这些全局变量的含义可以参考《memcached启动参数详解》。对这些全局变量,处理方式就像《如何浏览memcached源代码》所说的那样直接取其默许值。

            assoc.c文件里面的代码是构造1个哈希表。memcached快的1个缘由是使用了哈希表。现在就来看1下memcached是怎样使用哈希表的。

    哈希结构:

            main函数会调用assoc_init函数申请并初始化哈希表。为了减少哈希表产生冲突的可能性,memcached的哈希表是比较长的,并且哈希表的长度为2的幂。全局变量hashpower用来记录2的幂次。main函数调用assoc_init函数时使用全局变量settings.hashpower_init作为参数,用于指明哈希表初始化时的幂次。settings.hashpower_init可以在启动memcached的时候设置,具体可以参考《memcached启动参数详解和关键配置的默许值》。

    //memcached.h文件
    #define HASHPOWER_DEFAULT 16

    //assoc.h文件
    unsigned int hashpower = HASHPOWER_DEFAULT;

    #define hashsize(n) ((ub4)1<<(n))//这里是1 左移 n次
    //hashsize(n)为2的幂,所以hashmask的值的2进制情势就是后面全为1的数。这就很像位操作里面的 &
    //value & hashmask(n)的结果肯定是比hashsize(n)小的1个数字.即结果在hash表里面
    //hashmask(n)也能够称为哈希掩码
    #define hashmask(n) (hashsize(n)⑴)

    //哈希表数组指针
    static item** primary_hashtable = 0;

    //默许参数值为0。本函数由main函数调用,参数的默许值为0
    void assoc_init(const int hashtable_init) {
    if (hashtable_init) {
    hashpower = hashtable_init;
    }

    //由于哈希表会渐渐增大,所以要使用动态内存分配。哈希表存储的数据是1个
    //指针,这样更省空间。
    //hashsize(hashpower)就是哈希表的长度了
    primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
    if (! primary_hashtable) {
    fprintf(stderr, "Failed to init hashtable.
    ");
    exit(EXIT_FAILURE);//哈希表是memcached工作的基础,如果失败只能退出运行
    }

    }

            说到哈希表,那末就对应有两个问题,1个是哈希算法,1个怎样解决冲突。

            对哈希函数(算法),memcached直接使用开源的MurmurHash3和jenkins_hash两个中的1个。默许是使用jenkins,可以在启动memcached的时候设置设置为MurmurHash3。memcached是直接把客户端输入的键值作为哈希算法的输入,得到1个32位的无符号整型输出(用变量hv存储)。由于哈希表的长度没有2^32- 1这么大,所以需要用到前面代码中的hashmask宏进行截断。由因而位操作,所以常常能在memcached代码中看的hv & hashmask(hashpower)。

            memcached使用最多见的链地址法解决冲突问题。从前面的代码可以看到,primary_hashtable是1个的2级指针变量,它指向的是1个1维指针数组,数组的每个元素指向1条链表(链表上的item节点具有相同的哈希值)。数组的每个元素,在memcached里面也称为桶(bucket),所以后文的表述中会使用桶。下图是1个哈希表,其中第0号桶有2个item,第2、3、5号桶各有1个item。item就是用来存储用户数据的结构体。

            

    基本操作:

    插入item:

            接着看1下怎样在哈希表中插入1个item。它是直接根据哈希值找到哈希表中的位置(即找到对应的桶),然后使用头插法插入到桶的冲突链中。item结构体有1个专门的h_next指针成员变量用于连接哈希冲突链。

    static unsigned int hash_items = 0;//hash表中item的个数

    /* Note: this isn't an assoc_update. The key must not already exist to call this */
    //hv是这个item键值的哈希值
    int assoc_insert(item *it, const uint32_t hv) {
    unsigned int oldbucket;

    //使用头插法 插入1个item
    //第1次看本函数,直接看else部份
    if (expanding &&
    (oldbucket = (hv & hashmask(hashpower – 1))) >= expand_bucket)
    {

    } else {
    //使用头插法插入哈希表中
    it->h_next = primary_hashtable[hv & hashmask(hashpower)];
    primary_hashtable[hv & hashmask(hashpower)] = it;
    }

    hash_items++;//哈希表的item数量加1

    return 1;
    }

    查找item:

            往哈希表插入item后,就能够开始查找item了。下面看1下怎样在哈希表中查找1个item。item的键值hv只能定位到哈希表中的桶位置,但1个桶的冲突链上可能有多个item,所以除查找的时候除需要hv外还需要item的键值。

    //由于哈希值只能肯定是在哈希表中的哪一个桶(bucket),但1个桶里面是有1条冲突链的
    //此时需要用到具体的键值遍历并逐一比较冲突链上的所有节点。虽然key是以''结尾
    //的字符串,但调用strlen还是有点耗时(需要遍历键值字符串)。所以需要另外1个参数
    //nkey指明这个key的长度
    item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
    item *it;
    unsigned int oldbucket;

    //直接看else部份
    if (expanding &&
    (oldbucket = (hv & hashmask(hashpower – 1))) >= expand_bucket)
    {
    it = old_hashtable[oldbucket];
    } else {
    //由哈希值判断这个key是属于那个桶(bucket)的
    it = primary_hashtable[hv & hashmask(hashpower)];
    }

    //到这里,已肯定这个key是属于那个桶的。 遍历对应桶的冲突链便可

    item *ret = NULL;
    while (it) {
    //长度相同的情况下才调用memcmp比较,更高效
    if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
    ret = it;
    break;
    }
    it = it->h_next;
    }
    return ret;
    }

    删除item:

            下面看1下从哈希表中删除1个item是怎样实现的。从链表中删除1个节点的常规做法是:先找到这个节点的先驱节点,然后使用先驱节点的next指针进行删除和拼接操作。memcached的做法差不多,实现以下:

    void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
    item **before = _hashitem_before(key, nkey, hv);//得到先驱节点的h_next成员地址

    if (*before) {//查找成功
    item *nxt;
    hash_items–;
    //由于before是1个2级指针,其值为所查找item的先驱item的h_next成员地址.
    //所以*before指向的是所查找的item.由于before是1个2级指针,所以
    //*before作为左值时,可以给h_next成员变量赋值。所以下面3行代码是
    //使得删除中间的item后,前后的item还能连得起来。
    nxt = (*before)->h_next;
    (*before)->h_next = 0; /* probably pointless, but whatever. */
    *before = nxt;
    return;
    }
    /* Note: we never actually get here. the callers don't delete things
    they can't find. */
    assert(*before != 0);
    }

    //查找item。返回先驱节点的h_next成员地址,如果查找失败那末就返回冲突链中最后
    //1个节点的h_next成员地址。由于最后1个节点的h_next的值为NULL。通过对返回值
    //使用 * 运算符便可知道有无查找成功。
    static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
    item **pos;
    unsigned int oldbucket;

    //一样,看的时候直接跳到else部份
    if (expanding &&//正在扩大哈希表
    (oldbucket = (hv & hashmask(hashpower – 1))) >= expand_bucket)
    {
    pos = &old_hashtable[oldbucket];
    } else {
    //找到哈希表中对应的桶位置
    pos = &primary_hashtable[hv & hashmask(hashpower)];
    }

    //遍历桶的冲突链查找item
    while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
    pos = &(*pos)->h_next;
    }
    //*pos就能够知道有无查找成功。如果*pos等于NULL那末查找失败,否则查找成功。
    return pos;
    }

    扩大哈希表:

            当哈希表中item的数量到达了哈希表表长的1.5倍时,那末就会扩大哈希表增大哈希表的表长。memcached在插入1个item时会检查当前的item总数是不是到达了哈希表表长的1.5倍。由于item的哈希值是比较均匀的,所以平均来讲每一个桶的冲突链长度大概就是1.5个节点。所以memcached的哈希查找还是很快的。

    迁移线程:

            扩大哈希表有1个很大的问题:扩大后哈希表的长度变了,item哈希后的位置也是会随着变化的(回想1下memcached是怎样根据键值的哈希值肯定桶的位置的)。所以如果要扩大哈希表,那末就需要对哈希表中所有的item都要重新计算哈希值得到新的哈希位置(桶位置),然后把item迁移到新的桶上。对所有的item都要做这样的处理,所以这必定是1个耗时的操作。后文会把这个操作称为数据迁移。

            由于数据迁移是1个耗时的操作,所以这个工作由1个专门的线程(姑且把这个线程叫做迁移线程吧)负责完成。这个迁移线程是由main函数调用1个函数创建的。看下面代码:

    #define DEFAULT_HASH_BULK_MOVE 1
    int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;

    //main函数会调用本函数,启动数据迁移线程
    int start_assoc_maintenance_thread() {
    int ret;
    char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
    if (env != NULL) {
    //hash_bulk_move的作用在后面会说到。这里是通过环境变量给hash_bulk_move赋值
    hash_bulk_move = atoi(env);
    if (hash_bulk_move == 0) {
    hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
    }
    }
    if ((ret = pthread_create(&maintenance_tid, NULL,
    assoc_maintenance_thread, NULL)) != 0) {
    fprintf(stderr, "Can't create thread: %s
    ", strerror(ret));
    return ⑴;
    }
    return 0;
    }

            迁移线程被创建后会进入休眠状态(通过等待条件变量),当worker线程插入item后,发现需要扩大哈希表就会调用assoc_start_expand函数唤醒这个迁移线程。

    static bool started_expanding = false;

    //assoc_insert函数会调用本函数,当item数量到了哈希表表长的1.5倍才会调用的
    static void assoc_start_expand(void) {
    if (started_expanding)
    return;
    started_expanding = true;
    pthread_cond_signal(&maintenance_cond);
    }

    static bool expanding = false;//标明hash表是不是处于扩大状态
    static volatile int do_run_maintenance_thread = 1;
    static void *assoc_maintenance_thread(void *arg) {

    //do_run_maintenance_thread是全局变量,初始值为1,在stop_assoc_maintenance_thread
    //函数中会被赋值0,终止迁移线程
    while (do_run_maintenance_thread) {
    int ii = 0;

    //上锁
    item_lock_global();
    mutex_lock(&cache_lock);

    …//进行item迁移

    //遍历完就释放锁
    mutex_unlock(&cache_lock);
    item_unlock_global();

    if (!expanding) {//不需要迁移数据(了)。
    /* We are done expanding.. just wait for next invocation */
    mutex_lock(&cache_lock);
    started_expanding = false; //重置

    //挂起迁移线程,直到worker线程插入数据后发现item数量已到了1.5倍哈希表大小,
    //此时调用worker线程调用assoc_start_expand函数,该函数会调用pthread_cond_signal
    //唤醒迁移线程
    pthread_cond_wait(&maintenance_cond, &cache_lock);
    mutex_unlock(&cache_lock);

    mutex_lock(&cache_lock);
    assoc_expand();//申请更大的哈希表,并将expanding设置为true
    mutex_unlock(&cache_lock);
    }
    }
    return NULL;
    }

    逐渐迁移数据:

            为了不在迁移的时候worker线程增删哈希表,所以要在数据迁移的时候加锁,worker线程抢到了锁才能增删查找哈希表。memcached为了实现快速响应(即worker线程能够快速完成增删查找操作),就不能让迁移线程占锁太久。但数据迁移本身就是1个耗时的操作,这是1个矛盾。

            memcached为了解决这个矛盾,就采取了逐渐迁移的方法。其做法是,在1个循环里面:加锁-》只进行小部份数据的迁移-》解锁。这样做的效果是:虽然迁移线程会屡次抢占锁,但每次占有锁的时间都是很短的,这就增加了worker线程抢到锁的几率,使得worker线程能够快速完成它的操作。1小部份是多少个item呢?前面说到的全局变量hash_bulk_move就指明是多少个桶的item,默许值是1个桶,后面为了方便叙述也就认为hash_bulk_move的值为1。

            逐渐迁移的具体做法是,调用assoc_expand函数申请1个新的更大的哈希表,每次只迁移旧哈希表1个桶的item到新哈希表,迁移完1桶就释放锁。此时就要求有1个旧哈希表和新哈希表。在memcached实现里面,用primary_hashtable表示新表(也有1些博文称之为主表),old_hashtable表示旧表(副表)。

            前面说到,迁移线程被创建后就会休眠直到被worker线程唤醒。当迁移线程醒来后,就会调用assoc_expand函数扩大哈希表的表长。assoc_expand函数以下:

    static void assoc_expand(void) {
    old_hashtable = primary_hashtable;

    //申请1个新哈希表,并用old_hashtable指向旧哈希表
    primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
    if (primary_hashtable) {

    hashpower++;
    expanding = true;//标明已进入扩大状态
    expand_bucket = 0;//从0号桶开始数据迁移
    } else {
    primary_hashtable = old_hashtable;
    /* Bad news, but we can keep running. */
    }
    }

            现在看1下完全1点的assoc_maintenance_thread线程函数,体会迁移线程是怎样逐渐数据迁移的。为何说完全1点呢?由于该函数里面还是有1些东西本篇博文是没有解释的,但这其实不妨碍我们浏览该函数。后面还会有其他博文对这个线程函数进行讲授的。

    static unsigned int expand_bucket = 0;//指向待迁移的桶

    #define DEFAULT_HASH_BULK_MOVE 1
    int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;

    static volatile int do_run_maintenance_thread = 1;

    static void *assoc_maintenance_thread(void *arg) {

    //do_run_maintenance_thread是全局变量,初始值为1,在stop_assoc_maintenance_thread
    //函数中会被赋值0,终止迁移线程
    while (do_run_maintenance_thread) {
    int ii = 0;

    //上锁
    item_lock_global();
    mutex_lock(&cache_lock);

    //hash_bulk_move用来控制每次迁移,移动多少个桶的item。默许是1个.
    //如果expanding为true才会进入循环体,所以迁移线程刚创建的时候,其实不会进入循环体
    for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
    item *it, *next;
    int bucket;

    //在assoc_expand函数中expand_bucket会被赋值0
    //遍历旧哈希表中由expand_bucket指明的桶,将该桶的所有item
    //迁移到新哈希表中。
    for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
    next = it->h_next;

    //重新计算新的哈希值,得到其在新哈希表的位置
    bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);

    //将这个item插入到新哈希表中
    it->h_next = primary_hashtable[bucket];
    primary_hashtable[bucket] = it;
    }

    //不需要清空旧桶。直接将冲突链的链头赋值为NULL便可
    old_hashtable[expand_bucket] = NULL;

    //迁移完1个桶,接着把expand_bucket指向下1个待迁移的桶
    expand_bucket++;

    if (expand_bucket == hashsize(hashpower – 1)) {//全部数据迁移终了
    expanding = false; //将扩大标志设置为false
    free(old_hashtable);
    }
    }

    //遍历完hash_bulk_move个桶的所有item后,就释放锁
    mutex_unlock(&cache_lock);
    item_unlock_global();

    if (!expanding) {//不再需要迁移数据了。
    /* finished expanding. tell all threads to use fine-grained(细粒度的) locks */
    //进入到这里,说明已不需要迁移数据(停止扩大了)。


    mutex_lock(&cache_lock);
    started_expanding = false; //重置

    //挂起迁移线程,直到worker线程插入数据后发现item数量已到了1.5倍哈希表大小,
    //此时调用worker线程调用assoc_start_expand函数,该函数会调用pthread_cond_signal
    //唤醒迁移线程
    pthread_cond_wait(&maintenance_cond, &cache_lock);
    /* Before doing anything, tell threads to use a global lock */
    mutex_unlock(&cache_lock);


    mutex_lock(&cache_lock);
    assoc_expand();//申请更大的哈希表,并将expanding设置为true
    mutex_unlock(&cache_lock);
    }
    }
    return NULL;
    }

    回马枪:

            现在再回过头来再看1下哈希表的插入、删除和查找操作,由于这些操作可能产生在哈希表迁移阶段。有1点要注意,在assoc.c文件里面的插入、删除和查找操作,是看不到加锁操作的。但前面已说了,需要和迁移线程抢占锁,抢到了锁才能进行对应的操作。其实,这锁是由插入、删除和查找的调用者(主调函数)负责加的,所以在代码里面看不到。

            由于插入的时候可能哈希表正在扩大,所以插入的时候要面临1个选择:插入到新表还是旧表?memcached的做法是:当item对应在旧表中的桶还没被迁移到新表的话,就插入到旧表,否则插入到新表。下面是插入部份的代码。

    /* Note: this isn't an assoc_update. The key must not already exist to call this */
    //hv是这个item键值的哈希值
    int assoc_insert(item *it, const uint32_t hv) {
    unsigned int oldbucket;

    //使用头插法 插入1个item
    if (expanding &&//目前处于扩大hash表状态
    (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++;//哈希表的item数量加1
    //当hash表的item数量到达了hash表容量的1.5倍时,就会进行扩大
    //固然如果现在正处于扩大状态,是不会再扩大的
    if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
    assoc_start_expand();//唤醒迁移线程,扩大哈希表
    }

    return 1;
    }

            这里有1个疑问,为何不直接插入到新表呢?直接插入到新表对数据1致性来讲完全是没有问题的啊。网上有人说是为了保证同1个桶item的顺序,但由于迁移线程和插入线程对锁抢占的不肯定性,任何顺序都不能通过assoc_insert函数来保证。本文认为是为了快速查找。如果是直接插入到新表,那末在查找的时候便可能要同时查找新旧两个表才能找到item。查找完1个表,发现没有,然后再去查找另外1个表,这样的查找被认为是不够快速的。

            如果依照assoc_insert函数那样的实现,不用查找两个表就可以找到item。看下面的查找函数。

    //由于哈希值只能肯定是在哈希表中的哪一个桶(bucket),但1个桶里面是有1条冲突链的
    //此时需要用到具体的键值遍历并逐一比较冲突链上的所有节点。由于key其实不是以''结尾
    //的字符串,所以需要另外1个参数nkey指明这个key的长度
    item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
    item *it;
    unsigned int oldbucket;

    if (expanding &&//正在扩大哈希表
    (oldbucket = (hv & hashmask(hashpower – 1))) >= expand_bucket)//该item还在旧表里面
    {
    it = old_hashtable[oldbucket];
    } else {
    //由哈希值判断这个key是属于那个桶(bucket)的
    it = primary_hashtable[hv & hashmask(hashpower)];
    }

    //到这里已肯定了要查找的item是属于哪一个表的了,并且也肯定了桶位置。遍历对应桶的冲突链便可

    item *ret = NULL;
    while (it) {
    //长度相同的情况下才调用memcmp比较,更高效
    if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
    ret = it;
    break;
    }
    it = it->h_next;
    }

    return ret;
    }

            删除操作和查找操作差不多,这里直接贴出,不多说了。删除操作也是要进行查找操作的。

    void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
    item **before = _hashitem_before(key, nkey, hv);//得到先驱节点的h_next成员地址

    if (*before) {//查找成功
    item *nxt;
    hash_items–;

    //由于before是1个2级指针,其值为所查找item的先驱item的h_next成员地址.
    //所以*before指向的是所查找的item.由于before是1个2级指针,所以
    //*before作为左值时,可以给h_next成员变量赋值。所以下面3行代码是
    //使得删除中间的item后,前后的item还能连得起来。
    nxt = (*before)->h_next;
    (*before)->h_next = 0; /* probably pointless, but whatever. */
    *before = nxt;
    return;
    }
    /* Note: we never actually get here. the callers don't delete things
    they can't find. */
    assert(*before != 0);
    }

    //查找item。返回先驱节点的h_next成员地址,如果查找失败那末就返回冲突链中最后
    //1个节点的h_next成员地址。由于最后1个节点的h_next的值为NULL。通过对返回值
    //使用 * 运算符便可知道有无查找成功。
    static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
    item **pos;
    unsigned int oldbucket;

    if (expanding &&//正在扩大哈希表
    (oldbucket = (hv & hashmask(hashpower – 1))) >= expand_bucket)
    {
    pos = &old_hashtable[oldbucket];
    } else {
    //找到哈希表中对应的桶位置
    pos = &primary_hashtable[hv & hashmask(hashpower)];
    }

    //到这里已肯定了要查找的item是属于哪一个表的了,并且也肯定了桶位置。遍历对应桶的冲突链便可

    //遍历桶的冲突链查找item
    while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
    pos = &(*pos)->h_next;
    }
    //*pos就能够知道有无查找成功。如果*pos等于NULL那末查找失败,否则查找成功。
    return pos;
    }

            由上面的讨论可以知道,插入和删除1个item都必须知道这个item对应的桶有无被迁移到新表上了。

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » memcached源码分析—–哈希表基本操作以及扩容过程

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级