Like Share Discussion Bookmark Smile

J.J. Huang   2020-02-24   Tech.   瀏覽次數:

技術觀念 | CAP Theorem(CAP定理)

在進入CAP定理的主旨之前,我們首先要了解資訊系統的兩大類型標準設計準則,第一種準則稱為「ACID」,追求資訊的「一致性(Consistency)」,第二種準則「BASE」則是以系統的「可用性(Availability) 」為最高指導原則。

以一個簡單的商品訂購網站+資料庫的例子可以很容易了解兩者的區別,在ACID的例子中,最重要的內部邏輯是要首先確保不同消費者看到的庫存品與真實資料庫裡的商品數量是相同的,所以不會出現明明剩下1件商品卻同時有2個消費者下單成功的事情發生;
BASE的設計想法則是以瀏覽體驗為主軸,優先確保網頁能夠正確運作,至於是不是每個消費者畫面上看到的東西都一樣,或是畫面上的庫存數量是不是一定和資料庫中的數字一樣,則是次要考量。

你可能已經隱約感覺到了, 對同一個資訊系統而言,Consistency 與 Availability 兩者是有所衝突的。

  • ACID

    • A-tomicity:一個Transaction裡的所有動作要不全部成功或者失敗。

    • C-onsistency:一個Transaction只能將資料庫從一個合法的狀態轉移到另一個合法的狀態,也就是Transaction結束後,所有的資料仍然符合資料庫定義的約束。

    • I-solation:多個Transactions可能同時發生,保證這些Transactions的執行等價於就像他們是一系列的(sequentially)而非同時的,得到一樣的結果。

    • D-urability:一個Transaction結束後,對資料的改動就是永久保存的,即使系統失效重啟。

  • BASE

    • B-asically A-vailable:如同字面意思,服務基本上保持可用,client的請求一定會得到結果。(CAPA一樣的概念)

    • S-oft State:系統中元件儲存的資料可能會隨時間改變即使沒有client發送請求,搭配下面的原因。

    • E-ventual consistency:這裡抽換掉了ACIDConsistency的概念,已經開始偏向CAPConsistency。元件可能因為斷線,使得目前資料不是最新的,client也可能讀取到舊的資料。但是最終一段時間過後,所有元件會更新成最新的資料,client再次讀取就會取得最新的資料。這種Consistency從而交換到了一定程度的Availability

CAP 定理

分散式系統最知名的理論 - CAP Theorem

在理論計算機科學中,CAP定理(CAP theorem),又被稱作布魯爾定理(Brewer's theorem),它指出對於一個分布式計算系統來說,不可能同時滿足以下三點。

  • 一致性(Consistency):等同於所有節點訪問同一份最新的資料副本。

  • 可用性(Availability):每次請求都能獲取到非錯的響應,但是不保證獲取的資料為最新資料。

  • 分區容錯性(Partition tolerance):以實際效果而言,分區相當於對通信的時限要求。系統如果不能在時限內達成資料一致性,就意味著發生了分區的情況,必須就當前操作在CA之間做出選擇。

根據定理,分布式系統只能滿足三項中的兩項而不可能滿足全部三項。理解CAP理論的最簡單方式是想像兩個節點分處分區兩側。允許至少一個節點更新狀態會導致資料不一致,即喪失了C性質。如果為了保證資料一致性,將分區一側的節點設置為不可用,那麼又喪失了A性質。除非兩個節點可以互相通信,才能既保證C又保證A,這又會導致喪失P性質。

一個例子假設Server只提供儲存與讀取key-value的服務。

  • 圖1:
    只有一個Server,只要該Server正常,讀寫功能都不會有問題。

  • 圖2:
    因為單一Server可能出現問題導致服務中斷,最直接的方式就是兩個server來提供服務,來避免單一失敗或是增加處理流量的能力。而為了保持資料是一樣的,當有一方寫入後,他必須複製該新結果到其他的replica servers

  • 圖3:
    而在分散式系統裡,更常見的錯誤反而是網路的斷線,若是server 1server 2失去聯繫,那麼彼此就看不到對方更新的值,最終整個系統的資料會完全不一致。


CAP定理說的也就是設計系統的時候有三種選擇:

  1. Consistency 與 Availability (CA)

    • 所求:此種選擇沒辦法處理Partition的發生,卻又可以保證系統的讀取是永遠最新正確,同時保持可用不會返回錯誤?

    • 方法:唯一的可能就是執行在單一電腦上!例如單一電腦的服務,只要系統設計沒bug,電腦本身不斷電不失火,系統可以持續運作且保持一致。但缺點就是失去了Scalability,且執行在單一電腦還叫做分散式系統嗎?

  1. Consistency 與 Partition Tolerance (CP)

    • 所求:在Partition發生時,系統仍能針對每次讀取返回最新寫入的值。

    • 方法:犧牲掉Availability,只要系統內部有一個元件還沒更新成最新結果,就一律返回錯誤。直到元件彼此重新連上線,同步完結果後,讀取請求才會返回正確結果。

    • 例子:Distributed RDBMSConsistency為最高原則。不允許一個client A寫入到其中一個server A,然後client Aserver B讀取時,發現結果跟剛剛寫入的不一樣。因此當系統發生Partition時,系統返回錯誤。

  1. Availability 與 Partition Tolerance (AP):

    • 所求:即使系統發生Partitionclient的請求仍然會返回結果而不是直接丟出錯誤,即使結果可能不是最新的。

    • 方法:就是犧牲了Consistency,即使元件彼此暫時無法通訊,只要某元件收到請求它就返回目前手上的結果,但是可能不是最新的。

    • 例子:DNS系統與近年興起的NoSQL Database,強調的就是Availability,也就是系統保證運作,但是可能返回的結果不是最新的,畢竟在網路服務中,如果服務中斷可能帶來更大的不便。

突破 CAP 定理的資訊系統設計

CAP定理的存在,似乎設下了資訊系統架構的一道難題,因為俗世眾生最想要的,往往是「又要馬兒跑,又要馬兒不吃草」。有沒有什麼設計策略,可以避開或是減輕ConsistencyAvailability之間的牴觸呢?

學者們提供了幾個努力的方向,最常被應用的一個,就是設計混合式系統(Hybrid System),意思是,一個大型系統的一部分採用High-Availability的設計,而另外一些部分則採取High-Consistency的作法。

具體應該怎麼區分何時靠向Availability何時轉往Consistency取決於具體的業務場景,一般來說,靠近前端(網頁或是UI)比較適合採用High-Availability,而到了後端底層(資料庫)則是天然地需要採用High-Consistency的系統。

要說現實生活中High-Availability最鮮明的案例各種搜尋引擎(文本/商品…etc)可以算是一個,重點是要讓每次搜尋都能快速返回結果,至於是不是每次都搜出一樣的內容或是內容準確或即時性就不是那麼關鍵;而High-Consistency的代表就是線上購物付款了,回應速度往往慢吞吞的原因就是為了保證資料高度正確,事實上付款API在很多系統裡面都是系統瓶頸的所在。

另一個稍微比較複雜的作法是根據商業條件切割系統特性,例如:

  • By functionDNScache system的要求可能比較類似,兩者又跟database比較不同。

  • By operation:例如read操作的可用性要求較高;write操作的一致性要求較高。

  • By user type:有些系統的user只是需要參考資訊,對於精準度要求不高;另一些高級系統用戶可能對精確資訊的需求較強。

  • By data type:靜態資料不常變動,所以可以著重在availability;交易資料跟錢有關出錯成本很高,必須小心考量consistency

其他像是運用根據地理區、網路速度等條件來做系統區隔也都是可以考慮的設計作法。


註:以上參考了
CAP定理
分布式系統的架構天險:CAP THEOREM 的一點探討
我的C是你的C嗎,介紹CAP Theorem與ACID/BASE