如何設(shè)計(jì)一個(gè)支持高并發(fā)的高性能緩存庫(kù)

不 考慮并發(fā)情況下的緩存的設(shè)計(jì)大家應(yīng)該都比較清楚，基本上就是用map/hashmap存儲(chǔ)鍵值，然后用雙向鏈表記錄一個(gè)LRU來(lái)用于緩存的清理。這篇文章 應(yīng)該是講得很清楚http://timday.bitbucket.org/lru.html。但是考慮到高并發(fā)的情況，如何才能讓緩存保持高性能呢？

高并發(fā)緩存需要解決2個(gè)問(wèn)題：1. 高效率的內(nèi)存分配；2. 高效率的讀取，插入和清理數(shù)據(jù)。關(guān)于第一個(gè)問(wèn)題涉及到高效率的內(nèi)存分配器，使用成熟的jemalloc/tcmalloc足夠滿足需求。這里探討下如何解決第二個(gè)問(wèn)題。

由 于緩存系統(tǒng)的特點(diǎn)， 每次讀取緩存都需要更新一些訪問(wèn)信息（最后讀取時(shí)間，訪問(wèn)頻率），在清理時(shí)會(huì)根據(jù)這些信息使用不同的策略來(lái)進(jìn)行數(shù)據(jù)清理，這樣看來(lái)似乎每次的讀操作都變成 了寫操作。看過(guò)幾篇文章都比較集中在如何優(yōu)化這個(gè)讀操作修改LRU的行為。例如：?http://www.ebaytechblog.com/2011 /08/30/high-throughput-thread-safe-lru-caching/#.UzvEb3V53No 以及?http://openmymind.net/High-Concurrency-LRU-Caching/， 但是這種情況下不論怎么優(yōu)化，使用鏈表的LRU始終是個(gè)瓶頸， 因?yàn)槊看巫x操作只能一個(gè)線程來(lái)修改這個(gè)LRU鏈表，并且修改都是集中在鏈表的兩端。有些文章甚至使用lock-free的doubled linked list來(lái)減少鎖競(jìng)爭(zhēng)。 一些成熟的緩存系統(tǒng)如memcached，使用的是全局的LRU鏈表鎖，而redis是單線程的所以不需要考慮并發(fā)的問(wèn)題。由于這些都是遠(yuǎn)程的緩存服務(wù) 器，因此它們的瓶頸往往是網(wǎng)卡，所以并發(fā)上面并不需要什么高要求。

仔 細(xì)思考后，發(fā)現(xiàn)在并發(fā)的情況下使用LRU鏈表來(lái)記錄訪問(wèn)信息其實(shí)并不合適，會(huì)導(dǎo)致嚴(yán)重的鎖競(jìng)爭(zhēng)，這點(diǎn)無(wú)法避免。因此，需要徹底放棄使用LRU鏈表。鑒于緩 存系統(tǒng)的特性，可以做如下假設(shè)： 緩存如果達(dá)到閥值，可以使插入立即返回失敗。這樣，我們可以使用一個(gè)預(yù)分配的數(shù)組來(lái)記錄所有的cache item的訪問(wèn)信息。整個(gè)結(jié)構(gòu)如下：

concurrent cache system arch

可 以看到鎖粒度是hashmap里面的bucket級(jí)別，每次讀操作只需對(duì)相應(yīng)的bucket加鎖，然后更新bucket對(duì)應(yīng)的訪問(wèn)信息數(shù)組元素即可，由于 每個(gè)bucket對(duì)應(yīng)的訪問(wèn)信息是獨(dú)立占據(jù)數(shù)組的一個(gè)元素的，因此bucket鎖就保證了訪問(wèn)信息的線程安全。這樣就解決了讀取操作的并發(fā)競(jìng)爭(zhēng)問(wèn)題。

接 下來(lái)看看如何解決插入問(wèn)題。從圖可以看到，每個(gè)bucket的需要分配一個(gè)獨(dú)立的access info位置索引，多線程插入的時(shí)候會(huì)發(fā)生競(jìng)爭(zhēng)，為了減少競(jìng)爭(zhēng)，可以預(yù)先生成一個(gè)目前空閑的位置鏈表，這樣插入的時(shí)候，每個(gè)線程可以根據(jù)當(dāng)前的 bucket索引選擇從不同的free鏈表里面分配一個(gè)位置。這樣鎖競(jìng)爭(zhēng)可以分散到多個(gè)free list上面，每次插入時(shí)把分配過(guò)的位置索引從free list 移除。

最 后，清理過(guò)程可以放在一個(gè)獨(dú)立線程里面，為了避免插入因?yàn)榫彺鏉M了而返回失敗，每次在緩存快滿的時(shí)候（free list的size不夠用了），進(jìn)行一次access info array掃描。根據(jù)不同的緩存清除策略和訪問(wèn)信息（時(shí)間和頻率）來(lái)決定哪些位置索引是可以重新釋放到free list列表。由于掃描過(guò)程中無(wú)需加鎖，掃描對(duì)讀取和插入操作是沒(méi)有性能影響的。只有最后進(jìn)行釋放時(shí)才會(huì)對(duì)需要釋放的bucket和free list進(jìn)行加鎖，鎖競(jìng)爭(zhēng)大大減少。

如上設(shè)計(jì)，大大減少了緩存的讀取，插入和清理過(guò)程中的鎖競(jìng)爭(zhēng)問(wèn)題，并且讀取和插入都是O(1)的，并不會(huì)因?yàn)榫彺嫦到y(tǒng)的增大影響性能（清理后臺(tái)線程可能會(huì)跑的久點(diǎn)，可以選擇性清理來(lái)優(yōu)化）。這樣一個(gè)支持高并發(fā)的緩存系統(tǒng)就完成了。

簡(jiǎn) 單的實(shí)現(xiàn)后，實(shí)測(cè)在8核CPU上面8線程讀，8線程寫，可以跑到 讀寫TPS均在1M/S以上，參考官方單線程的redis的benchmark數(shù)據(jù)?Using a unix domain socket 排除網(wǎng)絡(luò)瓶頸，SET/GET的TPS大概在200k/s 左右，可以看到這樣一個(gè)高并發(fā)的cache基本上是scalable的。

轉(zhuǎn)載于:https://www.cnblogs.com/absolute8511/p/3641292.html

總結(jié)

以上是生活随笔為你收集整理的Design a high performance cache for multi-threaded environment的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。