“打敗”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ì)都遵循了這個(gè)定理。但CAP定理給目前的數(shù)據(jù)系統(tǒng)帶來(lái)了許多復(fù)雜的、不可控的問(wèn)題，使得數(shù)據(jù)系統(tǒng)的設(shè)計(jì)越來(lái)越復(fù)雜。Twitter首席工程師、Storm的作者Nathan Marz在本文中通過(guò)避開CAP定理帶來(lái)的諸多復(fù)雜問(wèn)題，展示了一個(gè)不同于以往的數(shù)據(jù)系統(tǒng)設(shè)計(jì)方案，給我們的數(shù)據(jù)系統(tǒng)設(shè)計(jì)帶來(lái)了全新的思路。

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

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

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

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

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

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

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

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

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

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

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

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

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

Query = Function(All Data)

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

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

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

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

數(shù)據(jù)

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

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

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

我去掉了“更新”操作，因?yàn)楦聦?duì)于不可改變的數(shù)據(jù)沒(méi)有任何作用。例如，更新Sally的位置信息本質(zhì)上就是在她住的地方數(shù)據(jù)中新加一條最近的位置信息而已。

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

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

查詢

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

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

打敗CAP定理

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

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

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

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

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

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

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

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

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

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

批量計(jì)算

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

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

本文題目：“打敗”CAP定理
網(wǎng)址分享：http://bm7419.com/news/184733.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、網(wǎng)站營(yíng)銷、ChatGPT、標(biāo)簽優(yōu)化、小程序開發(fā)、服務(wù)器托管

廣告

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