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。?