“打敗”CAP定理

標簽：網站建設 網站制作 成都網站制作  CAP定理

       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定理就被打敗了。

當然，現在講的只不過是想法而已，而且每次從原始數據計算查詢基本上不可能。但我們從中可以學到一些在實際解決方案中的關鍵點。

數據系統因為不可變數據和不斷增長的數據集變得簡單了。 基本的寫入操作就是寫入一條新的不可變數據。 數據系統通過重新從原始數據計算查詢規避了CAP定理帶來的復雜度。 數據系統利用增量算法使得查詢的返回延遲降低到一個可以接受的程度。

讓我們開始探索這個數據系統應該如何設計。請注意從這里開始我們所描述都是針對系統優化、數據庫、索引、EFL、批量計算、流處理——這些技術都是對查詢函數的優化，讓查詢返回時間降低到一個可以接受的程度。這很簡單，但也是數據系統所面對的現實。數據庫通常是數據管理的核心，但它們是更大藍圖中的一部分。

批量計算

“如何讓任意一個函數可以在任意一個數據集上快速執行完成”這個問題太過于復雜，所以我們先放寬了一下這個問題依賴條件。首先假設，可以允許數據滯后幾小時。放寬這個條件之后，我們可以得到一個簡單、優雅、通用的數據系統構建解決方案。之后，我們會通過擴展這個解決方案使得它可以不用放寬條件來解決問題。

由于查詢是所有數據的一個函數，讓查詢變快的最簡單的方法就是預先計算好這些查詢。只要這里有新的數據，你就重新計算這些查詢。這是可能的，因為我們放寬了條件使得我們的數據可以滯后幾個小時。圖1展示了這個工作流程。

文章標題：“打敗”CAP定理
當前URL：http://m.newbst.com/news33/184733.html

成都網站建設公司_創新互聯，為您提供外貿網站建設、面包屑導航、網站內鏈、電子商務、響應式網站、手機網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯