memcache（三）内存管理

木一

memcached（三）内存管理
　　memcached使用预申请的方式来管理内存的分配，从而避免内存碎片化的问题。如果采用mallo和free来动态的申请和销毁内存，必然会产生大量的内存碎片。

基本知识
　　slab：内存块是memcached一次申请内存的最小单元，在memcached中一个slab的默认大小为1M；
　　slabclass：特定大小的chunk的组。
　　chunk：缓存的内存空间，一个slab被划分为若干个chunk；
　　item：存储数据的最小单元，每一个chunk都会包含一个item；
　　factor:增长因子，默认为1.25，相邻slab中的item大小与factor成比例关系；

基本原理
　　memcached使用预分配方法，避免频繁的调用malloc和free；
　　memcached通过不同的slab来管理不同chunk大小的内存块，从而满足存储不同大小的数据。
　　slab的申请是通过在使用item时申请slab大小的内存空间，然后再把内存切割为大小相同的item，挂在到slab的未使用链表上。
　　过期和被删除item并不会被free掉，memcached并不会删除已经分配的内存；
　　Memcached会优先使用已超时的记录空间，通过LRU算法；
　　memcached使用lazy expiration来判断元素是否过期，所以过期监视上不会占用cpu时间。

源码分析
　　下面主要分析memcached的内存申请和存储相关代码。

item
　　item是key/value的存储单元。



typedef struct _stritem {
struct _stritem *next;      /* 前后指针用于在链表slab->slots中连接前后数据 */
struct _stritem *prev;
struct _stritem *h_next;    /* hash chain next */
rel_time_t      time;       /* 最后一次访问时间 */
rel_time_t      exptime;    /* 过期时间 */
int             nbytes;     /* 数据大小 */
unsigned short  refcount;   /* 引用次数 */
uint8_t         nsuffix;    /* suffix长度 */
uint8_t         it_flags;   /* ITEM_* above */
uint8_t         slabs_clsid;/* 所有slab的id */
uint8_t         nkey;       /* key长度 */
/* this odd type prevents type-punning issues when we do
* the little shuffle to save space when not using CAS. */
union {
uint64_t cas;
char end;
} data[]; /* cas|key|suffix|value */
} item;
slab初始化



void slabs_init(const size_t limit, const double factor, const bool prealloc) {
int i = POWER_SMALLEST - 1;
unsigned int size = sizeof(item) + settings.chunk_size; /* 得到每一个item的大小 */
mem_limit = limit;
if (prealloc) { /* 预分配一块内存 */
...
}
memset(slabclass, 0, sizeof(slabclass)); /* 把slabclass置为0，slabclass是一个slab数组，存储所有slab的信息 */
while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {  /* 循环初始化每一个slab的内容,保证slab中item的size小于max_size/factor */
/* Make sure items are always n-byte aligned */
if (size % CHUNK_ALIGN_BYTES)  /* 用于内存对齐 */
size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
slabclass.size = size; /* 初始化slabclass中item的大小 */
slabclass.perslab = settings.item_size_max / slabclass.size; /* 初始化每个slab中item的数量 */
size *= factor;  /* item的大小随factor逐渐增大 */
...
}
/* 初始化最后一个slab,大小为最大的max_size，只有一个item */
power_largest = i;
slabclass[power_largest].size = settings.item_size_max;
slabclass[power_largest].perslab = 1;
...
}
　　从源码中，可以看出来同一个slab中所有的item的大小都是固定的，

申请slab内存



static void *do_slabs_alloc(const size_t size, unsigned int id) {
slabclass_t *p;
void *ret = NULL;
item *it = NULL;
if (id < POWER_SMALLEST || id > power_largest) { /* 判断id是否合法 */
MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
return NULL;
}
p = &slabclass[id]; /* 获取slab */
assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0);
/* fail unless we have space at the end of a recently allocated page,
we have something on our freelist, or we could allocate a new page */
if (! (p->sl_curr != 0 || do_slabs_newslab(id) != 0)) { /*如果sl_curr为0，没有剩余的item，那么就执行do_slabs_newslab申请内存空间*/
/* We don't have more memory available */
ret = NULL;
} else if (p->sl_curr != 0) { /* 如果有未使用的空间，则获取该item，并从slots链表中删除该item */
/* return off our freelist */
it = (item *)p->slots;
p->slots = it->next;
if (it->next) it->next->prev = 0;
p->sl_curr--;
ret = (void *)it;
}
...
return ret;
}
　　sl_curr来判断是否存在未使用的内容空间，如果不存在需要调用do_slabs_newslab来申请slab空间。



static int do_slabs_newslab(const unsigned int id) {
slabclass_t *p = &slabclass[id];
int len = settings.slab_reassign ? settings.item_size_max
: p->size * p->perslab;
char *ptr;
/* 1. 判断是否超过内存限制
2. 判断是否申请过内存空间
3. 如果没有申请过，则申请slab->size*slab->perslab大小的整块内存
4.如果申请过，调用grow_slab_list来扩大slab大小 */
if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||
(grow_slab_list(id) == 0) ||
((ptr = memory_allocate((size_t)len)) == 0)) {
MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
return 0;
}
memset(ptr, 0, (size_t)len);
split_slab_page_into_freelist(ptr, id); /* 把申请的内存分配到slots链表中 */
p->slab_list[p->slabs++] = ptr;
mem_malloced += len;
MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
return 1;
}
　　申请空间后，需要通过split_slab_page_into_freelist函数把申请的内存空间分配到未使用的链表中。



static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {
slabclass_t *p = &slabclass[id];
int x;
for (x = 0; x < p->perslab; x++) { /* 循环分配内存 */
do_slabs_free(ptr, 0, id);
ptr += p->size;
}
}
static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
slabclass_t *p;
item *it;
...
p = &slabclass[id];
/* 获取内存指针，把item块挂在到slots链表中，增加sl_curr */
it = (item *)ptr;
it->it_flags |= ITEM_SLABBED;
it->prev = 0;
it->next = p->slots;
if (it->next) it->next->prev = it;
p->slots = it;
p->sl_curr++;
p->requested -= size;
return;
}
获取适当大小的item
　　在do_item_alloc中，调用了slabs_clsid来获取适合存储当前元素的slab id。



unsigned int slabs_clsid(const size_t size) {
int res = POWER_SMALLEST;
if (size == 0)
return 0;
while (size > slabclass[res].size)    /* 遍历slabclass来找到适合size的item */
if (res++ == power_largest)     /* won't fit in the biggest slab */
return 0;
return res;
}
优缺点
　　内存预分配可以避免内存碎片以及避免动态分配造成的开销。
　　内存分配是由冗余的，当一个slab不能被它所拥有的chunk大小整除时，slab尾部剩余的空间就会被丢弃。
　　由于分配的是特定长度的内存，因此无法有效地利用所有分配的内存，例如如果将100字节的数据存储在128字节的chunk中，会造成28字节的浪费。