Memcached深度分析

作者：奶瓶
網(wǎng)站： http://www.54np.com

Memcached是danga.com（運(yùn)營(yíng)LiveJournal的技術(shù)團(tuán)隊(duì)）開(kāi)發(fā)的一套分布式內(nèi)存對(duì)象緩存系統(tǒng)，用于在動(dòng)態(tài)系統(tǒng)中減少數(shù)據(jù)庫(kù)負(fù)載，提升性能。關(guān)于這個(gè)東西，相信很多人都用過(guò)，本文意在通過(guò)對(duì)memcached的實(shí)現(xiàn)及代碼分析，獲得對(duì)這個(gè)出色的開(kāi)源軟件更深入的了解，并可以根據(jù)我們的需要對(duì)其進(jìn)行更進(jìn)一步的優(yōu)化。末了將通過(guò)對(duì)BSM_Memcache擴(kuò)展的分析，加深對(duì)memcached的使用方式理解。

本文的部分內(nèi)容可能需要比較好的數(shù)學(xué)基礎(chǔ)作為輔助。

◎Memcached是什么

在闡述這個(gè)問(wèn)題之前，我們首先要清楚它“不是什么”。很多人把它當(dāng)作和SharedMemory那種形式的存儲(chǔ)載體來(lái)使用，雖然memcached使用了同樣的“Key=>Value”方式組織數(shù)據(jù)，但是它和共享內(nèi)存、APC等本地緩存有非常大的區(qū)別。Memcached是分布式的，也就是說(shuō)它不是本地的。它基于網(wǎng)絡(luò)連接（當(dāng)然它也可以使用localhost）方式完成服務(wù)，本身它是一個(gè)獨(dú)立于應(yīng)用的程序或守護(hù)進(jìn)程（Daemon方式）。

Memcached使用libevent庫(kù)實(shí)現(xiàn)網(wǎng)絡(luò)連接服務(wù)，理論上可以處理無(wú)限多的連接，但是它和Apache不同，它更多的時(shí)候是面向穩(wěn)定的持續(xù)連接的，所以它實(shí)際的并發(fā)能力是有限制的。在保守情況下memcached的最大同時(shí)連接數(shù)為200，這和Linux線程能力有關(guān)系，這個(gè)數(shù)值是可以調(diào)整的。關(guān)于libevent可以參考相關(guān)文檔。 Memcached內(nèi)存使用方式也和APC不同。APC是基于共享內(nèi)存和MMAP的，memcachd有自己的內(nèi)存分配算法和管理方式，它和共享內(nèi)存沒(méi)有關(guān)系，也沒(méi)有共享內(nèi)存的限制，通常情況下，每個(gè)memcached進(jìn)程可以管理2GB的內(nèi)存空間，如果需要更多的空間，可以增加進(jìn)程數(shù)。

◎Memcached適合什么場(chǎng)合

在很多時(shí)候，memcached都被濫用了，這當(dāng)然少不了對(duì)它的抱怨。我經(jīng)常在論壇上看見(jiàn)有人發(fā)貼，類(lèi)似于“如何提高效率”，回復(fù)是“用memcached”，至于怎么用，用在哪里，用來(lái)干什么一句沒(méi)有。memcached不是萬(wàn)能的，它也不是適用在所有場(chǎng)合。

Memcached是“分布式”的內(nèi)存對(duì)象緩存系統(tǒng)，那么就是說(shuō)，那些不需要“分布”的，不需要共享的，或者干脆規(guī)模小到只有一臺(tái)服務(wù)器的應(yīng)用，memcached不會(huì)帶來(lái)任何好處，相反還會(huì)拖慢系統(tǒng)效率，因?yàn)榫W(wǎng)絡(luò)連接同樣需要資源，即使是UNIX本地連接也一樣。 在我之前的測(cè)試數(shù)據(jù)中顯示，memcached本地讀寫(xiě)速度要比直接PHP內(nèi)存數(shù)組慢幾十倍，而APC、共享內(nèi)存方式都和直接數(shù)組差不多。可見(jiàn)，如果只是本地級(jí)緩存，使用memcached是非常不劃算的。

Memcached在很多時(shí)候都是作為數(shù)據(jù)庫(kù)前端cache使用的。因?yàn)樗葦?shù)據(jù)庫(kù)少了很多SQL解析、磁盤(pán)操作等開(kāi)銷(xiāo)，而且它是使用內(nèi)存來(lái)管理數(shù)據(jù)的，所以它可以提供比直接讀取數(shù)據(jù)庫(kù)更好的性能，在大型系統(tǒng)中，訪問(wèn)同樣的數(shù)據(jù)是很頻繁的，memcached可以大大降低數(shù)據(jù)庫(kù)壓力，使系統(tǒng)執(zhí)行效率提升。另外，memcached也經(jīng)常作為服務(wù)器之間數(shù)據(jù)共享的存儲(chǔ)媒介，例如在SSO系統(tǒng)中保存系統(tǒng)單點(diǎn)登陸狀態(tài)的數(shù)據(jù)就可以保存在memcached中，被多個(gè)應(yīng)用共享。

需要注意的是，memcached使用內(nèi)存管理數(shù)據(jù)，所以它是易失的，當(dāng)服務(wù)器重啟，或者memcached進(jìn)程中止，數(shù)據(jù)便會(huì)丟失，所以memcached不能用來(lái)持久保存數(shù)據(jù)。很多人的錯(cuò)誤理解，memcached的性能非常好，好到了內(nèi)存和硬盤(pán)的對(duì)比程度，其實(shí)memcached使用內(nèi)存并不會(huì)得到成百上千的讀寫(xiě)速度提高，它的實(shí)際瓶頸在于網(wǎng)絡(luò)連接，它和使用磁盤(pán)的數(shù)據(jù)庫(kù)系統(tǒng)相比，好處在于它本身非常“輕”，因?yàn)闆](méi)有過(guò)多的開(kāi)銷(xiāo)和直接的讀寫(xiě)方式，它可以輕松應(yīng)付非常大的數(shù)據(jù)交換量，所以經(jīng)常會(huì)出現(xiàn)兩條千兆網(wǎng)絡(luò)帶寬都滿負(fù)荷了，memcached進(jìn)程本身并不占用多少CPU資源的情況。

◎Memcached的工作方式

以下的部分中，讀者最好能準(zhǔn)備一份memcached的源代碼。

Memcached是傳統(tǒng)的網(wǎng)絡(luò)服務(wù)程序，如果啟動(dòng)的時(shí)候使用了-d參數(shù)，它會(huì)以守護(hù)進(jìn)程的方式執(zhí)行。創(chuàng)建守護(hù)進(jìn)程由daemon.c完成，這個(gè)程序只有一個(gè)daemon函數(shù)，這個(gè)函數(shù)很簡(jiǎn)單（如無(wú)特殊說(shuō)明，代碼以1.2.1為準(zhǔn)）：

              #include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>

int
daemon(nochdir, noclose)
    int nochdir, noclose;
{
    int fd; 

    switch (fork()) {
    case -1:
        return (-1);
    case 0: 
        break;  
    default:
        _exit(0);
    }

    if (setsid() == -1)
        return (-1);

    if (!nochdir)
        (void)chdir("/");

    if (!noclose && (fd = open("/dev/null", O_RDWR, 0)) != -1) {
        (void)dup2(fd, STDIN_FILENO);
        (void)dup2(fd, STDOUT_FILENO);
        (void)dup2(fd, STDERR_FILENO);
        if (fd > STDERR_FILENO)
            (void)close(fd);
    }
    return (0);
}
            

這個(gè)函數(shù) fork 了整個(gè)進(jìn)程之后，父進(jìn)程就退出，接著重新定位 STDIN 、 STDOUT 、 STDERR 到空設(shè)備， daemon 就建立成功了。

Memcached 本身的啟動(dòng)過(guò)程，在 memcached.c 的 main 函數(shù)中順序如下：

1 、調(diào)用 settings_init() 設(shè)定初始化參數(shù)
2 、從啟動(dòng)命令中讀取參數(shù)來(lái)設(shè)置 setting 值
3 、設(shè)定 LIMIT 參數(shù)
4 、開(kāi)始網(wǎng)絡(luò) socket 監(jiān)聽(tīng)（如果非 socketpath 存在）（ 1.2 之后支持 UDP 方式）
5 、檢查用戶(hù)身份（ Memcached 不允許 root 身份啟動(dòng)）
6 、如果有 socketpath 存在，開(kāi)啟 UNIX 本地連接（Sock 管道）
7 、如果以 -d 方式啟動(dòng)，創(chuàng)建守護(hù)進(jìn)程（如上調(diào)用 daemon 函數(shù)）
8 、初始化 item 、 event 、狀態(tài)信息、 hash 、連接、 slab
9 、如設(shè)置中 managed 生效，創(chuàng)建 bucket 數(shù)組
10 、檢查是否需要鎖定內(nèi)存頁(yè)
11 、初始化信號(hào)、連接、刪除隊(duì)列
12 、如果 daemon 方式，處理進(jìn)程 ID
13 、event 開(kāi)始，啟動(dòng)過(guò)程結(jié)束， main 函數(shù)進(jìn)入循環(huán)。

在 daemon 方式中，因?yàn)?stderr 已經(jīng)被定向到黑洞，所以不會(huì)反饋執(zhí)行中的可見(jiàn)錯(cuò)誤信息。

memcached.c 的主循環(huán)函數(shù)是 drive_machine ，傳入?yún)?shù)是指向當(dāng)前的連接的結(jié)構(gòu)指針，根據(jù) state 成員的狀態(tài)來(lái)決定動(dòng)作。

Memcached 使用一套自定義的協(xié)議完成數(shù)據(jù)交換，它的 protocol 文檔可以參考： http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt

在API中，換行符號(hào)統(tǒng)一為/r/n

◎Memcached的內(nèi)存管理方式

Memcached有一個(gè)很有特色的內(nèi)存管理方式，為了提高效率，它使用預(yù)申請(qǐng)和分組的方式管理內(nèi)存空間，而并不是每次需要寫(xiě)入數(shù)據(jù)的時(shí)候去malloc，刪除數(shù)據(jù)的時(shí)候free一個(gè)指針。Memcached使用slab->chunk的組織方式管理內(nèi)存。

1.1和1.2的slabs.c中的slab空間劃分算法有一些不同，后面會(huì)分別介紹。

Slab可以理解為一個(gè)內(nèi)存塊，一個(gè)slab是memcached一次申請(qǐng)內(nèi)存的最小單位，在memcached中，一個(gè)slab的大小默認(rèn)為1048576字節(jié)（1MB），所以memcached都是整MB的使用內(nèi)存。每一個(gè)slab被劃分為若干個(gè)chunk，每個(gè)chunk里保存一個(gè)item，每個(gè)item同時(shí)包含了item結(jié)構(gòu)體、key和value（注意在memcached中的value是只有字符串的）。slab按照自己的id分別組成鏈表，這些鏈表又按id掛在一個(gè)slabclass數(shù)組上，整個(gè)結(jié)構(gòu)看起來(lái)有點(diǎn)像二維數(shù)組。slabclass的長(zhǎng)度在1.1中是21，在1.2中是200。

slab有一個(gè)初始chunk大小，1.1中是1字節(jié)，1.2中是80字節(jié)，1.2中有一個(gè)factor值，默認(rèn)為1.25

在1.1中，chunk大小表示為初始大小*2^n，n為classid，即：id為0的slab，每chunk大小1字節(jié)，id為1的slab，每chunk大小2字節(jié)，id為2的slab，每chunk大小4字節(jié)……id為20的slab，每chunk大小為1MB，就是說(shuō)id為20的slab里只有一個(gè)chunk：

              void slabs_init(size_t limit) {
    int i;
    int size=1;

    mem_limit = limit;
    for(i=0; i<=POWER_LARGEST; i++, size*=2) {
        slabclass[i].size = size;
        slabclass[i].perslab = POWER_BLOCK / size;
        slabclass[i].slots = 0;
        slabclass[i].sl_curr = slabclass[i].sl_total = slabclass[i].slabs = 0;
        slabclass[i].end_page_ptr = 0;
        slabclass[i].end_page_free = 0;
        slabclass[i].slab_list = 0;
        slabclass[i].list_size = 0;
        slabclass[i].killing = 0;
    }

    /* for the test suite:  faking of how much we've already malloc'd */
    {
        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
        if (t_initial_malloc) {
            mem_malloced = atol(getenv("T_MEMD_INITIAL_MALLOC"));
        }
    }

    /* pre-allocate slabs by default, unless the environment variable
       for testing is set to something non-zero */
    {
        char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
        if (!pre_alloc || atoi(pre_alloc)) {
            slabs_preallocate(limit / POWER_BLOCK);
        }
    }
}
            

在1.2中，chunk大小表示為初始大小*f^n，f為factor，在memcached.c中定義，n為classid，同時(shí)，201個(gè)頭不是全部都要初始化的，因?yàn)閒actor可變，初始化只循環(huán)到計(jì)算出的大小達(dá)到slab大小的一半為止，而且它是從id1開(kāi)始的，即：id為1的slab，每chunk大小80字節(jié)，id為2的slab，每chunk大小80*f，id為3的slab，每chunk大小80*f^2，初始化大小有一個(gè)修正值CHUNK_ALIGN_BYTES，用來(lái)保證n-byte排列 （保證結(jié)果是CHUNK_ALIGN_BYTES的整倍數(shù)）。這樣，在標(biāo)準(zhǔn)情況下，memcached1.2會(huì)初始化到id40，這個(gè)slab中每個(gè)chunk大小為504692，每個(gè)slab中有兩個(gè)chunk。最后，slab_init函數(shù)會(huì)在最后補(bǔ)足一個(gè)id41，它是整塊的，也就是這個(gè)slab中只有一個(gè)1MB大的chunk：

              void slabs_init(size_t limit, double factor) {
    int i = POWER_SMALLEST - 1;
    unsigned int size = sizeof(item) + settings.chunk_size;

    /* Factor of 2.0 means use the default memcached behavior */
    if (factor == 2.0 && size < 128)
        size = 128;

    mem_limit = limit;
    memset(slabclass, 0, sizeof(slabclass));

    while (++i < POWER_LARGEST && size <= POWER_BLOCK / 2) {
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);

        slabclass[i].size = size; 
        slabclass[i].perslab = POWER_BLOCK / slabclass[i].size;
        size *= factor; 
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %6d perslab %5d/n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }       
    }

    power_largest = i;
    slabclass[power_largest].size = POWER_BLOCK;
    slabclass[power_largest].perslab = 1;

    /* for the test suite:  faking of how much we've already malloc'd */
    {
        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
        if (t_initial_malloc) {
            mem_malloced = atol(getenv("T_MEMD_INITIAL_MALLOC"));
        }       

    }

#ifndef DONT_PREALLOC_SLABS
    {
        char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
        if (!pre_alloc || atoi(pre_alloc)) {
            slabs_preallocate(limit / POWER_BLOCK);
        }
    }
#endif
}

            

由上可以看出，memcached的內(nèi)存分配是有冗余的，當(dāng)一個(gè)slab不能被它所擁有的chunk大小整除時(shí)，slab尾部剩余的空間就被丟棄了，如id40中，兩個(gè)chunk占用了1009384字節(jié)，這個(gè)slab一共有1MB，那么就有39192字節(jié)被浪費(fèi)了。

Memcached使用這種方式來(lái)分配內(nèi)存，是為了可以快速的通過(guò)item長(zhǎng)度定位出slab的classid，有一點(diǎn)類(lèi)似hash，因?yàn)閕tem的長(zhǎng)度是可以計(jì)算的，比如一個(gè)item的長(zhǎng)度是300字節(jié)，在1.2中就可以得到它應(yīng)該保存在id7的slab中，因?yàn)榘凑丈厦娴挠?jì)算方法，id6的chunk大小是252字節(jié)，id7的chunk大小是316字節(jié)，id8的chunk大小是396字節(jié)，表示所有252到316字節(jié)的item都應(yīng)該保存在id7中。同理，在1.1中，也可以計(jì)算得到它出于256和512之間，應(yīng)該放在chunk_size為512的id9中(32位系統(tǒng)）。

Memcached初始化的時(shí)候，會(huì)初始化slab（前面可以看到，在main函數(shù)中調(diào)用了slabs_init()）。它會(huì)在slabs_init()中檢查一個(gè)常量DONT_PREALLOC_SLABS，如果這個(gè)沒(méi)有被定義，說(shuō)明使用預(yù)分配內(nèi)存方式初始化slab，這樣在所有已經(jīng)定義過(guò)的slabclass中，每一個(gè)id創(chuàng)建一個(gè)slab。這樣就表示，1.2在默認(rèn)的環(huán)境中啟動(dòng)進(jìn)程后要分配41MB的slab空間，在這個(gè)過(guò)程里，memcached的第二個(gè)內(nèi)存冗余發(fā)生了，因?yàn)橛锌赡芤粋€(gè)id根本沒(méi)有被使用過(guò)，但是它也默認(rèn)申請(qǐng)了一個(gè)slab，每個(gè)slab會(huì)用掉1MB內(nèi)存

當(dāng)一個(gè)slab用光后，又有新的item要插入這個(gè)id，那么它就會(huì)重新申請(qǐng)新的slab，申請(qǐng)新的slab時(shí)，對(duì)應(yīng)id的slab鏈表就要增長(zhǎng)，這個(gè)鏈表是成倍增長(zhǎng)的，在函數(shù)grow_slab_list函數(shù)中，這個(gè)鏈的長(zhǎng)度從1變成2，從2變成4，從4變成8……：

              static int grow_slab_list (unsigned int id) {
    slabclass_t *p = &slabclass[id];
    if (p->slabs == p->list_size) {
        size_t new_size =  p->list_size ? p->list_size * 2 : 16; 
        void *new_list = realloc(p->slab_list, new_size*sizeof(void*));
        if (new_list == 0) return 0;
        p->list_size = new_size;
        p->slab_list = new_list;
    }
    return 1;
}
            

在定位item時(shí)，都是使用slabs_clsid函數(shù)，傳入?yún)?shù)為item大小，返回值為classid，由這個(gè)過(guò)程可以看出，memcached的第三個(gè)內(nèi)存冗余發(fā)生在保存item的過(guò)程中，item總是小于或等于chunk大小的，當(dāng)item小于chunk大小時(shí)，就又發(fā)生了空間浪費(fèi)。

◎Memcached的NewHash算法

Memcached的item保存基于一個(gè)大的hash表，它的實(shí)際地址就是slab中的chunk偏移，但是它的定位是依靠對(duì)key做hash的結(jié)果，在primary_hashtable中找到的。在assoc.c和items.c中定義了所有的hash和item操作。

Memcached使用了一個(gè)叫做NewHash的算法，它的效果很好，效率也很高。1.1和1.2的NewHash有一些不同，主要的實(shí)現(xiàn)方式還是一樣的，1.2的hash函數(shù)是經(jīng)過(guò)整理優(yōu)化的，適應(yīng)性更好一些。

NewHash的原型參考： http://burtleburtle.net/bob/hash/evahash.html 。數(shù)學(xué)家總是有點(diǎn)奇怪，呵呵～

為了變換方便，定義了u4和u1兩種數(shù)據(jù)類(lèi)型，u4就是無(wú)符號(hào)的長(zhǎng)整形，u1就是無(wú)符號(hào)char(0-255)。

具體代碼可以參考1.1和1.2源碼包。

注意這里的hashtable長(zhǎng)度，1.1和1.2也是有區(qū)別的，1.1中定義了HASHPOWER常量為20，hashtable表長(zhǎng)為hashsize(HASHPOWER)，就是4MB（hashsize是一個(gè)宏，表示1右移n位），1.2中是變量16，即hashtable表長(zhǎng)65536：

              typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
typedef  unsigned       char ub1;   /* unsigned 1-byte quantities */

#define hashsize(n) ((ub4)1<<(n))
#define hashmask(n) (hashsize(n)-1)

            

在assoc_init()中，會(huì)對(duì)primary_hashtable做初始化，對(duì)應(yīng)的hash操作包括：assoc_find()、assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete()，對(duì)應(yīng)于item的讀寫(xiě)操作。其中assoc_find()是根據(jù)key和key長(zhǎng)尋找對(duì)應(yīng)的item地址的函數(shù)（注意在C中，很多時(shí)候都是同時(shí)直接傳入字符串和字符串長(zhǎng)度，而不是在函數(shù)內(nèi)部做strlen），返回的是item結(jié)構(gòu)指針，它的數(shù)據(jù)地址在slab中的某個(gè)chunk上。

items.c是數(shù)據(jù)項(xiàng)的操作程序，每一個(gè)完整的item包括幾個(gè)部分，在item_make_header()中定義為：

key：鍵
nkey：鍵長(zhǎng)
flags：用戶(hù)定義的flag（其實(shí)這個(gè)flag在memcached中沒(méi)有啟用）
nbytes：值長(zhǎng)（包括換行符號(hào)/r/n）
suffix：后綴Buffer
nsuffix：后綴長(zhǎng)

一個(gè)完整的item長(zhǎng)度是鍵長(zhǎng)＋值長(zhǎng)＋后綴長(zhǎng)＋item結(jié)構(gòu)大小（32字節(jié)），item操作就是根據(jù)這個(gè)長(zhǎng)度來(lái)計(jì)算slab的classid的。

hashtable中的每一個(gè)桶上掛著一個(gè)雙鏈表，item_init()的時(shí)候已經(jīng)初始化了heads、tails、sizes三個(gè)數(shù)組為0，這三個(gè)數(shù)組的大小都為常量LARGEST_ID（默認(rèn)為255，這個(gè)值需要配合factor來(lái)修改），在每次item_assoc()的時(shí)候，它會(huì)首先嘗試從slab中獲取一塊空閑的chunk，如果沒(méi)有可用的chunk，會(huì)在鏈表中掃描50次，以得到一個(gè)被LRU踢掉的item，將它unlink，然后將需要插入的item插入鏈表中。

注意item的refcount成員。item被unlink之后只是從鏈表上摘掉，不是立刻就被free的，只是將它放到刪除隊(duì)列中（item_unlink_q()函數(shù)）。

item對(duì)應(yīng)一些讀寫(xiě)操作，包括remove、update、replace，當(dāng)然最重要的就是alloc操作。

item還有一個(gè)特性就是它有過(guò)期時(shí)間，這是memcached的一個(gè)很有用的特性，很多應(yīng)用都是依賴(lài)于memcached的item過(guò)期，比如session存儲(chǔ)、操作鎖等。item_flush_expired()函數(shù)就是掃描表中的item，對(duì)過(guò)期的item執(zhí)行unlink操作，當(dāng)然這只是一個(gè)回收動(dòng)作，實(shí)際上在get的時(shí)候還要進(jìn)行時(shí)間判斷：

              /* expires items that are more recent than the oldest_live setting. */
void item_flush_expired() {
    int i;  
    item *iter, *next;
    if (! settings.oldest_live)
        return; 
    for (i = 0; i < LARGEST_ID; i++) {
        /* The LRU is sorted in decreasing time order, and an item's timestamp
         * is never newer than its last access time, so we only need to walk
         * back until we hit an item older than the oldest_live time.
         * The oldest_live checking will auto-expire the remaining items.
         */
        for (iter = heads[i]; iter != NULL; iter = next) { 
            if (iter->time >= settings.oldest_live) {
                next = iter->next;
                if ((iter->it_flags & ITEM_SLABBED) == 0) { 
                    item_unlink(iter);
                }       
            } else {
                /* We've hit the first old item. Continue to the next queue. */
                break;  
            }       
        }       
    }
}

            

              /* wrapper around assoc_find which does the lazy expiration/deletion logic */
item *get_item_notedeleted(char *key, size_t nkey, int *delete_locked) {
    item *it = assoc_find(key, nkey);
    if (delete_locked) *delete_locked = 0;
    if (it && (it->it_flags & ITEM_DELETED)) {
        /* it's flagged as delete-locked.  let's see if that condition
           is past due, and the 5-second delete_timer just hasn't
           gotten to it yet... */
        if (! item_delete_lock_over(it)) {
            if (delete_locked) *delete_locked = 1;
            it = 0; 
        }       
    }
    if (it && settings.oldest_live && settings.oldest_live <= current_time &&
        it->time <= settings.oldest_live) {
        item_unlink(it);
        it = 0; 
    }
    if (it && it->exptime && it->exptime <= current_time) {
        item_unlink(it);
        it = 0; 
    }
    return it;
}

            

Memcached的內(nèi)存管理方式是非常精巧和高效的，它很大程度上減少了直接alloc系統(tǒng)內(nèi)存的次數(shù)，降低函數(shù)開(kāi)銷(xiāo)和內(nèi)存碎片產(chǎn)生幾率，雖然這種方式會(huì)造成一些冗余浪費(fèi)，但是這種浪費(fèi)在大型系統(tǒng)應(yīng)用中是微不足道的。

◎Memcached的理論參數(shù)計(jì)算方式

影響 memcached 工作的幾個(gè)參數(shù)有：

常量REALTIME_MAXDELTA 60*60*24*30
最大30天的過(guò)期時(shí)間

conn_init()中的freetotal（=200）
最大同時(shí)連接數(shù)

常量KEY_MAX_LENGTH 250
最大鍵長(zhǎng)

settings.factor（=1.25）
factor將影響chunk的步進(jìn)大小

settings.maxconns（=1024）
最大軟連接

settings.chunk_size（=48）
一個(gè)保守估計(jì)的key+value長(zhǎng)度，用來(lái)生成id1中的chunk長(zhǎng)度（1.2）。id1的chunk長(zhǎng)度等于這個(gè)數(shù)值加上item結(jié)構(gòu)體的長(zhǎng)度（32），即默認(rèn)的80字節(jié)。

常量POWER_SMALLEST 1
最小classid（1.2）

常量POWER_LARGEST 200
最大classid（1.2）

常量POWER_BLOCK 1048576
默認(rèn)slab大小

常量CHUNK_ALIGN_BYTES (sizeof(void *))
保證chunk大小是這個(gè)數(shù)值的整數(shù)倍，防止越界（void *的長(zhǎng)度在不同系統(tǒng)上不一樣，在標(biāo)準(zhǔn)32位系統(tǒng)上是4）

常量ITEM_UPDATE_INTERVAL 60
隊(duì)列刷新間隔

常量LARGEST_ID 255
最大item鏈表數(shù)（這個(gè)值不能比最大的classid小）

變量hashpower（在1.1中是常量HASHPOWER）
決定hashtable的大小

根據(jù)上面介紹的內(nèi)容及參數(shù)設(shè)定，可以計(jì)算出的一些結(jié)果：

1、在memcached中可以保存的item個(gè)數(shù)是沒(méi)有軟件上限的，之前我的100萬(wàn)的說(shuō)法是錯(cuò)誤的。
2、假設(shè)NewHash算法碰撞均勻，查找item的循環(huán)次數(shù)是item總數(shù)除以hashtable大小（由hashpower決定），是線性的。
3、Memcached限制了可以接受的最大item是1MB，大于1MB的數(shù)據(jù)不予理會(huì)。
4、Memcached的空間利用率和數(shù)據(jù)特性有很大的關(guān)系，又與DONT_PREALLOC_SLABS常量有關(guān)。 在最差情況下，有198個(gè)slab會(huì)被浪費(fèi)（所有item都集中在一個(gè)slab中，199個(gè)id全部分配滿）。

◎Memcached的定長(zhǎng)優(yōu)化

根據(jù)上面幾節(jié)的描述，多少對(duì)memcached有了一個(gè)比較深入的認(rèn)識(shí)。在深入認(rèn)識(shí)的基礎(chǔ)上才好對(duì)它進(jìn)行優(yōu)化。

Memcached本身是為變長(zhǎng)數(shù)據(jù)設(shè)計(jì)的，根據(jù)數(shù)據(jù)特性，可以說(shuō)它是“面向大眾”的設(shè)計(jì)，但是很多時(shí)候，我們的數(shù)據(jù)并不是這樣的“普遍”，典型的情況中，一種是非均勻分布，即數(shù)據(jù)長(zhǎng)度集中在幾個(gè)區(qū)域內(nèi)（如保存用戶(hù) Session）；另一種更極端的狀態(tài)是等長(zhǎng)數(shù)據(jù)（如定長(zhǎng)鍵值，定長(zhǎng)數(shù)據(jù)，多見(jiàn)于訪問(wèn)、在線統(tǒng)計(jì)或執(zhí)行鎖）。

這里主要研究一下定長(zhǎng)數(shù)據(jù)的優(yōu)化方案（1.2），集中分布的變長(zhǎng)數(shù)據(jù)僅供參考，實(shí)現(xiàn)起來(lái)也很容易。

解決定長(zhǎng)數(shù)據(jù)，首先需要解決的是slab的分配問(wèn)題，第一個(gè)需要確認(rèn)的是我們不需要那么多不同chunk長(zhǎng)度的slab，為了最大限度地利用資源，最好chunk和item等長(zhǎng)，所以首先要計(jì)算item長(zhǎng)度。

在之前已經(jīng)有了計(jì)算item長(zhǎng)度的算法，需要注意的是，除了字符串長(zhǎng)度外，還要加上item結(jié)構(gòu)的長(zhǎng)度32字節(jié)。

假設(shè)我們已經(jīng)計(jì)算出需要保存200字節(jié)的等長(zhǎng)數(shù)據(jù)。

接下來(lái)是要修改slab的classid和chunk長(zhǎng)度的關(guān)系。在原始版本中，chunk長(zhǎng)度和classid是有對(duì)應(yīng)關(guān)系的，現(xiàn)在如果把所有的chunk都定為200個(gè)字節(jié)，那么這個(gè)關(guān)系就不存在了，我們需要重新確定這二者的關(guān)系。一種方法是，整個(gè)存儲(chǔ)結(jié)構(gòu)只使用一個(gè)固定的id，即只使用199個(gè)槽中的1個(gè)，在這種條件下，就一定要定義DONT_PREALLOC_SLABS來(lái)避免另外的預(yù)分配浪費(fèi)。另一種方法是建立一個(gè)hash關(guān)系，來(lái)從item確定classid，不能使用長(zhǎng)度來(lái)做鍵，可以使用key的NewHash結(jié)果等不定數(shù)據(jù)，或者直接根據(jù)key來(lái)做hash（定長(zhǎng)數(shù)據(jù)的key也一定等長(zhǎng)）。這里簡(jiǎn)單起見(jiàn)，選擇第一種方法，這種方法的不足之處在于只使用一個(gè)id，在數(shù)據(jù)量非常大的情況下，slab鏈會(huì)很長(zhǎng)（因?yàn)樗袛?shù)據(jù)都擠在一條鏈上了），遍歷起來(lái)的代價(jià)比較高。

前面介紹了三種空間冗余，設(shè)置chunk長(zhǎng)度等于item長(zhǎng)度，解決了第一種空間浪費(fèi)問(wèn)題，不預(yù)申請(qǐng)空間解決了第二種空間浪費(fèi)問(wèn)題，那么對(duì)于第一種問(wèn)題（slab內(nèi)剩余）如何解決呢，這就需要修改POWER_BLOCK常量，使得每一個(gè)slab大小正好等于chunk長(zhǎng)度的整數(shù)倍，這樣一個(gè)slab就可以正好劃分成n個(gè)chunk。這個(gè)數(shù)值應(yīng)該比較接近1MB，過(guò)大的話同樣會(huì)造成冗余，過(guò)小的話會(huì)造成次數(shù)過(guò)多的alloc，根據(jù)chunk長(zhǎng)度為200，選擇1000000作為POWER_BLOCK的值，這樣一個(gè)slab就是100萬(wàn)字節(jié)，不是1048576。三個(gè)冗余問(wèn)題都解決了，空間利用率會(huì)大大提升。

修改 slabs_clsid 函數(shù)，讓它直接返回一個(gè)定值（比如 1 ）：

              unsigned int slabs_clsid(size_t size) {
	return 1;
}
            

修改slabs_init函數(shù)，去掉循環(huán)創(chuàng)建所有classid屬性的部分，直接添加slabclass[1]：

              slabclass[1].size = 200;		//每chunk200字節(jié)
slabclass[1].perslab = 5000;	//1000000/200
            

◎Memcached客戶(hù)端

Memcached是一個(gè)服務(wù)程序，使用的時(shí)候可以根據(jù)它的協(xié)議，連接到memcached服務(wù)器上，發(fā)送命令給服務(wù)進(jìn)程，就可以操作上面的數(shù)據(jù)。為了方便使用，memcached有很多個(gè)客戶(hù)端程序可以使用，對(duì)應(yīng)于各種語(yǔ)言，有各種語(yǔ)言的客戶(hù)端。基于C語(yǔ)言的有l(wèi)ibmemcache、APR_Memcache；基于Perl的有Cache::Memcached；另外還有Python、Ruby、Java、C#等語(yǔ)言的支持。PHP的客戶(hù)端是最多的，不光有mcache和PECL memcache兩個(gè)擴(kuò)展，還有大把的由PHP編寫(xiě)的封裝類(lèi)，下面介紹一下在PHP中使用memcached的方法：

mcache擴(kuò)展是基于libmemcache再封裝的。libmemcache一直沒(méi)有發(fā)布stable版本，目前版本是1.4.0-rc2，可以在 這里 找到。libmemcache有一個(gè)很不好的特性，就是會(huì)向stderr寫(xiě)很多錯(cuò)誤信息，一般的，作為lib使用的時(shí)候，stderr一般都會(huì)被定向到其它地方，比如Apache的錯(cuò)誤日志，而且libmemcache會(huì)自殺，可能會(huì)導(dǎo)致異常，不過(guò)它的性能還是很好的。

mcache擴(kuò)展最后更新到1.2.0-beta10，作者大概是離職了，不光停止更新，連網(wǎng)站也打不開(kāi)了（~_~），只能到其它地方去獲取這個(gè)不負(fù)責(zé)的擴(kuò)展了。解壓后安裝方法如常：phpize & configure & make & make install，一定要先安裝libmemcache。使用這個(gè)擴(kuò)展很簡(jiǎn)單：

              <?php
$mc = memcache();	// 創(chuàng)建一個(gè)memcache連接對(duì)象，注意這里不是用new！
$mc->add_server('localhost', 11211);	// 添加一個(gè)服務(wù)進(jìn)程
$mc->add_server('localhost', 11212);	// 添加第二個(gè)服務(wù)進(jìn)程
$mc->set('key1', 'Hello');	// 寫(xiě)入key1 => Hello
$mc->set('key2', 'World', 10);	// 寫(xiě)入key2 => World，10秒過(guò)期
$mc->set('arr1', array('Hello', 'World'));	// 寫(xiě)入一個(gè)數(shù)組
$key1 = $mc->get('key1');	// 獲取'key1'的值，賦給$key1
$key2 = $mc->get('key2');	// 獲取'key2'的值，賦給$key2，如果超過(guò)10秒，就取不到了
$arr1 = $mc->get('arr1');	// 獲取'arr1'數(shù)組
$mc->delete('arr1');	// 刪除'arr1'
$mc->flush_all();	// 刪掉所有數(shù)據(jù)
$stats = $mc->stats();	// 獲取服務(wù)器信息
var_dump($stats);	// 服務(wù)器信息是一個(gè)數(shù)組
?>

            

這個(gè)擴(kuò)展的好處是可以很方便地實(shí)現(xiàn)分布式存儲(chǔ)和負(fù)載均衡，因?yàn)樗梢蕴砑佣鄠€(gè)服務(wù)地址，數(shù)據(jù)在保存的時(shí)候是會(huì)根據(jù)hash結(jié)果定位到某臺(tái)服務(wù)器上的，這也是libmemcache的特性。libmemcache支持集中hash方式，包括CRC32、ELF和Perl hash。

PECL memcache是PECL發(fā)布的擴(kuò)展，目前最新版本是2.1.0，可以在pecl網(wǎng)站 得到 。memcache擴(kuò)展的使用方法可以在新一些的PHP手冊(cè)中找到，它和mcache很像，真的很像：

              <?php

$memcache = new Memcache;
$memcache->connect('localhost', 11211) or die ("Could not connect");

$version = $memcache->getVersion();
echo "Server's version: ".$version."/n";

$tmp_object = new stdClass;
$tmp_object->str_attr = 'test';
$tmp_object->int_attr = 123;

$memcache->set('key', $tmp_object, false, 10) or die ("Failed to save data at the server");
echo "Store data in the cache (data will expire in 10 seconds)/n";

$get_result = $memcache->get('key');
echo "Data from the cache:/n";

var_dump($get_result);

?>

            

這個(gè)擴(kuò)展是使用php的stream直接連接memcached服務(wù)器并通過(guò)socket發(fā)送命令的。它不像libmemcache那樣完善，也不支持add_server這種分布操作，但是因?yàn)樗灰蕾?lài)其它的外界程序，兼容性要好一些，也比較穩(wěn)定。至于效率，差別不是很大。

另外，有很多的PHP class可以使用，比如MemcacheClient.inc.php， phpclasses.org 上可以找到很多，一般都是對(duì)perl client API的再封裝，使用方式很像。

◎BSM_Memcache

從C client來(lái)說(shuō)，APR_Memcache是一個(gè)很成熟很穩(wěn)定的client程序，支持線程鎖和原子級(jí)操作，保證運(yùn)行的穩(wěn)定性。不過(guò)它是基于APR的（APR將在最后一節(jié)介紹），沒(méi)有l(wèi)ibmemcache的應(yīng)用范圍廣，目前也沒(méi)有很多基于它開(kāi)發(fā)的程序，現(xiàn)有的多是一些Apache Module，因?yàn)樗荒苊撾xAPR環(huán)境運(yùn)行。但是APR倒是可以脫離Apache單獨(dú)安裝的，在 APR網(wǎng)站 上可以下載APR和APR-util，不需要有Apache，可以直接安裝，而且它是跨平臺(tái)的。

BSM_Memcache是我在BS.Magic項(xiàng)目中開(kāi)發(fā)的一個(gè)基于APR_Memcache的PHP擴(kuò)展，說(shuō)起來(lái)有點(diǎn)拗口，至少它把APR扯進(jìn)了PHP擴(kuò)展中。這個(gè)程序很簡(jiǎn)單，也沒(méi)做太多的功能，只是一種形式的嘗試，它支持服務(wù)器分組。

和mcache擴(kuò)展支持多服務(wù)器分布存儲(chǔ)不同，BSM_Memcache支持多組服務(wù)器，每一組內(nèi)的服務(wù)器還是按照hash方式來(lái)分布保存數(shù)據(jù)，但是兩個(gè)組中保存的數(shù)據(jù)是一樣的，也就是實(shí)現(xiàn)了熱備，它不會(huì)因?yàn)橐慌_(tái)服務(wù)器發(fā)生單點(diǎn)故障導(dǎo)致數(shù)據(jù)無(wú)法獲取，除非所有的服務(wù)器組都損壞（例如機(jī)房停電）。當(dāng)然實(shí)現(xiàn)這個(gè)功能的代價(jià)就是性能上的犧牲，在每次添加刪除數(shù)據(jù)的時(shí)候都要掃描所有的組，在get數(shù)據(jù)的時(shí)候會(huì)隨機(jī)選擇一組服務(wù)器開(kāi)始輪詢(xún)，一直到找到數(shù)據(jù)為止，正常情況下一次就可以獲取得到。

BSM_Memcache只支持這幾個(gè)函數(shù)：

              zend_function_entry bsm_memcache_functions[] =
{
    PHP_FE(mc_get,          NULL)
    PHP_FE(mc_set,          NULL)
    PHP_FE(mc_del,          NULL)
    PHP_FE(mc_add_group,    NULL)
    PHP_FE(mc_add_server,   NULL)
    PHP_FE(mc_shutdown,     NULL)
    {NULL, NULL, NULL}
};

            

mc_add_group函數(shù)返回一個(gè)整形（其實(shí)應(yīng)該是一個(gè)object，我偷懶了~_~）作為組ID，mc_add_server的時(shí)候要提供兩個(gè)參數(shù)，一個(gè)是組ID，一個(gè)是服務(wù)器地址（ADDR:PORT）。

              /**
* Add a server group
*/
PHP_FUNCTION(mc_add_group)
{
    apr_int32_t group_id;
    apr_status_t rv;

    if (0 != ZEND_NUM_ARGS())
    {
        WRONG_PARAM_COUNT;
        RETURN_NULL();
    }

    group_id = free_group_id();
    if (-1 == group_id)
    {
        RETURN_FALSE;
    }

    apr_memcache_t *mc;
    rv = apr_memcache_create(p, MAX_G_SERVER, 0, &mc);

    add_group(group_id, mc);

    RETURN_DOUBLE(group_id);
}

            

              /**
* Add a server into group
*/
PHP_FUNCTION(mc_add_server)
{
    apr_status_t rv;
    apr_int32_t group_id;
    double g;
    char *srv_str;
    int srv_str_l;

    if (2 != ZEND_NUM_ARGS())
    {
        WRONG_PARAM_COUNT;
    }

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ds", &g, &srv_str, &srv_str_l) == FAILURE)
    {
        RETURN_FALSE;
    }

    group_id = (apr_int32_t) g;

    if (-1 == is_validate_group(group_id))
    {
        RETURN_FALSE;
    }

    char *host, *scope;
    apr_port_t port;

    rv = apr_parse_addr_port(&host, &scope, &port, srv_str, p);
    if (APR_SUCCESS == rv)
    {
        // Create this server object
        apr_memcache_server_t *st;
        rv = apr_memcache_server_create(p, host, port, 0, 64, 1024, 600, &st);
        if (APR_SUCCESS == rv)
        {
            if (NULL == mc_groups[group_id])
            {
                RETURN_FALSE;
            }

            // Add server
            rv = apr_memcache_add_server(mc_groups[group_id], st);

            if (APR_SUCCESS == rv)
            {
                RETURN_TRUE;
            }
        }
    }

    RETURN_FALSE;
}

            

在set和del數(shù)據(jù)的時(shí)候，要循環(huán)所有的組：

              /**
* Store item into all groups
*/
PHP_FUNCTION(mc_set)
{
    char *key, *value;
    int key_l, value_l;
    double ttl = 0;
    double set_ct = 0;

    if (2 != ZEND_NUM_ARGS())
    {
        WRONG_PARAM_COUNT;
    }

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|d", &key, &key_l, &value, &value_l, ttl) == FAILURE)
    {
        RETURN_FALSE;
    }

    // Write data into every object
    apr_int32_t i = 0;
    if (ttl < 0)
    {
        ttl = 0;
    }

    apr_status_t rv;

    for (i = 0; i < MAX_GROUP; i++)
    {
        if (0 == is_validate_group(i))
        {
            // Write it!
            rv = apr_memcache_add(mc_groups[i], key, value, value_l, (apr_uint32_t) ttl, 0);
            if (APR_SUCCESS == rv)
            {
                set_ct++;
            }
        }
    }

    RETURN_DOUBLE(set_ct);
}

            

在mc_get中，首先要隨機(jī)選擇一個(gè)組，然后從這個(gè)組開(kāi)始輪詢(xún)：

              /**
* Fetch a item from a random group
*/
PHP_FUNCTION(mc_get)
{               
    char *key, *value = NULL;
    int key_l;
    apr_size_t value_l;

    if (1 != ZEND_NUM_ARGS())
    {
        WRONG_PARAM_COUNT;
    }

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "s", &key, &key_l) == FAILURE)
    {
        RETURN_MULL();
    }
    
    // I will try ...
    // Random read
    apr_int32_t curr_group_id = random_group();
    apr_int32_t i = 0;
    apr_int32_t try = 0;
    apr_uint32_t flag;
    apr_memcache_t *oper;
    apr_status_t rv;

    for (i = 0; i < MAX_GROUP; i++)
    {
        try = i + curr_group_id;
        try = try % MAX_GROUP;
        if (0 == is_validate_group(try))
        {
            // Get a value
            oper = mc_groups[try];
            rv = apr_memcache_getp(mc_groups[try], p, (const char *) key, &value, &value_l, 0);
            if (APR_SUCCESS == rv)
            {
                RETURN_STRING(value, 1);
            }
        }
    }

    RETURN_FALSE;
}

            

              /**
* Random group id
* For mc_get()
*/
apr_int32_t random_group()
{
    struct timeval tv;
    struct timezone tz;
    int usec;

    gettimeofday(&tv, &tz);

    usec = tv.tv_usec;

    int curr = usec % count_group();

    return (apr_int32_t) curr;
}

            

BSM_Memcache的使用方式和其它的client類(lèi)似：

              <?php
$g1 = mc_add_group();	// 添加第一個(gè)組
$g2 = mc_add_group();	// 添加第二個(gè)組
mc_add_server($g1, 'localhost:11211');	// 在第一個(gè)組中添加第一臺(tái)服務(wù)器
mc_add_server($g1, 'localhost:11212');	// 在第一個(gè)組中添加第二臺(tái)服務(wù)器
mc_add_server($g2, '10.0.0.16:11211');	// 在第二個(gè)組中添加第一臺(tái)服務(wù)器
mc_add_server($g2, '10.0.0.17:11211');	// 在第二個(gè)組中添加第二臺(tái)服務(wù)器

mc_set('key', 'Hello');	// 寫(xiě)入數(shù)據(jù)
$key = mc_get('key');	// 讀出數(shù)據(jù)
mc_del('key');	// 刪除數(shù)據(jù)
mc_shutdown();	// 關(guān)閉所有組
?>

            

APR_Memcache的相關(guān)資料可以在 這里 找到，BSM_Memcache可以在本站 下載 。

◎APR環(huán)境介紹

APR的全稱(chēng)：Apache Portable Runtime。它是 Apache軟件基金會(huì) 創(chuàng)建并維持的一套跨平臺(tái)的C語(yǔ)言庫(kù)。它從Apache httpd1.x中抽取出來(lái)并獨(dú)立于httpd之外，Apache httpd2.x就是建立在APR上。APR提供了很多方便的API接口可供使用，包括如內(nèi)存池、字符串操作、網(wǎng)絡(luò)、數(shù)組、hash表等實(shí)用的功能。開(kāi)發(fā)Apache2 Module要接觸很多APR函數(shù)，當(dāng)然APR可以獨(dú)立安裝獨(dú)立使用，可以用來(lái)寫(xiě)自己的應(yīng)用程序，不一定是Apache httpd的相關(guān)開(kāi)發(fā)。

◎后記

這是我在農(nóng)歷丙戌年（我的本命年）的最后一篇文章，由于Memcached的內(nèi)涵很多，倉(cāng)促整理一定有很多遺漏和錯(cuò)誤。感謝新浪網(wǎng)提供的研究機(jī)會(huì)，感謝部門(mén)同事的幫助。

NP博士 02-13-2007