| 導購 | 订阅 | 在线投稿
分享
 
 
 

Memcached深度分析

來源:互聯網  2008-12-22 08:10:19  評論

Memcached是danga.com(運營LiveJournal的技術團隊)開發的一套分布式內存對象緩存系統,用于在動態系統中減少數據庫負載,提升性能。關于這個東西,相信很多人都用過,本文意在通過對memcached的實現及代碼分析,獲得對這個出色的開源軟件更深入的了解,並可以根據我們的需要對其進行更進一步的優化。末了將通過對BSM_Memcache擴展的分析,加深對memcached的使用方式理解。

本文的部分內容可能需要比較好的數學基礎作爲輔助。

◎Memcached是什麽

在闡述這個問題之前,我們首先要清楚它「不是什麽」。很多人把它當作和SharedMemory那種形式的存儲載體來使用,雖然memcached使用了同樣的「Key=>Value」方式組織數據,但是它和共享內存、APC等本地緩存有非常大的區別。Memcached是分布式的,也就是說它不是本地的。它基于網絡連接(當然它也可以使用localhost)方式完成服務,本身它是一個獨立于應用的程序或守護進程(Daemon方式)。

Memcached使用libevent庫實現網絡連接服務,理論上可以處理無限多的連接,但是它和Apache不同,它更多的時候是面向穩定的持續連接的,所以它實際的並發能力是有限制的。在保守情況下memcached的最大同時連接數爲200,這和Linux線程能力有關系,這個數值是可以調整的。關于libevent可以參考相關文檔。 Memcached內存使用方式也和APC不同。APC是基于共享內存和MMAP的,memcachd有自己的內存分配算法和管理方式,它和共享內存沒有關系,也沒有共享內存的限制,通常情況下,每個memcached進程可以管理2GB的內存空間,如果需要更多的空間,可以增加進程數。

◎Memcached適合什麽場合

在很多時候,memcached都被濫用了,這當然少不了對它的抱怨。我經常在論壇上看見有人發貼,類似于「如何提高效率」,回複是「用memcached」,至于怎麽用,用在哪裏,用來幹什麽一句沒有。memcached不是萬能的,它也不是適用在所有場合。

Memcached是「分布式」的內存對象緩存系統,那麽就是說,那些不需要「分布」的,不需要共享的,或者幹脆規模小到只有一台服務器的應用,memcached不會帶來任何好處,相反還會拖慢系統效率,因爲網絡連接同樣需要資源,即使是UNIX本地連接也一樣。 在我之前的測試數據中顯示,memcached本地讀寫速度要比直接PHP內存數組慢幾十倍,而APC、共享內存方式都和直接數組差不多。可見,如果只是本地級緩存,使用memcached是非常不劃算的。

Memcached在很多時候都是作爲數據庫前端cache使用的。因爲它比數據庫少了很多SQL解析、磁盤操作等開銷,而且它是使用內存來管理數據的,所以它可以提供比直接讀取數據庫更好的性能,在大型系統中,訪問同樣的數據是很頻繁的,memcached可以大大降低數據庫壓力,使系統執行效率提升。另外,memcached也經常作爲服務器之間數據共享的存儲媒介,例如在SSO系統中保存系統單點登陸狀態的數據就可以保存在memcached中,被多個應用共享。

需要注意的是,memcached使用內存管理數據,所以它是易失的,當服務器重啓,或者memcached進程中止,數據便會丟失,所以memcached不能用來持久保存數據。很多人的錯誤理解,memcached的性能非常好,好到了內存和硬盤的對比程度,其實memcached使用內存並不會得到成百上千的讀寫速度提高,它的實際瓶頸在于網絡連接,它和使用磁盤的數據庫系統相比,好處在于它本身非常「輕」,因爲沒有過多的開銷和直接的讀寫方式,它可以輕松應付非常大的數據交換量,所以經常會出現兩條千兆網絡帶寬都滿負荷了,memcached進程本身並不占用多少CPU資源的情況。

◎Memcached的工作方式

以下的部分中,讀者最好能准備一份memcached的源代碼。

Memcached是傳統的網絡服務程序,如果啓動的時候使用了-d參數,它會以守護進程的方式執行。創建守護進程由daemon.c完成,這個程序只有一個daemon函數,這個函數很簡單(如無特殊說明,代碼以1.2.1爲准):

CODE:[Copy to clipboard]#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);

}

這個函數 fork 了整個進程之後,父進程就退出,接著重新定位 STDIN 、 STDOUT 、 STDERR 到空設備, daemon 就建立成功了。

Memcached 本身的啓動過程,在 memcached.c 的 main 函數中順序如下:

1 、調用 settings_init() 設定初始化參數

2 、從啓動命令中讀取參數來設置 setting 值

3 、設定 LIMIT 參數

4 、開始網絡 socket 監聽(如果非 socketpath 存在)( 1.2 之後支持 UDP 方式)

5 、檢查用戶身份( Memcached 不允許 root 身份啓動)

6 、如果有 socketpath 存在,開啓 UNIX 本地連接(Sock 管道)

7 、如果以 -d 方式啓動,創建守護進程(如上調用 daemon 函數)

8 、初始化 item 、 event 、狀態信息、 hash 、連接、 slab

9 、如設置中 managed 生效,創建 bucket 數組

10 、檢查是否需要鎖定內存頁

11 、初始化信號、連接、刪除隊列

12 、如果 daemon 方式,處理進程 ID

13 、event 開始,啓動過程結束, main 函數進入循環。

在 daemon 方式中,因爲 stderr 已經被定向到黑洞,所以不會反饋執行中的可見錯誤信息。

memcached.c 的主循環函數是 drive_machine ,傳入參數是指向當前的連接的結構指針,根據 state 成員的狀態來決定動作。

Memcached 使用一套自定義的協議完成數據交換,它的 protocol 文檔可以參考: http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt

在API中,換行符號統一爲\r\n

◎Memcached的內存管理方式

Memcached有一個很有特色的內存管理方式,爲了提高效率,它使用預申請和分組的方式管理內存空間,而並不是每次需要寫入數據的時候去malloc,刪除數據的時候free一個指針。Memcached使用slab->chunk的組織方式管理內存。

1.1和1.2的slabs.c中的slab空間劃分算法有一些不同,後面會分別介紹。

Slab可以理解爲一個內存塊,一個slab是memcached一次申請內存的最小單位,在memcached中,一個slab的大小默認爲1048576字節(1MB),所以memcached都是整MB的使用內存。每一個slab被劃分爲若幹個chunk,每個chunk裏保存一個item,每個item同時包含了item結構體、key和value(注意在memcached中的value是只有字符串的)。slab按照自己的id分別組成鏈表,這些鏈表又按id挂在一個slabclass數組上,整個結構看起來有點像二維數組。slabclass的長度在1.1中是21,在1.2中是200。

slab有一個初始chunk大小,1.1中是1字節,1.2中是80字節,1.2中有一個factor值,默認爲1.25

在1.1中,chunk大小表示爲初始大小*2^n,n爲classid,即:id爲0的slab,每chunk大小1字節,id爲1的slab,每chunk大小2字節,id爲2的slab,每chunk大小4字節……id爲20的slab,每chunk大小爲1MB,就是說id爲20的slab裏只有一個chunk:

CODE:[Copy to clipboard]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,同時,201個頭不是全部都要初始化的,因爲factor可變,初始化只循環到計算出的大小達到slab大小的一半爲止,而且它是從id1開始的,即:id爲1的slab,每chunk大小80字節,id爲2的slab,每chunk大小80*f,id爲3的slab,每chunk大小80*f^2,初始化大小有一個修正值CHUNK_ALIGN_BYTES,用來保證n-byte排列 (保證結果是CHUNK_ALIGN_BYTES的整倍數)。這樣,在標准情況下,memcached1.2會初始化到id40,這個slab中每個chunk大小爲504692,每個slab中有兩個chunk。最後,slab_init函數會在最後補足一個id41,它是整塊的,也就是這個slab中只有一個1MB大的chunk:

CODE:[Copy to clipboard]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的內存分配是有冗余的,當一個slab不能被它所擁有的chunk大小整除時,slab尾部剩余的空間就被丟棄了,如id40中,兩個chunk占用了1009384字節,這個slab一共有1MB,那麽就有39192字節被浪費了。

Memcached使用這種方式來分配內存,是爲了可以快速的通過item長度定位出slab的classid,有一點類似hash,因爲item的長度是可以計算的,比如一個item的長度是300字節,在1.2中就可以得到它應該保存在id7的slab中,因爲按照上面的計算方法,id6的chunk大小是252字節,id7的chunk大小是316字節,id8的chunk大小是396字節,表示所有252到316字節的item都應該保存在id7中。同理,在1.1中,也可以計算得到它出于256和512之間,應該放在chunk_size爲512的id9中(32位系統)。

Memcached初始化的時候,會初始化slab(前面可以看到,在main函數中調用了slabs_init())。它會在slabs_init()中檢查一個常量DONT_PREALLOC_SLABS,如果這個沒有被定義,說明使用預分配內存方式初始化slab,這樣在所有已經定義過的slabclass中,每一個id創建一個slab。這樣就表示,1.2在默認的環境中啓動進程後要分配41MB的slab空間,在這個過程裏,memcached的第二個內存冗余發生了,因爲有可能一個id根本沒有被使用過,但是它也默認申請了一個slab,每個slab會用掉1MB內存

當一個slab用光後,又有新的item要插入這個id,那麽它就會重新申請新的slab,申請新的slab時,對應id的slab鏈表就要增長,這個鏈表是成倍增長的,在函數grow_slab_list函數中,這個鏈的長度從1變成2,從2變成4,從4變成8……:

CODE:[Copy to clipboard]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時,都是使用slabs_clsid函數,傳入參數爲item大小,返回值爲classid,由這個過程可以看出,memcached的第三個內存冗余發生在保存item的過程中,item總是小于或等于chunk大小的,當item小于chunk大小時,就又發生了空間浪費。

◎Memcached的NewHash算法

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

Memcached使用了一個叫做NewHash的算法,它的效果很好,效率也很高。1.1和1.2的NewHash有一些不同,主要的實現方式還是一樣的,1.2的hash函數是經過整理優化的,適應性更好一些。

NewHash的原型參考:http://burtleburtle.net/bob/hash/evahash.html。數學家總是有點奇怪,呵呵~

爲了變換方便,定義了u4和u1兩種數據類型,u4就是無符號的長整形,u1就是無符號char(0-255)。

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

注意這裏的hashtable長度,1.1和1.2也是有區別的,1.1中定義了HASHPOWER常量爲20,hashtable表長爲hashsize(HASHPOWER),就是4MB(hashsize是一個宏,表示1右移n位),1.2中是變量16,即hashtable表長65536:

CODE:[Copy to clipboard]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()中,會對primary_hashtable做初始化,對應的hash操作包括:assoc_find()、assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete(),對應于item的讀寫操作。其中assoc_find()是根據key和key長尋找對應的item地址的函數(注意在C中,很多時候都是同時直接傳入字符串和字符串長度,而不是在函數內部做strlen),返回的是item結構指針,它的數據地址在slab中的某個chunk上。

items.c是數據項的操作程序,每一個完整的item包括幾個部分,在item_make_header()中定義爲:

key:鍵

nkey:鍵長

flags:用戶定義的flag(其實這個flag在memcached中沒有啓用)

nbytes:值長(包括換行符號\r\n)

suffix:後綴Buffer

nsuffix:後綴長

一個完整的item長度是鍵長+值長+後綴長+item結構大小(32字節),item操作就是根據這個長度來計算slab的classid的。

hashtable中的每一個桶上挂著一個雙鏈表,item_init()的時候已經初始化了heads、tails、sizes三個數組爲0,這三個數組的大小都爲常量LARGEST_ID(默認爲255,這個值需要配合factor來修改),在每次item_assoc()的時候,它會首先嘗試從slab中獲取一塊空閑的chunk,如果沒有可用的chunk,會在鏈表中掃描50次,以得到一個被LRU踢掉的item,將它unlink,然後將需要插入的item插入鏈表中。

注意item的refcount成員。item被unlink之後只是從鏈表上摘掉,不是立刻就被free的,只是將它放到刪除隊列中(item_unlink_q()函數)。

item對應一些讀寫操作,包括remove、update、replace,當然最重要的就是alloc操作。

item還有一個特性就是它有過期時間,這是memcached的一個很有用的特性,很多應用都是依賴于memcached的item過期,比如session存儲、操作鎖等。item_flush_expired()函數就是掃描表中的item,對過期的item執行unlink操作,當然這只是一個回收動作,實際上在get的時候還要進行時間判斷:

CODE:[Copy to clipboard]/* 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;

}

}

}

}

CODE:[Copy to clipboard]/* 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的內存管理方式是非常精巧和高效的,它很大程度上減少了直接alloc系統內存的次數,降低函數開銷和內存碎片産生幾率,雖然這種方式會造成一些冗余浪費,但是這種浪費在大型系統應用中是微不足道的。

◎Memcached的理論參數計算方式

影響 memcached 工作的幾個參數有:

常量REALTIME_MAXDELTA 60*60*24*30

最大30天的過期時間

conn_init()中的freetotal(=200)

最大同時連接數

常量KEY_MAX_LENGTH 250

最大鍵長

settings.factor(=1.25)

factor將影響chunk的步進大小

settings.maxconns(=1024)

最大軟連接

settings.chunk_size(=48)

一個保守估計的key+value長度,用來生成id1中的chunk長度(1.2)。id1的chunk長度等于這個數值加上item結構體的長度(32),即默認的80字節。

常量POWER_SMALLEST 1

最小classid(1.2)

常量POWER_LARGEST 200

最大classid(1.2)

常量POWER_BLOCK 1048576

默認slab大小

常量CHUNK_ALIGN_BYTES (sizeof(void *))

保證chunk大小是這個數值的整數倍,防止越界(void *的長度在不同系統上不一樣,在標准32位系統上是4)

常量ITEM_UPDATE_INTERVAL 60

隊列刷新間隔

常量LARGEST_ID 255

最大item鏈表數(這個值不能比最大的classid小)

變量hashpower(在1.1中是常量HASHPOWER)

決定hashtable的大小

根據上面介紹的內容及參數設定,可以計算出的一些結果:

1、在memcached中可以保存的item個數是沒有軟件上限的,之前我的100萬的說法是錯誤的。

2、假設NewHash算法碰撞均勻,查找item的循環次數是item總數除以hashtable大小(由hashpower決定),是線性的。

3、Memcached限制了可以接受的最大item是1MB,大于1MB的數據不予理會。

4、Memcached的空間利用率和數據特性有很大的關系,又與DONT_PREALLOC_SLABS常量有關。 在最差情況下,有198個slab會被浪費(所有item都集中在一個slab中,199個id全部分配滿)。

◎Memcached的定長優化

根據上面幾節的描述,多少對memcached有了一個比較深入的認識。在深入認識的基礎上才好對它進行優化。

Memcached本身是爲變長數據設計的,根據數據特性,可以說它是「面向大衆」的設計,但是很多時候,我們的數據並不是這樣的「普遍」,典型的情況中,一種是非均勻分布,即數據長度集中在幾個區域內(如保存用戶 Session);另一種更極端的狀態是等長數據(如定長鍵值,定長數據,多見于訪問、在線統計或執行鎖)。

這裏主要研究一下定長數據的優化方案(1.2),集中分布的變長數據僅供參考,實現起來也很容易。

解決定長數據,首先需要解決的是slab的分配問題,第一個需要確認的是我們不需要那麽多不同chunk長度的slab,爲了最大限度地利用資源,最好chunk和item等長,所以首先要計算item長度。

在之前已經有了計算item長度的算法,需要注意的是,除了字符串長度外,還要加上item結構的長度32字節。

假設我們已經計算出需要保存200字節的等長數據。

接下來是要修改slab的classid和chunk長度的關系。在原始版本中,chunk長度和classid是有對應關系的,現在如果把所有的chunk都定爲200個字節,那麽這個關系就不存在了,我們需要重新確定這二者的關系。一種方法是,整個存儲結構只使用一個固定的id,即只使用199個槽中的1個,在這種條件下,就一定要定義DONT_PREALLOC_SLABS來避免另外的預分配浪費。另一種方法是建立一個hash關系,來從item確定classid,不能使用長度來做鍵,可以使用key的NewHash結果等不定數據,或者直接根據key來做hash(定長數據的key也一定等長)。這裏簡單起見,選擇第一種方法,這種方法的不足之處在于只使用一個id,在數據量非常大的情況下,slab鏈會很長(因爲所有數據都擠在一條鏈上了),遍曆起來的代價比較高。

前面介紹了三種空間冗余,設置chunk長度等于item長度,解決了第一種空間浪費問題,不預申請空間解決了第二種空間浪費問題,那麽對于第一種問題(slab內剩余)如何解決呢,這就需要修改POWER_BLOCK常量,使得每一個slab大小正好等于chunk長度的整數倍,這樣一個slab就可以正好劃分成n個chunk。這個數值應該比較接近1MB,過大的話同樣會造成冗余,過小的話會造成次數過多的alloc,根據chunk長度爲200,選擇1000000作爲POWER_BLOCK的值,這樣一個slab就是100萬字節,不是1048576。三個冗余問題都解決了,空間利用率會大大提升。

修改 slabs_clsid 函數,讓它直接返回一個定值(比如 1 ):

CODE:[Copy to clipboard]unsigned int slabs_clsid(size_t size) {

return 1;

}

修改slabs_init函數,去掉循環創建所有classid屬性的部分,直接添加slabclass[1]:

CODE:[Copy to clipboard]slabclass[1].size = 200; //每chunk200字節

slabclass[1].perslab = 5000; //1000000/200

◎Memcached客戶端

Memcached是一個服務程序,使用的時候可以根據它的協議,連接到memcached服務器上,發送命令給服務進程,就可以操作上面的數據。爲了方便使用,memcached有很多個客戶端程序可以使用,對應于各種語言,有各種語言的客戶端。基于C語言的有libmemcache、APR_Memcache;基于Perl的有Cache::Memcached;另外還有Python、Ruby、Java、C#等語言的支持。PHP的客戶端是最多的,不光有mcache和PECL memcache兩個擴展,還有大把的由PHP編寫的封裝類,下面介紹一下在PHP中使用memcached的方法:

mcache擴展是基于libmemcache再封裝的。libmemcache一直沒有發布stable版本,目前版本是1.4.0-rc2,可以在這裏找到。libmemcache有一個很不好的特性,就是會向stderr寫很多錯誤信息,一般的,作爲lib使用的時候,stderr一般都會被定向到其它地方,比如Apache的錯誤日志,而且libmemcache會自殺,可能會導致異常,不過它的性能還是很好的。

mcache擴展最後更新到1.2.0-beta10,作者大概是離職了,不光停止更新,連網站也打不開了(~_~),只能到其它地方去獲取這個不負責的擴展了。解壓後安裝方法如常:phpize & configure & make & make install,一定要先安裝libmemcache。使用這個擴展很簡單:

CODE:[Copy to clipboard]<?php

$mc = memcache(); // 創建一個memcache連接對象,注意這裏不是用new!

$mc->add_server('localhost', 11211); // 添加一個服務進程

$mc->add_server('localhost', 11212); // 添加第二個服務進程

$mc->set('key1', 'Hello'); // 寫入key1 => Hello

$mc->set('key2', 'World', 10); // 寫入key2 => World,10秒過期

$mc->set('arr1', array('Hello', 'World')); // 寫入一個數組

$key1 = $mc->get('key1'); // 獲取'key1'的值,賦給$key1

$key2 = $mc->get('key2'); // 獲取'key2'的值,賦給$key2,如果超過10秒,就取不到了

$arr1 = $mc->get('arr1'); // 獲取'arr1'數組

$mc->delete('arr1'); // 刪除'arr1'

$mc->flush_all(); // 刪掉所有數據

$stats = $mc->stats(); // 獲取服務器信息

var_dump($stats); // 服務器信息是一個數組

?>

這個擴展的好處是可以很方便地實現分布式存儲和負載均衡,因爲它可以添加多個服務地址,數據在保存的時候是會根據hash結果定位到某台服務器上的,這也是libmemcache的特性。libmemcache支持集中hash方式,包括CRC32、ELF和Perl hash。

PECL memcache是PECL發布的擴展,目前最新版本是2.1.0,可以在pecl網站得到。memcache擴展的使用方法可以在新一些的PHP手冊中找到,它和mcache很像,真的很像:

CODE:[Copy to clipboard]<?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);

?>

這個擴展是使用php的stream直接連接memcached服務器並通過socket發送命令的。它不像libmemcache那樣完善,也不支持add_server這種分布操作,但是因爲它不依賴其它的外界程序,兼容性要好一些,也比較穩定。至于效率,差別不是很大。

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

◎BSM_Memcache

從C client來說,APR_Memcache是一個很成熟很穩定的client程序,支持線程鎖和原子級操作,保證運行的穩定性。不過它是基于APR的(APR將在最後一節介紹),沒有libmemcache的應用範圍廣,目前也沒有很多基于它開發的程序,現有的多是一些Apache Module,因爲它不能脫離APR環境運行。但是APR倒是可以脫離Apache單獨安裝的,在APR網站上可以下載APR和APR-util,不需要有Apache,可以直接安裝,而且它是跨平台的。

BSM_Memcache是我在BS.Magic項目中開發的一個基于APR_Memcache的PHP擴展,說起來有點拗口,至少它把APR扯進了PHP擴展中。這個程序很簡單,也沒做太多的功能,只是一種形式的嘗試,它支持服務器分組。

和mcache擴展支持多服務器分布存儲不同,BSM_Memcache支持多組服務器,每一組內的服務器還是按照hash方式來分布保存數據,但是兩個組中保存的數據是一樣的,也就是實現了熱備,它不會因爲一台服務器發生單點故障導致數據無法獲取,除非所有的服務器組都損壞(例如機房停電)。當然實現這個功能的代價就是性能上的犧牲,在每次添加刪除數據的時候都要掃描所有的組,在get數據的時候會隨機選擇一組服務器開始輪詢,一直到找到數據爲止,正常情況下一次就可以獲取得到。

BSM_Memcache只支持這幾個函數:

CODE:[Copy to clipboard]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函數返回一個整形(其實應該是一個object,我偷懶了~_~)作爲組ID,mc_add_server的時候要提供兩個參數,一個是組ID,一個是服務器地址(ADDRORT)。

CODE:[Copy to clipboard]/**

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

}

CODE:[Copy to clipboard]/**

* 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數據的時候,要循環所有的組:

CODE:[Copy to clipboard]/**

* 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中,首先要隨機選擇一個組,然後從這個組開始輪詢:

CODE:[Copy to clipboard]/**

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

}

CODE:[Copy to clipboard]/**

* 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類似:

CODE:[Copy to clipboard]<?php

$g1 = mc_add_group(); // 添加第一個組

$g2 = mc_add_group(); // 添加第二個組

mc_add_server($g1, 'localhost:11211'); // 在第一個組中添加第一台服務器

mc_add_server($g1, 'localhost:11212'); // 在第一個組中添加第二台服務器

mc_add_server($g2, '10.0.0.16:11211'); // 在第二個組中添加第一台服務器

mc_add_server($g2, '10.0.0.17:11211'); // 在第二個組中添加第二台服務器

mc_set('key', 'Hello'); // 寫入數據

$key = mc_get('key'); // 讀出數據

mc_del('key'); // 刪除數據

mc_shutdown(); // 關閉所有組

?>

APR_Memcache的相關資料可以在這裏找到,BSM_Memcache可以在本站下載。

◎APR環境介紹

APR的全稱:Apache Portable Runtime。它是Apache軟件基金會創建並維持的一套跨平台的C語言庫。它從Apache httpd1.x中抽取出來並獨立于httpd之外,Apache httpd2.x就是建立在APR上。APR提供了很多方便的API接口可供使用,包括如內存池、字符串操作、網絡、數組、hash表等實用的功能。開發Apache2 Module要接觸很多APR函數,當然APR可以獨立安裝獨立使用,可以用來寫自己的應用程序,不一定是Apache httpd的相關開發。

◎後記

這是我在農曆丙戌年(我的本命年)的最後一篇文章,由于Memcached的內涵很多,倉促整理一定有很多遺漏和錯誤。感謝新浪網提供的研究機會,感謝部門同事的幫助。

NP博士 02-13-2007

Memcached是danga.com(運營LiveJournal的技術團隊)開發的一套分布式內存對象緩存系統,用于在動態系統中減少數據庫負載,提升性能。關于這個東西,相信很多人都用過,本文意在通過對memcached的實現及代碼分析,獲得對這個出色的開源軟件更深入的了解,並可以根據我們的需要對其進行更進一步的優化。末了將通過對BSM_Memcache擴展的分析,加深對memcached的使用方式理解。 本文的部分內容可能需要比較好的數學基礎作爲輔助。 ◎Memcached是什麽 在闡述這個問題之前,我們首先要清楚它「不是什麽」。很多人把它當作和SharedMemory那種形式的存儲載體來使用,雖然memcached使用了同樣的「Key=>Value」方式組織數據,但是它和共享內存、APC等本地緩存有非常大的區別。Memcached是分布式的,也就是說它不是本地的。它基于網絡連接(當然它也可以使用localhost)方式完成服務,本身它是一個獨立于應用的程序或守護進程(Daemon方式)。 Memcached使用libevent庫實現網絡連接服務,理論上可以處理無限多的連接,但是它和Apache不同,它更多的時候是面向穩定的持續連接的,所以它實際的並發能力是有限制的。在保守情況下memcached的最大同時連接數爲200,這和Linux線程能力有關系,這個數值是可以調整的。關于libevent可以參考相關文檔。 Memcached內存使用方式也和APC不同。APC是基于共享內存和MMAP的,memcachd有自己的內存分配算法和管理方式,它和共享內存沒有關系,也沒有共享內存的限制,通常情況下,每個memcached進程可以管理2GB的內存空間,如果需要更多的空間,可以增加進程數。 ◎Memcached適合什麽場合 在很多時候,memcached都被濫用了,這當然少不了對它的抱怨。我經常在論壇上看見有人發貼,類似于「如何提高效率」,回複是「用memcached」,至于怎麽用,用在哪裏,用來幹什麽一句沒有。memcached不是萬能的,它也不是適用在所有場合。 Memcached是「分布式」的內存對象緩存系統,那麽就是說,那些不需要「分布」的,不需要共享的,或者幹脆規模小到只有一台服務器的應用,memcached不會帶來任何好處,相反還會拖慢系統效率,因爲網絡連接同樣需要資源,即使是UNIX本地連接也一樣。 在我之前的測試數據中顯示,memcached本地讀寫速度要比直接PHP內存數組慢幾十倍,而APC、共享內存方式都和直接數組差不多。可見,如果只是本地級緩存,使用memcached是非常不劃算的。 Memcached在很多時候都是作爲數據庫前端cache使用的。因爲它比數據庫少了很多SQL解析、磁盤操作等開銷,而且它是使用內存來管理數據的,所以它可以提供比直接讀取數據庫更好的性能,在大型系統中,訪問同樣的數據是很頻繁的,memcached可以大大降低數據庫壓力,使系統執行效率提升。另外,memcached也經常作爲服務器之間數據共享的存儲媒介,例如在SSO系統中保存系統單點登陸狀態的數據就可以保存在memcached中,被多個應用共享。 需要注意的是,memcached使用內存管理數據,所以它是易失的,當服務器重啓,或者memcached進程中止,數據便會丟失,所以memcached不能用來持久保存數據。很多人的錯誤理解,memcached的性能非常好,好到了內存和硬盤的對比程度,其實memcached使用內存並不會得到成百上千的讀寫速度提高,它的實際瓶頸在于網絡連接,它和使用磁盤的數據庫系統相比,好處在于它本身非常「輕」,因爲沒有過多的開銷和直接的讀寫方式,它可以輕松應付非常大的數據交換量,所以經常會出現兩條千兆網絡帶寬都滿負荷了,memcached進程本身並不占用多少CPU資源的情況。 ◎Memcached的工作方式 以下的部分中,讀者最好能准備一份memcached的源代碼。 Memcached是傳統的網絡服務程序,如果啓動的時候使用了-d參數,它會以守護進程的方式執行。創建守護進程由daemon.c完成,這個程序只有一個daemon函數,這個函數很簡單(如無特殊說明,代碼以1.2.1爲准): CODE:[Copy to clipboard]#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); } 這個函數 fork 了整個進程之後,父進程就退出,接著重新定位 STDIN 、 STDOUT 、 STDERR 到空設備, daemon 就建立成功了。 Memcached 本身的啓動過程,在 memcached.c 的 main 函數中順序如下: 1 、調用 settings_init() 設定初始化參數 2 、從啓動命令中讀取參數來設置 setting 值 3 、設定 LIMIT 參數 4 、開始網絡 socket 監聽(如果非 socketpath 存在)( 1.2 之後支持 UDP 方式) 5 、檢查用戶身份( Memcached 不允許 root 身份啓動) 6 、如果有 socketpath 存在,開啓 UNIX 本地連接(Sock 管道) 7 、如果以 -d 方式啓動,創建守護進程(如上調用 daemon 函數) 8 、初始化 item 、 event 、狀態信息、 hash 、連接、 slab 9 、如設置中 managed 生效,創建 bucket 數組 10 、檢查是否需要鎖定內存頁 11 、初始化信號、連接、刪除隊列 12 、如果 daemon 方式,處理進程 ID 13 、event 開始,啓動過程結束, main 函數進入循環。 在 daemon 方式中,因爲 stderr 已經被定向到黑洞,所以不會反饋執行中的可見錯誤信息。 memcached.c 的主循環函數是 drive_machine ,傳入參數是指向當前的連接的結構指針,根據 state 成員的狀態來決定動作。 Memcached 使用一套自定義的協議完成數據交換,它的 protocol 文檔可以參考: [url=http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt]http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt[/url] 在API中,換行符號統一爲\r\n ◎Memcached的內存管理方式 Memcached有一個很有特色的內存管理方式,爲了提高效率,它使用預申請和分組的方式管理內存空間,而並不是每次需要寫入數據的時候去malloc,刪除數據的時候free一個指針。Memcached使用slab->chunk的組織方式管理內存。 1.1和1.2的slabs.c中的slab空間劃分算法有一些不同,後面會分別介紹。 Slab可以理解爲一個內存塊,一個slab是memcached一次申請內存的最小單位,在memcached中,一個slab的大小默認爲1048576字節(1MB),所以memcached都是整MB的使用內存。每一個slab被劃分爲若幹個chunk,每個chunk裏保存一個item,每個item同時包含了item結構體、key和value(注意在memcached中的value是只有字符串的)。slab按照自己的id分別組成鏈表,這些鏈表又按id挂在一個slabclass數組上,整個結構看起來有點像二維數組。slabclass的長度在1.1中是21,在1.2中是200。 slab有一個初始chunk大小,1.1中是1字節,1.2中是80字節,1.2中有一個factor值,默認爲1.25 在1.1中,chunk大小表示爲初始大小*2^n,n爲classid,即:id爲0的slab,每chunk大小1字節,id爲1的slab,每chunk大小2字節,id爲2的slab,每chunk大小4字節……id爲20的slab,每chunk大小爲1MB,就是說id爲20的slab裏只有一個chunk: CODE:[Copy to clipboard]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,同時,201個頭不是全部都要初始化的,因爲factor可變,初始化只循環到計算出的大小達到slab大小的一半爲止,而且它是從id1開始的,即:id爲1的slab,每chunk大小80字節,id爲2的slab,每chunk大小80*f,id爲3的slab,每chunk大小80*f^2,初始化大小有一個修正值CHUNK_ALIGN_BYTES,用來保證n-byte排列 (保證結果是CHUNK_ALIGN_BYTES的整倍數)。這樣,在標准情況下,memcached1.2會初始化到id40,這個slab中每個chunk大小爲504692,每個slab中有兩個chunk。最後,slab_init函數會在最後補足一個id41,它是整塊的,也就是這個slab中只有一個1MB大的chunk: CODE:[Copy to clipboard]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的內存分配是有冗余的,當一個slab不能被它所擁有的chunk大小整除時,slab尾部剩余的空間就被丟棄了,如id40中,兩個chunk占用了1009384字節,這個slab一共有1MB,那麽就有39192字節被浪費了。 Memcached使用這種方式來分配內存,是爲了可以快速的通過item長度定位出slab的classid,有一點類似hash,因爲item的長度是可以計算的,比如一個item的長度是300字節,在1.2中就可以得到它應該保存在id7的slab中,因爲按照上面的計算方法,id6的chunk大小是252字節,id7的chunk大小是316字節,id8的chunk大小是396字節,表示所有252到316字節的item都應該保存在id7中。同理,在1.1中,也可以計算得到它出于256和512之間,應該放在chunk_size爲512的id9中(32位系統)。 Memcached初始化的時候,會初始化slab(前面可以看到,在main函數中調用了slabs_init())。它會在slabs_init()中檢查一個常量DONT_PREALLOC_SLABS,如果這個沒有被定義,說明使用預分配內存方式初始化slab,這樣在所有已經定義過的slabclass中,每一個id創建一個slab。這樣就表示,1.2在默認的環境中啓動進程後要分配41MB的slab空間,在這個過程裏,memcached的第二個內存冗余發生了,因爲有可能一個id根本沒有被使用過,但是它也默認申請了一個slab,每個slab會用掉1MB內存 當一個slab用光後,又有新的item要插入這個id,那麽它就會重新申請新的slab,申請新的slab時,對應id的slab鏈表就要增長,這個鏈表是成倍增長的,在函數grow_slab_list函數中,這個鏈的長度從1變成2,從2變成4,從4變成8……: CODE:[Copy to clipboard]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時,都是使用slabs_clsid函數,傳入參數爲item大小,返回值爲classid,由這個過程可以看出,memcached的第三個內存冗余發生在保存item的過程中,item總是小于或等于chunk大小的,當item小于chunk大小時,就又發生了空間浪費。 ◎Memcached的NewHash算法 Memcached的item保存基于一個大的hash表,它的實際地址就是slab中的chunk偏移,但是它的定位是依靠對key做hash的結果,在primary_hashtable中找到的。在assoc.c和items.c中定義了所有的hash和item操作。 Memcached使用了一個叫做NewHash的算法,它的效果很好,效率也很高。1.1和1.2的NewHash有一些不同,主要的實現方式還是一樣的,1.2的hash函數是經過整理優化的,適應性更好一些。 NewHash的原型參考:[url=http://burtleburtle.net/bob/hash/evahash.html]http://burtleburtle.net/bob/hash/evahash.html[/url]。數學家總是有點奇怪,呵呵~ 爲了變換方便,定義了u4和u1兩種數據類型,u4就是無符號的長整形,u1就是無符號char(0-255)。 具體代碼可以參考1.1和1.2源碼包。 注意這裏的hashtable長度,1.1和1.2也是有區別的,1.1中定義了HASHPOWER常量爲20,hashtable表長爲hashsize(HASHPOWER),就是4MB(hashsize是一個宏,表示1右移n位),1.2中是變量16,即hashtable表長65536: CODE:[Copy to clipboard]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()中,會對primary_hashtable做初始化,對應的hash操作包括:assoc_find()、assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete(),對應于item的讀寫操作。其中assoc_find()是根據key和key長尋找對應的item地址的函數(注意在C中,很多時候都是同時直接傳入字符串和字符串長度,而不是在函數內部做strlen),返回的是item結構指針,它的數據地址在slab中的某個chunk上。 items.c是數據項的操作程序,每一個完整的item包括幾個部分,在item_make_header()中定義爲: key:鍵 nkey:鍵長 flags:用戶定義的flag(其實這個flag在memcached中沒有啓用) nbytes:值長(包括換行符號\r\n) suffix:後綴Buffer nsuffix:後綴長 一個完整的item長度是鍵長+值長+後綴長+item結構大小(32字節),item操作就是根據這個長度來計算slab的classid的。 hashtable中的每一個桶上挂著一個雙鏈表,item_init()的時候已經初始化了heads、tails、sizes三個數組爲0,這三個數組的大小都爲常量LARGEST_ID(默認爲255,這個值需要配合factor來修改),在每次item_assoc()的時候,它會首先嘗試從slab中獲取一塊空閑的chunk,如果沒有可用的chunk,會在鏈表中掃描50次,以得到一個被LRU踢掉的item,將它unlink,然後將需要插入的item插入鏈表中。 注意item的refcount成員。item被unlink之後只是從鏈表上摘掉,不是立刻就被free的,只是將它放到刪除隊列中(item_unlink_q()函數)。 item對應一些讀寫操作,包括remove、update、replace,當然最重要的就是alloc操作。 item還有一個特性就是它有過期時間,這是memcached的一個很有用的特性,很多應用都是依賴于memcached的item過期,比如session存儲、操作鎖等。item_flush_expired()函數就是掃描表中的item,對過期的item執行unlink操作,當然這只是一個回收動作,實際上在get的時候還要進行時間判斷: CODE:[Copy to clipboard]/* 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; } } } } CODE:[Copy to clipboard]/* 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的內存管理方式是非常精巧和高效的,它很大程度上減少了直接alloc系統內存的次數,降低函數開銷和內存碎片産生幾率,雖然這種方式會造成一些冗余浪費,但是這種浪費在大型系統應用中是微不足道的。 ◎Memcached的理論參數計算方式 影響 memcached 工作的幾個參數有: 常量REALTIME_MAXDELTA 60*60*24*30 最大30天的過期時間 conn_init()中的freetotal(=200) 最大同時連接數 常量KEY_MAX_LENGTH 250 最大鍵長 settings.factor(=1.25) factor將影響chunk的步進大小 settings.maxconns(=1024) 最大軟連接 settings.chunk_size(=48) 一個保守估計的key+value長度,用來生成id1中的chunk長度(1.2)。id1的chunk長度等于這個數值加上item結構體的長度(32),即默認的80字節。 常量POWER_SMALLEST 1 最小classid(1.2) 常量POWER_LARGEST 200 最大classid(1.2) 常量POWER_BLOCK 1048576 默認slab大小 常量CHUNK_ALIGN_BYTES (sizeof(void *)) 保證chunk大小是這個數值的整數倍,防止越界(void *的長度在不同系統上不一樣,在標准32位系統上是4) 常量ITEM_UPDATE_INTERVAL 60 隊列刷新間隔 常量LARGEST_ID 255 最大item鏈表數(這個值不能比最大的classid小) 變量hashpower(在1.1中是常量HASHPOWER) 決定hashtable的大小 根據上面介紹的內容及參數設定,可以計算出的一些結果: 1、在memcached中可以保存的item個數是沒有軟件上限的,之前我的100萬的說法是錯誤的。 2、假設NewHash算法碰撞均勻,查找item的循環次數是item總數除以hashtable大小(由hashpower決定),是線性的。 3、Memcached限制了可以接受的最大item是1MB,大于1MB的數據不予理會。 4、Memcached的空間利用率和數據特性有很大的關系,又與DONT_PREALLOC_SLABS常量有關。 在最差情況下,有198個slab會被浪費(所有item都集中在一個slab中,199個id全部分配滿)。 ◎Memcached的定長優化 根據上面幾節的描述,多少對memcached有了一個比較深入的認識。在深入認識的基礎上才好對它進行優化。 Memcached本身是爲變長數據設計的,根據數據特性,可以說它是「面向大衆」的設計,但是很多時候,我們的數據並不是這樣的「普遍」,典型的情況中,一種是非均勻分布,即數據長度集中在幾個區域內(如保存用戶 Session);另一種更極端的狀態是等長數據(如定長鍵值,定長數據,多見于訪問、在線統計或執行鎖)。 這裏主要研究一下定長數據的優化方案(1.2),集中分布的變長數據僅供參考,實現起來也很容易。 解決定長數據,首先需要解決的是slab的分配問題,第一個需要確認的是我們不需要那麽多不同chunk長度的slab,爲了最大限度地利用資源,最好chunk和item等長,所以首先要計算item長度。 在之前已經有了計算item長度的算法,需要注意的是,除了字符串長度外,還要加上item結構的長度32字節。 假設我們已經計算出需要保存200字節的等長數據。 接下來是要修改slab的classid和chunk長度的關系。在原始版本中,chunk長度和classid是有對應關系的,現在如果把所有的chunk都定爲200個字節,那麽這個關系就不存在了,我們需要重新確定這二者的關系。一種方法是,整個存儲結構只使用一個固定的id,即只使用199個槽中的1個,在這種條件下,就一定要定義DONT_PREALLOC_SLABS來避免另外的預分配浪費。另一種方法是建立一個hash關系,來從item確定classid,不能使用長度來做鍵,可以使用key的NewHash結果等不定數據,或者直接根據key來做hash(定長數據的key也一定等長)。這裏簡單起見,選擇第一種方法,這種方法的不足之處在于只使用一個id,在數據量非常大的情況下,slab鏈會很長(因爲所有數據都擠在一條鏈上了),遍曆起來的代價比較高。 前面介紹了三種空間冗余,設置chunk長度等于item長度,解決了第一種空間浪費問題,不預申請空間解決了第二種空間浪費問題,那麽對于第一種問題(slab內剩余)如何解決呢,這就需要修改POWER_BLOCK常量,使得每一個slab大小正好等于chunk長度的整數倍,這樣一個slab就可以正好劃分成n個chunk。這個數值應該比較接近1MB,過大的話同樣會造成冗余,過小的話會造成次數過多的alloc,根據chunk長度爲200,選擇1000000作爲POWER_BLOCK的值,這樣一個slab就是100萬字節,不是1048576。三個冗余問題都解決了,空間利用率會大大提升。 修改 slabs_clsid 函數,讓它直接返回一個定值(比如 1 ): CODE:[Copy to clipboard]unsigned int slabs_clsid(size_t size) { return 1; } 修改slabs_init函數,去掉循環創建所有classid屬性的部分,直接添加slabclass[1]: CODE:[Copy to clipboard]slabclass[1].size = 200; //每chunk200字節 slabclass[1].perslab = 5000; //1000000/200 ◎Memcached客戶端 Memcached是一個服務程序,使用的時候可以根據它的協議,連接到memcached服務器上,發送命令給服務進程,就可以操作上面的數據。爲了方便使用,memcached有很多個客戶端程序可以使用,對應于各種語言,有各種語言的客戶端。基于C語言的有libmemcache、APR_Memcache;基于Perl的有Cache::Memcached;另外還有Python、Ruby、Java、C#等語言的支持。PHP的客戶端是最多的,不光有mcache和PECL memcache兩個擴展,還有大把的由PHP編寫的封裝類,下面介紹一下在PHP中使用memcached的方法: mcache擴展是基于libmemcache再封裝的。libmemcache一直沒有發布stable版本,目前版本是1.4.0-rc2,可以在這裏找到。libmemcache有一個很不好的特性,就是會向stderr寫很多錯誤信息,一般的,作爲lib使用的時候,stderr一般都會被定向到其它地方,比如Apache的錯誤日志,而且libmemcache會自殺,可能會導致異常,不過它的性能還是很好的。 mcache擴展最後更新到1.2.0-beta10,作者大概是離職了,不光停止更新,連網站也打不開了(~_~),只能到其它地方去獲取這個不負責的擴展了。解壓後安裝方法如常:phpize & configure & make & make install,一定要先安裝libmemcache。使用這個擴展很簡單: CODE:[Copy to clipboard]<?php $mc = memcache(); // 創建一個memcache連接對象,注意這裏不是用new! $mc->add_server('localhost', 11211); // 添加一個服務進程 $mc->add_server('localhost', 11212); // 添加第二個服務進程 $mc->set('key1', 'Hello'); // 寫入key1 => Hello $mc->set('key2', 'World', 10); // 寫入key2 => World,10秒過期 $mc->set('arr1', array('Hello', 'World')); // 寫入一個數組 $key1 = $mc->get('key1'); // 獲取'key1'的值,賦給$key1 $key2 = $mc->get('key2'); // 獲取'key2'的值,賦給$key2,如果超過10秒,就取不到了 $arr1 = $mc->get('arr1'); // 獲取'arr1'數組 $mc->delete('arr1'); // 刪除'arr1' $mc->flush_all(); // 刪掉所有數據 $stats = $mc->stats(); // 獲取服務器信息 var_dump($stats); // 服務器信息是一個數組 ?> 這個擴展的好處是可以很方便地實現分布式存儲和負載均衡,因爲它可以添加多個服務地址,數據在保存的時候是會根據hash結果定位到某台服務器上的,這也是libmemcache的特性。libmemcache支持集中hash方式,包括CRC32、ELF和Perl hash。 PECL memcache是PECL發布的擴展,目前最新版本是2.1.0,可以在pecl網站得到。memcache擴展的使用方法可以在新一些的PHP手冊中找到,它和mcache很像,真的很像: CODE:[Copy to clipboard]<?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); ?> 這個擴展是使用php的stream直接連接memcached服務器並通過socket發送命令的。它不像libmemcache那樣完善,也不支持add_server這種分布操作,但是因爲它不依賴其它的外界程序,兼容性要好一些,也比較穩定。至于效率,差別不是很大。 另外,有很多的PHP class可以使用,比如MemcacheClient.inc.php,phpclasses.org上可以找到很多,一般都是對perl client API的再封裝,使用方式很像。 ◎BSM_Memcache 從C client來說,APR_Memcache是一個很成熟很穩定的client程序,支持線程鎖和原子級操作,保證運行的穩定性。不過它是基于APR的(APR將在最後一節介紹),沒有libmemcache的應用範圍廣,目前也沒有很多基于它開發的程序,現有的多是一些Apache Module,因爲它不能脫離APR環境運行。但是APR倒是可以脫離Apache單獨安裝的,在APR網站上可以下載APR和APR-util,不需要有Apache,可以直接安裝,而且它是跨平台的。 BSM_Memcache是我在BS.Magic項目中開發的一個基于APR_Memcache的PHP擴展,說起來有點拗口,至少它把APR扯進了PHP擴展中。這個程序很簡單,也沒做太多的功能,只是一種形式的嘗試,它支持服務器分組。 和mcache擴展支持多服務器分布存儲不同,BSM_Memcache支持多組服務器,每一組內的服務器還是按照hash方式來分布保存數據,但是兩個組中保存的數據是一樣的,也就是實現了熱備,它不會因爲一台服務器發生單點故障導致數據無法獲取,除非所有的服務器組都損壞(例如機房停電)。當然實現這個功能的代價就是性能上的犧牲,在每次添加刪除數據的時候都要掃描所有的組,在get數據的時候會隨機選擇一組服務器開始輪詢,一直到找到數據爲止,正常情況下一次就可以獲取得到。 BSM_Memcache只支持這幾個函數: CODE:[Copy to clipboard]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函數返回一個整形(其實應該是一個object,我偷懶了~_~)作爲組ID,mc_add_server的時候要提供兩個參數,一個是組ID,一個是服務器地址(ADDRORT)。 CODE:[Copy to clipboard]/** * 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); } CODE:[Copy to clipboard]/** * 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數據的時候,要循環所有的組: CODE:[Copy to clipboard]/** * 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中,首先要隨機選擇一個組,然後從這個組開始輪詢: CODE:[Copy to clipboard]/** * 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; } CODE:[Copy to clipboard]/** * 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類似: CODE:[Copy to clipboard]<?php $g1 = mc_add_group(); // 添加第一個組 $g2 = mc_add_group(); // 添加第二個組 mc_add_server($g1, 'localhost:11211'); // 在第一個組中添加第一台服務器 mc_add_server($g1, 'localhost:11212'); // 在第一個組中添加第二台服務器 mc_add_server($g2, '10.0.0.16:11211'); // 在第二個組中添加第一台服務器 mc_add_server($g2, '10.0.0.17:11211'); // 在第二個組中添加第二台服務器 mc_set('key', 'Hello'); // 寫入數據 $key = mc_get('key'); // 讀出數據 mc_del('key'); // 刪除數據 mc_shutdown(); // 關閉所有組 ?> APR_Memcache的相關資料可以在這裏找到,BSM_Memcache可以在本站下載。 ◎APR環境介紹 APR的全稱:Apache Portable Runtime。它是Apache軟件基金會創建並維持的一套跨平台的C語言庫。它從Apache httpd1.x中抽取出來並獨立于httpd之外,Apache httpd2.x就是建立在APR上。APR提供了很多方便的API接口可供使用,包括如內存池、字符串操作、網絡、數組、hash表等實用的功能。開發Apache2 Module要接觸很多APR函數,當然APR可以獨立安裝獨立使用,可以用來寫自己的應用程序,不一定是Apache httpd的相關開發。 ◎後記 這是我在農曆丙戌年(我的本命年)的最後一篇文章,由于Memcached的內涵很多,倉促整理一定有很多遺漏和錯誤。感謝新浪網提供的研究機會,感謝部門同事的幫助。 NP博士 02-13-2007
󰈣󰈤
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
王朝網路微信公眾號
微信掃碼關註本站公眾號 wangchaonetcn
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有