深入理解Memcached原理

來自： http://blog.csdn.net//chenleixing/article/details/47035453

1.為什么要使用memcache

 由于網站的高并發讀寫需求，傳統的關系型數據庫開始出現瓶頸，例如：

1）對數據庫的高并發讀寫：

關系型數據庫本身就是個龐然大物，處理過程非常耗時（如解析SQL語句，事務處理等）。如果對關系型數據庫進行高并發讀寫（每秒上萬次的訪問），那么它是無法承受的。

2）對海量數據的處理：

對于大型的SNS網站，每天有上千萬次的數據產生（如推ter, 新浪微博）。對于關系型數據庫，如果在一個有上億條數據的數據表種查找某條記錄，效率將非常低。

使用memcache能很好的解決以上問題。

在實際使用中，通常把數據庫查詢的結果保存到Memcache中，下次訪問時直接從memcache中讀取，而不再進行數據庫查詢操作，這樣就在很大程度上減少了數據庫的負擔。

保存在memcache中的對象實際放置在內存中，這也是memcache如此高效的原因。

2.memcache的安裝和使用

這個網上有太多教程了，不做贅言。

3.基于libevent的事件處理

 memcached使用這個libevent庫，因此能在Linux、BSD、Solaris等操作系統上發揮其高性能。 

參考：

• libevent: http://www.monkey.org/~provos/libevent/
• The C10K Problem: http://www.kegel.com/c10k.html

 

4.memcache使用實例：

<?php
$mc = new Memcache();
$mc->connect('127.0.0.1', 11211);

$uid = (int)$_GET['uid'];
$sql = "select * from users where uid='uid' ";
$key = md5($sql);
if(!($data = $mc->get($key))) {
    $conn = mysql_connect('localhost', 'test', 'test');
    mysql_select_db('test');
    $result = mysql_fetch_object($result);
    while($row = mysql_fetch_object($result)) {
          $data[] = $row;
    }
    $mc->add($key, $datas);
}

var_dump($datas);
?>

 

5.memcache如何支持高并發(此處還需深入研究)

memcache使用多路復用I/O模型，如（epoll, select等），傳統I/O中，系統可能會因為某個用戶連接還沒做好I/O準備而一直等待，知道這個連接做好I/O準備。這時如果有其他用戶連接到服務器，很可能會因為系統阻塞而得不到響應。

而多路復用I/O是一種消息通知模式，用戶連接做好I/O準備后，系統會通知我們這個連接可以進行I/O操作，這樣就不會阻塞在某個用戶連接。因此，memcache才能支持高并發。

此外，memcache使用了多線程機制。可以同時處理多個請求。線程數一般設置為CPU核數，這研報告效率最高。

6.使用Slab分配算法保存數據

slab分配算法的原理是：把固定大小（1MB）的內存分為n小塊，如下圖所示：

slab分配算法把每1MB大小的內存稱為一個slab頁，每次向系統申請一個slab頁，然后再通過分隔算法把這個slab頁分割成若干個小塊的chunk（如上圖所示），然后把這些chunk分配給用戶使用，分割算法如下（在slabs.c文件中）：

(注：memcache的github項目地址：https://github.com/wusuopubupt/memcached)

/**
 * Determines the chunk sizes and initializes the slab class descriptors
 * accordingly.
 */
void slabs_init(const size_t limit, const double factor, const bool prealloc) {
    int i = POWER_SMALLEST - 1;
    unsigned int size = sizeof(item) + settings.chunk_size;

    mem_limit = limit;

    if (prealloc) {
        /* Allocate everything in a big chunk with malloc 通過malloc的方式申請內存*/
        mem_base = malloc(mem_limit);
        if (mem_base != NULL) {
            mem_current = mem_base;
            mem_avail = mem_limit;
        } else {
            fprintf(stderr, "Warning: Failed to allocate requested memory in"
                    " one large chunk.\nWill allocate in smaller chunks\n");
        }
    }

    memset(slabclass, 0, sizeof(slabclass));

    while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {
        /* 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 = settings.item_size_max / slabclass[i].size;
        size *= factor;//以1.25為倍數增大chunk
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }
    }

    power_largest = i;
    slabclass[power_largest].size = settings.item_size_max;
    slabclass[power_largest].perslab = 1;
    if (settings.verbose > 1) {
        fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                i, slabclass[i].size, slabclass[i].perslab);
    }

    /* 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 = (size_t)atol(t_initial_malloc);
        }

    }

    if (prealloc) {
        slabs_preallocate(power_largest);
    }
}

 

上面代碼中的slabclass是一個類型為slabclass_t結構的數組，其定義如下：

typedef struct {
    unsigned int size;      /* sizes of items */
    unsigned int perslab;   /* how many items per slab */
    void **slots;           /* list of item ptrs */
    unsigned int sl_total;  /* size of previous array */
    unsigned int sl_curr;   /* first free slot */
    void *end_page_ptr;         /* pointer to next free item at end of page, or 0 */
    unsigned int end_page_free; /* number of items remaining at end of last alloced page */
    unsigned int slabs;     /* how many slabs were allocated for this class */
    void **slab_list;       /* array of slab pointers */
    unsigned int list_size; /* size of prev array */
    unsigned int killing;  /* index+1 of dying slab, or zero if none */
    size_t requested; /* The number of requested bytes */
} slabclass_t;

 

借用別人的一張圖說明slabclass_t結構:

由分割算法的源代碼可知，slab算法按照不同大小的chunk分割slab頁，而不同大小的chunk以factor（默認是1.25）倍增大。

使用memcache -u root -vv 命令查看內存分配情況(8字節對齊)：

找到大小最合適的chunk分配給請求緩存的數據：

/*
 * Figures out which slab class (chunk size) is required to store an item of
 * a given size.
 *
 * Given object size, return id to use when allocating/freeing memory for object
 * 0 means error: can't store such a large object
 */

unsigned int slabs_clsid(const size_t size) {
    int res = POWER_SMALLEST;// 初始化為最小的chunk

    if (size == 0)
        return 0;
    while (size > slabclass[res].size) //逐漸增大chunk size，直到找到第一個比申請的size大的chunk
        if (res++ == power_largest)     /* won't fit in the biggest slab */
            return 0;
    return res;
}

內存分配：

（此處參考：http://slowsnail.com.cn/?p=20）

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) {//判斷id是否會導致slabclass[]數組越界
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
        return NULL;
    }

    p = &slabclass[id];//獲取slabclass[id]的引用
    assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0);//判斷slabclass[id]是否有剩余的chunk

    if (! (p->sl_curr != 0 || do_slabs_newslab(id) != 0)) {//如果slabclass[id]中已經沒有空余chunk并且試圖向系統申請一個“頁”（slab）的chunk失敗,則返回NULL
    /* We don't have more memory available */
        ret = NULL;
    } else if (p->sl_curr != 0) {//slabclass[id]的空閑鏈表中還有chunk，則直接將其分配出去
        it = (item *)p->slots;//獲取空閑鏈表的頭指針
        p->slots = it->next;//將頭結點指向下一個結點（取下頭結點）
        if (it->next) it->next->prev = 0;//將新頭結點的prev指針置空
        p->sl_curr--;//減少slabclass[id]空閑鏈表中的chunk計數
        ret = (void *)it;//將頭結點賦給ret指針
    }

    if (ret) {//請求成功
        p->requested += size;//更新slabclass[id]所分配的內存總數
        MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);
    } else {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
    }

    return ret;
}

do_slabs_allc()函數首先嘗試從slot列表（被回收的chunk）中獲取可用的chunk,如果有可用的就返回，否則從空閑的chunk列表中獲取可用的chunk并返回。

刪除過期item:

延遲刪除過期item到查找時進行，可以提高memcache的效率，因為不必每時每刻檢查過期item,從而提高CPU工作效率

使用LRU(last recently used)算法淘汰數據：

/*
 * try to get one off the right LRU
 * don't necessariuly unlink the tail because it may be locked: refcount>0
 * search up from tail an item with refcount==0 and unlink it; give up after 50
 * tries
 */

if (tails[id] == 0) {
    itemstats[id].outofmemory++;
    return NULL;
}

for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
    if (search->refcount == 0) { //refount==0的情況，釋放掉
        if (search->exptime == 0 || search->exptime > current_time) {
            itemstats[id].evicted++;
            itemstats[id].evicted_time = current_time - search->time;
            STATS_LOCK();
            stats.evictions++;
            STATS_UNLOCK();
        }
        do_item_unlink(search);
        break;
    }
}
it = slabs_alloc(ntotal, id);
if (it == 0) {
    itemstats[id].outofmemory++;
    /* Last ditch effort. There is a very rare bug which causes
     * refcount leaks. We've fixed most of them, but it still happens,
     * and it may happen in the future.
     * We can reasonably assume no item can stay locked for more than
     * three hours, so if we find one in the tail which is that old,
     * free it anyway.
     */
    tries = 50;
    for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
        if (search->refcount != 0 && search->time + 10800 < current_time) { //最近3小時沒有被訪問到的情況，釋放掉
            itemstats[id].tailrepairs++;
            search->refcount = 0;
            do_item_unlink(search);
            break;
        }
    }
    it = slabs_alloc(ntotal, id);
    if (it == 0) {
        return NULL;
    }
}

 

從item列表的尾部開始遍歷，找到refcount==0的chunk,調用do_item_unlink()函數釋放掉，另外，search->time+10800<current_time(即最近3小時沒有被訪問過的item)，也釋放掉--這就是LRU算法的原理。

附：阿里2014筆試題一道：