深入理解分布式緩存設計
前言
在高并發(fā)的分布式的系統(tǒng)中，緩存是必不可少的一部分。沒有緩存對系統(tǒng)的加速和阻擋大量的請求直接落到系統(tǒng)的底層，系統(tǒng)是很難撐住高并發(fā)的沖擊，所以分布式系統(tǒng)中緩存的設計是很重要的一環(huán)。下面就來聊聊分布式系統(tǒng)中關于緩存的設計以及過程中遇到的一些問題。
緩存的收益與成本
使用緩存我們得到以下收益：
加速讀寫。因為緩存通常是全內(nèi)存的，比如Redis、Memcache。對內(nèi)存的直接讀寫會比傳統(tǒng)的存儲層如MySQL，性能好很多。舉個例子：同等配置單機Redis QPS可輕松上萬，MySQL則只有幾千。加速讀寫之后，響應時間加快，相比之下系統(tǒng)的用戶體驗能得到更好的提升。
降低后端的負載。緩存一些復雜計算或者耗時得出的結(jié)果可以降低后端系統(tǒng)對CPU、IO、線程這些資源的需求，讓系統(tǒng)運行在一個相對資源健康的環(huán)境。
但隨之以來也有一些成本：
數(shù)據(jù)不一致性：緩存層與存儲層的數(shù)據(jù)存在著一定時間窗口一致，時間窗口與緩存的過期時間更新策略有關。
代碼維護成本：加入緩存后，需要同時處理緩存層和存儲層的邏輯，增加了開發(fā)者維護代碼的成本。
運維成本：引入緩存層，比如Redis。為保證高可用，需要做主從，高并發(fā)需要做集群。
綜合起來，只要收益大于成本，我們就可以采用緩存。
緩存的更新
緩存的數(shù)據(jù)一般都是有生命時間的，過了一段時間之后就會失效，再次訪問時需要重新加載。緩存的失效是為了保證與數(shù)據(jù)源真實的數(shù)據(jù)保證一致性和緩存空間的有效利用性。下面將從使用場景、數(shù)據(jù)一致性、開發(fā)運維維護成本三個方面來介紹幾種緩存的更新策略。
1、LRU/LFU/FIFO
這三種算法都是屬于當緩存不夠用時采用的更新算法。只是選出的淘汰元素的規(guī)則不一樣：LRU淘汰最久沒有被訪問過的，LFU淘汰訪問次數(shù)最少的，F(xiàn)IFO先進先出。
一致性：要清理哪些數(shù)據(jù)是由具體的算法定的，開發(fā)人員只能選擇其中的一種，一致性差。
開發(fā)維護成本：算法不需要開發(fā)人員維護，只需要配置最大可使用內(nèi)存即可，然后選擇淘汰算法即可，故成本低。
使用場景：適合內(nèi)存空間有限，數(shù)據(jù)長期不變動，基本不存在數(shù)據(jù)一不致性業(yè)務。比如一些一經(jīng)確定就不允許變更的信息。
2、超時剔除
給緩存數(shù)據(jù)手動設置一個過期時間，比如Redis expire命令。當超過時間后，再次訪問時從數(shù)據(jù)源重新加載并設回緩存。
一致性：主要處決于緩存的生命時間窗口，這點由開發(fā)人員控制。但仍不能保證實時一致性，估一致性一般。
開發(fā)維護成本：成本不是很高，很多緩存系統(tǒng)都自帶過期時間API。比如Redis expire
使用場景：適合于能夠容忍一定時間內(nèi)數(shù)據(jù)不一致性的業(yè)務，比如促銷活動的描述文案。
3、主動更新
如果數(shù)據(jù)源的數(shù)據(jù)有更新，則主動更新緩存。
一致性：三者當中一致性最高，只要能確定正確更新，一致性就能有保證。
開發(fā)維護成本：這個相對來說就高了，**業(yè)務數(shù)據(jù)更新與緩存更新藕合了一起。需要處理業(yè)務數(shù)據(jù)更新成功，而緩存更新失敗的情景，**為了解耦一般用來消息隊列的方式更新。不過為了提高容錯性，一般會結(jié)合超時剔除方案，避免緩存更新失敗，緩存得不到更新的場景。
使用場景：對于數(shù)據(jù)的一致性要求很高，比如交易系統(tǒng)，優(yōu)惠劵的總張數(shù)。
所以總的來說緩存更新的最佳實踐是：
低一致性業(yè)務：可以選擇第一并結(jié)合第二種策略。
高一致性業(yè)務：二、三策略結(jié)合。
穿透優(yōu)化
緩存穿透指查詢一個根本不存在的數(shù)據(jù)，緩存層和存儲層都不命中。一般的處理邏輯是如果存儲層都不命中的話，緩存層就沒有對應的數(shù)據(jù)。但在高并發(fā)場景中大量的緩存穿透，請求直接落到存儲層，稍微不慎后端系統(tǒng)就會被壓垮。所以對于緩存穿透我們有以下方案來優(yōu)化。
1、緩存空對象
第一種方案就是緩存一個空對象。對于存儲層都沒有命中請求，我們默認返回一個業(yè)務上的對象。這樣就可以抵擋大量重復的沒有意義的請求，起到了保護后端的作用。不過這個方案還是不能應對大量高并發(fā)且不相同的緩存穿透，如果有人之前摸清楚了你業(yè)務有效范圍，一瞬間發(fā)起大量不相同的請求，你第一次查詢還是會穿透到DB。另外這個方案的一種缺點就是：每一次不同的緩存穿透，緩存一個空對象。大量不同的穿透，緩存大量空對象。內(nèi)存被大量白白占用，使真正有效的數(shù)據(jù)不能被緩存起來。
所以對于這種方案需要做到：第一，做好業(yè)務過濾。比如我們確定業(yè)務ID的范圍是[a, b]，只要不屬于[a,b]的，系統(tǒng)直接返回，直接不走查詢。第二，給緩存的空對象設置一個較短的過期時間，在內(nèi)存空間不足時可以被有效快速清除。
2、布隆過濾器
布隆過濾器是一種結(jié)合hash函數(shù)與bitmap的一種數(shù)據(jù)結(jié)構(gòu)。相關定義如下：
布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。
關于布隆過濾器的原理與實現(xiàn)網(wǎng)上有很多介紹，大家百度/GOOGLE一下便可。
布隆過濾器可以有效的判別元素是否集合中，比如上面的業(yè)務ID，并且即使是上億的數(shù)據(jù)布隆過濾器也能運用得很好。所以對于一些歷史數(shù)據(jù)的查詢布隆過濾器是極佳的防穿透的選擇。對于實時數(shù)據(jù)，則需要在業(yè)務數(shù)據(jù)時主動更新布隆過濾器，這里會增加開發(fā)維護更新的成本，與主動更新緩存邏輯一樣需要處理各種異常結(jié)果。
綜上所述，其實我覺得布隆過濾器和緩存空對象是完全可以結(jié)合起來的。具體做法是布隆過濾器用本地緩存實現(xiàn)，因為內(nèi)存占用極低，不命中時再走redis/memcache這種遠程緩存查詢。
無底洞優(yōu)化
1. 什么是緩存無底洞問題：
Facebook的工作人員反應2010年已達到3000個memcached節(jié)點，儲存數(shù)千G的緩存。他們發(fā)現(xiàn)一個問題–memcached的連接效率下降了，于是添加memcached節(jié)點，添加完之后，并沒有好轉(zhuǎn)。稱為“無底洞”現(xiàn)象
2. 緩存無底洞產(chǎn)生的原因：
鍵值數(shù)據(jù)庫或者緩存系統(tǒng)，由于通常采用hash函數(shù)將key映射到對應的實例，造成key的分布與業(yè)務無關，但是由于數(shù)據(jù)量、訪問量的需求，需要使用分布式后（無論是客戶端一致性哈性、redis-cluster、codis），批量操作比如批量獲取多個key(例如redis的mget操作)，通常需要從不同實例獲取key值，相比于單機批量操作只涉及到一次網(wǎng)絡操作，分布式批量操作會涉及到多次網(wǎng)絡io。
3. 無底洞問題帶來的危害：
(1) 客戶端一次批量操作會涉及多次網(wǎng)絡操作，也就意味著批量操作會隨著實例的增多，耗時會不斷增大。
(2) 服務端網(wǎng)絡連接次數(shù)變多，對實例的性能也有一定影響。
所以無底洞似乎是一個無解的問題。實際上我們只要了解無底洞產(chǎn)生原因在業(yè)務前期規(guī)劃好就可以減輕甚至避免無底洞的產(chǎn)生。
1、首先如果你的業(yè)務查詢沒有，像mget這種批量操作，恭喜你，無底洞將遠離你。
2、將集群以項目組做隔離，這樣每組業(yè)務的redis/memcache集群就不會太大。
3、如果你公司的最大峰值流量遠不及FB，可能也不需要擔心這個問題。
那技術(shù)上有沒有一些優(yōu)先點？解決思路如下：
1. IO的優(yōu)化思路：
(1) 命令本身的效率：例如sql優(yōu)化，命令優(yōu)化。
(2) 網(wǎng)絡次數(shù)：減少通信次數(shù)。
(3) 降低接入成本:長連/連接池,NIO等。
(4) IO訪問合并:O(n)到O(1)過程:批量接口(mget)。
(1)、(3)、(4)通常是由緩存系統(tǒng)的設計開發(fā)者來決定的，作為使用者我們可以從(2)減少通信次數(shù)上做優(yōu)化
以mget來說有四種方案：
(1).串行mget
將mget操作(n個key)拆分為逐次執(zhí)行N次get操作, 很明顯這種操作時間復雜度較高，它的操作時間=n次網(wǎng)絡時間+n次命令時間，網(wǎng)絡次數(shù)是n，很顯然這種方案不是最優(yōu)的，但是足夠簡單。
(2). 串行IO
將mget操作(n個key)，利用已知的hash函數(shù)算出key對應的節(jié)點，這樣就可以得到一個這樣的關系：Map，也就是每個節(jié)點對應的一些keys
它的操作時間=node次網(wǎng)絡時間+n次命令時間，網(wǎng)絡次數(shù)是node的個數(shù)，很明顯這種方案比第一種要好很多，但是如果節(jié)點數(shù)足夠多，還是有一定的性能問題。
(3). 并行IO
此方案是將方案（2）中的最后一步，改為多線程執(zhí)行，網(wǎng)絡次數(shù)雖然還是nodes.size()，但網(wǎng)絡時間變?yōu)閛(1)，但是這種方案會增加編程的復雜度。
它的操作時間=1次網(wǎng)絡時間+n次命令時間
(4). hash-tag實現(xiàn)。
由于hash函數(shù)會造成key隨機分配到各個節(jié)點，那么有沒有一種方法能夠強制一些key到指定節(jié)點到指定的節(jié)點呢?
redis提供了這樣的功能，叫做hash-tag。什么意思呢？假如我們現(xiàn)在使用的是redis-cluster（10個redis節(jié)點組成），我們現(xiàn)在有1000個k-v，那么按照hash函數(shù)(crc16)規(guī)則，這1000個key會被打散到10個節(jié)點上，那么時間復雜度還是上述(1)~(3)
那么我們能不能像使用單機redis一樣，一次IO將所有的key取出來呢？hash-tag提供了這樣的功能，如果將上述的key改為如下，也就是用大括號括起來相同的內(nèi)容，那么這些key就會到指定的一個節(jié)點上。
它的操作時間=1次網(wǎng)絡時間+n次命令時間
3. 四種批量操作解決方案對比：
關于無底洞優(yōu)化這塊的內(nèi)容，詳細可參考并發(fā)編程網(wǎng)上面的一篇文章。
提一下，生產(chǎn)中串行IO和并行IO的方案，我都有用過，其實效果還好。畢竟結(jié)點都是有限，不是FB、BAT這種流量那么多。并行IO如果你是用java，并且JDK8或以上，只要開啟labmda并行流就可以實現(xiàn)并行IO了，很方便的，編程起來并不復雜，超時定位的話，可以加多些日志。
雪崩優(yōu)化
緩存雪崩：由于緩存層承載著大量請求，有效保護了存儲層，但是如果緩存層由于某些原因不能提供服務，于是所有的請求到達存儲層，存儲層的調(diào)用量會暴增，造成存儲層級聯(lián)宕機的情況。預防和解決緩存雪崩問題可以從以下幾方面入手。
(1)保證緩存層服務的高可用性，比如一主多從，Redis Sentine機制。
(2)依賴隔離組件為后端限流并降級，比如netflix的hystrix。關于限流、降級以及hystrix的技術(shù)設計可參考以下鏈接。
(3)項目資源隔離。避免某個項目的bug，影響了整個系統(tǒng)架構(gòu)，有問題也局限在項目內(nèi)部。
熱點key重建優(yōu)化
開發(fā)人員使用"緩存+過期時間"的策略來加速讀寫，又保證數(shù)據(jù)的定期更新，這種模式基本能滿足絕大部分需求。但是如果有兩個問題同時出現(xiàn)，可能會對應用造成致命的傷害。
當前key是一個hot key，比如熱點娛樂新聞，并發(fā)量非常大。
重建緩存不能在短時間完成，可能是一個復雜計算，例如復雜的SQL, 多次IO，多個依賴等。
當緩存失效的瞬間，將會有大量線程來重建緩存，造成后端負載加大，甚至讓應該崩潰。要解決這個問題有以下方案：
1、互斥鎖
具體做法是只允許一個線程重建緩存，其它線程等待重建緩存的線程執(zhí)行完，重新從緩存獲取數(shù)據(jù)即可。這種方案的話，有個風險就是重建的時間太長或者并發(fā)量太大，將會大量的線程阻塞，同樣會加大系統(tǒng)負載。優(yōu)化方法：除了重建線程之外，其它線程拿舊值直接返回。比如Google 的 Guava Cache 的refreshAfterWrite采用的就是這種方案避免雪崩效應。
2、永不過期
這種就是緩存更新操作是獨立的，可以通過跑定時任務來定期更新，或者變更數(shù)據(jù)時主動更新。
3、后端限流
以上兩種方案都是建立在我們事先知道hot key的情況下，如果我們事先知道哪些是hot key的話，其實問題都不是很大。問題是我們不知道的情況！既然hot key的危害是因為有大量的重建請求落到了后端，如果后端自己做了限流呢，只有部分請求落到了后端, 其它的都打回去了。一個hot key 只要有一個重建請求處理成功了,后面的請求都是直接走緩存了，問題就解決了。
所以高并發(fā)情況下，后端限流是必不可少。
以上就是我在工作中關于緩存設計、使用的一些心得。如果喜歡文章的話，歡迎點贊或者加關注。