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]。

下面图解上述的过程：

转自：http://wiki.jikexueyuan.com/project/redis/slab.html