memcached深度分析(3)

发表于:2015-07-10来源:uml.org.cn作者:火龙果软件点击数: 标签:数据库
void slabs_init(size_t limit, double factor) { int i = POWER_SMALLEST - 1; unsigned int size = sizeof(item) + settings.chunk_size; /* Factor of 2.0 means use the default memcached behavior */ if (fact

void slabs_init(size_t limit, double factor) {
    int i = POWER_SMALLEST - 1;
    unsigned int size = sizeof(item) + settings.chunk_size;
 
    /* Factor of 2.0 means use the default memcached behavior */
    if (factor == 2.0 && size < 128)
        size = 128;
 
    mem_limit = limit;
    memset(slabclass, 0, sizeof(slabclass));
 
    while (++i < POWER_LARGEST && size <= POWER_BLOCK / 2) {
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
 
        slabclass[i].size = size; 
        slabclass[i].perslab = POWER_BLOCK / slabclass[i].size;
        size *= factor; 
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %6d perslab %5d\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }       
    }
 
    power_largest = i;
    slabclass[power_largest].size = POWER_BLOCK;
    slabclass[power_largest].perslab = 1;
 
    /* for the test suite:  faking of how much we've already malloc'd */
    {
        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
        if (t_initial_malloc) {
            mem_malloced = atol(getenv("T_MEMD_INITIAL_MALLOC"));
        }       
 
    }
 
#ifndef DONT_PREALLOC_SLABS
    {
        char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
        if (!pre_alloc || atoi(pre_alloc)) {
            slabs_preallocate(limit / POWER_BLOCK);
        }
    }
#endif
}

  由上可以看出,memcached的内存分配是有冗余的,当一个slab不能被它所拥有的chunk大小整除时,slab尾部剩余的空间就被丢弃了,如id40中,两个chunk占用了1009384字节,这个slab一共有1MB,那么就有39192字节被浪费了。

  Memcached使用这种方式来分配内存,是为了可以快速的通过item长度定位出slab的classid,有一点类似hash,因为item的长度是可以计算的,比如一个item的长度是300字节,在1.2中就可以得到它应该保存在id7的slab中,因为按照上面的计算方法,id6的chunk 大小是252字节,id7的chunk大小是316字节,id8的chunk大小是396字节,表示所有252到316字节的item都应该保存在id7 中。同理,在1.1中,也可以计算得到它出于256和512之间,应该放在chunk_size为512的id9中(32位系统)。

  Memcached初始化的时候,会初始化slab(前面可以看到,在main函数中调用了slabs_init())。它会在slabs_init() 中检查一个常量DONT_PREALLOC_SLABS,如果这个没有被定义,说明使用预分配内存方式初始化slab,这样在所有已经定义过的 slabclass中,每一个id创建一个slab。这样就表示,1.2在默认的环境中启动进程后要分配41MB的slab空间,在这个过程里,memcached的第二个内存冗余发生了,因为有可能一个id根本没有被使用过,但是它也默认申请了一个slab,每个slab会用掉1MB内存

  当一个slab用光后,又有新的item要插入这个id,那么它就会重新申请新的slab,申请新的slab时,对应id的slab链表就要增长,这个链表是成倍增长的,在函数grow_slab_list函数中,这个链的长度从1变成2,从2变成4,从4变成8……:

static int grow_slab_list (unsigned int id) {
    slabclass_t *p = &slabclass[id];
    if (p->slabs == p->list_size) {
        size_t new_size =  p->list_size ? p->list_size * 2 : 16; 
        void *new_list = realloc(p->slab_list, new_size*sizeof(void*));
        if (new_list == 0) return 0;
        p->list_size = new_size;
        p->slab_list = new_list;
    }
    return 1;
}

  在定位item时,都是使用slabs_clsid函数,传入参数为item大小,返回值为classid,由这个过程可以看出,memcached的第三个内存冗余发生在保存item的过程中,item总是小于或等于chunk大小的,当item小于chunk大小时,就又发生了空间浪费。

  Memcached的NewHash算法

  Memcached的item保存基于一个大的hash表,它的实际地址就是slab中的chunk偏移,但是它的定位是依靠对key做hash的结果,在primary_hashtable中找到的。在assoc.c和items.c中定义了所有的hash和item操作。

  Memcached使用了一个叫做NewHash的算法,它的效果很好,效率也很高。1.1和1.2的NewHash有一些不同,主要的实现方式还是一样的,1.2的hash函数是经过整理优化的,适应性更好一些。

原文转自:http://www.uml.org.cn/sjjm/201411134.asp