Memcached slab 分配策略
Memcached 自带了一个内存分配模块slab,自己在用户层实现了内存的分配,而不是完全依赖于系统的 malloc。这篇文章,来看看 Memcached slab 内存分配算法是怎么做的。
一个内存分配算法要考虑算法的效率,管理内存所占的空间和内存碎片的问题。这个是三个衡量点往往不能个个都得到满足,每个实现都会各有所长。slab 能较好的规避内存碎片的问题,但也带来了一定的内存浪费,算法的效率还不错。
Memcached slab 概述
在 Memcached 中,为键值对分配空间的时候都会调用 do_item_alloc() 函数,真正设计 slab 的是slabs_alloc() 这个函数:
void *slabs_alloc(size_t size, unsigned int id);
size 是所需分配空间的实际大小,id 是这个空间大小所对应的数量级。
slab class
slab 为空间的大小划分了数量级。在 memecached 初始化的时候可以设置 chrunk 和 factor 属性,前者是一个底数,后者是一个因子,前一个数量级乘于因子已得到新的数量级,依次可以推算下一级的数量级。
来看看内存管理的结构体 slabclass_t:
typedef struct {
// 每个内存块大小
unsigned int size; /* sizes of items */
// 每个slab 内存块的数量
unsigned int perslab; /* how many items per slab */
// 空闲的内存块会组成一个链表
void *slots; /* list of item ptrs */
// 当前空闲内存块的数量
unsigned int sl_curr; /* total free items in list */
// slab 数量
unsigned int slabs; /* how many slabs were allocated for this class */
// slab 指针
void **slab_list; /* array of slab pointers */
unsigned int list_size; /* size of prev array */
......
} slabclass_t;
现在对于某一级别的 slab 有如下印象图:
对于不同的 class 有如下印象图:
内存分配的过程
来看看 slab 内存分配入口函数做了什么?
void *slabs_alloc(size_t size, unsigned int id) {
void *ret;
// 每次内存的分配都需要加锁
pthread_mutex_lock(&slabs_lock);
ret = do_slabs_alloc(size, id);
pthread_mutex_unlock(&slabs_lock);
return ret;
}
do_slabs_alloc() 实际上会先检测是否有空闲的内存块,有则返回空闲的内存块;否则,会调用do_slabs_newslab() 分配新的内存。
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) {
MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
return NULL;
}
p = &slabclass[id];
assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0);
// 如果指定的slab 内还有空闲的内存块,返回空闲的内存块,否则调用
// do_slabs_newslab()
// do_slabs_newslab() 为指定的slab 分配更多的空间
if (! (p->sl_curr != 0 || do_slabs_newslab(id) != 0)) {
/* We don't have more memory available */
ret = NULL;
} else if (p->sl_curr != 0) {
/* 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;
}
我们来看看 do_slabs_newslab() 是怎么做的:首先会看 slab_list 是否已经满了,如果满 了则 resize slab_list 并分配空间,将新分配的空间初始化后切割插入到空闲链表中。
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;
// 扩大slab_list,并分配内存
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);
// 调整slab_list 指针指向新分配的空间
p->slab_list[p->slabs++] = ptr;
mem_malloced += len;
MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
return 1;
}
do_slabs_newslab() 之前:
do_slabs_newslab() 之后:
slab 能较好的规避内存碎片的问题,但也带来了一定的内存浪费,算法的效率还不错。现在能够较好的理解这一句话。因为 slab 内存分配算法预先分配了一大块的连续紧凑的内存空间,只一点能将内存的使用都限定在紧凑连续的空间内;但很明显它会带来一定的浪费,因为每个 slab class 内的每个内存块大小都是固定的,数据的大小必须小于等于内存块的大小。
lru 机制
Memcached slab 还有一个超时淘汰的机制,当发现某个 slab class 内无空间可分配的时候,并不是立即去像上面所说的一样去扩展空间,而是尝试从已经被使用的内存块中寻找是否有已经超时的块,如果超时了,则原有的数据会被删除,这个内存块被作为结果内存分配的结果。
那如何快速找到这个块呢?对于某个 slab class,所有已使用和空闲的内存块都会被组织成一个链表,
static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
这两个全局变量就保存这些链表的头指针和尾指针。对于新的数据插入,会更新 heads[classid],对于超时被剔除的数据删除操作,会更新 tails[classid]。
下面图解上述的过程: