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