memcached和redis，作為近些年最常用的緩存服務(wù)器，相信大家對它們再熟悉不過了。前兩年還在學校時，我曾經(jīng)讀過它們的主要源碼，如今寫篇筆記從個人角度簡單對比一下它們的實現(xiàn)方式，權(quán)當做復習，有理解錯誤之處，歡迎指正。
文中使用的架構(gòu)類的圖片大多來自于網(wǎng)絡(luò)，有部分圖與最新實現(xiàn)有出入，文中已經(jīng)指出。
一. 綜述
讀一個軟件的源碼，首先要弄懂軟件是用作干什么的，那memcached和redis是干啥的？眾所周知，數(shù)據(jù)一般會放在數(shù)據(jù)庫中，但是查詢數(shù)據(jù)會相對比較慢，特別是用戶很多時，頻繁的查詢，需要耗費大量的時間。怎么辦呢？數(shù)據(jù)放在哪里查詢快？那肯定是內(nèi)存中。memcached和redis就是將數(shù)據(jù)存儲在內(nèi)存中，按照key-value的方式查詢，可以大幅度提高效率。所以一般它們都用做緩存服務(wù)器，緩存常用的數(shù)據(jù)，需要查詢的時候，直接從它們那兒獲取，減少查詢數(shù)據(jù)庫的次數(shù)，提高查詢效率。
二. 服務(wù)方式
memcached和redis怎么提供服務(wù)呢？它們是獨立的進程，需要的話，還可以讓他們變成daemon進程，所以我們的用戶進程要使用memcached和redis的服務(wù)的話，就需要進程間通信了。考慮到用戶進程和memcached和redis不一定在同一臺機器上，所以還需要支持網(wǎng)絡(luò)間通信。因此，memcached和redis自己本身就是網(wǎng)絡(luò)服務(wù)器，用戶進程通過與他們通過網(wǎng)絡(luò)來傳輸數(shù)據(jù)，顯然最簡單和最常用的就是使用tcp連接了。另外，memcached和redis都支持udp協(xié)議。而且當用戶進程和memcached和redis在同一機器時，還可以使用unix域套接字通信。
三. 事件模型
下面開始講他們具體是怎么實現(xiàn)的了。首先來看一下它們的事件模型。
自從epoll出來以后，幾乎所有的網(wǎng)絡(luò)服務(wù)器全都拋棄select和poll，換成了epoll。redis也一樣，只不多它還提供對select和poll的支持，可以自己配置使用哪一個，但是一般都是用epoll。另外針對BSD，還支持使用kqueue。而memcached是基于libevent的，不過libevent底層也是使用epoll的，所以可以認為它們都是使用epoll。epoll的特性這里就不介紹了，網(wǎng)上介紹文章很多。
它們都使用epoll來做事件循環(huán)，不過redis是單線程的服務(wù)器（redis也是多線程的，只不過除了主線程以外，其他線程沒有event loop，只是會進行一些后臺存儲工作），而memcached是多線程的。 redis的事件模型很簡單，只有一個event loop，是簡單的reactor實現(xiàn)。不過redis事件模型中有一個亮點，我們知道epoll是針對fd的，它返回的就緒事件也是只有fd，redis里面的fd就是服務(wù)器與客戶端連接的socket的fd，但是處理的時候，需要根據(jù)這個fd找到具體的客戶端的信息，怎么找呢？通常的處理方式就是用紅黑樹將fd與客戶端信息保存起來，通過fd查找，效率是lgn。不過redis比較特殊，redis的客戶端的數(shù)量上限可以設(shè)置，即可以知道同一時刻，redis所打開的fd的上限，而我們知道，進程的fd在同一時刻是不會重復的（fd只有關(guān)閉后才能復用），所以redis使用一個數(shù)組，將fd作為數(shù)組的下標，數(shù)組的元素就是客戶端的信息，這樣，直接通過fd就能定位客戶端信息，查找效率是O(1)，還省去了復雜的紅黑樹的實現(xiàn)（我曾經(jīng)用c寫一個網(wǎng)絡(luò)服務(wù)器，就因為要保持fd和connect對應(yīng)關(guān)系，不想自己寫紅黑樹，然后用了STL里面的set，導致項目變成了c++的，最后項目使用g++編譯，這事我不說誰知道？）。顯然這種方式只能針對connection數(shù)量上限已確定，并且不是太大的網(wǎng)絡(luò)服務(wù)器，像nginx這種http服務(wù)器就不適用，nginx就是自己寫了紅黑樹。
而memcached是多線程的，使用master-worker的方式，主線程監(jiān)聽端口，建立連接，然后順序分配給各個工作線程。每一個從線程都有一個event loop，它們服務(wù)不同的客戶端。master線程和worker線程之間使用管道通信，每一個工作線程都會創(chuàng)建一個管道，然后保存寫端和讀端，并且將讀端加入event loop，監(jiān)聽可讀事件。同時，每個從線程都有一個就緒連接隊列，主線程連接連接后，將連接的item放入這個隊列，然后往該線程的管道的寫端寫入一個connect命令，這樣event loop中加入的管道讀端就會就緒，從線程讀取命令，解析命令發(fā)現(xiàn)是有連接，然后就會去自己的就緒隊列中獲取連接，并進行處理。多線程的優(yōu)勢就是可以充分發(fā)揮多核的優(yōu)勢，不過編寫程序麻煩一點，memcached里面就有各種鎖和條件變量來進行線程同步。
四. 內(nèi)存分配
memcached和redis的核心任務(wù)都是在內(nèi)存中操作數(shù)據(jù)，內(nèi)存管理自然是核心的內(nèi)容。
首先看看他們的內(nèi)存分配方式。memcached是有自己得內(nèi)存池的，即預(yù)先分配一大塊內(nèi)存，然后接下來分配內(nèi)存就從內(nèi)存池中分配，這樣可以減少內(nèi)存分配的次數(shù)，提高效率，這也是大部分網(wǎng)絡(luò)服務(wù)器的實現(xiàn)方式，只不過各個內(nèi)存池的管理方式根據(jù)具體情況而不同。而redis沒有自己得內(nèi)存池，而是直接使用時分配，即什么時候需要什么時候分配，內(nèi)存管理的事交給內(nèi)核，自己只負責取和釋放（redis既是單線程，又沒有自己的內(nèi)存池，是不是感覺實現(xiàn)的太簡單了？那是因為它的重點都放在數(shù)據(jù)庫模塊了）。不過redis支持使用tcmalloc來替換glibc的malloc，前者是google的產(chǎn)品，比glibc的malloc快。
由于redis沒有自己的內(nèi)存池，所以內(nèi)存申請和釋放的管理就簡單很多，直接malloc和free即可，十分方便。而memcached是支持內(nèi)存池的，所以內(nèi)存申請是從內(nèi)存池中獲取，而free也是還給內(nèi)存池，所以需要很多額外的管理操作，實現(xiàn)起來麻煩很多，具體的會在后面memcached的slab機制講解中分析。
五. 數(shù)據(jù)庫實現(xiàn)
接下來看看他們的最核心內(nèi)容，各自數(shù)據(jù)庫的實現(xiàn)。
1. memcached數(shù)據(jù)庫實現(xiàn)
memcached只支持key-value，即只能一個key對于一個value。它的數(shù)據(jù)在內(nèi)存中也是這樣以key-value對的方式存儲，它使用slab機制。
首先看memcached是如何存儲數(shù)據(jù)的，即存儲key-value對。如下圖，每一個key-value對都存儲在一個item結(jié)構(gòu)中，包含了相關(guān)的屬性和key和value的值。
item是保存key-value對的，當item多的時候，怎么查找特定的item是個問題。所以memcached維護了一個hash表，它用于快速查找item。hash表適用開鏈法（與redis一樣）解決鍵的沖突，每一個hash表的桶里面存儲了一個鏈表，鏈表節(jié)點就是item的指針，如上圖中的h_next就是指桶里面的鏈表的下一個節(jié)點。 hash表支持擴容（item的數(shù)量是桶的數(shù)量的1.5以上時擴容），有一個primary_hashtable，還有一個old_hashtable，其中正常適用primary_hashtable，但是擴容的時候，將old_hashtable = primary_hashtable，然后primary_hashtable設(shè)置為新申請的hash表（桶的數(shù)量乘以2），然后依次將old_hashtable 里面的數(shù)據(jù)往新的hash表里面移動，并用一個變量expand_bucket記錄以及移動了多少個桶，移動完成后，再free原來的old_hashtable 即可（redis也是有兩個hash表，也是移動，不過不是后臺線程完成，而是每次移動一個桶）。擴容的操作，專門有一個后臺擴容的線程來完成，需要擴容的時候，使用條件變量通知它，完成擴容后，它又考試阻塞等待擴容的條件變量。這樣在擴容的時候，查找一個item可能會在primary_hashtable和old_hashtable的任意一個中，需要根據(jù)比較它的桶的位置和expand_bucket的大小來比較確定它在哪個表里。
item是從哪里分配的呢？從slab中。如下圖，memcached有很多slabclass，它們管理slab，每一個slab其實是trunk的集合，真正的item是在trunk中分配的，一個trunk分配一個item。一個slab中的trunk的大小一樣，不同的slab，trunk的大小按比例遞增，需要新申請一個item的時候，根據(jù)它的大小來選擇trunk，規(guī)則是比它大的最小的那個trunk。這樣，不同大小的item就分配在不同的slab中，歸不同的slabclass管理。 這樣的缺點是會有部分內(nèi)存浪費，因為一個trunk可能比item大，如圖2，分配100B的item的時候，選擇112的trunk，但是會有12B的浪費，這部分內(nèi)存資源沒有使用。
如上圖，整個構(gòu)造就是這樣，slabclass管理slab，一個slabclass有一個slab_list，可以管理多個slab，同一個slabclass中的slab的trunk大小都一樣。slabclass有一個指針slot，保存了未分配的item已經(jīng)被free掉的item（不是真的free內(nèi)存，只是不用了而已），有item不用的時候，就放入slot的頭部，這樣每次需要在當前slab中分配item的時候，直接取slot取即可，不用管item是未分配過的還是被釋放掉的。
然后，每一個slabclass對應(yīng)一個鏈表，有head數(shù)組和tail數(shù)組，它們分別保存了鏈表的頭節(jié)點和尾節(jié)點。鏈表中的節(jié)點就是改slabclass所分配的item，新分配的放在頭部，鏈表越往后的item，表示它已經(jīng)很久沒有被使用了。當slabclass的內(nèi)存不足，需要刪除一些過期item的時候，就可以從鏈表的尾部開始刪除，沒錯，這個鏈表就是為了實現(xiàn)LRU。光靠它還不行，因為鏈表的查詢是O（n）的，所以定位item的時候，使用hash表，這已經(jīng)有了，所有分配的item已經(jīng)在hash表中了，所以，hash用于查找item，然后鏈表有用存儲item的最近使用順序，這也是lru的標準實現(xiàn)方法。
每次需要新分配item的時候，找到slabclass對于的鏈表，從尾部往前找，看item是否已經(jīng)過期，過期的話，直接就用這個過期的item當做新的item。沒有過期的，則需要從slab中分配trunk，如果slab用完了，則需要往slabclass中添加slab了。
memcached支持設(shè)置過期時間，即expire time，但是內(nèi)部并不定期檢查數(shù)據(jù)是否過期，而是客戶進程使用該數(shù)據(jù)的時候，memcached會檢查expire time，如果過期，直接返回錯誤。這樣的優(yōu)點是，不需要額外的cpu來進行expire time的檢查，缺點是有可能過期數(shù)據(jù)很久不被使用，則一直沒有被釋放，占用內(nèi)存。
memcached是多線程的，而且只維護了一個數(shù)據(jù)庫，所以可能有多個客戶進程操作同一個數(shù)據(jù)，這就有可能產(chǎn)生問題。比如，A已經(jīng)把數(shù)據(jù)更改了，然后B也更改了改數(shù)據(jù)，那么A的操作就被覆蓋了，而可能A不知道，A任務(wù)數(shù)據(jù)現(xiàn)在的狀態(tài)時他改完后的那個值，這樣就可能產(chǎn)生問題。為了解決這個問題，memcached使用了CAS協(xié)議，簡單說就是item保存一個64位的unsigned int值，標記數(shù)據(jù)的版本，每更新一次（數(shù)據(jù)值有修改），版本號增加，然后每次對數(shù)據(jù)進行更改操作，需要比對客戶進程傳來的版本號和服務(wù)器這邊item的版本號是否一致，一致則可進行更改操作，否則提示臟數(shù)據(jù)。
