CAP 理論 FAQ
0. 關于這個檔案
沒有其它比CAP理論更引人注意的話題了, 這個FAQ的目的, 是說明對于CAP, 當前哪些是已知的, 并幫助那些剛接觸這個理論的人快速了解, 并解決一些錯誤的觀念和常見的誤解.
當然, 很可能我的認知是膚淺甚至完全錯誤的, 歡迎任何評論和糾正.
1. CAP理論的來源是什么?
Eric Brewer 博士在2000年的 Principles of Distributed Computing 會議上作了一個報告, 標題是"Towards Robust Distributed Systems", 在這個報告中, 他提出了CAP 理論 - 那時候這個理論還未被證明 - 描述了在分布式系統中一致性和可用性之間的矛盾.
兩年后, 在MIT研究分布式系統的 Seth Gilbert 和 Nancy Lynch 教授在他們的論文“Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services”中證明了CAP理論.
2. CAP理論到底說了什么?
CAP定理(以下簡稱 CAP)指出, 在異步網路中實作的讀寫存盤, 不可能同時滿足以下三個特性:
- 可用性 - 是否對于資料存盤的每個請求都會成功執行?
- 一致性 - 對于資料的讀寫執行, 是否從每個分布式節點所觀察到的都是一致的, 或者是可線性化一致的?
- 隔離容忍性 - 分布式系統之間的通信是否允許丟失任意訊息?
更通俗地說, CAP定理告訴我們, 無法建立一個既能回應每個請求又能每次都回傳預期結果的分布式存盤系統. 這是一個不可能的結果, 它告訴我們, 我們在努力嘗試的目標實際上是不可實作的. 這很重要, 因為過去幾年已經建立和正在建立的許多分布式系統都會受到這個理論的影響. 但它并不意味著我們不能在這些限制下建立有用的系統. 細節是魔鬼, 在你開始"是的, 但是..."之前, 確定自己已經明白什么是CAP理論允許和不允許的.
3. 什么是 ‘讀寫存盤’?
CAP理論特別關注的一種結構, 叫 register, 即嵌入式領域中的暫存器. 暫存器是一種具有兩種操作的資料結構:
- set(X) 將暫存器的值設為 X
- get() 回傳暫存器中最新的值
一個KV存盤可以看成是一組暫存器的集合. 即使暫存器看起來非常簡單, 但它體現了分布式系統做的事情本質 - 寫入資料和讀取資料.
4. 原子一致性(Atomic Consistency), 線性一致性(Linearizable Consistency)是什么含義?
原子一致性(Atomic Consistency), 或者說線性一致性(Linearizable Consistency), 是關于客戶端在執行讀寫操作時回傳值的可見度問題, 體現在暫存器上, 就是在被所有的分布式節點訪問時, 回應和請求是基于同一個時鐘順序的(注: 這是強一致性, 理想狀態的一致性).
例如一個執行由多個客戶端的操作組成, 這些操作可能是并發的, 在原子一致性的要求下, 這個執行的結果必須等同于所有操作單次串行(按順序，一個接一個)執行的結果. 這是一個很強的約束, 與其它的約束是沖突的, 除了其他約束之外, 它還排除了最終一致性(EC, 允許在寫入變得可見之前有延遲). 所以在EC下, 可能會出現:
set(10),
set(5),
get() = 10 // 但是讀取到的是10
在原子一致性下, 上面的流程是不可能出現的.
原子一致性會確保暫存器的外部訪問順序, 也就是說, 如果A讀取了X, 并且A能與B通信, B去讀也能讀取到一致的結果. 在稍微弱一些的約束下(例如順序一致性)這個結果可能不一定成立. 下面我們做如下的操作:
B:set(5), A:set(10), A:get() = 10, B:get() = 10
這體現了操作的原子一致性, 但是下面這種情況就不是
B:set(5), A:set(10), A:get() = 10, B:get() = 5
雖然這和下面的序列化操作是一樣的
B:set(5), B:get() = 5, A:set(10), A:get() = 10
在第二個例子中, 如果A在讀取暫存器后告訴B關于暫存器的值(10), B會錯誤地認為有另外的操作在 A:get() 和 B:get() 之間把暫存器值改成了5. 如果不允許節點間通信, B 并不知道 A:set, 并且要保持讀寫的一致, 就像 B:get() 發生在 A:set 之前一樣.
Wikipedia 有更多的說明. Maurice Herlihy 1990年的論文原文在這里.
5. 什么是異步(asynchronous)?
異步網路, 就是對節點處理訊息或網路送達訊息的時間沒有限制的網路, 這個定義帶來的影響, 就是無法判斷一個節點到底是宕機了, 還是它的訊息被延遲了.
6. 什么是可用(available)?
一個資料存盤的可用, 體現在所有的get和set請求最終都會回傳回應. 這個回應不是指回傳錯誤, 因為如果用這個判斷的話, 很明顯一個系統可以只靠回傳錯誤而保證可用性. 因為可用性對于回應的時效性并沒有約束, 所以系統可以花任意長的時間來處理一個請求, 但是必須最侄訓傳回應.
要注意到, 這是同時是一個強約束, 也是一個弱約束. 強約束是指所有的請求都必須正確處理并回傳, 弱約束是指處理時間的長度沒有限制.
7. 什么是磁區隔離(partition)?
磁區隔離, 是指分布式系統中一個或多個節點間的通信出現故障, 導致訊息丟失(不是延遲, 如果訊息最終到達了, 就不屬于這種情況).
這個詞有時用于描述一個時間區間, 這個時間區間內兩組節點之間的訊息傳遞都失敗了. 這是一種更嚴格的失敗模型, 可以稱這種隔離為完全隔離.
CAP的證明依賴于完全隔離, 在實際應用中, 如果所有的訊息都通過一個組件, 如果這個組件失效, 那么這兩個節點的所有訊息發送都會失敗.
8. 為什么 CAP 理論是正確的?
CAP理論的基本思想是, 如果存在磁區隔離的情況, 一個客戶端向一側磁區寫入資料, 那么對另一磁區的任何讀取都不可能讀取到這些寫入. 這時候就會面臨著一個選擇: 是用可能過時的資料來回應讀取, 還是等待(可能永遠等待)來自另一側磁區的訊息而影響可用性? 基于這個構造的場景, 我們描述了一個分布式系統無法同時保持一致性和可用性的情況. CAP理論受到這么多關注的一個原因, 是這個場景是很可能出現的, 當網路設備出現故障時就會發生磁區間的完全隔離.
9. 什么時候系統不得不放棄 C 或者 A?
CAP理論僅僅說明在某些情況下一個分布式系統必須放棄A或者C. 這屬于比較極端的情況, 而理論并沒有說明發生這種極端情況的可能性有多大. C 和 A 都是強約束: 只有操作100%滿足時才成立. 只要有一個非一致的讀取或失敗的寫入, 都會使 C 或 A 的保證無效. 但是在極端情況之外是很容易滿足 C 和 A 同時成立的.
由于大多數分布式系統都會長時間運行, 在整個生命周期中處理數百萬千萬的請求, 這期間大概率會遇上某個極端情況, 了解CAP理論, 就可以提前了解在哪個方面會出問題, 并進行準備.
10. 為什么當我說我的系統是CA時, 一些人會不滿意?
Brewer的觀點, Gilbert的論文, 以及很多其他人的觀點, 通常把C, A和P作為等同的特性, 并在其中可以任意選擇兩個. 然而這是一種誤導性的表述, 因為"磁區隔離的容忍性"是無法避免的: 分布式系統幾乎不可避免地會遇到節點間通信障礙. 所以CAP更適合理解為: 構建一個可能出現磁區隔離的系統時, 如何做出權衡. 實際上，這就是分布式系統: 沒有100%可靠的網路, 所以(至少在分布式環境中)現實中并不存在CA系統.
所以, 將定理改一下可能更有指導意義: 一個分布式系統出現通信故障時，不可能同時兼顧A和C.
有些系統不會出現磁區隔離，例如單節點的資料庫服務器, 然而這些系統通常與CAP適用的環境不相關. 如果您將一個分布式資料庫描述為"CA"系統, 那么您對分布式系統和CAP理論還存在誤解.
11. 如果訊息不會丟失呢?
Gilbert的論文中, 一個可能令人驚訝的結論是: 在一個異步網路中, 讓一個暫存器保持永遠可用是無法實作的, 并且只有當訊息不會丟失時才能保持一致性.
這個結論基于異步網路的屬性, 其思想是無法判斷一個訊息是否已經丟失, 所以一個節點無法一邊等待一邊維持可用性, 這種情況下只要回應了, 結果一致性就被破壞了.
12. 我的網路真的是異步的嗎?
可以說, 是的. 不同的網路有不同的特征.
如果
- 您的節點沒有時鐘(不太可能), 或者它們的時鐘可能會偏離(更有可能)
- 系統行程可能會任意延遲訊息的傳遞(由于重試或GC暫停)
那么您的網路就可以被認為是異步的.
Gilbert和Lynch還證明, 在部分同步系統中, 節點共享但時鐘不是同步的, 并且每個訊息的處理時間都有限制, 因此不可能實作可用的原子性存盤.
然而，來自#8的結果在部分同步模型中不成立, 實作始終可用的原子性存盤是可能的, 并且當所有訊息都不會丟失時可以保證一致性.
原文
Gilbert and Lynch also proved that in a partially-synchronous system, where nodes have shared but not synchronised clocks and there is a bound on the processing time of every message, that it is still impossible to implement available atomic storage.
However, the result from #8 does not hold in the partially-synchronous model; it is possible to implement atomic storage that is available all the time, and consistent when all messages are delivered.
13. FLP 和 CAP 之間有什么聯系?
FLP理論(Fischer, Lynch 和 Patterson)是三十年前提出的一個非常有名的"不可能性(Impossibility)"理論, 這個理論確立了共識(一致性, 讓所有的節點達成一致)問題: 如果有一個異步網路, 這個網路的節點可能會失效, 那么這種一致性是無法實作的.
FLP理論與CAP理論沒有直接關系, 盡管它們在某些方面是相似的: 兩者都是對于分布式系統中無法解決的問題的"不可能性"結論. 細節是魔鬼, 下面是FLP與CAP的一些不同之處:
- FLP允許一個節點失敗, 這個節點與系統完全隔離, 并且不必回應請求
- 否則, FLP不允許訊息丟失, 網路只是異步但是沒有訊息丟失
- FLP 用于處理共識問題, 這是一個類似的, 但不同于原子性存盤的問題
14. C 和 A 是可以調節的嗎?
在設計分布式系統時, 可以對一致性或可用性降低標準而實作一個"可用"的系統. 實際上CAP理論的意義在于, 這是不可避免的，任何設計和構建的系統都必須對其中的一項或兩項作出妥協. 作為設計者, 則需要弄清楚什么時候并且如何做.
關心一致性的系統會選擇降低可用性, 比如ZooKeeper. 其他系統, 例如Amazon的Dynamo, 為了保持高度的可用性, 則選擇降低一致性.
如果不能滿足CAP理論中的理想狀態假設, 就必須重新證明這個不可能性結論.
原文
Once you weaken any of the assumptions made in the statement or proof of CAP, you have to start again when it comes to proving an impossibility result.
15. 一個故障節點是否等效于一個被隔離的節點?
不等效. 一個故障節點通常不需要再回應請求. CAP理論并不允許節點"故障"(這是一個強假設, 因為實際上節點不發生故障是不可能的).
在一個異步網路中當N-1個節點發生故障時, 可以證明原子性存盤的不可能性結論. 這個結論會對設計上的權衡造成影響: 是保證寫入的節點數量(性能問題), 還是容錯能力(可靠性問題)
16. 一個運行很慢的節點是否等效于一個被隔離的節點?
不一樣: 訊息最侄訓被傳遞到一臺很慢的節點, 但永遠不會被傳遞到一臺被隔離的節點. 實際上, 很難區分訊息丟失(節點故障)和節點很慢的情況, 這也是CAP, FLP和其它分布式理論為什么成立的原因.
17. 我是否能繞過或者戰勝 CAP 理論?
不能, 您可能設計了一個還未受到明顯影響的系統, 這很好.
來源
https://www.the-paper-trail.org/page/cap-faq/, 作者 Henry Robinson
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/431034.html
標籤：架構設計