2010 年 9 月 23 日，F(xiàn)acebook 遭遇了迄今為止最嚴(yán)重的宕機(jī)事件之一，網(wǎng)站關(guān)閉了四個(gè)小時(shí)，情況非常嚴(yán)重。為進(jìn)行恢復(fù)工作，工程師們不得不先讓 Facebook 下線。雖然當(dāng)時(shí)的 Facebook 規(guī)模還沒有現(xiàn)在這么龐大，但仍然有超過 10 億用戶，宕機(jī)事件也沒能逃過用戶的眼睛。人們在推特上抱怨或取笑這次事件：

那么，到底是什么導(dǎo)致了這次宕機(jī)事件？事后的診斷報(bào)告提到：

今天，我們修改了一個(gè)錯(cuò)誤的配置，每個(gè)客戶端都看到這個(gè)錯(cuò)誤的配置，然后試圖更新它。因?yàn)楦聰?shù)據(jù)需要查詢數(shù)據(jù)庫集群，集群很快就被每秒數(shù)十萬次的查詢拖垮。

一個(gè)錯(cuò)誤的配置導(dǎo)致大量的數(shù)據(jù)庫請求，這種蜂擁而至的請求被稱為緩存踩踏（Cache Stampede）。這是困擾科技行業(yè)的一個(gè)常見問題，已經(jīng)導(dǎo)致很多公司發(fā)生宕機(jī)事件，比如 2016 年的“互聯(lián)網(wǎng)檔案館”（archive.org）事件。還有很多大型應(yīng)用程序每天都在與之做斗爭，比如 Instagram 和 DoorDash。

當(dāng)多個(gè)線程試圖并行訪問緩存時(shí)，就會(huì)發(fā)生緩存踩踏。如果緩存的值不存在，那么線程將同時(shí)嘗試從數(shù)據(jù)源獲取數(shù)據(jù)。數(shù)據(jù)源通常是數(shù)據(jù)庫，也可以是 Web 服務(wù)器、第三方 API 或任何其他可以返回?cái)?shù)據(jù)的東西。

緩存踩踏之所以極具破壞性，一個(gè)主要原因是它會(huì)導(dǎo)致惡性的失敗循環(huán)：

1. 大量的并發(fā)線程無法從緩存中獲得數(shù)據(jù)，然后直接調(diào)用數(shù)據(jù)庫。

2. 數(shù)據(jù)庫由于巨大的 CPU 峰值發(fā)生崩潰，并導(dǎo)致超時(shí)錯(cuò)誤。

3. 收到超時(shí)錯(cuò)誤后，所有的線程都會(huì)發(fā)起重試，從而導(dǎo)致另一次踩踏。

4. 這個(gè)循環(huán)不斷持續(xù)。

即使你沒有 Facebook 那樣的規(guī)模，也會(huì)遇到這個(gè)問題，因?yàn)樗c規(guī)模無關(guān)。這個(gè)問題一直困擾著初創(chuàng)公司和科技巨頭。

我在得知 Facebook 宕機(jī)事件后問了自己這個(gè)問題。不出所料，自 2010 年以來，關(guān)于如何防止緩存踩踏這個(gè)問題，人們進(jìn)行了大量研究，我從頭到尾把它們看了一遍。

在本文中，我們將探索防止和減輕緩存踩踏影響的不同策略。畢竟，你不會(huì)希望等到發(fā)生宕機(jī)后才去了解可以采取哪些安全措施。

一個(gè)簡單的解決方案就是增加更多的緩存。雖然這似乎有違直覺，但這與操作系統(tǒng)的工作原理是相似的。

操作系統(tǒng)利用了一個(gè)緩存層次結(jié)構(gòu)，其中每個(gè)組件負(fù)責(zé)緩存自己的數(shù)據(jù)，以獲得更快的訪問速度。

你可以在應(yīng)用程序中采用類似的模式，其中內(nèi)存緩存是 Layer 1(L1) 緩存，遠(yuǎn)程緩存是 Layer 2(L2) 緩存。

這對(duì)于防止被頻繁訪問的數(shù)據(jù)發(fā)生踩踏事件特別有用。即使 L2 緩存中的一個(gè)值過期，L1 緩存中可能仍然有緩存的值，避免了重新計(jì)算緩存值。

但這種方法有一些值得注意的地方。在應(yīng)用服務(wù)器的內(nèi)存中，緩存數(shù)據(jù)可能會(huì)導(dǎo)致內(nèi)存不足，特別是在緩存大量數(shù)據(jù)的情況下。

此外，這種緩存策略仍然容易受跟隨者踩踏的影響。

舉一個(gè)跟隨者踩踏的例子：當(dāng)一個(gè)名人上傳了新照片或視頻到他們的社交媒體賬戶，所有關(guān)注者都收到通知，這個(gè)時(shí)候，他們會(huì)急于去查看新上傳的內(nèi)容。由于內(nèi)容是新上傳的，還沒有被緩存，這個(gè)時(shí)候就會(huì)導(dǎo)致可怕的緩存踩踏。

那么，我們該如何解決跟隨者踩踏問題呢？

緩存踩踏最主要的核心問題竟態(tài)條件——多個(gè)線程爭奪共享資源。在這里，共享資源就是緩存。

在高并發(fā)系統(tǒng)中，防止共享資源出現(xiàn)竟態(tài)條件的一種常見方法是使用鎖。鎖通常被用在同一臺(tái)機(jī)器的線程上，但也有一些方法可以將分布式鎖用于遠(yuǎn)程緩存。

通過給緩存鍵加鎖，每次只有一個(gè)調(diào)用者能夠訪問這個(gè)緩存鍵。如果鍵丟失或過期，調(diào)用者可以重新生成數(shù)據(jù)，并放到緩存中，同時(shí)保持持有鎖。其他任何試圖讀取同一個(gè)鍵的進(jìn)程都必須等待，直到鎖被釋放。

使用鎖可以解決竟態(tài)條件問題，但它會(huì)帶來另一個(gè)問題，即如何處理所有等待鎖釋放的線程？使用自旋鎖并讓線程連續(xù)輪詢鎖？這造成了一種繁忙等待。

在檢查鎖是否可用前，讓線程隨機(jī) sleep 一段時(shí)間？現(xiàn)在你要面對(duì)的是驚群效應(yīng)問題。

引入退避和抖動(dòng)機(jī)制來防止驚群效應(yīng)？這可能行得通，但還有另外一個(gè)問題。持有鎖的線程必須重新計(jì)算值，并在釋放鎖之前更新緩存鍵。

https://www.baeldung.com/resilience4j-backoff-jitter

這個(gè)過程可能需要耗費(fèi)一點(diǎn)時(shí)間，特別是當(dāng)計(jì)算成本很高或存在網(wǎng)絡(luò)問題時(shí)。如果因?yàn)橛?jì)算緩存而耗盡了可用的連接池，仍然可能導(dǎo)致宕機(jī)。

所幸的是，一些頂級(jí)科技巨頭正在使用一種更簡單的解決方案：Promise。

引用 Instagram 工程博客的一篇文章“驚群效應(yīng)和 Promise”：

在 Instagram，當(dāng)我們啟動(dòng)一個(gè)新集群時(shí)，會(huì)遇到一個(gè)緩存踩踏問題，因?yàn)榧旱木彺媸强盏?。然后，我們使?Promise 來解決這個(gè)問題：我們緩存的不是實(shí)際數(shù)據(jù)，而是最終會(huì)提供數(shù)據(jù)的 Promise。當(dāng)訪問緩存但獲取不到數(shù)據(jù)時(shí)，我們不是立即去訪問后端，而是創(chuàng)建一個(gè) Promise 并將其放到緩存中。這個(gè) Promise 會(huì)去查詢后端。這樣做的好處是，其他并發(fā)請求也會(huì)拿到這個(gè) Promise，而所有這些并發(fā)線程都將等待后端請求返回的實(shí)際數(shù)據(jù)。

通過緩存 Promise 而不是實(shí)際數(shù)據(jù)，就不需要自旋鎖。第一個(gè)獲取緩存數(shù)據(jù)失敗的線程將使用原子操作（例如 Java 的 computeIfAbsent）創(chuàng)建并緩存異步 Promise。所有后續(xù)的 fetch 請求都會(huì)立即返回這個(gè) Promise。

你仍然需要使用鎖來防止多個(gè)線程訪問緩存鍵，但假設(shè)創(chuàng)建 Promise 是一個(gè)近乎即時(shí)的操作，那么線程停留在自旋鎖中的時(shí)間長度就可以忽略不計(jì)了。

這就是 DoorDash 所采用的避免高速緩存踩踏的方法。

但是，如果重新計(jì)算緩存數(shù)據(jù)需要相當(dāng)長的時(shí)間，那該怎么辦？即使線程能夠立即獲取到緩存的 Promise，它們?nèi)匀恍枰却惒竭M(jìn)程完成后才能將數(shù)據(jù)返回。

雖然這種場景不一定會(huì)導(dǎo)致宕機(jī)，但仍然會(huì)導(dǎo)致尾部延遲和影響整體用戶體驗(yàn)。如果保持較低的尾部延遲對(duì)于應(yīng)用程序來說很重要，那么就需要考慮另外一種策略。

預(yù)先重計(jì)算 (也稱為提前過期) 背后的原理很簡單。在緩存鍵正式過期前，重新計(jì)算緩存值并延長過期時(shí)間。這可以確保緩存始終是最新的，并且不會(huì)發(fā)生緩存失效。

預(yù)先重計(jì)算最簡單的實(shí)現(xiàn)是使用后臺(tái)進(jìn)程或 cron 作業(yè)。例如，假設(shè)有一個(gè)緩存鍵，它的 TTL 是一個(gè)小時(shí)，而重新計(jì)算緩存值需要兩分鐘。cron 作業(yè)可以在 TTL 到期前五分鐘運(yùn)行，并在更新數(shù)值后將 TTL 延長一個(gè)小時(shí)。

雖然這個(gè)想法理論上很簡單，但它有一個(gè)明顯的不足。除非你確切地知道將使用哪些緩存鍵，否則你就需要重新計(jì)算緩存中所有的鍵，這可能是一個(gè)非常費(fèi)時(shí)費(fèi)力的過程。

由于這些原因，我無法在生產(chǎn)環(huán)境中找到這種預(yù)先重計(jì)算的例子，但有一個(gè)例外。

2015 年，一組研究人員發(fā)表了一份白皮書，叫作“最優(yōu)概率性緩存踩踏預(yù)防”。在白皮書中，他們描述了一種算法，用于預(yù)測何時(shí)在緩存過期前重新計(jì)算緩存值。

https://cseweb.ucsd.edu/~avattani/papers/cache_stampede.pdf

雖然白皮書中提到了很多數(shù)學(xué)理論，但這個(gè)算法可以簡單地歸納為：

currentTime - ( timeToCompute * beta * log(rand()) ) > expiry

• currentTime 是當(dāng)前時(shí)間戳

• timeToCompute 是重新計(jì)算緩存值所花費(fèi)的時(shí)間

• beta 是一個(gè)大于 0 的非負(fù)數(shù)，默認(rèn)值為 1，是可配置的

• rand() 是一個(gè)返回 0 到 1 之間隨機(jī)數(shù)的函數(shù)

• expiry 是緩存值未來被設(shè)置為過期的時(shí)間戳

其思想是，每當(dāng)線程從緩存中獲取數(shù)據(jù)時(shí)，都會(huì)執(zhí)行這個(gè)算法。如果返回 true，那么該線程將重新計(jì)算這個(gè)緩存值。離過期時(shí)間越近，這個(gè)算法返回 true 的幾率就會(huì)顯著增加。

雖然這個(gè)策略不是最容易理解的，但執(zhí)行起來相當(dāng)簡單，不需要任何額外的組件，也不需要重新計(jì)算緩存中所有的值。

在 2016 年的宕機(jī)事件后，archive.org 開始使用這種方法。RedisConf17 的一個(gè)演講對(duì)概率性預(yù)先重計(jì)算的工作原理進(jìn)行了很好的概述，我強(qiáng)烈建議觀看 

https://youtu.be/1sKn4gWesTw

當(dāng)然，預(yù)先重計(jì)算假設(shè)有一個(gè)值需要重新計(jì)算，它本身并不能防止追隨者踩踏問題。為此，你需要將其與鎖和 Promise 結(jié)合起來使用。

Facebook 的緩存踩踏事件之所以如此具有破壞性，其原因之一是即使工程師找到了解決方案，也無法進(jìn)行部署，因?yàn)椴忍な录栽谶M(jìn)行當(dāng)中。

事后診斷報(bào)告提到：

更糟糕的是，每次客戶端在試圖查詢數(shù)據(jù)庫時(shí)出現(xiàn)錯(cuò)誤，都會(huì)將其解釋為無效值，并刪除相應(yīng)的緩存鍵。這意味著即使原來的問題被修復(fù)，查詢請求流仍在繼續(xù)涌入。只要數(shù)據(jù)庫無法滿足某些請求的數(shù)據(jù)，就會(huì)帶來更多的請求。我們陷入了一個(gè)不讓數(shù)據(jù)庫恢復(fù)到正常狀態(tài)的循環(huán)中。

現(xiàn)實(shí)情況是，沒有人能保證預(yù)防總是有效的，所以在出現(xiàn)問題時(shí)你還需要知道如何降低影響。防御性編程規(guī)定要制定好計(jì)劃，以防流量繞過屏障發(fā)生踩踏事件。

所幸的是，有一個(gè)已知的模式可用來處理這個(gè)問題。

在程序中使用斷路器的想法并不是什么新鮮事。在 Michael Nygard 的《Release It!》于 2007 年出版后，斷路器模式就開始流行起來。Martin Fowler 在他的文章《回路斷路器》中寫道：

斷路器背后的基本思想非常簡單。你將一個(gè)受保護(hù)的函數(shù)調(diào)用封裝在一個(gè)斷路器對(duì)象中，斷路器對(duì)象負(fù)責(zé)監(jiān)控故障。一旦故障達(dá)到某一閾值，斷路器就跳閘，所有對(duì)斷路器的進(jìn)一步調(diào)用都返回錯(cuò)誤，根本調(diào)用不到受保護(hù)的函數(shù)。

斷路器是反應(yīng)式的，所以它們無法防止宕機(jī)，不過它們可以防止連鎖故障的發(fā)生。當(dāng)事態(tài)失控時(shí)，它們提供了一個(gè)終止開關(guān)。如果 Facebook 使用了熔斷機(jī)制，就可以避免讓整個(gè)網(wǎng)站癱瘓下線。

當(dāng)然，斷路器不像在 2010 年那么流行了。現(xiàn)在，有幾個(gè)庫附帶了斷路器，如 Resilience4j、Istio 和 Envoy。Netflix 和 Lyft 等公司在生產(chǎn)環(huán)境中使用了這些服務(wù)。

在本文中，我們討論了很多關(guān)于解決高速緩存踩踏問題的不同策略，以及其他技術(shù)公司是如何使用它們的。那么 Facebook 呢？Facebook 從故障中吸取了什么教訓(xùn)？他們采取了什么措施來防止故障再次發(fā)生？

Facebook 工程博客的一篇文章“揭秘: 向數(shù)百萬人直播視頻”討論了他們對(duì) Facebook 網(wǎng)站架構(gòu)所做出的改進(jìn)。這篇文章討論了我們已經(jīng)討論過的內(nèi)容，比如緩存層次結(jié)構(gòu)，但也提到了一些新的方法，比如 HTTP 請求合并。這篇文章值得一讀，如果你時(shí)間不夠，這個(gè)視頻為你提供了一個(gè)全面的概述。

https://engineering.fb.com/2015/12/03/ios/under-the-hood-broadcasting-live-video-to-millions/

https://www.facebook.com/Engineering/videos/10153675295382200/?t=0

可以說，F(xiàn)acebook 已經(jīng)從過去的錯(cuò)誤中吸取了教訓(xùn)。

雖然我認(rèn)為有必要了解高速緩存踩踏是如對(duì)系統(tǒng)造成破壞的，但我不認(rèn)為每個(gè)技術(shù)團(tuán)隊(duì)都一定要立即把文中提到的措施添加到自己的架構(gòu)中。選擇處理高速緩存踩踏問題的策略取決于你的實(shí)際場景、架構(gòu)和流量負(fù)載。但是，當(dāng)你在面對(duì)大規(guī)模的流量時(shí)，了解高速緩存踩踏問題和可能的解決方案對(duì)你來說肯定是有好處的。

原文鏈接：

https://betterprogramming.pub/how-a-cache-stampede-caused-one-of-facebooks-biggest-outages-dbb964ffc8ed