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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、緩存失效模型

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

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

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

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

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

四、針對(duì)一致性的可觀察性

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

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

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

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

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

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

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

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

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

五、一致性追蹤

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

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

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

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

它是否收到了失效信息？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

drop_cache(key, version);

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

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

七、未來(lái)的緩存一致性工作

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