如何設計一個支持高并發的高性能緩存庫
不 考慮并發情況下的緩存的設計大家應該都比較清楚，基本上就是用map/hashmap存儲鍵值，然后用雙向鏈表記錄一個LRU來用于緩存的清理。這篇文章 應該是講得很清楚http://timday.bitbucket.org/lru.html。但是考慮到高并發的情況，如何才能讓緩存保持高性能呢？
高并發緩存需要解決2個問題：1. 高效率的內存分配；2. 高效率的讀取，插入和清理數據。關于第一個問題涉及到高效率的內存分配器，使用成熟的jemalloc/tcmalloc足夠滿足需求。這里探討下如何解決第二個問題。
由 于緩存系統的特點， 每次讀取緩存都需要更新一些訪問信息（最后讀取時間，訪問頻率），在清理時會根據這些信息使用不同的策略來進行數據清理，這樣看來似乎每次的讀操作都變成 了寫操作。看過幾篇文章都比較集中在如何優化這個讀操作修改LRU的行為。例如：?http://www.ebaytechblog.com/2011 /08/30/high-throughput-thread-safe-lru-caching/#.UzvEb3V53No 以及?http://openmymind.net/High-Concurrency-LRU-Caching/， 但是這種情況下不論怎么優化，使用鏈表的LRU始終是個瓶頸， 因為每次讀操作只能一個線程來修改這個LRU鏈表，并且修改都是集中在鏈表的兩端。有些文章甚至使用lock-free的doubled linked list來減少鎖競爭。 一些成熟的緩存系統如memcached，使用的是全局的LRU鏈表鎖，而redis是單線程的所以不需要考慮并發的問題。由于這些都是遠程的緩存服務 器，因此它們的瓶頸往往是網卡，所以并發上面并不需要什么高要求。
仔 細思考后，發現在并發的情況下使用LRU鏈表來記錄訪問信息其實并不合適，會導致嚴重的鎖競爭，這點無法避免。因此，需要徹底放棄使用LRU鏈表。鑒于緩 存系統的特性，可以做如下假設： 緩存如果達到閥值，可以使插入立即返回失敗。這樣，我們可以使用一個預分配的數組來記錄所有的cache item的訪問信息。整個結構如下：
concurrent cache system arch
可 以看到鎖粒度是hashmap里面的bucket級別，每次讀操作只需對相應的bucket加鎖，然后更新bucket對應的訪問信息數組元素即可，由于 每個bucket對應的訪問信息是獨立占據數組的一個元素的，因此bucket鎖就保證了訪問信息的線程安全。這樣就解決了讀取操作的并發競爭問題。
接 下來看看如何解決插入問題。從圖可以看到，每個bucket的需要分配一個獨立的access info位置索引，多線程插入的時候會發生競爭，為了減少競爭，可以預先生成一個目前空閑的位置鏈表，這樣插入的時候，每個線程可以根據當前的 bucket索引選擇從不同的free鏈表里面分配一個位置。這樣鎖競爭可以分散到多個free list上面，每次插入時把分配過的位置索引從free list 移除。
最 后，清理過程可以放在一個獨立線程里面，為了避免插入因為緩存滿了而返回失敗，每次在緩存快滿的時候（free list的size不夠用了），進行一次access info array掃描。根據不同的緩存清除策略和訪問信息（時間和頻率）來決定哪些位置索引是可以重新釋放到free list列表。由于掃描過程中無需加鎖，掃描對讀取和插入操作是沒有性能影響的。只有最后進行釋放時才會對需要釋放的bucket和free list進行加鎖，鎖競爭大大減少。
如上設計，大大減少了緩存的讀取，插入和清理過程中的鎖競爭問題，并且讀取和插入都是O(1)的，并不會因為緩存系統的增大影響性能（清理后臺線程可能會跑的久點，可以選擇性清理來優化）。這樣一個支持高并發的緩存系統就完成了。
簡 單的實現后，實測在8核CPU上面8線程讀，8線程寫，可以跑到 讀寫TPS均在1M/S以上，參考官方單線程的redis的benchmark數據?Using a unix domain socket 排除網絡瓶頸，SET/GET的TPS大概在200k/s 左右，可以看到這樣一個高并發的cache基本上是scalable的。
