推薦學習這篇博客。博客的地址：http://kenby.CUOxin.com/blog/1423989

item是Memcached中記錄存儲的基本單元，用戶向memcached寫入的key value鍵值對信息都以item的形式存入Memcached中。

首先用一張圖來描述item的基本結構：

圖 1-1 item的基本機構

圖片來自博客，畫的非常的清晰。從圖片中可以看到，item主要有兩個部分構成：item的元數據（屬性）部分+item的數據本身部分構成。這個就是Memcached中記錄的存儲單元。以下是其定義的源代碼：

typedef struct _stritem {    struct _stritem *next;    struct _stritem *PRev;    struct _stritem *h_next;    /* hash chain next*/    rel_time_t      time;       /* least recent access */    rel_time_t      exptime;    /* expire time */    int             nbytes;     /* size of data */    unsigned short  refcount;    uint8_t         nsuffix;    /* length of flags-and-length string */    uint8_t         it_flags;   /* ITEM_* above */    uint8_t         slabs_clsid;/* which slab class we're in */    uint8_t         nkey;       /* key length, w/terminating null and padding */     union {        uint64_t cas;        char end;    } data[];//data 不占用任何空間} item;

使用typedef定義結構體_stritem為item。這個就是item的定義了。從item的定義中，可以看到，結構體本身并不包含任何關于數據key value的定義。那么是否和圖中的紅色部分有違背呢？

答案是在操作item的時候肯定會在堆上分配空間，開發人員使用了宏定義的技巧，使得對內存的管理更加的靈活方便：

unsigned int size = sizeof(item) + settings.chunk_size;

上面是一個完整的chunk的大小的求解方法，可以看到除了sizeof以外，還額外負擔了用戶手動配置的chunk_size。可以看到一個item所占的空間由兩部分構成，符合2.1.1中對item的定義。而chunk_size所指向的內存空間又是如何劃分的？

首先撇開內存空間的定義，結構體item中最關鍵的data[]空數組的定義：

typedef _stritem{　　....　　union{　　    uint64_t cas;　　    char end;　　}data[];}item;

在_stritem結構體中定義了一個空的數組data[]，data[]不占用任何的空間。當item后續有數據時，data的地址就是緊接著item元數據部分的成員的首地址。有了這個就不難理解宏定義了。

cas是Memcached中為了支持多線程讀寫的一個標志，類似compare and swap（實際上是check and set），是可選的標志。當用戶啟動了cas特性后，則通過以下方式訪問cas位：

item->data->cas;

而當用戶沒有啟用cas的時候，則data就純當指針基地址來使用了。有了以上的知識，我們來看幾個宏定義的使用：

#define ITEM_key(item) (((char*)&((item)->data)) /         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))#define ITEM_suffix(item) ((char*) &((item)->data) + (item)->nkey + 1 /         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))#define ITEM_data(item) ((char*) &((item)->data) + (item)->nkey + 1 /         + (item)->nsuffix /         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))

使用四個宏定義來給予data指針計算不同成員的在堆空間上面的偏移量。來看第一個：ITEM_key(item)，首先將data的地址強制轉換成char*指針，從而以步進為字節方式獲得地址。隨后判斷當前flag是否包含cas的部分，如果包含，則指針加上uint64_t的大?。?個字節）越過cas占用的地址；如果沒有包含，則加0，表明data的地址就是key的地址。

剩下求解suffix、data的地址采用類似相同的方式來完成?？梢钥吹竭@個技巧的牛逼的地方。求解suffix、data地址的時候，可以看到有個+1的操作，這個原因是key的末尾有一個null終結符，占用1個字節的空間。因此需要加一操作。

為了求解整個item占用空間大?。ú皇莄hunk的占用空間），同樣定義了宏來求解：

#define ITEM_ntotal(item) (sizeof(struct _stritem) + (item)->nkey + 1 /         + (item)->nsuffix + (item)->nbytes /         + (((item)->it_flags & ITEM_CAS) ? sizeof(uint64_t) : 0))

首先是_stritem本身的大小，隨后是key的大小，空字節的大小，suffix的大小，value的大小，最后看當前是否使用了cas，如果使用了需要計算cas的大小。對每個分量求和便是整個item的大小。

從本小結的宏定義中我們看到了C語言項目對于內存的精細操作，縱觀編程世界，可能也只有C能夠做出這么精彩的內存操作。

再來引入item的定義，這次直接截圖了，寫代碼太占用空間了。

圖 1-2 item的基本定義

這些數據代表了item的基本信息，在后續的很多數據結構中都會用到他們，以下列舉主要的成員：

v LRU鏈表

next和prev指針用于構成鏈表，這個鏈表維護了當前已經分配的item空間。為了支持LRU特性，鏈表默認以訪問頻度排序，最新訪問的item將位于鏈表的表頭。

v hash表桶

h_next指針用于構成在hash鏈表中，桶內組成鏈表。hash表主要用于快速檢索item。

v 相關時間

item的最近訪問時間以及超時時間，在內存空間不足時，不得不將一些item換出內存，因此使用這個來完成。

v slabs_clsid

描述當前item位于哪個slabs類中。由于每個slab類的大小依次成指數遞增，因此某個item需要位于一個slab類中，而slabs_clsid就是當前slab類的編號。

為了實現快速的檢索，Memcached內部實現了Hash表，就是為了純檢索。Memcached中的Hash表位于assoc.c以及assoc.h中實現的。我們來一睹hash表的定義：

static item** primary_hashtable = 0;

用一個二級item指針就實現了hashtable，其實hashtable的實現都在業務邏輯中了。

Hash表的實際構成結構如下：

圖 1-3 memcached hash表的實現

如上圖，Memcached采用了開鏈方法，對Hash表進行了實現。本節將對Hash表進行介紹。

從圖 1-3可以看出hash表的基本實現。整體來講就是一個指針數組，數組的每個元素存放著一個item。當對item進行存儲檢索時，將item的key求hash值，hash值的求法就是經典的取模法。存入之后就放入對應的編號位置。

如果遇上hash值相同沖突的情況，memcached則使用開鏈法，將相同hash值的item都鏈接在一起，使用item->h_next進行鏈接操作。

為了求解hash值，memcached使用宏定義來求解給定的item應該存入哪個位置。

#define hashsize(n) ((ub4)1<<(n))#define hashmask(n) (hashsize(n)-1)hv = hash(key, nkey, 0);it = primary_hashtable[hv & hashmask(hashpower)]

以上兩個宏定義和兩條語句求解hash表位置的item。其中hv的求解依賴自定義的hash函數，這個函數就不分析了。當求解出hv后，和宏2進行與操作就求出了hash表中桶的位置。而hashsize()就是將1左移n位，達到一個乘二的效果，而hashmask的目的是求出遮擋位：

以下為二進制：

原本：100000

遮擋：011111

可以看出遮擋位將首位變為0，剩余的都變為1。然后hv & hashmask的目的就是進行了一次求余數操作。這種求余操作避免了使用%這樣消耗比較高的操作，缺點是只能應用于2的冪次的求余數操作。但一般為了快速，hash表的桶的個數也是2的冪次數。

求解出桶的位置之后，查找一個item就簡單了。從桶的第0個元素的位置開始依次沿著h_next進行就可以了。

求余一般我都會直接使用%方法進行求解，開源項目能讓人提煉自己的編程功力，提升基礎。

hash表起始桶的個數為16，當存不下之后，hash表需要進行一次擴張操作。hash表的擴張需要一定時間，Memcached為了在表擴張時繼續服務，使用了雙hash表機制：

static item** primary_hashtable = 0;static item** old_hashtable = 0;

平常主要使用primary_hashtable，當hash表擴張的時候，臨時使用old_hashtable，當hash表擴張完畢之后再切換到primary_hashtable。

Memcached使用assoc_maintenance_thread()這個函數對hash表進行管理，實質上是通過一個守護線程死循環處理：

while (do_run_maintenance_thread){    ......}

通過一個while死循環，一直查看hash表的狀態，當hash表滿的時候對表進行擴容。

old_hashtable = primary_hashtable;primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));if (primary_hashtable) {    if (settings.verbose > 1)            fprintf(stderr, "Hash table expansion starting/n");    hashpower++;    expanding = true;    expand_bucket = 0;    STATS_LOCK();    stats.hash_power_level = hashpower;    stats.hash_bytes += hashsize(hashpower) * sizeof(void *);    stats.hash_is_expanding = 1;    STATS_UNLOCK();

開始擴張前，將old_hashtable指向主表，隨即主表重新開始分配空間，可以看到新空間的大小是老空間的2倍。隨后再狀態位里面設置一些標記，記錄hash表新使用的空間。最后將hash_is_expanding置為1，通知線程開始對hash表進行擴張操作。

線程do_run_maintenance_thread負責將老表中的所有數據依次拷貝到新表中。每個循環拷貝一個桶中的所有item，用戶可以設置每個循環拷貝多個桶，通過改變hash_bulk_move變量的值。但是這樣可能會導致堆cache鎖占用的時間過長，影響Memcached對外提供的服務。hash表擴張拷貝的代碼如下：

item *it, *next;int bucket;for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {    next = it->h_next;    bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower);    it->h_next = primary_hashtable[bucket];    primary_hashtable[bucket] = it;}old_hashtable[expand_bucket] = NULLexpand_bucket++;

expand_bucket從0開始?？截悤r，將老表第0個桶中的所有元素依次取出，并重新計算在新表中的桶的位置，拷貝到新表中。如果新表當前桶中已經有了item了，那么就放到桶中的第一個位置中。隨后將老表當前桶的位置置為空。最后對桶計數自增，進入下一個循環，繼續拷貝數據。

memcached刪除元素并不是真的刪除，因為內存都是預先分配好的，hash表中存的東西相當于引用。指針變量退出函數后內存自動就釋放了。因此元素的刪除只是修改hash表的指針結構：

  item **before = _hashitem_before(key, nkey, hv);    if (*before) {        item *nxt;        hash_items--;            MEMCACHED_ASSOC_DELETE(key, nkey, hash_items);        nxt = (*before)->h_next;        (*before)->h_next = 0;   /* probably pointless, but whatever. */        *before = nxt;  //*before代表item->next指針        return;    }

就是將before->h_next=item->h_next操作，經典的跨指針刪除法。函數_hashitem_before查找當前key對應元素的前一個item，以方便刪除操作。

Memcached將所有slab類組織在一起，構成了slab存儲結構。

圖 1-4 slab結構體系

圖1-4是整個slab存儲體系的結構圖，以slab為核心，將空閑槽、LRU隊列、slab列表、hash表完整的組合在一起。hash表已經在上一個小節中分析了，同時也不好在這張圖中進行表述。本小結介紹slab結構體系。

直接上結構體的定義：

圖1-5 slab類定義

定義一個結構體為slabclass_t類型。

size表明當前slab類中item的大小，slab id越高，則當前存儲的item的chunk的大小越大，最大是1MB。perslab保存了當前slab類中擁有多少個item。計算方法很簡單size/perslab就可以計算出來。

slots存儲當前空閑的item。當item不用被回收時，會進入slot中去。slab在分配內存時優先從slots中進行分配。sl_curr看見變量定義的很牛逼，其實就是slots的數量。

slabs，一個slab類可能包含多個slab。系統分配內存時，當一個slab空間用完之后才會再分配下一個slab，這個slabs就是用于當前記錄當前slab類已經分配了多少個slab了。

slab_list，就是多個slab形成的鏈表，用這個指針進行描述。而下面list_size記錄前一個list的大小。記錄的原因是在分配新的slab list的時，通常分配的數量都是前一個list大小的二倍。（很多空間自動增長的數據結構的內部的經典做法）

killing，在slab進行rebalance中使用的機制，暫時沒有涉及這部分的代碼，因此先跳過。

requested，已經請求的數據量大小，當前slab類已經分配出去的內存。

每個slab類都有若干item，構成一個LRU列表。當對這個slab進行內存分配時，如果內存不足，就必須將某個item換出內存，騰出空間給其他申請內存的item使用。某個slab類的item LRU隊列并沒有直接和slabclass_t直接掛鉤，而是通過slab id進行關聯：

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

在item.c文件中定義了兩個全局的指針數組，這個就是當前系統中所有slabclass的LRU隊列的頭、尾指針。如果想要使用指定的LRU隊列，使用head[id]以及tail[id]就可以對特定列表進行引用了。

v item插入

當系統新分配一個item時，需要將item放入LRU隊列中進行保存。放入LRU隊列的對首中：

圖 1-6 item插入

將item插入鏈表的頭部，經典的頭部操作。鏈表插入頭部而不是尾部是有深刻原因的。當一個item插入鏈表時，表明這個item是最新，因此插入頭部。后續進行淘汰item的時候就是從鏈表尾部進行淘汰。Memcached將LRU鏈表中，越靠近頭部的節點，看成越新（更新、插入）的節點，LRU節點尾端的節點看成越老的節點。

v item刪除

刪除指定的item很容易，同樣是經典的指針操作：

圖 1-7 item unlink

可以看出將指針關系更新后，函數就退出了，并沒有真正刪除數據。沒有free的原因就是memcached自己進行內存的管理。釋放item留出的空間放入slab類的空閑槽slot中：

圖 1-8 item unlink后的操作：掛入slot中

函數do_slabs_free負責將釋放的item掛入slot中。同樣是掛入slots隊列的頭部。

當對LRU隊列中item訪問時，需要更新item的狀態，因為空間不夠的時候換出的是一直沒有使用的item。更新操作：

圖 1-9 LRU隊列更新

更新關鍵操作就是if語句塊中的三行代碼：1 把這個item拿出來，2 更新item的訪問時間，3 把這個item再放進去。1和3兩條語句將item從LRU隊列中放入隊列的首部，完成更新的目的。

之前的小結都是零碎的一些源碼部分，這小節以slab的操作為軸，進行相關代碼的分析工作。

主要調用函數do_item_alloc()完成。這個函數的代碼量較多，業務邏輯較為復雜，這里進行簡要的分析。

內存分配時優先從LRU隊列中超時的item進行分配：

圖 1-10 首先從LRU隊列中尋找

search=tails[id]，找到slab類id為id的LRU尾指針，并賦值給Search。從LRU隊列末端開始選擇的原因是LRU隊列尾巴保存著最有可能超時的item，如果隊列末端的都沒超時，則跳過LRU item的換出操作。

從尾端開始查找，如果當前的hash桶被鎖住了，就跳過，查找前一個item。如果沒有跳過，并且item也超時了，則將調用do_item_unlink_nolock將item從hash表和LRU隊列中移除。

如果LRU最后一個item沒有超時，則表明所有LRU隊列中的item均沒有超時，因此暫時不能從LRU隊列進行內存的分配，需要從slab系統進行內存的分配工作：

it = slabs_alloc(ntotal, id)

調用slabs_alloc()函數從slab系統中進行分配。slabs_alloc()函數操作同樣較為負責，為了不打斷do_item_alloc()的邏輯，先把這個函數放放，等do_item_alloc()函數分析完之后再討論。

如果從slab系統中進行內存分配同樣失敗了，則只能還是從LRU隊列中淘汰最舊未使用的item中了：

圖 1-11 LRU隊列換出item

如果slabs_alloc()失敗，則只能無奈從LRU隊列置換一個item出來。如果用戶設置了不允許進行item置換，則最終只能報錯：outofmemory了。否則更新evicted的item數量，并將這個item換出，更新當前slab類需要的內存信息，將換出的item從slab系統中移除。

當移除之后，返回選定的item，對item做基本的初始化，并將item返回給函數上層調用者。

圖 1-12 分配item的初始化

上小節在item分配的時候，首先查看LRU隊列中是否有合適的item。如果沒有，則從slab類中進行內存的分配，調用函數：do_slabs_alloc()。

函數do_slabs_alloc()首先檢查當前slab類中的空閑slot鏈表是否還有可用的slot，如果有則拿一個slot出來：

/* 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;

將slot鏈表中的第一個slot拿出來返回給調用者。如果當前slab類已經沒有后空閑的slot鏈表，則需要重新分配內存，即調用函數：do_slabs_newslab()進行：

if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||        (grow_slab_list(id) == 0) ||//確保slab_list有足夠容量        ((ptr = memory_allocate((size_t)len)) == 0)) {// memory_allocate 分配 1M 的內存空間,         //memory_allocate 就是移動指針        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);        return 0;    }

分配時，首先調用grow_slab_list()確保當前slab類有足夠的空間。函數grow_slab_list()首先判斷已經分配的slab個數是否已經趕上slab list的大小，如果趕上了說明slab list已經分配完了，調用realloc()將slab list的大小擴大一倍。

隨后調用memory_allocate()分配1MB的空間出來，該函數將返回分配空間的指針mem_current，并將mem_current向前移動1MB大小，為下一次分配內存進行準備。又是一個手動管理內存的實例。

最后調用函數split_slab_page_into_freelist()將分配的內存初始化為slots，加入slot鏈表中。函數split_slab_page_into_freelist()將空間切分：

 slabclass_t *p = &slabclass[id];    int x;    //將一大塊兒內存分割成item，掛載到空閑slot中    for (x = 0; x < p->perslab; x++) {        do_slabs_free(ptr, 0, id);        ptr += p->size;　　}

依次將指針進行步進移動，劃分為item，并將這個item進行fdo_slabs_free操作。而do_slabs_free()：

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;

修改當前item的前后指針，將item移入slots鏈表中去。

有了前面小節的基礎，當需要手動刪除item時則比較簡單了，調用函數do_item_unlink()完成。

void do_item_unlink(item *it, const uint32_t hv) {    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes);    mutex_lock(&cache_lock);    if ((it->it_flags & ITEM_LINKED) != 0) {        it->it_flags &= ~ITEM_LINKED;        STATS_LOCK();        stats.curr_bytes -= ITEM_ntotal(it);        stats.curr_items -= 1;        STATS_UNLOCK();        assoc_delete(ITEM_key(it), it->nkey, hv);//hash表中刪除        item_unlink_q(it);//LRU隊列中刪除        do_item_remove(it);//把item放入slot中    }    mutex_unlock(&cache_lock);}

首先設置標志位，更新狀態信息。隨后調用assoc_delete()將item指針關系從hash表中刪除。再調用item_unlink_q()將item指針關系從LRU隊列中刪除。最后調用do_item_remove()將item放入空閑slots隊列中。

可以看出，刪除item的時候并不真正的釋放內存，而是巧妙的將空閑的item放入slots中，以備將來使用。優秀的內存管理操作使得Memcached的性能很高。

本章對slab內存管理進行了介紹?？梢钥闯?，Memcached在對內存管理時，以slab類為核心，通過靈活改變操控hash表、LRU隊列、slab空閑slots三類數據結構，改變item的具體行為以及位置，達成內存的分配與管理工作。設計非常合理與巧妙。