Memcached slab 分配策略

Memcached 自帶了一個內(nèi)存分配模塊slab，自己在用戶層實現(xiàn)了內(nèi)存的分配，而不是完全依賴于系統(tǒng)的 malloc。這篇文章，來看看 Memcached slab 內(nèi)存分配算法是怎么做的。

一個內(nèi)存分配算法要考慮算法的效率，管理內(nèi)存所占的空間和內(nèi)存碎片的問題。這個是三個衡量點往往不能個個都得到滿足，每個實現(xiàn)都會各有所長。slab 能較好的規(guī)避內(nèi)存碎片的問題，但也帶來了一定的內(nèi)存浪費，算法的效率還不錯。

Memcached slab 概述

在 Memcached 中，為鍵值對分配空間的時候都會調(diào)用 do_item_alloc() 函數(shù)，真正設(shè)計 slab 的是slabs_alloc() 這個函數(shù)：

void *slabs_alloc(size_t size, unsigned int id);

size 是所需分配空間的實際大小，id 是這個空間大小所對應(yīng)的數(shù)量級。

slab class

slab 為空間的大小劃分了數(shù)量級。在 memecached 初始化的時候可以設(shè)置 chrunk 和 factor 屬性，前者是一個底數(shù)，后者是一個因子，前一個數(shù)量級乘于因子已得到新的數(shù)量級，依次可以推算下一級的數(shù)量級。

來看看內(nèi)存管理的結(jié)構(gòu)體 slabclass_t：

typedef struct {
    // 每個內(nèi)存塊大小
    unsigned int size; /* sizes of items */
    // 每個slab 內(nèi)存塊的數(shù)量
    unsigned int perslab; /* how many items per slab */
    // 空閑的內(nèi)存塊會組成一個鏈表
    void *slots; /* list of item ptrs */
    // 當前空閑內(nèi)存塊的數(shù)量
    unsigned int sl_curr; /* total free items in list */
    // slab 數(shù)量
    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;

現(xiàn)在對于某一級別的 slab 有如下印象圖：

http://wiki.jikexueyuan.com/project/redis/images/slab.png" alt="" />

對于不同的 class 有如下印象圖：

http://wiki.jikexueyuan.com/project/redis/images/slab1.png" alt="" />

內(nèi)存分配的過程

來看看 slab 內(nèi)存分配入口函數(shù)做了什么？

void *slabs_alloc(size_t size, unsigned int id) {
    void *ret;
    // 每次內(nèi)存的分配都需要加鎖
    pthread_mutex_lock(&slabs_lock);
    ret = do_slabs_alloc(size, id);
    pthread_mutex_unlock(&slabs_lock);
    return ret;
}

do_slabs_alloc() 實際上會先檢測是否有空閑的內(nèi)存塊，有則返回空閑的內(nèi)存塊；否則，會調(diào)用do_slabs_newslab() 分配新的內(nèi)存。

static void *do_slabs_alloc(const size_t size, unsigned int id) {
    slabclass_t *p;
    void *ret = NULL;
    item *it = NULL;
    // 所需分配空間的數(shù)量級別不合法
    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 內(nèi)還有空閑的內(nèi)存塊，返回空閑的內(nèi)存塊，否則調(diào)用
    // 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 是否已經(jīng)滿了，如果滿 了則 resize slab_list 并分配空間，將新分配的空間初始化后切割插入到空閑鏈表中。

static int do_slabs_newslab(const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    // 計算需要分配內(nèi)存的大小
    int len = settings.slab_reassign ? settings.item_size_max
    : p->size * p->perslab;
    char *ptr;
    // 擴大slab_list，并分配內(nèi)存
    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;
    }
    // 將新分配的內(nèi)存初始化，并切割插入到空閑鏈表中
    memset(ptr, 0, (size_t)len);
    split_slab_page_into_freelist(ptr, id);
    // 調(diào)整slab_list 指針指向新分配的空間
    p->slab_list[p->slabs++] = ptr;
    mem_malloced += len;
    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
    return 1;
}

do_slabs_newslab() 之前：

http://wiki.jikexueyuan.com/project/redis/images/sl.png" alt="" />

do_slabs_newslab() 之后：

http://wiki.jikexueyuan.com/project/redis/images/sl1.png" alt="" />

slab 能較好的規(guī)避內(nèi)存碎片的問題，但也帶來了一定的內(nèi)存浪費，算法的效率還不錯?，F(xiàn)在能夠較好的理解這一句話。因為 slab 內(nèi)存分配算法預(yù)先分配了一大塊的連續(xù)緊湊的內(nèi)存空間，只一點能將內(nèi)存的使用都限定在緊湊連續(xù)的空間內(nèi)；但很明顯它會帶來一定的浪費，因為每個 slab class 內(nèi)的每個內(nèi)存塊大小都是固定的，數(shù)據(jù)的大小必須小于等于內(nèi)存塊的大小。

lru 機制

Memcached slab 還有一個超時淘汰的機制，當發(fā)現(xiàn)某個 slab class 內(nèi)無空間可分配的時候，并不是立即去像上面所說的一樣去擴展空間，而是嘗試從已經(jīng)被使用的內(nèi)存塊中尋找是否有已經(jīng)超時的塊，如果超時了，則原有的數(shù)據(jù)會被刪除，這個內(nèi)存塊被作為結(jié)果內(nèi)存分配的結(jié)果。

那如何快速找到這個塊呢？對于某個 slab class，所有已使用和空閑的內(nèi)存塊都會被組織成一個鏈表，

static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];

這兩個全局變量就保存這些鏈表的頭指針和尾指針。對于新的數(shù)據(jù)插入，會更新 heads[classid]，對于超時被剔除的數(shù)據(jù)刪除操作，會更新 tails[classid]。

下面圖解上述的過程：

http://wiki.jikexueyuan.com/project/redis/images/sl2.png" alt="" />