深入理解分佈式緩存設計

來源：https://zhuanlan.zhihu.com/p/55303228

前言

在高併發的分佈式的系統中，緩存是必不可少的一部分。沒有緩存對系統的加速和阻擋大量的請求直接落到系統的底層，系統是很難撐住高併發的衝擊，所以分佈式系統中緩存的設計是很重要的一環。下面就來聊聊分佈式系統中關於緩存的設計以及過程中遇到的一些問題。

緩存的收益與成本

使用緩存我們得到以下收益：

• 加速讀寫。因爲緩存通常是全內存的，比如 Redis、Memcache。對內存的直接讀寫會比傳統的存儲層如 MySQL，性能好很多。舉個例子：同等配置單機 Redis QPS 可輕鬆上萬，MySQL 則只有幾千。加速讀寫之後，響應時間加快，相比之下系統的用戶體驗能得到更好的提升。

• 降低後端的負載。緩存一些複雜計算或者耗時得出的結果可以降低後端系統對 CPU、IO、線程這些資源的需求，讓系統運行在一個相對資源健康的環境。

但隨之以來也有一些成本：

• 數據不一致性：緩存層與存儲層的數據存在着一定時間窗口一致，時間窗口與緩存的過期時間更新策略有關。

• 代碼維護成本：加入緩存後，需要同時處理緩存層和存儲層的邏輯，增加了開發者維護代碼的成本。

• 運維成本：引入緩存層，比如 Redis。爲保證高可用，需要做主從，高併發需要做集羣。

綜合起來，只要收益大於成本，我們就可以採用緩存。

緩存的更新

緩存的數據一般都是有生命時間的，過了一段時間之後就會失效，再次訪問時需要重新加載。緩存的失效是爲了保證與數據源真實的數據保證一致性和緩存空間的有效利用性。下面將從使用場景、數據一致性、開發運維維護成本三個方面來介紹幾種緩存的更新策略。

1、LRU/LFU/FIFO

這三種算法都是屬於當緩存不夠用時採用的更新算法。只是選出的淘汰元素的規則不一樣：LRU 淘汰最久沒有被訪問過的，LFU 淘汰訪問次數最少的，FIFO 先進先出。

一致性：要清理哪些數據是由具體的算法定的，開發人員只能選擇其中的一種，一致性差。

開發維護成本：算法不需要開發人員維護，只需要配置最大可使用內存即可，然後選擇淘汰算法即可，故成本低。

使用場景：適合內存空間有限，數據長期不變動，基本不存在數據一不致性業務。比如一些一經確定就不允許變更的信息。

2、超時剔除

給緩存數據手動設置一個過期時間，比如 Redis expire 命令。當超過時間後，再次訪問時從數據源重新加載並設回緩存。

一致性：主要處決於緩存的生命時間窗口，這點由開發人員控制。但仍不能保證實時一致性，估一致性一般。

開發維護成本：成本不是很高，很多緩存系統都自帶過期時間 API。比如 Redis expire

使用場景：適合於能夠容忍一定時間內數據不一致性的業務，比如促銷活動的描述文案。

3、主動更新

如果數據源的數據有更新，則主動更新緩存。

一致性：三者當中一致性最高，只要能確定正確更新，一致性就能有保證。

開發維護成本：這個相對來說就高了，**業務數據更新與緩存更新藕合了一起。需要處理業務數據更新成功，而緩存更新失敗的情景，**爲了解耦一般用來消息隊列的方式更新。不過爲了提高容錯性，一般會結合超時剔除方案，避免緩存更新失敗，緩存得不到更新的場景。

使用場景：對於數據的一致性要求很高，比如交易系統，優惠劵的總張數。

所以總的來說緩存更新的最佳實踐是：

低一致性業務：可以選擇第一併結合第二種策略。

高一致性業務：二、三策略結合。

穿透優化

緩存穿透指查詢一個根本不存在的數據，緩存層和存儲層都不命中。一般的處理邏輯是如果存儲層都不命中的話，緩存層就沒有對應的數據。但在高併發場景中大量的緩存穿透，請求直接落到存儲層，稍微不慎後端系統就會被壓垮。所以對於緩存穿透我們有以下方案來優化。

1、緩存空對象

第一種方案就是緩存一個空對象。對於存儲層都沒有命中請求，我們默認返回一個業務上的對象。這樣就可以抵擋大量重複的沒有意義的請求，起到了保護後端的作用。不過這個方案還是不能應對大量高併發且不相同的緩存穿透，如果有人之前摸清楚了你業務有效範圍，一瞬間發起大量不相同的請求，你第一次查詢還是會穿透到 DB。另外這個方案的一種缺點就是**：每一次不同的緩存穿透，緩存一個空對象。大量不同的穿透，緩存大量空對象。內存被大量白白佔用，使真正有效的數據不能被緩存起來。**

所以對於這種方案需要做到：第一，做好業務過濾。比如我們確定業務 ID 的範圍是 [a, b]，只要不屬於[a,b] 的，系統直接返回，直接不走查詢。第二，給緩存的空對象設置一個較短的過期時間，在內存空間不足時可以被有效快速清除。

2、布隆過濾器

布隆過濾器是一種結合 hash 函數與 bitmap 的一種數據結構。相關定義如下：

布隆過濾器（英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。

關於布隆過濾器的原理與實現網上有很多介紹，大家百度 / GOOGLE 一下便可。

布隆過濾器可以有效的判別元素是否集合中，比如上面的業務 ID，並且即使是上億的數據布隆過濾器也能運用得很好。所以對於一些歷史數據的查詢布隆過濾器是極佳的防穿透的選擇。對於實時數據，則需要在業務數據時主動更新布隆過濾器，這裏會增加開發維護更新的成本，與主動更新緩存邏輯一樣需要處理各種異常結果。

綜上所述，其實我覺得布隆過濾器和緩存空對象是完全可以結合起來的。具體做法是布隆過濾器用本地緩存實現，因爲內存佔用極低，不命中時再走 redis/memcache 這種遠程緩存查詢。

無底洞優化

1. 什麼是緩存無底洞問題：

Facebook 的工作人員反應 2010 年已達到 3000 個 memcached 節點，儲存數千 G 的緩存。他們發現一個問題–memcached 的連接效率下降了，於是添加 memcached 節點，添加完之後，並沒有好轉。稱爲 “無底洞” 現象

2. 緩存無底洞產生的原因：

鍵值數據庫或者緩存系統，由於通常採用 hash 函數將 key 映射到對應的實例，造成 key 的分佈與業務無關，但是由於數據量、訪問量的需求，需要使用分佈式後（無論是客戶端一致性哈性、redis-cluster、codis），批量操作比如批量獲取多個 key(例如 redis 的 mget 操作)，通常需要從不同實例獲取 key 值，相比於單機批量操作只涉及到一次網絡操作，分佈式批量操作會涉及到多次網絡 io。

3. 無底洞問題帶來的危害：

(1) 客戶端一次批量操作會涉及多次網絡操作，也就意味着批量操作會隨着實例的增多，耗時會不斷增大。

(2) 服務端網絡連接次數變多，對實例的性能也有一定影響。

所以無底洞似乎是一個無解的問題。實際上我們只要瞭解無底洞產生原因在業務前期規劃好就可以減輕甚至避免無底洞的產生。

1、首先如果你的業務查詢沒有，像 mget 這種批量操作，恭喜你，無底洞將遠離你。

2、將集羣以項目組做隔離，這樣每組業務的 redis/memcache 集羣就不會太大。

3、如果你公司的最大峯值流量遠不及 FB，可能也不需要擔心這個問題。

那技術上有沒有一些優先點？解決思路如下：

1. IO 的優化思路：

(1) 命令本身的效率：例如 sql 優化，命令優化。

(2) 網絡次數：減少通信次數。

(3) 降低接入成本: 長連 / 連接池, NIO 等。

(4) IO 訪問合併: O(n) 到 O(1) 過程: 批量接口 (mget)。

(1)、(3)、(4)通常是由緩存系統的設計開發者來決定的，作爲使用者我們可以從 (2) 減少通信次數上做優化

以 mget 來說有四種方案：

(1). 串行 mget

將 mget 操作 (n 個 key) 拆分爲逐次執行 N 次 get 操作, 很明顯這種操作時間複雜度較高，它的操作時間 = n 次網絡時間 + n 次命令時間，網絡次數是 n，很顯然這種方案不是最優的，但是足夠簡單。

(2). 串行 IO

將 mget 操作 (n 個 key)，利用已知的 hash 函數算出 key 對應的節點，這樣就可以得到一個這樣的關係：Map，也就是每個節點對應的一些 keys

它的操作時間 = node 次網絡時間 + n 次命令時間，網絡次數是 node 的個數，很明顯這種方案比第一種要好很多，但是如果節點數足夠多，還是有一定的性能問題。

(3). 並行 IO

此方案是將方案（2）中的最後一步，改爲多線程執行，網絡次數雖然還是 nodes.size()，但網絡時間變爲 o(1)，但是這種方案會增加編程的複雜度。

它的操作時間 = 1 次網絡時間 + n 次命令時間

(4). hash-tag 實現。

由於 hash 函數會造成 key 隨機分配到各個節點，那麼有沒有一種方法能夠強制一些 key 到指定節點到指定的節點呢?

redis 提供了這樣的功能，叫做 hash-tag。什麼意思呢？假如我們現在使用的是 redis-cluster（10 個 redis 節點組成），我們現在有 1000 個 k-v，那麼按照 hash 函數 (crc16) 規則，這 1000 個 key 會被打散到 10 個節點上，那麼時間複雜度還是上述(1)~(3)

那麼我們能不能像使用單機 redis 一樣，一次 IO 將所有的 key 取出來呢？hash-tag 提供了這樣的功能，如果將上述的 key 改爲如下，也就是用大括號括起來相同的內容，那麼這些 key 就會到指定的一個節點上。

它的操作時間 = 1 次網絡時間 + n 次命令時間

3. 四種批量操作解決方案對比：

關於無底洞優化這塊的內容，詳細可參考併發編程網上面的一篇文章。

**提一下，生產中串行 IO 和並行 IO 的方案，我都有用過，其實效果還好。**畢竟結點都是有限，不是 FB、BAT 這種流量那麼多。並行 IO 如果你是用 java，並且 JDK8 或以上，只要開啓 labmda 並行流就可以實現並行 IO 了，很方便的，編程起來並不複雜，超時定位的話，可以加多些日誌。

雪崩優化

緩存雪崩：由於緩存層承載着大量請求，有效保護了存儲層，但是如果緩存層由於某些原因不能提供服務，於是所有的請求到達存儲層，存儲層的調用量會暴增，造成存儲層級聯宕機的情況。預防和解決緩存雪崩問題可以從以下幾方面入手。

(1) 保證緩存層服務的高可用性，比如一主多從，Redis Sentine 機制。

(2) 依賴隔離組件爲後端限流並降級，比如 netflix 的 hystrix。關於限流、降級以及 hystrix 的技術設計可參考以下鏈接。

(3) 項目資源隔離。避免某個項目的 bug，影響了整個系統架構，有問題也侷限在項目內部。

熱點 key 重建優化

開發人員使用 "緩存 + 過期時間" 的策略來加速讀寫，又保證數據的定期更新，這種模式基本能滿足絕大部分需求。但是如果有兩個問題同時出現，可能會對應用造成致命的傷害。

1. 當前 key 是一個 hot key，比如熱點娛樂新聞，併發量非常大。

2. 重建緩存不能在短時間完成，可能是一個複雜計算，例如複雜的 SQL, 多次 IO，多個依賴等。

當緩存失效的瞬間，將會有大量線程來重建緩存，造成後端負載加大，甚至讓應該崩潰。要解決這個問題有以下方案：

1、互斥鎖

具體做法是隻允許一個線程重建緩存，其它線程等待重建緩存的線程執行完，重新從緩存獲取數據即可。這種方案的話，有個風險就是重建的時間太長或者併發量太大，將會大量的線程阻塞，同樣會加大系統負載。優化方法：除了重建線程之外，其它線程拿舊值直接返回。比如 Google 的 Guava Cache 的 refreshAfterWrite 採用的就是這種方案避免雪崩效應。

2、永不過期

這種就是緩存更新操作是獨立的，可以通過跑定時任務來定期更新，或者變更數據時主動更新。

3、後端限流

**以上兩種方案都是建立在我們事先知道 hot key 的情況下，如果我們事先知道哪些是 hot key 的話，其實問題都不是很大。問題是我們不知道的情況！既然 hot key 的危害是因爲有大量的重建請求落到了後端，如果後端自己做了限流呢，**只有部分請求落到了後端, 其它的都打回去了。一個 hot key 只要有一個重建請求處理成功了, 後面的請求都是直接走緩存了，問題就解決了。

所以高併發情況下，後端限流是必不可少。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/AaOznndlx9P4_-Vg6F4xCA