“打敗”CAP定理

“打敗”CAP定理

標(biāo)簽：網(wǎng)站建設(shè) 網(wǎng)站制作 成都網(wǎng)站制作  CAP定理

       CAP定理是數(shù)據(jù)系統(tǒng)設(shè)計(jì)的基本理論，目前幾乎所有的數(shù)據(jù)系統(tǒng)的設(shè)計(jì)都遵循了這個定理。但CAP定理給目前的數(shù)據(jù)系統(tǒng)帶來了許多復(fù)雜的、不可控的問題，使得數(shù)據(jù)系統(tǒng)的設(shè)計(jì)越來越復(fù)雜。Twitter首席工程師、Storm的作者Nathan Marz在本文中通過避開CAP定理帶來的諸多復(fù)雜問題，展示了一個不同于以往的數(shù)據(jù)系統(tǒng)設(shè)計(jì)方案，給我們的數(shù)據(jù)系統(tǒng)設(shè)計(jì)帶來了全新的思路。

CAP定理指出，一個數(shù)據(jù)庫不可能同時滿足一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（Partition-Tolerance）。

一致性（Consistency）是指執(zhí)行了一次成功的寫操作之后，未來的讀操作一定可以讀到這個寫入的值。可用性（Availability）是指系統(tǒng)總是可讀可寫的。Yammer的Coda Hale和Cloudera的Henry Robinson都闡述過，分區(qū)容錯性是不能犧牲的，因此只能在一致性和可用性上做取舍，如何處理這種取舍正是目前NoSQL數(shù)據(jù)庫的核心焦點(diǎn)。

選擇一致性而不是可用性的系統(tǒng)將面臨一些尷尬的問題，當(dāng)系統(tǒng)不可用時怎么辦？你可以對寫操作進(jìn)行緩沖處理，但如果存儲緩沖數(shù)據(jù)的機(jī)器出現(xiàn)故障，客戶端將丟失寫入的值。同樣地，緩沖寫也可以被認(rèn)為是一種非一致性的操作，因?yàn)榭蛻舳苏J(rèn)為成功的寫入實(shí)際上并沒有寫入到實(shí)際的數(shù)據(jù)庫中。當(dāng)然，系統(tǒng)可以在機(jī)器不可用時向客戶端返回錯誤，但可以想象，一個經(jīng)常告訴客戶端“請重試”的產(chǎn)品是多么令人討厭。

另一個方案是選擇可用性放棄一致性。這種情況下最好的一致性保障是“最終一致性”（Eventually Consistency）。當(dāng)使用最終一致性的系統(tǒng)時，客戶端有時會讀到與剛剛寫入數(shù)據(jù)不同的數(shù)據(jù)。有時候，同一時間同一個key的多個請求有可能返回不同的結(jié)果。數(shù)據(jù)更新并不能及時在所有的復(fù)制節(jié)點(diǎn)上生效，所以不同的復(fù)制節(jié)點(diǎn)上可能讀取到的是不同的值。當(dāng)你檢測到數(shù)據(jù)不一致性時，你需要進(jìn)行修復(fù)（Repair）操作，這就需要使用矢量時鐘（vector clock）記錄數(shù)據(jù)的版本歷史并合并不同的數(shù)據(jù)更新（這稱為讀取修復(fù)，read repair）。

我相信在應(yīng)用層維護(hù)最終一致性對開發(fā)人員負(fù)擔(dān)太重，開發(fā)人員極易弄錯讀取修復(fù)的代碼，而一旦開發(fā)人員犯錯，有問題的讀取修復(fù)將對數(shù)據(jù)庫系統(tǒng)造成不可逆的損壞。

所以犧牲可用性時問題會很多，犧牲一致性時構(gòu)建和維護(hù)系統(tǒng)的復(fù)雜度又很高，但這里又只有兩個選擇，不管怎樣做都會不好。CAP定理是改不了的，那么還有什么其他可能的選擇嗎？

實(shí)際上，還有一個辦法：你并不能避開CAP定理，但可以把復(fù)雜的問題獨(dú)立出來，免得你喪失對整個系統(tǒng)的掌控能力。CAP定理帶來的復(fù)雜性，其實(shí)是我們?nèi)绾螛?gòu)建數(shù)據(jù)系統(tǒng)這一根本問題的體現(xiàn)。其中有兩點(diǎn)特別重要：數(shù)據(jù)庫中可變狀態(tài)和更新狀態(tài)的增量算法。復(fù)雜性正是這兩點(diǎn)和CAP定理之間的相互作用導(dǎo)致的。

本文將通過一個數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)，來說明如何解決CAP定理通常會造成的復(fù)雜性問題。但我要做的不僅僅如此，CAP定理是一個針對機(jī)器發(fā)生錯誤時系統(tǒng)容錯性的一個定理，而這里有比機(jī)器容錯性更加重要的容錯性——人為操作容錯性。在軟件開發(fā)中一個確定的事實(shí)是，開發(fā)人員都并非完人，產(chǎn)品中難免有一些Bug，我們的系統(tǒng)必須對有Bug的程序?qū)懭氲腻e誤數(shù)據(jù)有足夠的適應(yīng)能力，我要展示的系統(tǒng)將是這樣一個可以容忍人為錯誤的系統(tǒng)。

本文將挑戰(zhàn)你對數(shù)據(jù)系統(tǒng)如何構(gòu)建這一問題的假設(shè)，通過顛覆傳統(tǒng)數(shù)據(jù)系統(tǒng)構(gòu)建方法，我會讓大家看到一個前所未見的優(yōu)雅、擴(kuò)展性強(qiáng)、健壯的數(shù)據(jù)系統(tǒng)。

什么是數(shù)據(jù)系統(tǒng)？

在開始介紹系統(tǒng)設(shè)計(jì)之前，讓我們先來看看我們要解決的問題：數(shù)據(jù)系統(tǒng)的目的在于什么？ 什么是數(shù)據(jù)？ 在我們考慮CAP定理之前，我們必須給出一個可以適用于所有數(shù)據(jù)應(yīng)用程序的定義來回答上述問題。

數(shù)據(jù)應(yīng)用程序種類很多，包括存入和提取數(shù)據(jù)對象、連接、聚合、流處理、機(jī)器學(xué)習(xí)等。似乎并不存在一個對數(shù)據(jù)系統(tǒng)的明確定義，數(shù)據(jù)處理的多樣性使得我們很難用一個定義來描述。

事實(shí)卻并非如此，下面這個簡單的定義：

Query = Function(All Data)

概括了數(shù)據(jù)庫和數(shù)據(jù)系統(tǒng)的所有領(lǐng)域。每一個領(lǐng)域——有50年歷史的RDBMS、索引、OLAP、OLTP、MapReduce、EFL、分布式文件系統(tǒng)、流處理器、NoSQL等——都可以被概括進(jìn)這個方程。

所謂數(shù)據(jù)系統(tǒng)就是要回答數(shù)據(jù)集問題的系統(tǒng)，這些問題我們稱之為“查詢”。上面的方程表明，查詢就是數(shù)據(jù)上的一個函數(shù)。

上述方程對于實(shí)際使用來說太過于籠統(tǒng)，幾乎對復(fù)雜的數(shù)據(jù)系統(tǒng)設(shè)計(jì)不起什么作用。但如果所有的數(shù)據(jù)系統(tǒng)都遵循這個方程又會怎樣呢？這個方程是探索我們數(shù)據(jù)系統(tǒng)的第一步，而它最終將引導(dǎo)我們找到“打敗”CAP定理的方法。

這個方程里面有兩個關(guān)鍵概念：數(shù)據(jù)、查詢。這兩個完全不同的概念經(jīng)常被混為一談，所以下面來看看這兩個概念究竟是什么意思。

數(shù)據(jù)

我們先從“數(shù)據(jù)”開始。所謂數(shù)據(jù)就是一個不可分割的單位，它肯定存在，就跟數(shù)學(xué)里面的公理一樣。

關(guān)于“數(shù)據(jù)”有兩個關(guān)鍵的性質(zhì)。首先，數(shù)據(jù)是跟時間相關(guān)的，一個真實(shí)的數(shù)據(jù)一定是在某個時間點(diǎn)存在于那兒。比如，假如Sally在她的社交網(wǎng)絡(luò)個人資料中寫她住在芝加哥，你拿到的這個數(shù)據(jù)肯定是她某個時間在芝加哥填寫的。假如某天Sally把她資料里面居住地點(diǎn)更新為亞特蘭大，那么她肯定在這個時候是住在亞特蘭大的，但她住在亞特蘭大的事實(shí)無法改變她曾經(jīng)住在芝加哥這個事實(shí)——這兩個數(shù)據(jù)都是真實(shí)的。

其次，數(shù)據(jù)無法改變。由于數(shù)據(jù)跟某個時間點(diǎn)相關(guān)，所以數(shù)據(jù)的真實(shí)性是無法改變的。沒有人可以回到那個時間去改變數(shù)據(jù)的真實(shí)性，這說明了對數(shù)據(jù)操作只有兩種：讀取已存在的數(shù)據(jù)和添加更多的新數(shù)據(jù)。那么CRUD就變成了CR【譯者注：CRUD是指Create Read Update Delete，即數(shù)據(jù)的創(chuàng)建、讀取、更新和刪除】。

我去掉了“更新”操作，因?yàn)楦聦τ诓豢筛淖兊臄?shù)據(jù)沒有任何作用。例如，更新Sally的位置信息本質(zhì)上就是在她住的地方數(shù)據(jù)中新加一條最近的位置信息而已。

我同樣去掉了“刪除”操作，因?yàn)榻^大部分刪除操作可以更好地表述為新加一條數(shù)據(jù)。比如Bob在Twitter上不再關(guān)注Mary了，這并不能改變他曾經(jīng)關(guān)注過Mary這個事實(shí)。所以與其刪除Bob關(guān)注Mary這個數(shù)據(jù)，還不如新加一條Bob在某個時間點(diǎn)不再關(guān)注Mary這個數(shù)據(jù)。

這里只有很少數(shù)的情況需要永久“刪除”數(shù)據(jù)，例如規(guī)則要求你每隔一段時間清掉數(shù)據(jù)，這個情況在我將要展示的系統(tǒng)中有很好的解決方案，所以為了簡潔，我們暫不考慮這些情況。

查詢

查詢是一個針對數(shù)據(jù)集的推導(dǎo)，就像是一個數(shù)學(xué)里面的定理。例如，你可以通過計(jì)算“Sally現(xiàn)在的位置在哪里”這個查詢來得到Sally最新的位置數(shù)據(jù)。查詢是整個數(shù)據(jù)集合上的函數(shù)，可以做一切事情：聚合、連接不同類型的數(shù)據(jù)等。因此，你可以查詢系統(tǒng)中女性用戶的數(shù)量，可以查詢最近幾小時熱門的 Twitter內(nèi)容。

前面我已經(jīng)定義查詢是整個數(shù)據(jù)集上的函數(shù)，當(dāng)然，不是所有的查詢都需要整個數(shù)據(jù)集，它們只需要數(shù)據(jù)集的一個子集。但我的定義是涵蓋了所有的查詢類型，如果想要“打敗”CAP定理，我們需要能夠處理所有的查詢。

打敗CAP定理

計(jì)算查詢最簡單的辦法就是按照查詢語義在整個數(shù)據(jù)集上運(yùn)行一個函數(shù)。如果這可以滿足你對延遲的要求，那么就沒有其他需要構(gòu)建的了。

可想而知，我們不能指望在整個數(shù)據(jù)集上的查詢能夠很快完成，特別是那些服務(wù)大型網(wǎng)站、需要每秒處理幾百萬次請求的系統(tǒng)。但假如這種查詢可以很快完成，讓我們來看看像這樣的系統(tǒng)和CAP定理的PK結(jié)果：你將會看到，這個系統(tǒng)不僅打敗了CAP定理，而且還消滅了它。

CAP定理仍然適用，所以你需要在可用性和一致性上做出選擇，這里的漂亮之處在于，一旦你權(quán)衡之后做出了選擇，你就做完了所有的事情。通常的那些因?yàn)镃AP定理帶來的問題，都可以通過不可改變的數(shù)據(jù)和從原始數(shù)據(jù)中計(jì)算查詢來規(guī)避。

如果你選擇一致性而不是可用性，那么跟以前并沒有多大的區(qū)別，因?yàn)槟惴艞壛丝捎眯裕砸恍r候你將無法讀取或者寫入數(shù)據(jù)。當(dāng)然這只是針對對強(qiáng)一致性有要求的系統(tǒng)。

如果你選擇可用性而不是一致性，在這種情況下，系統(tǒng)可以達(dá)到最終一致性而且規(guī)避了所有最終一致性帶來的復(fù)雜問題。由于系統(tǒng)總是可用的，所以你總可以寫入新數(shù)據(jù)或者進(jìn)行查詢。在出錯情況下，查詢可能返回的不是最近寫入的數(shù)據(jù)，但根據(jù)最終一致性，這個數(shù)據(jù)最終會一致，而查詢函數(shù)最終會把這個數(shù)據(jù)計(jì)算進(jìn)去。

這里的關(guān)鍵在于數(shù)據(jù)是不可變的。不可變數(shù)據(jù)意味著這里沒有更新操作，所以不可能出現(xiàn)數(shù)據(jù)復(fù)制不同這種不一致的情況，也意味著不需要版本化的數(shù)據(jù)、矢量時鐘或者讀取修復(fù)。在一個查詢場景中，一個數(shù)據(jù)只有存在或者不存在兩種情況。這里只有數(shù)據(jù)和在數(shù)據(jù)之上的函數(shù)。這里沒有需要你為確保最終一致性額外做的事情，最終一致性也不會因此使你的系統(tǒng)變得復(fù)雜。

之前的復(fù)雜度主要來自增量更新操作和CAP定理之間的矛盾，在最終一致性系統(tǒng)中可變的值需要通過讀取修復(fù)來保證最終一致性。通過使用不可變數(shù)據(jù)，去掉增量更新，使用不可變數(shù)據(jù)，每次從原始數(shù)據(jù)計(jì)算查詢，你可以規(guī)避那些復(fù)雜的問題。CAP定理就被打敗了。

當(dāng)然，現(xiàn)在講的只不過是想法而已，而且每次從原始數(shù)據(jù)計(jì)算查詢基本上不可能。但我們從中可以學(xué)到一些在實(shí)際解決方案中的關(guān)鍵點(diǎn)。

數(shù)據(jù)系統(tǒng)因?yàn)椴豢勺償?shù)據(jù)和不斷增長的數(shù)據(jù)集變得簡單了。 基本的寫入操作就是寫入一條新的不可變數(shù)據(jù)。 數(shù)據(jù)系統(tǒng)通過重新從原始數(shù)據(jù)計(jì)算查詢規(guī)避了CAP定理帶來的復(fù)雜度。 數(shù)據(jù)系統(tǒng)利用增量算法使得查詢的返回延遲降低到一個可以接受的程度。

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

批量計(jì)算

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

由于查詢是所有數(shù)據(jù)的一個函數(shù)，讓查詢變快的最簡單的方法就是預(yù)先計(jì)算好這些查詢。只要這里有新的數(shù)據(jù)，你就重新計(jì)算這些查詢。這是可能的，因?yàn)槲覀兎艑捔藯l件使得我們的數(shù)據(jù)可以滯后幾個小時。圖1展示了這個工作流程。

文章標(biāo)題：“打敗”CAP定理
當(dāng)前URL：http://www.muchs.cn/news33/184733.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、面包屑導(dǎo)航、網(wǎng)站內(nèi)鏈、電子商務(wù)、響應(yīng)式網(wǎng)站、手機(jī)網(wǎng)站建設(shè)

廣告

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