英文原文：How to beat the CAP theorem
CAP 定理是數據系統設計的基本理論，目前幾乎所有的數據系統的設計都遵循了這個定理。但 CAP 定理給目前的數據系統帶來了許多複雜的、不可控的問題，使得數據系統的設計越來越複雜。Twitter 首席工程師、Storm 的作者 Nathan Marz 在本文中通過避開 CAP 定理帶來的諸多複雜問題，展示了一個不同於以往的數據系統設計方案，給我們的數據系統設計帶來了全新的思路。
CAP 定理指出，一個數據庫不可能同時滿足一致性（Consistency）、可用性（Availability）和分區容錯性（Partition-Tolerance）。
一致性（Consistency）是指執行了一次成功的寫操作之後，未來的讀操作一定可以讀到這個寫入的值。可用性（Availability）是指系統總是可讀可寫的。Yammer 的 Coda Hale 和 Cloudera 的 Henry Robinson 都闡述過，分區容錯性是不能犧牲的，因此只能在一致性和可用性上做取捨，如何處理這種取捨正是目前 NoSQL 數據庫的核心焦點。
選擇一致性而不是可用性的系統將面臨一些尷尬的問題，當系統不可用時怎麼辦？你可以對寫操作進行緩衝處理，但如果存儲緩衝數據的機器出現故障，客戶端將丟失寫入的值。同樣地，緩衝寫也可以被認為是一種非一致性的操作，因為客戶端認為成功的寫入實際上並沒有寫入到實際的數據庫中。當然，系統可以在機器不可用時向客戶端返回錯誤，但可以想象，一個經常告訴客戶端“請重試”的產品是多麼令人討厭。
另一個方案是選擇可用性放棄一致性。這種情況下最好的一致性保障是“最終一致性”（Eventually Consistency）。當使用最終一致性的系統時，客戶端有時會讀到與剛剛寫入數據不同的數據。有時候，同一時間同一個 key 的多個請求有可能返回不同的結果。數據更新並不能及時在所有的複製節點上生效，所以不同的複製節點上可能讀取到的是不同的值。當你檢測到數據不一致性時，你需要進行修復（Repair）操作，這就需要使用矢量時鐘（vector clock）記錄數據的版本歷史併合並不同的數據更新（這稱為讀取修復，read repair）。
我相信在應用層維護最終一致性對開發人員負擔太重，開發人員極易弄錯讀取修復的代碼，而一旦開發人員犯錯，有問題的讀取修復將對數據庫系統造成不可逆的損壞。
所以犧牲可用性時問題會很多，犧牲一致性時構建和維護系統的複雜度又很高，但這裡又只有兩個選擇，不管怎樣做都會不完美。CAP 定理是改不了的，那麼還有什麼其他可能的選擇嗎？
實際上，還有一個辦法：你並不能避開 CAP 定理，但可以把複雜的問題獨立出來，免得你喪失對整個系統的掌控能力。CAP 定理帶來的複雜性，其實是我們如何構建數據系統這一根本問題的體現。其中有兩點特別重要：數據庫中可變狀態和更新狀態的增量算法。複雜性正是這兩點和 CAP 定理之間的相互作用導致的。
本文將通過一個數據庫系統的設計，來說明如何解決 CAP 定理通常會造成的複雜性問題。但我要做的不僅僅如此，CAP 定理是一個針對機器發生錯誤時系統容錯性的一個定理，而這裡有比機器容錯性更加重要的容錯性——人為操作容錯性。在軟件開發中一個確定的事實是，開發人員都並非完人，產品中難免有一些 Bug，我們的系統必須對有 Bug 的程序寫入的錯誤數據有足夠的適應能力，我要展示的系統將是這樣一個可以容忍人為錯誤的系統。
本文將挑戰你對數據系統如何構建這一問題的假設，通過顛覆傳統數據系統構建方法，我會讓大家看到一個前所未見的優雅、擴展性強、健壯的數據系統。
什麼是數據系統？
在開始介紹系統設計之前，讓我們先來看看我們要解決的問題：數據系統的目的在於什麼？ 什麼是數據？ 在我們考慮 CAP 定理之前，我們必須給出一個可以適用於所有數據應用程序的定義來回答上述問題。
數據應用程序種類很多，包括存入和提取數據對象、連接、聚合、流處理、機器學習等。似乎並不存在一個對數據系統的明確定義，數據處理的多樣性使得我們很難用一個定義來描述。
事實卻並非如此，下面這個簡單的定義：
Query = Function (All Data)
概括了數據庫和數據系統的所有領域。每一個領域——有 50 年曆史的 RDBMS、索引、OLAP、OLTP、MapReduce、EFL、分佈式文件系統、流處理器、NoSQL 等——都可以被概括進這個方程。
所謂數據系統就是要回答數據集問題的系統，這些問題我們稱之為“查詢”。上面的方程表明，查詢就是數據上的一個函數。
上述方程對於實際使用來說太過於籠統，幾乎對複雜的數據系統設計不起什麼作用。但如果所有的數據系統都遵循這個方程又會怎樣呢？這個方程是探索我們數據系統的第一步，而它最終將引導我們找到“打敗”CAP 定理的方法。
這個方程裡面有兩個關鍵概念：數據、查詢。這兩個完全不同的概念經常被混為一談，所以下面來看看這兩個概念究竟是什麼意思。
數據
我們先從“數據”開始。所謂數據就是一個不可分割的單位，它肯定存在，就跟數學裡面的公理一樣。
關於“數據”有兩個關鍵的性質。首先，數據是跟時間相關的，一個真實的數據一定是在某個時間點存在於那兒。比如，假如 Sally 在她的社交網絡個人資料中寫她住在芝加哥，你拿到的這個數據肯定是她某個時間在芝加哥填寫的。假如某天 Sally 把她資料裡面居住地點更新為亞特蘭大，那麼她肯定在這個時候是住在亞特蘭大的，但她住在亞特蘭大的事實無法改變她曾經住在芝加哥這個事實——這兩個數據都是真實的。
其次，數據無法改變。由於數據跟某個時間點相關，所以數據的真實性是無法改變的。沒有人可以回到那個時間去改變數據的真實性，這說明了對數據操作只有兩種：讀取已存在的數據和添加更多的新數據。那麼 CRUD 就變成了 CR【譯者注：CRUD 是指 Create Read Update Delete，即數據的創建、讀取、更新和刪除】。
我去掉了“更新”操作，因為更新對於不可改變的數據沒有任何作用。例如，更新 Sally 的位置信息本質上就是在她住的地方數據中新加一條最近的位置信息而已。
我同樣去掉了“刪除”操作，因為絕大部分刪除操作可以更好地表述為新加一條數據。比如 Bob 在 Twitter 上不再關注 Mary 了，這並不能改變他曾經關注過 Mary 這個事實。所以與其刪除 Bob 關注 Mary 這個數據，還不如新加一條 Bob 在某個時間點不再關注 Mary 這個數據。
這裡只有很少數的情況需要永久“刪除”數據，例如規則要求你每隔一段時間清掉數據，這個情況在我將要展示的系統中有很好的解決方案，所以為了簡潔，我們暫不考慮這些情況。
查詢
查詢是一個針對數據集的推導，就像是一個數學裡面的定理。例如，你可以通過計算“Sally 現在的位置在哪裡”這個查詢來得到 Sally 最新的位置數據。查詢是整個數據集合上的函數，可以做一切事情：聚合、連接不同類型的數據等。因此，你可以查詢系統中女性用戶的數量，可以查詢最近幾小時熱門的 Twitter 內容。
前面我已經定義查詢是整個數據集上的函數，當然，不是所有的查詢都需要整個數據集，它們只需要數據集的一個子集。但我的定義是涵蓋了所有的查詢類型，如果想要“打敗”CAP 定理，我們需要能夠處理所有的查詢。
打敗 CAP 定理
計算查詢最簡單的辦法就是按照查詢語義在整個數據集上運行一個函數。如果這可以滿足你對延遲的要求，那麼就沒有其他需要構建的了。
可想而知，我們不能指望在整個數據集上的查詢能夠很快完成，特別是那些服務大型網站、需要每秒處理幾百萬次請求的系統。但假如這種查詢可以很快完成，讓我們來看看像這樣的系統和 CAP 定理的 PK 結果：你將會看到，這個系統不僅打敗了 CAP 定理，而且還消滅了它。
CAP 定理仍然適用，所以你需要在可用性和一致性上做出選擇，這裡的漂亮之處在於，一旦你權衡之後做出了選擇，你就做完了所有的事情。通常的那些因為 CAP 定理帶來的問題，都可以通過不可改變的數據和從原始數據中計算查詢來規避。
如果你選擇一致性而不是可用性，那麼跟以前並沒有多大的區別，因為你放棄了可用性，所以一些時候你將無法讀取或者寫入數據。當然這只是針對對強一致性有要求的系統。
如果你選擇可用性而不是一致性，在這種情況下，系統可以達到最終一致性而且規避了所有最終一致性帶來的複雜問題。由於系統總是可用的，所以你總可以寫入新數據或者進行查詢。在出錯情況下，查詢可能返回的不是最近寫入的數據，但根據最終一致性，這個數據最終會一致，而查詢函數最終會把這個數據計算進去。
這裡的關鍵在於數據是不可變的。不可變數據意味著這裡沒有更新操作，所以不可能出現數據複製不同這種不一致的情況，也意味著不需要版本化的數據、矢量時鐘或者讀取修復。在一個查詢場景中，一個數據只有存在或者不存在兩種情況。這裡只有數據和在數據之上的函數。這裡沒有需要你為確保最終一致性額外做的事情，最終一致性也不會因此使你的系統變得複雜。
之前的複雜度主要來自增量更新操作和 CAP 定理之間的矛盾，在最終一致性系統中可變的值需要通過讀取修復來保證最終一致性。通過使用不可變數據，去掉增量更新，使用不可變數據，每次從原始數據計算查詢，你可以規避那些複雜的問題。CAP 定理就被打敗了。
當然，現在講的只不過是想法而已，而且每次從原始數據計算查詢基本上不可能。但我們從中可以學到一些在實際解決方案中的關鍵點。
- [li]數據系統因為不可變數據和不斷增長的數據集變得簡單了。[/li][li]基本的寫入操作就是寫入一條新的不可變數據。[/li][li]數據系統通過重新從原始數據計算查詢規避了 CAP 定理帶來的複雜度。[/li][li]數據系統利用增量算法使得查詢的返回延遲降低到一個可以接受的程度。 [/li]
讓我們開始探索這個數據系統應該如何設計。請注意從這裡開始我們所描述都是針對系統優化、數據庫、索引、EFL、批量計算、流處理——這些技術都是對查詢函數的優化，讓查詢返回時間降低到一個可以接受的程度。這很簡單，但也是數據系統所面對的現實。數據庫通常是數據管理的核心，但它們是更大藍圖中的一部分。
批量計算
“如何讓任意一個函數可以在任意一個數據集上快速執行完成”這個問題太過於複雜，所以我們先放寬了一下這個問題依賴條件。首先假設，可以允許數據滯後幾小時。放寬這個條件之後，我們可以得到一個簡單、優雅、通用的數據系統構建解決方案。之後，我們會通過擴展這個解決方案使得它可以不用放寬條件來解決問題。
由於查詢是所有數據的一個函數，讓查詢變快的最簡單的方法就是預先計算好這些查詢。只要這裡有新的數據，你就重新計算這些查詢。這是可能的，因為我們放寬了條件使得我們的數據可以滯後幾個小時。圖 1 展示了這個工作流程。
圖 1 預計算工作流程
為了實現這個，你的系統需要：
- [li]能很容易存儲大的、不斷增長的數據集；[/li][li]能在數據集上可擴展地計算查詢函數。 [/li]
這樣的系統是存在的，即 Hadoop。它是一個成熟的、經歷了無數團隊實戰檢驗過的系統，同時擁有一個巨大的工具生態系統。它雖不完美，但是這裡用來做批量處理的最好的一個工具。
許多人也許會告訴你，Hadoop 只適用於那些“非結構化”的數據，這是完全錯誤的看法。Hadoop 處理“結構化”的數據也很不錯，通過使用像 Thrift 或者 Protocol Buffers 這樣的工具，你可以使用豐富的數據結構存儲你的數據。
Hadoop 由分佈式文件系統 HDFS 和批處理框架 MapReduce 兩部分構成。HDFS 可以通過文件存儲大量數據，MapReduce 可以在這樣數據上進行可擴展計算。這個系統完全符合我們的要求。
我們將數據以文件形式存儲到 HDFS 中去。文件可以包括一個數據記錄序列。新增數據時，我們只需要在包括所有數據的文件夾中新增一個包含這條新記錄的文件即可。像這樣在 HDFS 存儲數據滿足了“能夠很容易存儲大的、不斷增長的數據集”這個要求。
預計算數據集上的查詢也很直觀，MapReduce 是一個足夠複雜的框架，使得幾乎所有的函數都可以按照多個 MapReduce 任務這種方式實現。像 Cascalog、Cascading 和 Pig 這樣的工具使實現這些函數變得十分簡單。
最後，為了可以快速訪問這些預計算查詢結果，你需要對查詢結果進行索引，這裡有許多數據庫可以完成這個工作。ElephantDB 和 Voldemort read-only 可以通過從 Hadoop 中導出 key/value 數據來加快查詢速度。這些數據庫支持批量寫和隨機讀，同時不支持隨機寫。隨機寫使得數據庫變得複雜，所以通過不支持隨機寫，這些數據庫設計得特別簡潔，也就幾千行代碼而已。簡潔使得這些數據庫魯棒性變得非常好。
下面來看批量處理系統整體上是如何配合工作的。假設寫一個網站分析程序來跟蹤頁面訪問量，你需要能夠查詢到任意時間段的頁面訪問量，數據是以小時方式提供的。如圖 2 所示。
圖 2 批處理工程流程示例(timestamp 代表時間戳，count 代表個數)
實現這個很簡單，每一個數據記錄包括一個單一頁面的訪問量。這些數據通過文件形式存儲到 HDFS 中，一個函數通過實現 MapReduce 計算任務，來計算一個 URL 下頁面每小時的訪問量。這個函數產生的是 key/value 對，其中[URL, hour]是 key，value 是頁面的訪問量。這些 key/value 對被導出到 ElephantDB 中去，使得應用程序可以快速得到任意[URL, hour]對對應的值。如果應用程序想要知道某個時間範圍內某個頁面的訪問量，它可以查詢 ElephantDB 中那段時間內的數據，然後把這些數據相加就可以得到這個訪問量數據了。
在數據滯後幾小時這個缺陷下，批量處理可以計算任意數據集上的任意函數。系統中的“任意性”是指這個系統可以處理任何問題。更重要的是，它很簡單，容易理解和完全可擴展，你需要考慮的只是數據和查詢函數，Hadoop 會幫你處理並行的事情。
批處理系統、CAP 定理和容忍人為錯誤
截至目前，我們的系統都很不錯，這個批處理系統是不是可以達到容忍人為錯誤的目標呢？
讓我們從 CAP 定理開始。這個批處理系統總是最終一致的：寫入的數據總可以在幾小時後被查詢到。這個系統是一個很容易掌控的最終一致性系統，使得你可以只用關注你的數據和針對數據的查詢函數。這裡沒有涉及讀取修復、併發和其他一些需要考慮的複雜問題。
接下來看看這個系統對人為錯誤的容忍性。在這個系統中人們可能會犯兩個錯誤：部署了一個有 Bug 的查詢函數或者寫入了錯誤的數據。
如果部署了一個有 Bug 的查詢函數，需要做的所有事情就是修正那個 Bug，重新部署這個查詢函數，然後在主數據集上重新計算它。這之所以能起作用是因為查詢只是一個函數而已。
另外，錯誤的數據有明確的辦法可以恢復：刪除錯誤數據，然後重新計算查詢。由於數據是不可變的，而且數據集只是往後添加新數據，寫入錯誤的數據不會覆蓋或者刪除正確的數據，這與傳統數據庫更新一個數據就丟掉舊的數據形成了鮮明的對比。
注意到 MVCC 和 HBase 類似的行版本管理並不能達到上面人為錯誤容忍級別。MVCC 和 HBase 行版本管理不能永久保存數據，一旦數據庫合併了這些版本，舊的數據就會丟失。只有不可變數據系統能夠保證你在寫入錯誤數據時可以找到一個恢復數據的方法。
實時層
上面的批量處理系統幾乎完全解決了在任意數據集上運行任意函數的實時性需求。任何超過幾個小時的數據已經被計算進入了批處理視圖中，所以剩下來要做的就是處理最近幾個小時的數據。我們知道在最近幾小時數據上進行查詢比在整個數據集上查詢要容易，這是關鍵點。
為了處理最近幾個小時的數據，需要一個實時系統和批處理系統同時運行。這個實時系統在最近幾個小時數據上預計算查詢函數。要計算一個查詢函數，需要查詢批處理視圖和實時視圖，並把它們合併起來以得到最終的數據。
圖 3 計算一個查詢
在實時層，可以使用 Riak 或者 Cassandra 這種讀寫數據庫，而且實時層依賴那些數據庫中對狀態更新的增量算法。
讓 Hadoop 模擬實時計算的工具是 Storm。我寫 Storm 的目的是讓 Hadoop 可以健壯、可擴展地處理大量的實時數據。Storm 在數據流上運行無限的計算，並且對這些數據處理提供了強有力的保障。
讓我們回到剛才那個根據某個 URL 查詢某個頁面在某個時間段內頁面訪問量的例子，通過這個例子我將展示實時層是如何工作的。
批處理系統還是跟之前一樣：一個基於 Hadoop 和 ElephantDB 的批處理工作流，在幾個小時之前的數據上預計算查詢函數。剩下就是讓實時系統去處理最近幾小時數據了。
我們將最近幾小時的數據狀態存入 Cassandra 中，用 Storm 去處理頁面訪問量數據流並並行更新到數據庫中，針對每一個頁面訪問量，在[URL, hour]所代表的 key 下，有一個計數器，這個計數器在 Cassandra 中實現。這就是所有的事情，Storm 讓事情變得非常簡單。
圖 4 批處理/實時架構示例
批處理層+實時層、CAP 定理和人為錯誤容忍性
貌似又回到一開始提出的問題上去了，訪問實時數據需要使用 NoSQL 數據庫和增量算法。這就說明回到了版本化數據、矢量時鐘和讀取修復這些複雜問題中來。但這是有本質區別的。由於實時層只處理最近幾小時的數據，所有實時層的計算都會被最終批處理層重新計算。所以如果犯了什麼錯誤或者實時層出了問題，最終都會被批處理層更正過來，所有複雜的問題都是暫時的。
這並不意味著不需要關心實時層的讀取修復和最終一致性，你仍然需要實時層儘可能的一致。但當犯了一個錯誤時，不會永久性地破壞數據。這便移除了許多你所需要面對的複雜問題。
在批處理層僅需要考慮數據和數據上的查詢函數，批處理層因此很好掌控。在實時層，需要使用增量算法和複雜的 NoSQL 數據庫。把所有的複雜問題獨立到實時層中，對系統的魯棒性、可靠性做出了重大貢獻。
同樣的，實時層並沒有影響系統的人為錯誤容忍性，這個數據不可變和只追加的批處理系統，仍然是整個系統的核心，所以所有的都可以像上面說的一樣被糾正過來。
我有一個類似的系統：Hadoop 和 ElephantDB 組成批處理系統，Storm 和 Cassandra 組成實時系統。由於缺乏監控，某天當我起床的時候發現 Cassandra 運行滿負荷了，使得所有的數據請求都超時。這使得 Storm 計算失敗，一些數據又重新回到了等待隊列中，這個數據就一次次重複請求。
如果我沒有批處理層，那麼我就需要擴展和恢復 Cassandra，這個很不容易。更糟的是，因為請求不斷的重複，無法得到正確的數據。
幸運的是，所有的複雜問題都被隔離到實時層中去了，我清空了所有的後臺請求隊列，把它們打到了批處理層上，同時重啟了 Cassandra 集群，過了幾個小時之後所有數據都恢復正常了。沒有錯誤數據，請求中也沒有不準確的地方。
垃圾回收
上面描述的所有東西都是建立在一個不可變的、不斷增長的數據集上的。如果數據集已經很大，使得不可能用水平擴展儲存所有時間的所有數據，該如何處理呢？這是不是就推翻了我說的一切呢？是不是需要回到可變數據的系統上呢？
不。我們可以很容易地用“垃圾回收”對基本模型進行擴展來解決上面的問題。垃圾回收是一個在主數據集上的簡單函數，返回的是一個過濾版本的主數據集。垃圾回收掉了舊數據，可以選擇任意的垃圾回收策略。可以在易變的系統中只保留數據最新的一個值或者保留每個數據的歷史。比如，如果要處理位置數據，可以保留每人每年的一個地點。可變性是一個不是很靈活的垃圾回收形式（它跟 CAP 定理交互得也很糟糕）。
垃圾回收可以被實現成批處理的一個任務，隔段時間運行一下。由於它是作為離線批處理任務執行的，所以不影響我們與 CAP 定理的交互。
總結
讓可擴展的數據系統複雜的原因不是 CAP 系統，而是數據增量算法和數據的可變狀態。最近由於分佈式數據庫的興起導致了複雜度越來越不可控。前面講過，我將挑戰對傳統數據系統構建方法的假設。我把 CRUD 變成了 CR，把持久化層分成了批處理和實時兩個層，並且得到對人為錯誤容忍的能力。我花費了多年來之不易的經驗打破我對傳統數據庫的假設，並得到了這些結論。
批處理/實時架構有許多有趣的能力我並沒有提到，下面我總結了一些。
算法的靈活性。隨著數據量的增長，一些算法會越來越難計算。比如計算標識符的數量，當標識符集合越來越大時，將會越來越難計算。批處理/實時分離系統給了你在批處理系統上使用精確算法和在實時系統上使用近似算法的靈活性。批處理系統計算結果會最終覆蓋實時系統的計算結果，所以最終近似值會被修正，而你的系統擁有了“最終精確性”。
數據結構遷移變得很容易。數據結構遷移的難題將一去不復返。由於批量計算是系統的核心，很容易在整個系統上運行一個函數，所以很容易更改你數據的結構或者視圖。
簡單的 Ad-Hoc 網絡。由於批處理系統的任意性，使得你可以在數據上進行任意查詢。由於所有的數據在一個點上都可以獲取，所以 Ad-Hoc 網絡變得簡單而且方便。
自我檢查。由於數據是不可變的，數據集就可以自我檢查。數據集記錄了它的數據歷史，對於人為錯誤容忍性和數據分析很有用。
我並沒有說我已經“解決”了數據量過大的問題，但我已經為解決大數據問題制訂了一個框架。批處理/實時架構可以應用到任何一個數據系統中去，“授人以魚，不如授人以漁”，我已經告訴你瞭如何去構建這樣的系統。
為了提高系統整體能力來解決大數據的問題，我們還有許多工作需要做。
- [li]擴展數據模型，支持批量寫和隨機讀。不是每一個應用程序都支持 key/value 的數據庫，這也是我們團隊對擴展 ElephantDB，使得可以支持搜索、文檔數據庫、區間查詢感興趣的原因。[/li][li]更好的批處理原語。Hadoop 並不是批處理的最終形態，好多批處理計算 Hadoop 效率不高。Spark 是一個有意思的擴展 MapReduce 的項目。[/li][li]提升後的讀寫 NoSQL 數據庫。這裡不同類型數據的數據庫還有很大的提升空間，隨著這些數據庫的成熟，它們將收穫很多。[/li][li]高層級的抽象。未來工作中最有意思的就是對批處理模塊和實時處理模塊的高層次抽象，在批處理和實時架構下你沒有理由不擁有一個簡單的、描述性的、魯棒性好的語言。 [/li]
許多人需要一個可擴展的關係型數據庫，本文就是想讓你知道完全不需要那個。大數據量和 NoSQL 運動使數據管理比 RDBMS 更加複雜。那僅僅是因為我對大數據的處理採用了跟 RDBMS 同樣的方法：把數據和視圖混為一談，並且依賴增量算法。大數據量需要採用完全不同的方式構建數據系統。通過存儲持續增長的不可變數據，並且系統核心採用預計算，大數據系統就可以變得比關係型數據庫更易掌控，並且可擴展性很強。
（感謝 Nathan Marz 先生的授權，原文名為 How to beat the CAP theorem。同時感謝方建對本文翻譯做出的貢獻。）
閱讀更多 遊聚網 的文章
