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