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

Memcached slab 概述

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

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

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

slab class

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

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

typedef struct {
    // 每個(gè)內(nèi)存塊大小
    unsigned int size; /* sizes of items */
    // 每個(gè)slab 內(nèi)存塊的數(shù)量
    unsigned int perslab; /* how many items per slab */
    // 空閑的內(nèi)存塊會(huì)組成一個(gè)鏈表
    void *slots; /* list of item ptrs */
    // 當(dāng)前空閑內(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)在對(duì)于某一級(jí)別的 slab 有如下印象圖：

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

對(duì)于不同的 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() 實(shí)際上會(huì)先檢測是否有空閑的內(nèi)存塊，有則返回空閑的內(nèi)存塊；否則，會(huì)調(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ù)量級(jí)別不合法
    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() 是怎么做的：首先會(huì)看 slab_list 是否已經(jīng)滿了，如果滿了則 resize slab_list 并分配空間，將新分配的空間初始化后切割插入到空閑鏈表中。

static int do_slabs_newslab(const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    // 計(jì)算需要分配內(nèi)存的大小
    int len = settings.slab_reassign ? settings.item_size_max
    : p->size * p->perslab;
    char *ptr;
    // 擴(kuò)大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èi)，算法的效率還不錯(cuò)?，F(xiàn)在能夠較好的理解這一句話。因?yàn)?slab 內(nèi)存分配算法預(yù)先分配了一大塊的連續(xù)緊湊的內(nèi)存空間，只一點(diǎn)能將內(nèi)存的使用都限定在緊湊連續(xù)的空間內(nèi)；但很明顯它會(huì)帶來一定的浪費(fèi)，因?yàn)槊總€(gè) slab class 內(nèi)的每個(gè)內(nèi)存塊大小都是固定的，數(shù)據(jù)的大小必須小于等于內(nèi)存塊的大小。

lru 機(jī)制

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

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

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

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

下面圖解上述的過程：

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

上一篇：Redis 哨兵機(jī)制下一篇：Redis 數(shù)據(jù)結(jié)構(gòu) intset