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

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

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

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

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

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

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

為什么這個看似簡單的過程在計算機(jī)科學(xué)中被認(rèn)為是個困難的問題？下面是個簡單的例子，說明如何引入緩存不一致的問題。

緩存首先嘗試從數(shù)據(jù)庫中填充x。但是在 "x=42 "到達(dá)緩存主機(jī)之前，有人將x設(shè)置為43。緩存失效事件 "x=43 "首先到達(dá)緩存主機(jī)，將x設(shè)置為43。"x=42 "到達(dá)了緩存，將x設(shè)置為42?，F(xiàn)在數(shù)據(jù)庫中"x=43 "，而緩存中 "x=42 "。

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

緩存失效的挑戰(zhàn)不僅來自于失效協(xié)議的復(fù)雜性，還來自于監(jiān)控緩存一致性和如何確定緩存不一致的原因。設(shè)計一個一致的緩存與操作一個一致的緩存有很大不同，就像設(shè)計Paxos協(xié)議與構(gòu)建在生產(chǎn)中實際運(yùn)行的Paxos一樣，都有很大區(qū)別。

二、我們?yōu)槭裁匆P(guān)心緩存的一致性

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

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

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

三、緩存失效模型

了解緩存失效的困難之處尤其具有挑戰(zhàn)性。讓我們從一個簡單的模型開始。緩存的核心是一個有狀態(tài)的服務(wù)，它將數(shù)據(jù)存儲在一個可尋址的存儲介質(zhì)中。分布式系統(tǒng)本質(zhì)上是一種狀態(tài)機(jī)。如果每個狀態(tài)轉(zhuǎn)換都能正確執(zhí)行，我們就會有一個按預(yù)期工作的分布式系統(tǒng)。否則，系統(tǒng)就會問題。所以，關(guān)鍵的問題是：對于有狀態(tài)的服務(wù)，什么在改數(shù)據(jù)？

靜態(tài)緩存有一個非常簡單的緩存模型（例如，簡化的CDN接近這個模型）。數(shù)據(jù)是不可改變的。沒有緩存主動失效。對于數(shù)據(jù)庫來說，數(shù)據(jù)只有在寫入（或復(fù)制）時才會發(fā)生變化。我們通常對數(shù)據(jù)庫的每一個狀態(tài)變化都有日志。每當(dāng)發(fā)生異常時，日志可以幫助我們了解發(fā)生了什么，縮小問題的范圍，并找出問題所在。構(gòu)建容錯的分布式數(shù)據(jù)庫（這已經(jīng)很困難了），有其獨特的挑戰(zhàn)。這些只是簡化的模型。

對于像TAO和Memcache這樣的動態(tài)緩存，數(shù)據(jù)在讀取（緩存填充）和寫入（緩存失效）的路徑上都會發(fā)生變化。這種組合使得多競態(tài)條件成為可能，而緩存失效則是一個困難的問題。緩存中的數(shù)據(jù)是不持久的，這意味著有時候?qū)鉀Q沖突很重要的版本信息會被清除出去。結(jié)合所有這些特點，動態(tài)緩存產(chǎn)生的競態(tài)條件超出了我們的想象。

而且，記錄和跟蹤每一個緩存狀態(tài)的變化幾乎是不現(xiàn)實的。緩存經(jīng)常被引入來擴(kuò)展重讀的工作負(fù)載。這意味著大部分的緩存狀態(tài)變化都來自緩存填充路徑。以TAO為例。它每天提供超過四億次的查詢。即使緩存命中率達(dá)到99%，我們每天也要進(jìn)行超過10萬億次的緩存填充。記錄和追蹤所有的緩存狀態(tài)變化會使一個重讀的緩存工作負(fù)載變成一個極重寫的日志系統(tǒng)工作負(fù)載。調(diào)試一個分布式系統(tǒng)已經(jīng)帶來了巨大的挑戰(zhàn)。調(diào)試一個沒有緩存狀態(tài)變化的日志或追蹤的分布式系統(tǒng)，基本是不可能的。

盡管有這些挑戰(zhàn)，我們還是提高了TAO的緩存一致性，這些年來從99.9999%提高到99.99999999%。在文章的其余部分，我們將解釋我們是如何做到的，并強(qiáng)調(diào)一些未來的工作。

四、針對一致性的可觀察性

為了解決緩存失效和緩存一致性問題，第一步涉及測量。我們要測量高速緩存的一致性，并在高速緩存中出現(xiàn)不一致的條目時發(fā)出警報。測量不能包含任何假陽性。人類的大腦可以很容易地調(diào)出噪音。如果存在任何誤報，人們很快就會學(xué)會忽略它，而這個測量也變得毫無用處。我們還需要測量是精確的，因為我們談?wù)摰氖菧y量超過10個九的一致性。如果一個修正已經(jīng)落地，我們要保證我們可以定量地測量它帶來的改進(jìn)。

為了解決測量問題，我們建立了一個名為Polaris的服務(wù)。對于一個有狀態(tài)的服務(wù)中的任何異常，只有當(dāng)客戶能夠以這種或那種方式觀察到它，它才是一個異常。否則，它就根本不重要?；谶@一原則，Polaris 專注于測量違反客戶可觀察不變量的情況。

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

這種多時間尺度的設(shè)計不僅允許Polaris在內(nèi)部存在多個隊列，以有效地實現(xiàn)回退和重試，而且對于防止產(chǎn)生誤報也是至關(guān)重要的。

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

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

我們還在Polaris發(fā)給緩存服務(wù)器的查詢中加入了一個特殊的標(biāo)志。因此，Polaris會知道目標(biāo)緩存服務(wù)器是否已經(jīng)看到并處理了緩存失效事件。這一點信息使Polaris能夠區(qū)分瞬時的緩存不一致（通常由復(fù)制/驗證滯后引起）和 "永久 "的緩存不一致(舊版本還無限期地存在于緩存中)。

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

我們將Polaris部署為一個單獨的服務(wù)，這樣它就可以獨立于生產(chǎn)服務(wù)及其工作負(fù)載進(jìn)行擴(kuò)展。如果我們想測量到更多的數(shù)據(jù)，我們可以只增加Polaris的吞吐量或在更長的時間窗口上執(zhí)行聚合。

五、一致性追蹤

在大多數(shù)圖中，我們用一個簡單的盒子來表示緩存。在現(xiàn)實中，省略了許多依賴關(guān)系和數(shù)據(jù)流之后，看起來可能像這樣。

緩存可以在不同的時間點從不同的上游填充，這些上游可以是在同一region內(nèi)或跨region。升級、分片移動、故障恢復(fù)、網(wǎng)絡(luò)分區(qū)和硬件故障都有可能觸發(fā)導(dǎo)致緩存不一致的問題。

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

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

它是否收到了失效信息？

它是否正確地處理了這個失效信息？

之后緩存是否變得不一致了？

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

我們建立了一個有狀態(tài)的庫，記錄和跟蹤這個小的紫色窗口中的緩存突變，在這個窗口中，所有相關(guān)的復(fù)雜交互都會引發(fā)導(dǎo)致緩存不一致的問題。它涵蓋了緩存的過期，甚至沒有日志也能告訴我們是否無效事件從未到達(dá)。它被嵌入到幾個主要的緩存服務(wù)中，并貫穿于整個失效管道。它緩沖了最近修改的數(shù)據(jù)索引，用于確定后續(xù)的緩存狀態(tài)變化是否應(yīng)該被記錄下來。它還支持代碼追蹤，所以我們會知道每個被追蹤查詢的確切代碼路徑。

這種方法幫助我們發(fā)現(xiàn)并修復(fù)了許多缺陷。它為診斷緩存的不一致提供了一個系統(tǒng)性的、更可擴(kuò)展的方法。事實證明，它非常有效。

六、我們今年發(fā)現(xiàn)并修復(fù)的一個線上錯誤

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

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

在系統(tǒng)中，一個非常罕見的操作以事務(wù)方式更新了底層數(shù)據(jù)庫的兩個表—元數(shù)據(jù)表和版本表。

根據(jù)一致性追蹤，我們知道發(fā)生了以下情況：

1）緩存試圖添加版本數(shù)據(jù)和元數(shù)據(jù)。

2）在第一輪中，緩存首先填充了舊的元數(shù)據(jù)。

3）接下來，一個寫事務(wù)以原子方式更新了元數(shù)據(jù)表和版本表。

4）在第二輪中，緩存寫入了新的版本數(shù)據(jù)。這里，緩存填充操作與數(shù)據(jù)庫事務(wù)交錯進(jìn)行。因為競態(tài)窗口很小，所以這種情況很少發(fā)生。你可能會想，“這就是bug”。但是實際上到目前為止，一切都按預(yù)期進(jìn)行，因為緩存失效應(yīng)該可以把緩存恢復(fù)一致。

5）稍后，在嘗試將緩存項更新為新元數(shù)據(jù)和新版本時，出現(xiàn)了緩存無效。這幾乎總是有效的，但這次沒有。

6）緩存失效在緩存主機(jī)上遇到了一個罕見的瞬時錯誤，這觸發(fā)了錯誤處理代碼。

7）錯誤處理程序?qū)⒃摋l目刪除。偽代碼看起來是這樣的。

drop_cache(key, version);

如果條目的版本低于指定的版本，則將其放入緩存。但是，不一致的緩存項包含最新版本。所以這段代碼什么也沒做，將過時的元數(shù)據(jù)無限期地留在緩存中。這就是bug。我們在這里把這個例子簡化了很多。實際的bug甚至更加復(fù)雜，涉及到數(shù)據(jù)庫復(fù)制和跨區(qū)域通信。只有當(dāng)以上所有的步驟都發(fā)生，并且以這個順序具體發(fā)生時，這個bug才會被觸發(fā)。不一致的情況很少出現(xiàn)。該錯誤隱藏在交互操作和瞬時錯誤背后的錯誤處理代碼中。

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

七、未來的緩存一致性工作

我們已經(jīng)分享了我們?nèi)绾斡靡环N通用的、系統(tǒng)的、可擴(kuò)展的方法來增強(qiáng)我們的緩存一致性。展望未來，我們想讓我們所有緩存的一致性在物理上盡可能地接近100%。分散的二級指數(shù)的一致性帶來了一個有趣的挑戰(zhàn)。我們也在測量并有目的地改善讀取時的緩存一致性。最后，我們正在為分布式系統(tǒng)建立高水平的一致性API，想想針對分布式系統(tǒng)的C++的std::memory_order。?