快取有助於減少延遲，提高重讀工作負載的可擴充套件性，並且節省成本。實際上快取是無處不在的，它也在你的手機和你的瀏覽器中執行。例如，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”。快取無限期地保持不一致。這種狀態應該是不可能的。你會如何處理這個問題？如果我們能得到導致最終不一致狀態的每一個步驟的完整時間線，那該有多好？

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

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

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

快取試圖新增版本資料和元資料。

在第一輪中，快取首先填充了舊的元資料。

接下來，一個寫事務以原子方式更新了元資料表和版本表。

在第二輪中，快取寫入了新的版本資料。這裡，快取填充操作與資料庫事務交錯進行。因為競態視窗很小，所以這種情況很少發生。你可能會想，“這就是bug。”。但是實際上到目前為止，一切都按預期進行，因為快取失效應該可以把快取恢復一致。

稍後，在嘗試將快取項更新為新元資料和新版本時，出現了快取無效。這幾乎總是有效的，但這次沒有。

快取失效在快取主機上遇到了一個罕見的瞬時錯誤，這觸發了錯誤處理程式碼。

錯誤處理程式將該條目刪除。虛擬碼看起來是這樣的。

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

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

活動預告