Kevin.Zhong

Memcached深度分析

作者：奶瓶
網站：http://www.54np.com

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為準）：

這個函數 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：

在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：

由上可以看出，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……：

在定位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：

在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的時候還要進行時間判斷：

/* 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 ）：

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

◎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。使用這個擴展很簡單：

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

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

這個擴展是使用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只支持這幾個函數：

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

在set和del數據的時候，要循環所有的組：

在mc_get中，首先要隨機選擇一個組，然后從這個組開始輪詢：

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

BSM_Memcache的使用方式和其它的client類似：

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的內涵很多，倉促整理一定有很多遺漏和錯誤。感謝新浪網提供的研究機會，感謝部門同事的幫助。