Memcached源碼剖析筆記

1、Memcached源碼剖析筆記XguruMemcached是一個自由、源碼開放、高性能、分布式 內存對象緩存系統(tǒng)，目的在于通過減輕數(shù)據庫負載來使 動態(tài)Web應用程序提速。XGuruMemcached源碼剖析筆記目錄1. 背景32. memcached 的安裝43. memcached 的配置54. memcached 的使用64.1. 存儲命令74.2. 讀取命令84.3. 刪除命令84.4. 高級命令94.5. 其他命令105. Memcached內部工作機制 115.1. Memcached基本的數(shù)據結構 115.2. 基本設計概念和處理流程 125.3. 內部Hash機制155.3.1.

2、 Hash函數(shù)及沖突解決 155.3.2. HashTable 主要函數(shù) 155.4. slab內存處理機制175.4.1. slab 主要函數(shù) 175.4.2. slab機制中所采用的 LRU算法 195.5. 控制item各種函數(shù) 205.6. 守護進程機制 225.7. Socket 處理機制235.7.1. Unix域協(xié)議235.7.2. TCP/UDP協(xié)議245.8. 多線程處理機制 255.9. 事件處理機制 256. 未完善之處27參考文獻282XGuruMemcached源碼剖析筆記1. 背景Memcached是一個高性能的分布式內存對象緩存系統(tǒng)，用于動態(tài)Web應用以減輕數(shù)據庫

3、負載。它通過在內存中緩存數(shù)據和對象來減少讀取數(shù)據庫的次數(shù)，從而提供動態(tài)、數(shù)據庫驅動網站的速度。Memcached基于一個存儲鍵/值對的hashmap。Memcached是一個自由、源碼開放、高性能、分布式內存對象緩存系統(tǒng)，目的在 于通過減輕數(shù)據庫負載來使動態(tài)Web應用程序提速。Memcached是一個在內存中對任意的數(shù)據 （比如字符串，對象等）所使用的key-value 存儲。數(shù)據可以來自數(shù)據庫調用，API調用，或者頁面渲染的結果。Memcached設計理念就是小而強大，它簡單的設計促進了快速部署、易于開發(fā)，并 解決面對大規(guī)模的數(shù)據緩存的許多難題。所開放的API能用于大部分流行的程序語言3XG

4、uruMemcached源碼剖析筆記2. memcached 的安裝由于memcached采用libevent的事件處理機制，因此安裝memcached之前需要先安裝libeve nt。Memcached: /Libeve nt : http:/www.m on /provos/libeve nt/在 Ubuntu 下可以使用 sudo apt-get in stall libeve nt 禾口 sudo apt-get in stall memcached 來安裝或者使用傳統(tǒng)wget的方式$ wget http:/memcached.goo

5、glecode.eom/files/memcached-1.2.8.tar.gz.tar.gz$ tar zxf memcached1.2.8.tar.gz$ cd memcached1.2.8$ ./c on figure$ make目前最新的版本為1.4.44XGuruMemcached源碼剖析筆記5XGuruMemcached源碼剖析筆記3. memcached 的配置xg uruxgiuru-d ektop;文件舊晦舊珥端(T)第爲汨Jtgijrij(nxg：Liru dfikrnp： -5 nenKached 1-2-p-u-5-齊nenrucrhpdhelpfa L-dsum &l

6、t;num<nask><ip_dddr>8 TCP part UDP port miLx socket path to listennask tor umx socket, in octal (fletault Q7Q9)mnber to ninber tolisten on Idefault: 1121)listen on default: 1J211, 6 is Dftl an (disables netwcrk support)、usernfiiw* <num><num>V-wv h-r-tR<factor>cnum=-bin

7、Lt rf die Lc listen an, defdLill h INDRR_ANy run as a daemon ndjiiidzc cutc file limit as tune identity of cost rnane?- (only when run as root) rK Pfiiwry in ijsp for irrms in iwgbymi defnuH fi4 MS return error on memory exhausted (rather than irenoving items 1 rviK iimjlrrinpoijs cnrert伽矢 rtefau r

8、1 LG?4 lock down $ll paqed uienoryNote that there 1$ a Limit on how nuch Tiemory you may .ack. Trying to allocate norE thmn That would fail, so be sure you iet the Linit 匚dtectly for the use 丫口口 started rhe da eft on wiih (noi for -u <usernsite> user； 口11血mh this dne Allh ' ulikiit - 5 -L

9、MUM_KB- I . verbose (print errors/wangs wtiilc in event loop) vtry vei tdl&o print client <oiindixj&/ repo ns ei) print tfiis help snrl exit print mencaches and libccnx license 陰餐 FID in vfils only used 協(xié)ith -d optionhunk size growth fartor, default 1.25 mini mu m space alltjcdt&d for

10、 ke+'ualue+f laqs default 48 number cf threads to user default 4 Max丄rum rvLinber of r&juests per eventimts the nunber ot requests p racess tor a givin con nection ro prevent starvation, default 2eStL the bdikloi) qu?u« limit (dcfaulL 1024 >主要使用的命令-d 以守護程序(daemon) 方式運行 memcached；-m設置

11、 memcached可以使用的內存大小，單位為M ；-I設置監(jiān)聽的IP地址，如果是本機的話，通?？梢圆辉O置此參數(shù);-p設置監(jiān)聽的端口，默認為11211，所以也可以不設置此參數(shù)；-u指定用戶，如果當前為root的話，需要使用此參數(shù)指定用戶。-f設置增長因子(調優(yōu)時使用)-V/-VV詳細顯示工作時各種參數(shù)Memcached采用典型的getopt()函數(shù)獲取各種配置比如./memcached -m 512 -p 11211 -vv該例分配給memcached的可用內存512M，監(jiān)聽11211端口，顯示詳細的運行信息4. memcached 的使用memcached提供的API可以在大多數(shù)的編程語言使

12、用，在這里測試使用的是PuTTy的tel net方式，使用tel net連接其11211端口。Memcached有4種類型的命令:存儲命令(set/add / replace/append/prepend)指示服務器儲存一些由鍵值標識的數(shù)據?？蛻舳税l(fā)送一行命令，后面跟著數(shù)據區(qū)塊；然后，客戶端等待接收服務器回傳的命令行，指示成功與否。讀取命令(get/bget/gets )指示服務器返回與所給鍵值相符合的數(shù)據(一個請求中右一個或多個鍵值)?？蛻舳税l(fā)送一行命令，包括所有請求的鍵值；服務器每找到一項內緊跟著是對應的數(shù)據區(qū)塊；直到服務容，都會發(fā)送回客戶端一行關于這項內容的信息, 器以一行“ end ”

13、回應命令結束。狀態(tài)命令（stat）被用于查詢服務器的運行狀態(tài)和其他內部數(shù)據。其他命令，女口 flush_all,version,quit 等。4.1.存儲命令命令格式：vcomma nd n ame> <key> <flags> <exptime> <bytes> <data block>命令解釋vcomma nd n ame>set/add / replace<key>查找關鍵字<flags>客戶機使用它存儲關于鍵值對的額外信息<exptime>該數(shù)據的存活時間,0為永遠<byt

14、es>存儲字節(jié)數(shù)<data block>存儲的數(shù)據塊存儲命令區(qū)別setaddrepalce無論如何都進行存儲只有數(shù)據不存在時進行添加只有數(shù)據存在時進行替換7XGuruMemcached源碼剖析筆記8XGuruMemcached源碼剖析筆記#XGuruMemcached源碼剖析筆記#XGuruMemcached源碼剖析筆記4.2.讀取命令get <key><key>可以表示一個或多個鍵值，由空格隔開的字串用 202,193,77.23? - PuTTY get工 u an.OLh.erVALUE Jtgiini 0 S 123-15VALUE anoth

15、er 0 7 123-15«7END4.3.刪除命令delete <key>刪除鍵值為key的數(shù)據用 202,193,77.33- PUTTYger 蠱guruVALUE Kgu m 0 554321ENDdelete xgurnDELETEDget xquruEND#XGuruMemcached源碼剖析筆記4.4.高級命令值得一提的是，新版本的memcached加入了 gets和cas命令1逛 202,193,77,23? - PuTTY忑gu工"UV2Q.UE0 S ' 7.'123-15ENDreplace xgum 0 0 654321S

16、TOREDgets xijuruVALUE xguru 08S4321ENC202,193,77.23?- PuTTY可以看到此處gets比普通的get多返回一個數(shù)字，這個數(shù)字可以用作檢查數(shù)據是否 發(fā)生改變。當key對應的數(shù)據改變的時候，該數(shù)會發(fā)生改變，如圖中紅圈所示。s.z Jiguxu 0STORED gets zqutu VALUE XQuru 1235 END c&s xguru 0 S4321 EXISTS-一一- eas xqutu 0 0 5 54321_ 1"STORED -_cas就是check and set之意，只有當最后一個參數(shù)與gets所獲取的參數(shù)匹

17、配時才能存儲，否則返回“ EXISTS ”。這種設計的意圖是防止使用經過改變了的value/key對4.5.其他命令查看狀態(tài)世 202,193,77.23- PUTTYstatsSTAT pid 1716STAI Xlne 12621B9&99STAT version 128STAT p0ijxt-er_3iEe 92 方丁 N丁STATSTAITusa'e_ii3er 0. dDOOQQ TU3a-ge_3y3teni 0.032002 curT 1 tens 25TATtoxal_i匸亡ms TSTAT bytes-122STATSTJVTcu tt_co n_n.&

18、; ct Lons 10 Total conaecc1oas 15STATconnec匸:Lon. m匸micrureg 11STATSTATSTATETATcrMl_flush 1 crad_g是 t 7 cmd t 12 ger hits 4 qet iaisses 3 evictions 0r-ead. G-23STATSTATSTAT bytesSTAT bytes written 14&9L)其他更多的命令可以參看memcached的協(xié)議：了解了其基本工作方式以后再來看源代碼發(fā)現(xiàn)清晰很多。11XGuruMemcached源碼剖析筆記5. Memcached內部工作機制5.1.

19、 Memcached基本的數(shù)據結構12XGuruMemcached源碼剖析筆記#XGuruMemcached源碼剖析筆記ltem( _stritem )結構示意圖_stritem *n ext;指向鏈表下一個ite m的指針_stritem *prev指向鏈表上一個ite m的指針*h_n exthash指向hash表該桶(Bucket)的下一項rel_time_t time最近訪問時間Slab( slabclass_t)結構示意圖un sig ned int size每個chunk的大小un sig ned int perslab能存放size大小chunk的個數(shù)void *slots目前空

20、閑可插入item的插糟un sig ned int sl_totalslots插糟的總容量#XGuruMemcached源碼剖析筆記rel_time_t exptime消亡時間un sig ned int sl_curr當前可用的插糟曹#XGuruMemcached源碼剖析筆記int n bytes數(shù)據大小#XGuruMemcached源碼剖析筆記void *en d_page_ptrunsigned short refcount 弓丨用計數(shù)void * en d存放的數(shù)據最后的slab空閑內存起始地址un sig ned int slabsSlab 數(shù)void *slab_list;存儲sl

21、ab指針的數(shù)組uin t8_t n suffix,it_flags,slabs_clsid ,n key雜項item為memcached中的存儲數(shù)據最小單位，其中還記錄有數(shù)據和最近訪問時間數(shù)據 大小，桶的下一項等數(shù)據，每個不同slab的元素內含有具有統(tǒng)一分配的尺寸的各個item可以這樣理解，每個item是存儲在其對應大小的 slabclass_t里的，同時又在hash表中有 記錄。既可以使用自己的內存分配機制來減少操作系統(tǒng)在處理內存碎片，添加釋放等多 余的操作，又可以使用 hash表的性質對其進行快速的定位。slabclass是由(POWER_LARGEST + 1 )個slabclass_t

22、結構體構成的數(shù)組，每個slabclass_t結構體的大小是根據增長因子遞增的，增長因子可以由客戶端來設定，1.28版本的默認值為2,合理的調優(yōu)增長因子可以避免空間的浪費。13XGuruMemcached源碼剖析筆記14XGuruMemcached源碼剖析筆記52基本設計概念和處理流程#XGuruMemcached源碼剖析筆記15XGuruMemcached源碼剖析筆記#XGuruMemcached源碼剖析筆記#XGuruMemcached源碼剖析筆記(conn * ) c ->stateconn readconn writeconn listening連接所監(jiān)聽讀取命令并處向客戶端簡單理

23、，讓循環(huán)繼續(xù)寫入響應數(shù)據的端口conn nreadconn mwrite進行后續(xù)的存向客戶端連串儲工作寫入item數(shù)據y11Tconn swallow:處理不必要的 w/o存儲字節(jié)Error處理傳輸不完整錯誤，硬錯誤與軟 錯誤conn_closing關閉該連接#XGuruMemcached源碼剖析筆記#XGuruMemcached源碼剖析筆記iMemcached核心函數(shù) drive_machine()#XGuruMemcached源碼剖析筆記在這里值得注意的是，add/set/replace/cas這類存儲命令在conn_read里的操作只是分配了 item的空間，并沒有對其進行存儲工作，當c

24、onn_read結束后設置狀態(tài)為conn_nread再做進一步的處理。5.3. 內部Hash機制Memcached采用開鏈法(separate chaining 解決沖突5.3.1. Hash函數(shù)及沖突解決memcached采用的hash函數(shù)是Bob Jenkins 先生在1996創(chuàng)立的一個算法，復雜度 為0(6n+35),而且沖突率極低，該算法具體過程可以參閱 這里。沖突處理的方法為開 鏈法。memcached 中實際有兩個 hash 表，一個是“主 hash 表" (primary_hashtable),另 外一個是“原有hash表” (old_hashtable)。每次操作的時

25、候，先會檢測表是否正處于 擴展(expanding)狀態(tài)，如果擴展還沒完成時，先在原有hash表中操作數(shù)據。5.3.2. HashTable 主要函數(shù)assoc_init()初始化hash表，為主hash表分配空間assoc_find()根據key值來查找item，如果有沖突存在，則不停往桶的下一個元素(h_next)里查找，直至找到為止，并返回其指針。assoc_insert()在hash表中插入item，如果裝載因子大于1.5，則擴展哈希表assoc_delete()用_hashitem_befor()找鍵值為key的item之前的指針，改變其指向，數(shù)據實際上是沒有被釋放的，在這里只是從h

26、ash表中移除 assoc_expend()擴展hash表到2的下一次方，比如現(xiàn)在是hash表的大小2A16，擴展后大小則為2A17 再進行數(shù)據遷移，擴展時候不能再分配內存時，就保持原有的表不變。do_assoc_move_next_bucket()將下一個桶遷移到先前的我們擴充的哈希表中_hashitem_before ()(內部使用)返回該鍵值所對應的item的之前的指針18XGuruMemcached源碼剖析筆記5.4. slab內存處理機制slab源于Jeff Bon wick為SunOS操作系統(tǒng)首次引入的一種內存處理機制，SLAB的設計理念是基于對象緩沖的，基本想法是避免重復大量的初

27、始化和清理操作。SLAB主要可以用于頻繁分配釋放的內存對象。如果是采用系統(tǒng)自帶的 malloc/free話，反復地操作會造成大量內存碎片，操作系統(tǒng)將會花費大量的時間去查找連續(xù)的內存塊來滿足 malloc的請求。memcached中內存分配機制主要理念1. 先為分配相應的大塊內存，再在上面進行無縫小對象填充2. 懶惰檢測機制，Memcached不花過多的時間在檢測各個item對象是否超時，當get獲取數(shù)據時，才檢查item對象是否應該刪除，你不訪問，我就不處理。3懶惰刪除機制，在memecached中刪除一個item對象的時候，并不是從內存中釋放， 而是單單的進行標記處理，再將其指針放入slot

28、回收插糟，下次分配的時候直接使用。5.4.1. slab主要函數(shù)slabs_init()slab初始化，如果配置時采用預分配機制(prealloc)則在先在這使用 malloc分配所有內存。再根據增長因子factor給每個slabclass分配容量。slabs_clsid()計算出哪個slabclass適合用來儲存大小給定為 size的item，如果返回值為0則存儲 的物件過大，無法進行存儲。do_slabs_alloc()在這個函數(shù)里面，由宏定義來決定采用系統(tǒng)自帶的malloc機制還是memcached的slab機制對內存進行分配，理所當然，在大多數(shù)情況下，系統(tǒng)的malloc會比slab慢上

29、一個數(shù)量級。分配時首先考慮slot內的空間(被回收的空間)，再檢查end_page_ptr指針指向的的空 閑空間，還是沒有的空間的話，再試試分配新的內存。如果所有空間都用盡的時候，則 返回NULL表示目前資源已經枯竭了。do_slabs_free()首先檢查當目前的插糟是否已經達到可用總插糟的總容量，如果達到就為其重新 分配空間，再將該回收的item的指針插入對應當前id的slabclass的插糟(slots)之中do_slabs_stats()將目前slab的狀態(tài)填充至buf緩存中并將其返回。do_slab_reassign()清除在一個slab class里的所有的item，將其移動到另外

30、一個 class。只有在處 理"slab reassign"命令選擇手動調整內存分配的時候才會使用，默認是禁止的。Slab( slabclass_t)結構un sig ned int size 每個chunk的大小un sig ned int perslab 能存放size大小chunk的個數(shù)void *slots目前空閑可插入item的插糟un sig ned int sl_totalslots插糟的總容量un sig ned int sl_curr當前可用的插糟void *en d_page_ptr最后的slab空閑內存起始地址un sig ned int slabsS

31、lab 數(shù)void *slab_list;存儲slab指針的數(shù)組list_size killi ng-雜項21XGuruMemcached源碼剖析筆記#XGuruMemcached源碼剖析筆記內存不足時，Slab采用LRU算法淘汰不常用item22XGuruMemcached源碼剖析筆記542. slab機制中所采用的LRU算法在memcached運行過程中，要把一個item調入內存，但內存已無空閑空間時，為 了保證程序能正常運行，系統(tǒng)必須從內存中調出一部分數(shù)據，送磁盤的對換區(qū)中。但應 將哪些數(shù)據調出，須根據一定的算法來確定。通常，把選擇換出數(shù)據（頁面）的算法稱為頁面置換算法（Page Rep

32、lacement Algorithms）。Memcached采用最近最久未使用（LRU） 置換算法，是根據數(shù)據（頁面）調入內存后的使用情況進行決策的。由于無法預測各頁 面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。當內存不足時，memcached會從slab各個class中的雙向鏈表的尾部開始檢測，即最近最久未使用的頁面，往前一直尋找合 適的item予以淘汰。所以該 LRU算法為slab局部class淘汰的機制。但是在一些特定 情形也會可能引起一些不必要的麻煩，可以在運行時加入”-M ”參數(shù)禁止該算法。23XGuruM

33、emcached源碼剖析筆記5.5. 控制item各種函數(shù)do_itemnit()初始化item:將itemstats結構體數(shù)組全部初始化為0,將各個頭，尾指針初始化。do_item_alloc()首先調用slabs_clsid給item歸類，然后調用slabs_alloc()函數(shù)分配內存，當可使用空間枯竭了的時候，就開始使用 LRU算法了，從一個對應大小的尾部tailsid開始，向前不斷嘗試能否釋放，當發(fā)現(xiàn)一個item當前沒有被使用(引用計數(shù)refcount為0)，且其生存時間已經為0或生存時間大于現(xiàn)在時間，就果斷的把它釋放掉。并再次調用 slabs_alloc(),作者在此提到有一種非常罕

34、見的bug能夠使引用計數(shù)(refcount)發(fā)生泄漏，處理方法是，當item連續(xù)保持鎖定狀態(tài)3小時以上，說明它已經足夠陳舊了，應該果 斷將其釋放。最后再將數(shù)據復制到分配的空間內。item_free()調用slabs_free將其釋放。do_item_link()1. 調用assoc_insert()將item指針插入hash表中2. 調用 get_cas_id()給 it 的 cas_id 賦值。3調用itemink_q(),把該item插入LRU隊列的最前面do_item_unlink ()1. 調用 assoc_delete(在 hash表中刪除此 item2. 調用item_unlink

35、_q()從該slab class去除此item的連接，此處考慮了 item在鏈表頭 部，尾部等各種情況。3. 最后當引用計數(shù)為0的時候，調用item_free()將其釋放。do_item_remove ()減少引用計數(shù)refcount，當發(fā)現(xiàn)引用計數(shù)為0的時候，就將其釋放。do_item_update ()先調用item_unlink_q(),更新了時間以后，再調用itemnk_q()。將其重新連接到 LRU隊列之中，即讓該item移到LRU隊列的最前。do_item_replace ()調用do_item_unlink()解除原有item的連接，再調用 do_item_link()連接到新的

36、 item。item_get ()值得說明的是，memcached的懶惰刪除邏輯在這里有體現(xiàn)。就是當你需要 get 一個 item的時候才考慮該item是否應該刪除。首先調用do_item_get_notedeleted()函數(shù)，根據關鍵字使用 assoc_find()查找item,如 果沒找到，返回NULL，再判斷是否達到最大的生存時間，如果是的話，就 do_item_unlink 該 item，返回 NULL。如果該item沒有滿足刪除條件，將其引用計數(shù)加1并返回該item的指針。56守護進程機制Memcached使用經典的 UNIX daemon模式(daemon.c)。具體工作流程處理

37、如下26XGuruMemcached源碼剖析筆記5.7. Socket處理機制5.7.1. Unix 域協(xié)議Unix域協(xié)議并不是一個實際的協(xié)議族，它只是在同一主機上進行客戶-服務器通信時，使用與在不同主機上進行客戶-服務器通信時使用的相同的API的一種方法。memcached默認是不使用該機制，可以使用-s參數(shù)設置sockpath開啟。5.7.2. TCP/UDP 協(xié)議通過設置TCP或者UDP端口為0可以選擇不打開其中的協(xié)議5.8. 多線程處理機制memcached 1.2之后開始加入多線程機制，在頭文件 memcached.h中使用宏來決定 是否使用線程，一般以“ do_”開頭的就為單線程函

38、數(shù)，以“ mt_”開頭則為多線程的版 本。memcached使用的是pthread (POSIX)線程模式，默認并沒有開啟，在編譯前使用“ ./con figure -e nable-threads "可以開啟多線程模式。目前來說，memcached的多線程設計還是比較粗糙，特別是其中的鎖(lock ing)不夠完善，畢竟該項目一開始并沒有考慮加入多線程，現(xiàn)在加入的多線程機制也只是通過 一系列的包裹(wrapper)函數(shù)來實現(xiàn)。當你的網站負載過重時，可以考慮開啟多線程模 式，官方的文檔建議“ one thread per processor core (線程數(shù)對應處理器核心數(shù))，開啟 過多的線程沒有實際的優(yōu)點。可以通過”-t ”參數(shù)設置線程數(shù)。線程模型可以參考這篇文章。5.9. 事件處理機制memcached采用的是libevent框架。libevent是一種處理異步事件程序庫。該庫的性 能非常優(yōu)秀，提供的 API簡單易用。這里提一下 memcached主要用到的幾個 API:event_init()(事件初始化)表示初始化libevent所使用到的變量，并返回這個新建立的even_base結構體。event_set(struct event *ev, int fd, short event