Facebook 是怎麼保證緩存一致性的

緩存有助於減少延遲，提高重讀工作負載的可擴展性，並且節省成本。實際上緩存是無處不在的，它也在你的手機和你的瀏覽器中運行。例如，CDN 和 DNS 本質上是地理複製的緩存。正是由於許多緩存在幕後工作，你現在才能閱讀這篇文章。

Phil Karlton 有句名言："計算機科學中只有兩個難題：緩存失效和命名"。如果你曾經處理過的無效緩存，那麼你很有可能遇到過緩存不一致這個惱人的問題。

在 Meta，我們運營着世界上最大的高速緩存，包括 TAO 和 Memcache。多年來，我們將 TAO 的緩存一致性提高了一個檔次，從 99.9999%（六個九）提高到 99.99999999%（十個九）。

當涉及到緩存無效時，我們相信我們現在有一個有效的解決方案來彌補理論和實踐之間的差距。這篇博文中的原則和方法廣泛適用於大多數（如果不是所有）的緩存服務。無論你是在 Redis 中緩存 Postgres 數據，還是將分散數據具像化，都是如此。

我們希望能幫助減少工程師必須處理的緩存失效問題，並幫助增強緩存的一致性。

定義緩存失效和緩存一致性

根據定義，緩存並不是你數據的真實來源（例如，數據庫）。緩存失效描述的是當真實源中的數據發生變化時，主動將陳舊的緩存條目失效的過程。如果緩存失效處理不當，就會在緩存中無限期地保留一個不一致的值。

緩存失效涉及到一個必須由緩存自身以外的程序來執行的動作。一些程序（例如，客戶端或公共 / 子系統）需要告訴緩存其中數據發生了變化。僅僅依靠 TTL 來保持有效性的緩存，不在本文討論範圍之內。在這篇文章的其餘部分，我們將假設存在緩存失效操作。

爲什麼這個看似簡單的過程在計算機科學中被認爲是個困難的問題？下面是個簡單的例子，說明如何引入緩存不一致的問題。

緩存首先嚐試從數據庫中填充 x。但是在 "x=42" 到達緩存主機之前，有人將 x 設置爲 43。緩存失效事件 "x=43" 首先到達緩存主機，將 x 設置爲 43。"x=42" 到達了緩存，將 x 設置爲 42。現在數據庫中 "x=43"，而緩存中 "x=42"。

有很多方法來解決這個問題，其中之一就是維護版本字段。這樣我們就可解決衝突，因爲舊的數據不應該覆蓋新的數據。但是，如果緩存條目 "x=43 @version=2" 在 "x=42" 到達之前就失效了呢？在這種情況下，緩存數據依然是錯誤的。

緩存失效的挑戰不僅來自於失效協議的複雜性，還來自於監控緩存一致性和如何確定緩存不一致的原因。設計一個一致的緩存與操作一個一致的緩存有很大不同，就像設計 Paxos 協議與構建在生產中實際運行的 Paxos 一樣，都有很大區別。

我們爲什麼要關心緩存的一致性

我們必須解決複雜的緩存失效問題嗎？在某些情況下，緩存的不一致性幾乎和數據庫數據丟失一樣嚴重。從用戶的角度來看，它甚至和數據丟失沒有區別。

讓我們來看看另一個關於緩存不一致如何導致腦裂的例子。Meta 公司使用消息將其從用戶在主存儲數據的映射到 TAO 中。它經常進行移動，以保證用戶可以就近訪問。每次你向某人發送消息時，系統都會查詢 TAO，以找到消息的存儲位置。許多年前，當 TAO 的一致性較差時，一些 TAO 副本在重新移動後會出現不一致的數據，如下例所示。

想象一下，在將 Alice 的主消息存儲從區域 2 切換到區域 1 後，Bob 和 Mary，都向 Alice 發送了消息。當 Bob 向 Alice 發送消息時，系統查詢了靠近 Bob 居住地的區域的 TAO 副本，並將消息發送到區域 1。當 Mary 向 Alice 發送消息時，系統查詢了靠近 Mary 居住地的地區的 TAO 副本，命中了不一致的 TAO 副本，並將消息發送到了地區 2。Bob 和 Mary 將他們的消息發送到不同的區域，而兩個區域都沒有愛麗絲消息的完整副本。

緩存失效模型

瞭解緩存失效的困難之處尤其具有挑戰性。讓我們從一個簡單的模型開始。緩存的核心是一個有狀態的服務，它將數據存儲在一個可尋址的存儲介質中。分佈式系統本質上是一種狀態機。如果每個狀態轉換都能正確執行，我們就會有一個按預期工作的分佈式系統。否則，系統就會問題。所以，關鍵的問題是：對於有狀態的服務，什麼在改數據？

靜態緩存有一個非常簡單的緩存模型（例如，簡化的 CDN 接近這個模型）。數據是不可改變的。沒有緩存主動失效。對於數據庫來說，數據只有在寫入（或複製）時纔會發生變化。我們通常對數據庫的每一個狀態變化都有日誌。每當發生異常時，日誌可以幫助我們瞭解發生了什麼，縮小問題的範圍，並找出問題所在。構建容錯的分佈式數據庫（這已經很困難了），有其獨特的挑戰。這些只是簡化的模型。

對於像 TAO 和 Memcache 這樣的動態緩存，數據在讀取（緩存填充）和寫入（緩存失效）的路徑上都會發生變化。這種組合使得多競態條件成爲可能，而緩存失效則是一個困難的問題。緩存中的數據是不持久的，這意味着有時候對解決衝突很重要的版本信息會被清除出去。結合所有這些特點，動態緩存產生的競態條件超出了我們的想象。

而且，記錄和跟蹤每一個緩存狀態的變化幾乎是不現實的。緩存經常被引入來擴展重讀的工作負載。這意味着大部分的緩存狀態變化都來自緩存填充路徑。以 TAO 爲例。它每天提供超過四億次的查詢。即使緩存命中率達到 99%，我們每天也要進行超過 10 萬億次的緩存填充。記錄和追蹤所有的緩存狀態變化會使一個重讀的緩存工作負載變成一個極重寫的日誌系統工作負載。調試一個分佈式系統已經帶來了巨大的挑戰。調試一個沒有緩存狀態變化的日誌或追蹤的分佈式系統，基本是不可能的。

儘管有這些挑戰，我們還是提高了 TAO 的緩存一致性，這些年來從 99.9999 提高到 99.99999999。在文章的其餘部分，我們將解釋我們是如何做到的，並強調一些未來的工作。

針對一致性的可觀察性

爲了解決緩存失效和緩存一致性問題，第一步涉及測量。我們要測量高速緩存的一致性，並在高速緩存中出現不一致的條目時發出警報。測量不能包含任何假陽性。人類的大腦可以很容易地調出噪音。如果存在任何誤報，人們很快就會學會忽略它，而這個測量也變得毫無用處。我們還需要測量是精確的，因爲我們談論的是測量超過 10 個九的一致性。如果一個修正已經落地，我們要保證我們可以定量地測量它帶來的改進。

爲了解決測量問題，我們建立了一個名爲 Polaris 的服務。對於一個有狀態的服務中的任何異常，只有當客戶能夠以這種或那種方式觀察到它，它纔是一個異常。否則，它就根本不重要。基於這一原則，Polaris 專注於測量違反客戶可觀察不變量的情況。

在高層次上，Polaris 作爲客戶端與有狀態的服務進行交互，並且不假設了解服務內部。這使得它是通用的。Meta 有幾十個服務使用 Polaris。"緩存最終應該與數據庫一致" 是 Polaris 監控的一個典型的客戶端可觀察到的不變因素，特別是在異步緩存失效的情況下。在這種情況下，Polaris 假裝是一個緩存服務器並接收緩存失效事件。例如，如果 Polaris 收到一個無效事件，說 "x=4 @version 4"，它就會作爲客戶查詢所有的緩存副本，以驗證是否有任何違反該不變性的情況發生。如果一個緩存副本返回 "x=3 @version 3"，Polaris 將其標記爲不一致，並重新等待樣本，以便以後針對同一目標緩存主機進行檢查。Polaris 在某些時間尺度上報告不一致，例如一分鐘、五分鐘或十分鐘。如果這個樣本在一分鐘後仍然顯示爲不一致，Polaris 就將其報告爲相應時間尺度的不一致。

這種多時間尺度的設計不僅允許 Polaris 在內部存在多個隊列，以有效地實現回退和重試，而且對於防止產生誤報也是至關重要的。

我們來看看一個更有趣的例子。假設 Polaris 收到一個 "x=4 @version 4" 的無效信息。但是當它查詢一個緩存副本時，得到的答覆是 x 不存在。目前還不清楚 Polaris 是否應該將此作爲一個不一致的標記。有可能 x 在版本 3 的時候是不存在的，版本 4 的寫入是對 key 的最新寫入，而這種情況確實是緩存不一致。也有可能是第 5 個版本的操作刪除了 x，也許 Polaris 只是看到了失效事件中的數據更新的視圖。

爲了區分這兩種情況，我們需要繞過緩存，檢查數據庫中的內容。繞過緩存的查詢是非常密集的運算。它們也會使數據庫面臨風險，因爲保護數據庫和擴展重讀工作負載是緩存最常見的用例之一。因此，我們不能繞過緩存發送太多的查詢。Polaris 通過延遲執行計算密集型操作來解決這個問題，直到不一致的樣本跨越報告時間尺度（如一分鐘或五分鐘）。真正的緩存不一致和對同一 key 的競爭寫操作是很少的。因此，在它跨越下一個時間尺度邊界之前才進行一致性檢查有助於消除執行大部分數據庫查詢。

我們還在 Polaris 發給緩存服務器的查詢中加入了一個特殊的標誌。因此，Polaris 會知道目標緩存服務器是否已經看到並處理了緩存失效事件。這一點信息使 Polaris 能夠區分瞬時的緩存不一致（通常由複製 / 驗證滯後引起）和 "永久" 的緩存不一致 (舊版本還無限期地存在於緩存中)。

Polaris 也提供觀測指標，如 "N 個 9 的緩存寫入在 M 分鐘內是一致的"。在文章的開頭，我們提到，通過一項改進，我們將 TAO 的緩存一致性從 99.9999% 提高到 99.99999999%。Polaris 提供了 5 分鐘時間尺度的指標。換句話說，99.99999999% 的緩存寫入在 5 分鐘內是一致的。在 TAO 中 5 分鐘內，100 億次緩存寫入中不到 1 次會出現不一致。

我們將 Polaris 部署爲一個單獨的服務，這樣它就可以獨立於生產服務及其工作負載進行擴展。如果我們想測量到更多的數據，我們可以只增加 Polaris 的吞吐量或在更長的時間窗口上執行聚合。

一致性追蹤

在大多數圖中，我們用一個簡單的盒子來表示緩存。在現實中，省略了許多依賴關係和數據流之後，看起來可能像這樣。

緩存可以在不同的時間點從不同的上游填充，這些上游可以是在同一 region 內或跨 region。升級、分片移動、故障恢復、網絡分區和硬件故障都有可能觸發導致緩存不一致的問題。

然而，正如前面提到的，記錄和追蹤每一個緩存數據的變化是不切實際的。但是，如果我們只在緩存不一致的地方和時候（或者緩存失效可能被錯誤地處理）記錄和跟蹤緩存的突變，會怎麼樣呢？在這個龐大而複雜的分佈式系統中，任何組件的缺陷都可能導致緩存不一致，是否有可能找到一個引入大部分（如果不是全部）緩存不一致的地方？

我們的任務變成了尋找一個簡單的解決方案來幫助我們管理這種複雜性。我們想從單個緩存服務器的角度來評估整個緩存一致性問題。最後，不一致的問題必須在一個緩存服務器上出現。從它的角度來看，它只關心幾個方面。

這就是我們在文章開頭解釋的那個例子，現在用一個時空圖來說明。如果我們把注意力集中在底部的緩存時間軸上，我們可以看到在客戶端寫完之後，有一個窗口，在這個窗口中，失效和緩存填充都在競爭更新緩存。一段時間後，緩存將處於靜止狀態。在這種狀態下，緩存的填充仍然會大量發生，但從一致性的角度來看，由於沒有寫入，它已經淪爲一個靜態的緩存，所以它的意義不大。

我們建立了一個有狀態的庫，記錄和跟蹤這個小的紫色窗口中的緩存突變，在這個窗口中，所有相關的複雜交互都會引發導致緩存不一致的問題。它涵蓋了緩存的過期，甚至沒有日誌也能告訴我們是否無效事件從未到達。它被嵌入到幾個主要的緩存服務中，並貫穿於整個失效管道。它緩衝了最近修改的數據索引，用於確定後續的緩存狀態變化是否應該被記錄下來。它還支持代碼追蹤，所以我們會知道每個被追蹤查詢的確切代碼路徑。

這種方法幫助我們發現並修復了許多缺陷。它爲診斷緩存的不一致提供了一個系統性的、更可擴展的方法。事實證明，它非常有效。

我們今年發現並修復的一個線上錯誤

在一個系統中，我們對每條數據進行了版本排序和衝突解決。在這種情況下，我們在緩存中觀察到 "metadata=0 @version4"，而數據庫中包含 "metadata=1 @version4"。緩存無限期地保持不一致。這種狀態應該是不可能的。你會如何處理這個問題？如果我們能得到導致最終不一致狀態的每一個步驟的完整時間線，那該有多好？

一致性追蹤正好提供了我們需要的時間線。

在系統中，一個非常罕見的操作以事務方式更新了底層數據庫的兩個表—元數據表和版本表。

根據一致性追蹤，我們知道發生了以下情況。

  1. 緩存試圖添加版本數據和元數據。

  2. 在第一輪中，緩存首先填充了舊的元數據。

  3. 接下來，一個寫事務以原子方式更新了元數據表和版本表。

  4. 在第二輪中，緩存寫入了新的版本數據。這裏，緩存填充操作與數據庫事務交錯進行。因爲競態窗口很小，所以這種情況很少發生。你可能會想，"這就是 bug。"。但是實際上到目前爲止，一切都按預期進行，因爲緩存失效應該可以把緩存恢復一致。

  5. 稍後，在嘗試將緩存項更新爲新元數據和新版本時，出現了緩存無效。這幾乎總是有效的，但這次沒有。

  6. 緩存失效在緩存主機上遇到了一個罕見的瞬時錯誤，這觸發了錯誤處理代碼。

  7. 錯誤處理程序將該條目刪除。僞代碼看起來是這樣的。

drop_cache(key, version);

如果條目的版本低於指定的版本，則將其放入緩存。但是，不一致的緩存項包含最新版本。所以這段代碼什麼也沒做，將過時的元數據無限期地留在緩存中。這就是 bug。我們在這裏把這個例子簡化了很多。實際的 bug 甚至更加複雜，涉及到數據庫複製和跨區域通信。只有當以上所有的步驟都發生，並且以這個順序具體發生時，這個 bug 纔會被觸發。不一致的情況很少出現。該錯誤隱藏在交互操作和瞬時錯誤背後的錯誤處理代碼中。

許多年前，如果有人對代碼和服務瞭如指掌並且他們足夠幸運的話，要花幾周時間才能找到這種錯誤的根本原因。在這種情況下，Polaris 發現了異常情況，並立即發出警報。通過一致性追蹤的信息，值班工程師花了不到 30 分鐘就可以找到這個錯誤。

未來的緩存一致性工作

我們已經分享了我們如何用一種通用的、系統的、可擴展的方法來增強我們的緩存一致性。展望未來，我們想讓我們所有緩存的一致性在物理上儘可能地接近 100%。分散的二級指數的一致性帶來了一個有趣的挑戰。我們也在測量並有目的地改善讀取時的緩存一致性。最後，我們正在爲分佈式系統建立高水平的一致性 API，想想針對分佈式系統的 C++ 的 std::memory_order。

原文鏈接：

https://engineering.fb.com/2022/06/08/core-data/cache-invalidation/?continueFlag=5d7598b8068e4850d16d3bc686805488

參考閱讀：

本文由高可用架構翻譯。技術原創及架構實踐文章，歡迎通過公衆號菜單「聯繫我們」進行投稿。

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

猜你喜歡