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