1.為什么要使用memcache
由于網(wǎng)站的高并發(fā)讀寫需求，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫開始出現(xiàn)瓶頸，例如：
1）對(duì)數(shù)據(jù)庫的高并發(fā)讀寫：
關(guān)系型數(shù)據(jù)庫本身就是個(gè)龐然大物，處理過程非常耗時(shí)（如解析SQL語句，事務(wù)處理等）。如果對(duì)關(guān)系型數(shù)據(jù)庫進(jìn)行高并發(fā)讀寫（每秒上萬次的訪問），那么它是無法承受的。
2）對(duì)海量數(shù)據(jù)的處理：
對(duì)于大型的SNS網(wǎng)站，每天有上千萬次的數(shù)據(jù)產(chǎn)生（如twitter, 新浪微博）。對(duì)于關(guān)系型數(shù)據(jù)庫，如果在一個(gè)有上億條數(shù)據(jù)的數(shù)據(jù)表種查找某條記錄，效率將非常低。
使用memcache能很好的解決以上問題。
在實(shí)際使用中，通常把數(shù)據(jù)庫查詢的結(jié)果保存到Memcache中，下次訪問時(shí)直接從memcache中讀取，而不再進(jìn)行數(shù)據(jù)庫查詢操作，這樣就在很大程度上減少了數(shù)據(jù)庫的負(fù)擔(dān)。
保存在memcache中的對(duì)象實(shí)際放置在內(nèi)存中，這也是memcache如此高效的原因。
2.memcache的安裝和使用
這個(gè)網(wǎng)上有太多教程了，不做贅言。
3.基于libevent的事件處理
libevent是個(gè)程序庫，它將Linux的epoll、BSD類操作系統(tǒng)的kqueue等事件處理功能 封裝成統(tǒng)一的接口。即使對(duì)服務(wù)器的連接數(shù)增加，也能發(fā)揮O(1)的性能。
memcached使用這個(gè)libevent庫，因此能在Linux、BSD、Solaris等操作系統(tǒng)上發(fā)揮其高性能。
參考：
libevent: http://www.monkey.org/~provos/libevent/
The C10K Problem: http://www.kegel.com/c10k.html
4.memcache使用實(shí)例：
$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如何支持高并發(fā)(此處還需深入研究)
memcache使用多路復(fù)用I/O模型，如（epoll, select等），傳統(tǒng)I/O中，系統(tǒng)可能會(huì)因?yàn)槟硞€(gè)用戶連接還沒做好I/O準(zhǔn)備而一直等待，知道這個(gè)連接做好I/O準(zhǔn)備。這時(shí)如果有其他用戶連接到服務(wù)器，很可能會(huì)因?yàn)橄到y(tǒng)阻塞而得不到響應(yīng)。
而多路復(fù)用I/O是一種消息通知模式，用戶連接做好I/O準(zhǔn)備后，系統(tǒng)會(huì)通知我們這個(gè)連接可以進(jìn)行I/O操作，這樣就不會(huì)阻塞在某個(gè)用戶連接。因此，memcache才能支持高并發(fā)。
此外，memcache使用了多線程機(jī)制?？梢酝瑫r(shí)處理多個(gè)請(qǐng)求。線程數(shù)一般設(shè)置為CPU核數(shù)，這研報(bào)告效率最高。
6.使用Slab分配算法保存數(shù)據(jù)
slab分配算法的原理是：把固定大?。?MB）的內(nèi)存分為n小塊，如下圖所示：
slab分配算法把每1MB大小的內(nèi)存稱為一個(gè)slab頁，每次向系統(tǒng)申請(qǐng)一個(gè)slab頁，然后再通過分隔算法把這個(gè)slab頁分割成若干個(gè)小塊的chunk（如上圖所示），然后把這些chunk分配給用戶使用，分割算法如下（在slabs.c文件中）：
(注：memcache的github項(xiàng)目地址：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的方式申請(qǐng)內(nèi)存*/
? ? ? ?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 ?注意這里的字節(jié)對(duì)齊*/
? ? ? ?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為倍數(shù)增大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是一個(gè)類型為slabclass_t結(jié)構(gòu)的數(shù)組，其定義如下：
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結(jié)構(gòu):
由分割算法的源代碼可知，slab算法按照不同大小的chunk分割slab頁，而不同大小的chunk以factor（默認(rèn)是1.25）倍增大。
使用memcache -u root -vv 命令查看內(nèi)存分配情況(8字節(jié)對(duì)齊)：
找到大小最合適的chunk分配給請(qǐng)求緩存的數(shù)據(jù)：
/*
* 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，直到找到第一個(gè)比申請(qǐng)的size大的chunk
? ? ? ?if (res++ == power_largest) ? ? /* won't fit in the biggest slab */
? ? ? ? ? ?return 0;
? ?return res;
}
內(nèi)存分配：
（此處參考：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是否會(huì)導(dǎo)致slabclass[]數(shù)組越界
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]中已經(jīng)沒有空余chunk并且試圖向系統(tǒng)申請(qǐng)一個(gè)“頁”（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;//將頭結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)（取下頭結(jié)點(diǎn)）
if (it->next) it->next->prev = 0;//將新頭結(jié)點(diǎn)的prev指針置空
p->sl_curr--;//減少slabclass[id]空閑鏈表中的chunk計(jì)數(shù)
ret = (void *)it;//將頭結(jié)點(diǎn)賦給ret指針
}
if (ret) {//請(qǐng)求成功
p->requested += size;//更新slabclass[id]所分配的內(nèi)存總數(shù)
MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);
} else {
MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
}
return ret;
}
do_slabs_allc()函數(shù)首先嘗試從slot列表（被回收的chunk）中獲取可用的chunk,如果有可用的就返回，否則從空閑的chunk列表中獲取可用的chunk并返回。
刪除過期item:
延遲刪除過期item到查找時(shí)進(jìn)行，可以提高memcache的效率，因?yàn)椴槐孛繒r(shí)每刻檢查過期item,從而提高CPU工作效率
使用LRU(last recently used)算法淘汰數(shù)據(jù)：
/*
* 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小時(shí)沒有被訪問到的情況，釋放掉
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,調(diào)用do_item_unlink()函數(shù)釋放掉，另外，search->time+10800
附：阿里2014筆試題一道：
某緩存系統(tǒng)采用LRU淘汰算法，假定緩存容量為4,并且初始為空，那么在順序訪問一下數(shù)據(jù)項(xiàng)的時(shí)候：1,5,1,3,5,2,4,1,2出現(xiàn)緩存直接命中的次數(shù)是？，最后緩存中即將準(zhǔn)備淘汰的數(shù)據(jù)項(xiàng)是？
答案：3， 5
解答：
1調(diào)入內(nèi)存 1
5調(diào)入內(nèi)存 1 5
1調(diào)入內(nèi)存 5 1（命中 1，更新次序）
3調(diào)入內(nèi)存 5 1 3
5調(diào)入內(nèi)存 1 3 5 （命中5）
2調(diào)入內(nèi)存 1 3 5 2
4調(diào)入內(nèi)存（1最久未使用，淘汰1） 3 5 2 4
1調(diào)入內(nèi)存（3最久未使用，淘汰3） 5 2 4 1
2調(diào)入內(nèi)存 5 4 1 2（命中2）
因此，直接命中次數(shù)是3,最后緩存即將準(zhǔn)備淘汰的數(shù)據(jù)項(xiàng)是5
