現代分布式存儲系統設計中“一致性”的取舍

CAP定理對現代分布式數據庫系統設計的影響比我們預想的要小。相反，一致性和延遲之間取舍 - 對幾個主流DDBS產生了更為直接的影響。本文提出的新理論PACELC，將這種權衡與CAP結合起來, 以便對分布式數據系統的設計權衡更加系統全面。

盡管學術界幾十年前就開始對分布式數據庫系統進行研究，但直到最近，某些行業才開始廣泛使用DDBS。這種趨勢的出現有兩個主要驅動因素，首先，現代應用程序需要增加數據和事務吞吐量，這導致了對彈性可伸縮數據庫系統的需求。其次，全球化和業務拓展的加快要求將數據放在遍布全球的客戶附近。過去10年中試圖實現高可擴展性或全球可訪問性(或兩者兼有)的DDBS示例包括SimpleDB/Dynamo/DynamoDB，Cassandra，Voldemort(http://projectvoldemort.com)，Sherpa/PNUTS，Riak (http://wiki.basho.com)，HBase/BigTable，MongoDB(www.mongodb.org)，VoltDB/H-Store和Megastore.

DDBS很復雜，構建它們很困難。因此，任何幫助設計人員理解創建DDBS所涉及的權衡的工具都是有益的。特別是CAP定理在幫助設計師推理所提出的系統能力以及揭露許多商業DDBS的夸大營銷炒作方面非常有用。然而，自從最初的正式證明以來，CAP已經變得越來越被誤解和誤用。特別是，許多設計者錯誤地斷定該定理在正常系統操作期間對DDBS施加了某些限制，因此實現了不必要的系統約束。實際上，CAP僅在面對某些類型的故障時附加了限制，而在正常操作期間不會對系統能力產生任何約束和限制。

盡管如此，在正常操作期間抑制DDBS能力的基本權衡影響了主流系統的不同設計選擇。實際上，在一致性和延遲之間的一個特定權衡 - 可以說對DDBS設計的影響比CAP理論更大。兩組權衡都很重要; 將CAP和一致性/延遲權衡統一到一個理論中 - PACELC中可以相應地使得對現代DDBS的設計進行更深入的理解。

CAP IS FOR FAILURES 

CAP表明，在構建DDBS時，設計人員可以選擇三個理想屬性中的兩個：一致性(C)，可用性(A)和分區容忍性(P)。因此，只有CA系統(一致且高可用，但不能容忍分區)，CP系統(一致和分區容錯，但不高可用)和AP系統(高可用性和分區容忍但不一致)是可能的。

許多現代DDBS(包括SimpleDB/Dynamo，Cassandra，Voldemort，Sherpa/PNUTS和Riak)默認不保證CAP定義的一致性。 (雖然這些系統中的一些系統的一致性在初始版本發布后變得可調，但重點在于它們的原始設計。)在他們的CAP證明中，Seth Gilbert和Nancy Lynch使用了原子/線性化一致性的定義：“必須在所有操作中存在一個全局順序，使得每個操作看起來好像是在一個瞬間完成的。這相當于要求分布式共享內存的請求就像它們在單個節點上執行一樣，一次響應一個操作。”

鑒于早期的DDBS研究側重于一致系統，因此很自然地認為CAP是對現代系統架構師的主要影響，他們在定理證明之后的時期內構建了越來越多的系統來實現簡化的一致性模型。這種假設背后的原因是，因為任何DDBS都必須容忍網絡分區，所以根據CAP，系統必須在高可用性和一致性之間進行選擇。對于高可用性非常重要的任務關鍵型應用程序，它別無選擇，只能犧牲一致性。

但是，這種邏輯存在缺陷，與CAP實際所說的不一致。不僅僅是分區容忍需要在一致性和可用性之間進行權衡; 相反，它們是以下兩點的組合：

• 分區容忍

• 網絡分區本身的存在

該定理簡單地指出網絡分區導致系統必須在降低可用性或一致性之間做出決定。網絡分區的概率高度依賴于系統實現的各種細節：它是通過廣域網(WAN)還是僅通過本地集群分布的？什么樣的硬件質量？有哪些流程可以確保仔細執行對網絡配置參數的更改？冗余程度如何？盡管如此，一般而言，網絡分區比較罕見，并且通常不如DDBS中其他嚴重類型的故障事件一樣頻繁發生。

基于CAP的決策而在沒有任何分區發生的情況下降低一致性的DDBS是錯誤的。

由于CAP在基線情況下沒有規定系統限制，因此假設在沒有任何分區的情況下降低一致性的DDBS是錯誤的。事實上，CAP允許系統在沒有分區時提供完整的ACID(原子性，一致性，隔離和持久性)保證以及高可用性。因此，該定理并不能完全證明降低一致性的DDBS的默認配置(通常還有其他一些ACID保證)

CONSISTENCY/LATENCY TRADEOFF

要了解現代DDBS設計，重要的是要實現這些系統的構建背景。亞馬遜最初設計的Dynamo用于向其電子商務平臺(例如購物車)中的核心服務提供數據。 Facebook構建了Cassandra以支持其收件箱搜索功能。 LinkedIn創建了Voldemort，通過其網站上的各種寫密集功能處理在線更新。雅虎構建了PNUTS，用于存儲可在每個網頁視圖中讀取或寫入的用戶數據，存儲Yahoo購物頁面的列表數據，以及存儲數據以服務其社交網絡應用程序。

在每種情況下，系統通常為即時構建并發送給活動網站用戶的網頁提供數據，并接收在線更新。研究表明，延遲是在線互動的一個關鍵因素：小到100毫秒的增加，就可能大大降低客戶未來繼續互動或返回的可能性

不幸的是，在一致性，可用性和延遲之間存在著根本的權衡。 (請注意，可用性和延遲可以說是相同的：不可用的系統本質上提供了極高的延遲。為了討論的目的，我認為延遲大于典型請求超時的系統，例如幾秒鐘就意味著不可用；延遲小于請求超時，但仍然接近幾百毫秒的情況為“高延遲”。但是，我最終會放棄這種區別，并允許低延遲要求包含兩種情況。因此，權衡實際上只是在一致性和延遲之間，正如本文的標題所示。)

即使沒有網絡分區，這種權衡也存在，因此與CAP描述的權衡完全分開。盡管如此，它是設計上述系統的關鍵因素。 (與此討論無關，是否將單個機器故障視為特殊類型的網絡分區。)

權衡的原因是高可用性要求意味著系統必須復制數據。如果系統運行的時間足夠長，系統中至少有一個組件最終會失敗。發生此故障時，除非系統在故障之前復制了另一版本的數據，否則組件控制的所有數據都將變為不可用。因此，即使在沒有故障本身的情況下，故障的可能性也意味著可用性要求在正常系統操作期間需要一定程度的數據復制。 (注意這種權衡和CAP權衡之間的重要區別：雖然失敗的發生導致CAP權衡，但失敗的可能性本身會導致這種權衡。)

為了實現盡可能高的可用性，DDBS必須通過WAN復制數據，以防止整個數據中心因例如颶風，恐怖襲擊而發生故障，或者像2011年4月著名的Amazon EC2云中斷一樣，單個網絡配置錯誤。上面提到的五個降低一致性系統的設計具有極高的可用性，通常用于通過WAN進行復制。

DATA REPLICATION

一旦DDBS復制數據，就會出現一致性和延遲之間的權衡。發生這種情況是因為實現數據復制只有三種選擇：系統同時向所有副本發送數據更新，首先向某個一致的主節點發送數據更新，或者首先向單個(任意)節點發送數據更新。系統可以以各種方式實現這些情況中的每一種; 但是，每個實現都帶有一致性/延遲權衡。

• (1) Data updates sent to all replicas at the same time

如果更新沒有首先通過預處理層或其他協議協議，則可能會出現副本分歧 - 明顯缺乏一致性(假設系統的多個更新同時提交，例如，來自不同的客戶端)，因為每個副本可能選擇應用更新的不同順序。 (即使所有更新都是可交換的 - 這樣每個副本最終都會變得一致，盡管副本可能會以不同的順序應用更新 — 但以Gilbert和Lynch對一致性的嚴格定義來衡量，這任然不是一個一致性的系統。但是，廣義的Paxos可以通過一次RTT的代價提供一致的復制。)

另一方面，如果更新首先通過預處理層或者寫入過程中協調所有節點來決定操作的順序，那么可以確保所有副本就更新的順序達成一致。但是，這會導致延遲增加。比如使用協議的情況下，協議本身是延遲的來源之一。

在預處理的情況下，有兩個延遲源。首先，通過附加系統組件(預處理模塊)路由更新會增加延遲。其次，預處理模塊由多臺機器或一臺機器組成。在前一種情況下，需要一個協議來決定整個機器的操作順序。在后一種情況下，即使另一個數據副本更接近更新發起位置，系統也會強制所有更新，無論它們在何處發起 - 可能在世界的任何地方 - 首先一直路由到單個預處理模塊。

• (2) Data updates sent to an agreed-upon location first

我將這個商定的位置稱為“主節點”(不同的數據項可以有不同的主節點)。此主節點解析所有更新數據項的請求，并且它選擇執行這些更新的順序決定了所有副本執行更新的順序。主節點解析更新后，會將它們復制到所有副本位置。

一旦DDBS復制數據，就會出現一致性和延遲之間的權衡。

有三種復制選項: 

1. 復制是同步的：主節點等待，直到所有更新都進入副本。這確保了副本保持一致，但是由于需要在這些實體之間傳遞消息以及延遲受最慢實體限制的事實，跨獨立實體(尤其是WAN)的同步操作會增加延遲。

2. 復制是異步的：系統將更新視為在復制之前完成更新。通常，在更新的發起者獲知它已完成復制之前(如果主節點發生故障)，更新至少已經在某處持久化存儲，但不保證系統已傳播更新。在這種情況下，一致性/延遲權衡取決于系統如何處理讀取:
   i. 如果系統將所有讀取路由到主節點并從那里提供服務，則不會降低一致性。但是，這種方法存在兩個延遲問題:
   1. 即使有一個靠近讀取請求發起者的副本，系統仍然必須將請求路由到主節點，這可能在物理上更遠
   2. 如果主節點因其他請求過載或發生故障，則無法從其他節點提供讀取服務。相反，請求必須等待主節點變為空閑或恢復。換句話說，缺乏負載平衡選項會增加潛在延遲

3. ii. 如果系統可以從任何節點提供讀取，則讀取延遲要好得多，但這也會導致 同一數據項的讀取不一致，因為不同位置在系統仍在傳播更新時具有不同版本的數據項，并且可以向任何這些位置發送讀取。盡管可以通過跟蹤更新序列號并使用它們來實現順序/時序一致性或讀寫一致性來限制一致性降低的程度，但這些仍然是一種殘次的一致性模型。此外，如果寫操作的主節點在地理上遠離寫請求者，則寫延遲可能很高

4.  (a)和(b)的組合是可能的：系統同步地向副本的某個子集發送更新，而其余的異步發送。在這種情況下，一致性/延遲權衡再次取決于系統如何處理讀取：

     i. 如果它將讀取路由到至少一個已同步更新的節點 - 例如，當Quorum協議中的R + W> N時，其中R是同步讀取中涉及的節點數，W是節點數參與同步寫入，N是副本的數量 - 然后可以保持一致性。然而，(a)，(b)(i)(1)和(b)(i)(2)的等待時間問題都存在，盡管程度稍低，因為同步中涉及的節點數量更小，并且多個節點可以提供讀取請求。
ii. 如果系統有可能從尚未同步更新的節點提供讀取，例如，當R +W≤N時，則可能存在不一致的讀取，如(b)(ii)中所示。從技術上講，簡單地使用Quorum協議并不足以保證Gilbert和Lynch定義標準的一致性。但是，確保完全一致性所需的附加協議在此處不相關，因為即使沒有這些附加條件，延遲也是Quorum協議中固有的。

• (3) Data updates sent to an arbitrary location first

這種情況與(2)之間的區別在于系統為特定數據項發送更新的位置并不總是相同的。例如，可以同時在兩個不同位置發起針對特定數據項的兩個不同更新。一致性/延遲權衡再次取決于兩個選項

a. 如果復制是同步的，則存在(2)(a)的延遲問題。另外，該系統可能產生額外的延遲，以檢測和解決在兩個不同位置發起的同一數據項的同時更新的情況
b. 如果復制是異步的，則存在類似于(1)和(2)(b)的一致性問題

TRADEOFF EXAMPLES

無論DDBS如何復制數據，顯然它必須權衡一致性和延遲。對于短距離精心控制的復制，存在合理的選項，如(2)(a)，因為本地數據中心的網絡通信延遲很小;但是，對于通過WAN進行復制，無法繞過一致性/延遲權衡。

為了更全面地理解這種權衡，考慮四個DDBS為達到極高的可用性，是如何設計的 — Dynamo，Cassandra，PNUTS和Riak。由于這些系統是為與活動Web客戶端的低延遲交互而設計的，因此每個系統都犧牲了一致性以降低延遲。 

Dynamo，Cassandra和Riak使用(2)(c)和(3)的組合。特別是，系統將更新發送到同一節點，然后將這些更新同步傳播到其他W節點 - 即情況(2)(c)。系統同步向R節點發送讀取，R + W通常設置為小于或等于N的數字，導致讀取不一致的可能性。但是，系統并不總是將更新發送到特定數據項的同一節點 - 例如，這可能發生在各種故障情況下，或者由于負載均衡器的重新路由。這導致了(3)中描述的情況以及可能更大的一致性缺陷。 PNUTS使用選項(2)(b)(ii)，在降低一致性的情況下實現更好的延遲。 

Jun Rao，Eugene Shekita和Sandeep Tata最近的一項研究進一步證明了這些系統基線實施的一致性/延時權衡。研究人員通過實驗評估了Cassandra一致性/延遲權衡中的兩個選項。第一個選項“弱讀取”允許系統為任何副本的讀取提供服務，即使該副本尚未收到數據項的所有未完成更新。第二個選項“Quorum讀取”要求系統在讀取數據之前明確檢查多個副本之間的不一致性。相對于第一種選擇，第二種選擇顯然是以延遲為代價而增加了一致性。這兩個選項之間的延遲差異可達四倍或更多。

Hiroshi Wada及其同事的另一項研究似乎與此結果相矛盾。這些研究人員發現，相對于默認(可能不一致)的讀取選項，在SimpleDB中請求一致讀取不會顯著增加延遲。然而，研究人員在Amazon某個Zone(美國西部)內部進行了實驗，他們推測SimpleDB使用主從復制，如果復制發生在短距離內，則可以以適度的延遲成本實現。特別是，Wada及其同事得出結論，SimpleDB強制所有一致讀取都要由master執行。只要讀取請求來自物理上靠近master的位置，并且只要主設備沒有過載，那么一致讀取的額外延遲是不可見的(這些條件在他們的實驗中都是正確的)

如果SimpleDB跨Amazon區域復制數據，并且讀取請求來自與master位置不同的區域，則一致性讀取的延遲成本將更加明顯。即使沒有跨區域復制(SimpleDB目前不支持跨區域復制)，官方的亞馬遜文檔也會警告用戶延遲增加并降低吞吐量以實現一致性讀取。

所有四個DDBS都允許用戶更改默認參數以換取更好的一致性和更大的延時 - 例如，通過在Quorum類型系統中使R + W大于N.盡管如此，即使在沒有網絡分區的情況下，在正常系統操作期間也會發生一致性/等待時間權衡。如果通過WAN進行數據復制，則權衡會被放大。顯而易見的結論是，一致性降低可歸因于運行時延遲，而不是CAP。 PNUTS提供了最有力的證據表明：CAP不是這些系統中降低一致性水平的主要原因。在PNUTS中，主節點擁有每個數據項。系統將對該數據項的更新路由到主節點，然后通過WAN將這些更新異步傳播到副本。 PNUTS可以從任何副本提供讀取，這將系統置于類別(2)(b)(ii)中：它降低了一致性以實現更好的延遲。但是，在網絡分區的情況下，主節點在少數分區內變得不可用，系統默認使數據項不可用于更新。換句話說，PNUTS默認配置實際上是CP：在分區的情況下，系統選擇一致性以避免解決在不同主節點處發起的沖突更新的問題。

因此，降低基線情況一致性的選擇更明顯地歸因于持續的一致性/等待時間權衡，而不是CAP中的一致性/可用性權衡，這僅在網絡分區上發生。 當然，PNUTS在基線情況下一致性不友好的缺陷，在網絡分區情況下也許很有用，因為在不可用分區中的數據仍然可以讀取。

CAP對其他三個系統產生更大的影響可能更大一些。如果發生網絡分區，Dynamo，Cassandra和Riak會更充分地切換到數據復制選項(3)，并使用在檢測到副本差異時運行的特殊協調代碼來處理產生的一致性問題。因此，可以合理地假設這些系統的設計考慮了網絡分區的可能性。因為這些是AP系統，所以從一開始就將協調代碼和切換到(3)的能力內置到代碼中。但是，一旦該代碼存在，就可以方便地重用一些靈活的一致性模型來選擇基線一致性/延遲權衡中的一個點。這個論點比聲稱這些系統的設計者選擇完全降低CAP的一致性(忽略延遲因子)更合乎邏輯。

忽略復制系統的一致性/延遲權衡是一個大問題，因為它在系統運行期間始終存在。

總之，CAP只是現代DDBS降低一致性的兩個主要原因之一。忽略復制系統的一致性/等待時間折衷是一個大問題，因為它在系統操作期間始終存在，而CAP僅與可能極少的網絡分區情況相關。實際上，前者的權衡可能更有影響力，因為它對系統的基線操作有更直接的影響。

PACELC

通過將CAP重寫為PACELC(發音為“pass-elk”)可以實現對DDBS潛在一致性權衡空間的更完整描述：如果存在分區(P)，系統如何權衡可用性和一致性(A 和C); 否則(E)，當系統在沒有分區的情況下正常運行時，系統如何權衡延遲(L)和一致性(C)？

請注意，延遲/一致性權衡(ELC)僅適用于復制數據的系統。否則，系統會遇到任何類型的故障或節點過載時的可用性問題。由于此類問題只是極端延遲的實例，因此ELC權衡的延遲部分可以包含是否復制數據的選擇。

Dynamo，Cassandra和Riak的默認版本是PA/EL系統：如果發生分區，它們會選擇可用性而放棄一致性，在正常操作下，它們會放棄一致性以降低延遲。放棄PACELC中的兩個C使設計更簡單; 一旦系統配置為處理不一致，就有選擇放棄一致性而提供更好的可用性和較低的延遲。然而，這些系統具有用戶可調整的設置以改變ELC權衡 - 例如，通過增加R + W，它們以延遲為代價獲得更高的一致性(盡管它們無法實現Gilbert和Lynch定義的完全一致性，即使R + W> N)。

完全ACID系統(如VoltDB/H-Store和Megastore)是PC/EC：它們拒絕放棄一致性，并將支付實現它的可用性和延遲成本。 BigTable和相關系統(如HBase)也是PC/EC。

MongoDB可以歸類為PA/EC系統。在基線情況下，系統保證讀取和寫入一致。但是，MongoDB使用數據復制選項(2)，如果主節點發生故障或與系統的其余部分分區，則它會存儲已發送到主節點但尚未復制到本地回滾目錄中的所有寫入。同時，系統的其余部分選擇一個新的主服務器以保持可讀和寫入狀態。因此，舊主服務器的狀態和新主服務器的狀態變得不一致，直到系統修復故障并使用回滾目錄來協調狀態，這個過程目前是手動的。 (從技術上講，當發生分區時，根據CAP的可用性定義，MongoDB不可用，因為少數分區不可用。但是，在PACELC的上下文中，因為分區導致比可用性問題更多的一致性問題，MongoDB可以歸類為PA/EC系統。)

PNUTS是一個PC/EL系統。在正常操作中，它選擇更好的延時而放棄了一致性; 但是，如果發生分區，它會放棄可用性以保持一致性。這無疑令人困惑：據PACELC稱，PNUTS似乎在網絡分區上更加一致。但是，不應以這種方式解釋PC/EL。 PC并不表示系統完全一致; 相反，它表示當發生網絡分區時，系統不會降低超出基準一致性級別的一致性 - 相反，它會降低可用性

構建分布式數據庫系統所涉及的權衡是復雜的，CAP和PACELC都無法解釋它們。盡管如此，將一致性/延遲權衡結合到現代DDBS設計考慮中是非常重要的，以保證使權衡更接近架構討論的最前沿。