緩存穿透問題導致Facebook史上嚴重事故之一
2010年9月23，這個世界上最大的社交平臺項目facebook，遭遇了最嚴重宕機故障之一，以至于facebook網站4個小時后才恢復運行。而且這次事故非常極端，工程師不得不先讓facebook下線，才能恢復。雖然10年前的facebook遠沒有現在這么大，不過仍然有超過10億用戶，人們去twitter上抱怨或者取笑這次故障。
那么，導致是什么原因導致這次facebook宕機呢?
Today we made a change to the persistent copy of a configuration value that was interpreted as invalid. This meant that every single client saw the invalid value and attempted to fix it. Because the fix involves making a query to a cluster of databases, that cluster was quickly overwhelmed by hundreds of thousands of queries a second.
一個錯誤的配置變更，導致大量的請求擊穿緩存，直達數據庫。我們把這種現象稱之為cache stampede，wiki地址：https://en.wikipedia.org/wiki/Cache_stampede。這在技術行業是一個非常普遍的問題，很多公司都出現過類似的事故，無數工程師為了不讓自己的項目遭遇這樣的問題做了大量的工作。
1、什么是緩存踩踏
cache stampede是指很多線程嘗試并行訪問緩存，如果緩存中不存在要訪問的數據，那么這時候，線程一般會請求數據庫獲取它們需要的數據(所以cache stampede可以翻譯成緩存踩踏。和緩存穿透有點不一樣，Cache Stampede的重點是很多的線程穿透緩存)。
緩存踩踏破壞性這么大的主要原因是，它可能會導致故障雪崩，也就是說一個故障接著一個故障：
- 大量線程并發請求沒有從緩存中獲取到數據，導致這些請求都會落到數據庫上。
- 數據庫由于恐怖的CPU毛刺而宕機，從而導致大量的超時錯誤。
- 請求線程接收到超時后，又不斷重試請求，從而又導致新一輪的災難。
- 反反復復，無窮無盡。
需要說明的是，即使你沒有 Facebook 那樣的規模，也會遇到這個問題，因為它與規模無關。這個問題一直困擾著初創公司和科技巨頭。
2、如何阻止緩存踩踏
這是個很好的問題，在這篇文章中，我們將探索不同的策略來緩解甚至阻止緩存踩踏的出現。畢竟，你也不想等到你自己的服務出現問題后，才想到要學習如何預防。
2.1 增加更多的緩存
一個很簡單的方法就是增加更多的緩存，它的原理有點類似操作系統的多級緩存。操作系統使用了一個緩存層次結構(L1、L2、L3)，為了更快速的訪問。參考操作系統，你也能在你的應用中引入多級緩存。比如本地內存緩存叫做L1緩存(例如Guava Cache，Caffeine)，遠程緩存叫做L2緩存(例如Redis，memcached)：
這個策略對那些頻繁訪問的數據來說是非常有用的。即使L2緩存中的Key失效了，L1緩存中仍然有值，能夠擋住大量請求不會打到數據庫上。
然后，這種方法需要做一些取舍，在應用服務器本地緩存中緩存數據可能會導致OOM。在使用本地緩存的時候要非常小心，尤其當你會緩存一些大量數據的時候。
另外，這個策略在接下來我要說的這種情況下仍然沒有作用。例如，當一個有很多粉絲的大V上傳了一個新的照片或者視頻到他們的社交賬號上，這時候大量粉絲被提醒大V有新的內容發布，這時候粉絲會集中在相同的時間點上登陸社交平臺查看新的內容。但是可能大V發送的新內容數據還沒有加載到緩存中，這就會導致可怕的緩存踩踏。那么，我們還能做什么呢?
2.2 鎖和Promise
緩存踩踏的核心問題是競態條件(race condition)，即很多的線程爭奪共享資源。只不過這里爭奪的共享資源是緩存。
通常在高并發的系統中，一種阻止共享資源競態的方法是加鎖。一般來講，鎖是用在相同機器上的不同線程，不過也可以使用分布式鎖來應對不同機器對共享資源的競爭(參考redis分布式鎖：http://redis.cn/topics/distlock.html)。
通過給緩存KEY加鎖，就會在同一時間只有一個調用者能訪問爭奪的緩存。如果KEY不存在或者已經過期，調用者就會拿到鎖。這時候其他爭奪的處理線程必須等待直到這個鎖被釋放。
用鎖來解決這個問題，它也會引入另一個問題：系統如何處理所有正在等待鎖釋放的那些線程?
你想嘗試自旋鎖(spinlock)，讓這些線程持續不斷的輪詢去獲取鎖?這就會導致出現非常busy的場景，消耗大量的CPU。或者讓線程在檢查鎖是否可用之前隨機等待一段時間?這樣的話，你又會碰到驚群效應問題(thundering herd problem)。
引入退避和抖動機制來防止驚群效應?這可能行得通，但還有另外一個問題。持有鎖的線程必須重新計算值，并在釋放鎖之前更新緩存鍵。這個過程可能需要耗費一點時間，特別是當計算成本很高或存在網絡問題時，如果因為計算緩存而耗盡了可用的連接池，仍然可能導致宕機。
- backoff-and-jitter
幸運的是，一些大公司也碰到過這樣的問題，他們使用promises來解決這樣的問題。
2.3 Promises如何防止自旋
引用instagram工程師博客(Thundering Herds & Promises)中的內容：
在instagram, 當我們啟用一個新的集群，并且因為集群中的緩存是空的，我們就會碰到緩存stampede問題。這時候，我們就會用promises來解決這個問題。它的核心思想是：不緩存實際的值，而是緩存一個promise，這個promise最終會提供我們需要的值。當我們使用緩存時，如果碰到一個不存在的KEY，我們不立即去數據庫中查詢，而是創建一個promise然后放到緩存中，這個緩存中的promise會去查詢數據庫，其他的并發請求發現這個promise就不會把請求打到數據庫上，它們都會等待第一個線程放進去的promise去數據庫中查詢結果。
通過緩存promise而不是實際的值，就不會自旋鎖了。第一個線程發現緩存中沒有數據，就會用原子性的操作創建并緩存一個異步的promise，所有后續的請求都能立即返回這個promise：
你仍然需要使用鎖來防止多個線程訪問緩存KEY，假設創建 Promise 是一個近乎即時的操作，那么線程停留在自旋鎖中的時間長度就可以忽略不計了。但是，如果重新計算緩存數據需要相當長的時間，那該怎么辦?即使線程能夠立即獲取到緩存的 Promise，它們仍然需要等待異步進程完成后才能將數據返回。雖然這種場景不一定會導致宕機，但仍然會導致尾部延遲和影響整體用戶體驗。如果保持較低的尾部延遲對于應用程序來說很重要，那么就需要考慮另外一種策略。
2.4 預先重新計算
預先重新計算(也被稱為提前過期)原理很簡單：在緩存KEY失效發生前，重新計算緩存的值然后延長失效時間，這就能確保緩存總是最新的，緩存缺失的問題也永遠不會發生。
最簡單的實現方式就是開啟一個后臺處理線程，或者一個定時任務。例如。假設緩存KEY過期時間時一個小時，它需要花兩分鐘來計算值。那么，定時任務可以在過期時間到來之前的5分鐘運行，更新緩存的值并延長失效時間一個小時。
雖然原理非常簡單，但是有一個明顯的缺點，除非你很清楚哪個緩存KEY會被使用，否則你需要重新計算緩存中每個KEY的值，這將是一個非常耗時的過程。而且如果考慮到高可用，某個節點上計算任務失敗了，還需要轉移到另一個可用的節點上繼續計算。
基于這個原因，生產環境上很少有這么做的。當然，也有一個例外。
2.5 概率性重新計算
在2015年，一組研究員發布了一份白皮書 Optimal Probabilistic Cache Stampede Prevention，即最優概率性預防緩存踩踏。在這份白皮書中，他們描述了一個算法來預測在緩存失效之前，什么時候需要重新計算緩存的值。這里涉及到很多數學理論，但是可以做一個簡單的總結：
currentTime - ( timeToCompute * beta * log(rand()) ) > expiry
這個公式中各變量的含義如下所示：
- currentTime 表示當前時間;
- timeToCompute 表示重新計算緩存值需要的時間;
- beta是一個大于0的非負數，默認為1，可配置;
- rand() 一個返回0～1之間隨機數的方法;
- expiry 下一次需要設置的失效時間戳;
它的思想是，每次線程從緩存中獲取數據時，它都需要運行這個算法，如果返回true，那么這個線程將主動去重新計算緩存值。而且離失效時間越近，這個算法返回true的概率就越大。
這個策略不是很好理解，但是實現非常簡單，不需要考慮失敗轉移，也不需要到重新計算緩存中每一個KEY的值。當然，預先重計算假設有一個值需要重新計算，它本身并不能防止其他線程引起緩存踩踏問題。為此，你需要將其與鎖和 Promise 結合起來使用。
3、如何停止正在發生的緩存踩踏
facebook緩存踩踏之所以如此嚴重的原因之一是，即使當工程師找到了解決方案，他們并不能通過部署來解決。因為踩踏仍在繼續。事后診斷報告提到:
更糟糕的是，每次客戶端接收到數據庫查詢錯誤時，都會把它當作一個無效的值，然后就會刪除緩存中相關的KEY，這就意味著即使原來的問題被修復了，但是查詢還在繼續。一旦數據庫無法正確響應某一部分請求，那么就會導致緩存KEY被刪除，從而引起更多的請求打到數據庫上。
所幸的是，有一種已知的模型能處理這個問題。
熔斷器
這個想法不是很新的事情，2007年Michael Nygard發布了 Release It!后就慢慢流行了。熔斷器(Circuit breaking)的原理非常簡單，我們會在熔斷器中封裝一個方法，當監測到失敗時進行計數，并且一旦失敗達到一定閾值時，調用就會收到熔斷器直接返回的錯誤碼，而不會調用到受到熔斷器保護的地方，例如數據庫等。如下圖所示，第一次supplier能正常服務，但是第二次、第三次訪問都是超時。達到熔斷器閾值后，第四次直接返回錯誤碼，而不會將請求直接打給supplier：
熔斷器是響應式的，所以它不能阻止宕機。不過它可以防止連鎖故障的發生。而且它提供了一個終止開關，當事態已經徹底失控時可以開啟。如果 Facebook 使用了熔斷機制，就可以避免讓整個網站癱瘓下線。2010年的時候熔斷器還不是很流行，不過今天已經有很多熔斷的開源組件，例如：Resilience4j, Istio和 Envoy。
4、學到了什么
這篇文章中談論了很多應對緩存踩踏問題的策略，以及其他的科技公司是如何使用這些策略的。那么facebook呢?他們從這次事故中學到了什么?以及他們采取了什么措施來防止事故再次發生?他們的工程師寫了一篇文章：Under the hood: Broadcasting live video to millions，討論了他們對架構所做的改進。和本文我們提到的一樣，比如二級緩存。當然，也提到了一些新的方法，比如 HTTP請求合并。總之，這篇文章非常值得一讀
5、寫在最后
我相信理解緩存踩踏對系統的破壞性是非常有必要的，當然，并不是說每個團隊必須馬上把這些策略用到他們的系統中。因為，選擇何種策略要應對緩存踩踏并不是一件容易的事情，它依賴你的實際用戶場景，架構，以及流量負載情況。但是了解緩存踩踏以及對可能的解決方案對您將來有所幫助，當你以后面對類型問題時，能從容應對。
原文地址：https://betterprogramming.pub/how-a-cache-stampede-caused-one-of-facebooks-biggest-outages-dbb964ffc8ed
本文轉載自微信公眾號「阿飛的博客」，可以通過以下二維碼關注。轉載本文請聯系阿飛的博客公眾號。
