iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 2
3

第一天,我們輕鬆一點。在走入一堆系統與理論的迷宮前,
我們來認識一下分散式系統最知名的理論 - CAP Theorem

先看一個例子

先舉一個簡單的服務讓大家有一個直觀的分散式系統想法,假設它只提供儲存與讀取 key-value 的服務。

圖1:
如果今天服務只有一個元件,那事情非常簡單,只要該server一直活著,那我的讀寫功能都不會出問題。

圖2:
但是我知道電腦可能斷電或是失效,且可能一瞬間有百萬個人要存取我的服務,因此我希望用最直觀的方法,也就是scale up成兩個servers來提供服務,來避免單一電腦失敗或是增加處理流量的能力。而為了保持數據是一樣的,當有一方寫入後,他必須複製該新結果到其他的replica servers。

圖3:
上述想法非常直觀簡單,但是在分散式系統裡,更常見的錯誤反而是網路的斷線,若是s1與s2失去聯繫,那麼彼此就看不到對方更新的值,最終整個系統的資料會完全不一致。

究竟系統成長成分散式系統後,有哪些細節我們應該考慮,就是接下來幾天探討的主題。

CAP Theorem 介紹

CAP是一個縮寫分別代表三個字,也是未來系列文章每個主題都在奮力爭取的三個字
分別是:

  • C-onsistency: (Strong Consistency)
    每一次對系統的讀取皆能讀到最新一次寫入的資料,或著系統返回錯誤。
  • A-vailability:
    每一次對系統的請求皆能返回結果,系統不會返回錯誤,但是不保證讀到的資料是最新且正確的。
  • P-artition Tolerance:
    網路可能掉封包或是斷線,導致系統分成兩個或多個子系統無法通訊。在此情形下,整個系統仍能保持運作返回正確結果。

而CAP Theorem說的是

"在分散式系統中,不可能同時滿足上面三個性質,最多只能同時滿足兩個。"

也就是設計系統的時候有三種選擇

  1. ConsistencyAvailability:

    • 所求: 此種選擇沒辦法處理Partition的發生,卻又可以保證系統的讀取是永遠最新正確,同時保持可用不會返回錯誤?
    • 方法: 唯一的可能就是...執行在單一電腦上!例如單一電腦的服務,只要系統設計沒bug,電腦本身不斷電不失火,系統可以持續運作且保持一致。但缺點就是失去了Scalibility,且執行在單一電腦還叫做分散式系統嗎?
  2. ConsistencyPartition Tolerance:

    • 所求: 在Partition發生時,系統仍能針對每次讀取返回最新寫入的值。
    • 方法: 犧牲掉Availability,只要系統內部有一個元件還沒更新成最新結果,就一律返回錯誤。直到元件彼此重新連上線,同步完結果後,讀取請求才會返回正確結果。
    • 例子: Distributed RDBMS 以Consistency為最高原則。不允許一個clientA寫入到其中一個serverA,然後clientA從serverB讀取時,發現結果跟剛剛寫入的不一樣。因此當系統發生Partition時,系統返回錯誤。
  3. AvailabilityPartition Tolerance:

    • 所求: 即使系統發生Partition,client的請求仍然會返回結果而不是直接丟出錯誤,即使結果可能不是最新的。
    • 方法: 也就是犧牲了Consistency,即使元件彼此暫時無法通訊,只要某元件收到請求它就返回目前手上的結果,但是可能不是最新的。
    • 例子: DNS系統與近年興起的NoSQL Database,強調的就是Availablity,也就是系統保證運作,但是可能返回的結果不是最新的,畢竟在網路服務中,如果服務中斷可能帶來更大的不便。

CAP Theorem 由來

CAP最初由Eric Brewer(目前Google VP Infrastructure)在2000提出,在CAP出現前我們先聊聊更早之前就有的兩個名詞: ACID, BASE

在網路、雲端開始興起之初,資料庫是最早被大量研究的應用。而針對資料庫最重要的就是Transaction。簡單說明,當我透過銀行轉帳,資料庫第一步從我帳戶扣除金額,第二部在對方帳戶增加金額,這兩步連續動作就是一個 Transaction (wiki例子)。資料庫必須保證這個Transaction是安全有效的,因此提出了ACID特性。

ACID:

  • A-tomicity: 一個Transaction裡的所有動作要不全部成功或者失敗。
  • C-onsistency: 一個Transaction只能將資料庫從一個合法的狀態轉移到另一個合法的狀態,也就是Transaction結束後,所有的資料仍然符合資料庫定義的約束。
  • I-solation: 多個Transactions可能同時發生,保證這些Transactions的執行等價於就像他們是一系列的(sequencially)而非同時的,得到一樣的結果。
  • D-urability: 一個Transaction結束後,對數據的改動就是永久保存的,即使系統失效重啟。

這邊小比較:
從這裡可以看到ACID的C跟CAP的C不一樣,
一個是資料庫的數據在被修改後仍然必須合法,
一個是分散式系統中每個元件手中的副本資料必須一致,使得client不管從哪個元件讀取皆會得到一樣最新的結果。

而因為網路服務的興起,服務中斷的成本變得越來越高,因為會影響使用者的黏著度。Eric Brewer首先提出了另一個理念BASE來設計往後的網路服務。

BASE

  • B-asically A-vailable: 如同字面意思,服務基本上保持可用,client的請求一定會得到結果。( CAP 的A一樣的概念)
  • S-oft State: 系統中元件儲存的資料可能會隨時間改變即使沒有client發送請求,搭配下面的原因。
  • E-ventual consistency: 這裡抽換掉了ACID的Consistency的概念,已經開始偏向CAP的Consistency。元件可能因為斷線,使得目前資料不是最新的,client也可能讀取到舊的資料。但是最終一段時間過後,所有元件會更新成最新的資料,client再次讀取就會取得最新的資料。這種Consistency從而交換到了一定程度的Availability。

小插曲
大家應該知道做電腦科學的人命名很隨性,其實BASE某程度上也是掰出來的縮寫。
剛好ACID是"酸性",BASE是"鹼性",形成一個對比。

"I came up with acronym with my students in their office earlier that year. I agree it is contrived a bit, but so is “ACID” – much more than people realize, so we figured it was good enough" - Eric Brewer

再過了一段時間到2000年 Eric Brewer 就提出了上面介紹的CAP Theorem

CAP Theorem 總結

CAP看似三選二,但當今天我們要設計分散式系統的時候,Network Partition是不可避免的。所以更重要的是如何在Consistency和Availability做取捨。

  1. 著重Availability: 每個元件手上的資料副本可能不是最新的,使用者是可以接受的嗎,接受程度有多高?
  2. 著重Consistency: 當系統一有網路斷線發生時,就中斷服務,是否會影響使用者,影響多久可以接受?

不過,從上面可以知道,BASE 的提出已經意識到可以在Consistency和Availability做取捨,而開始將Consistency定義出不同的等級,所以我們其實不用絕對拋棄任一個性質,而是找出最適合自己服務的平衡。

這一系列的思路也帶動了NoSQL資料庫的興起,最有名的例子應該就是Amazon DynamoDB,他就是採用了Eventual consistency來保證服務的Availability。

另一個例子也藏在生活之中,就是訪問網路時一定會用到的服務 DNS。前面提到Domain Name Service當然也是一種分散式系統,而為了保證大家都可以用網路,他選擇側重了Availibility,並且也是用了Eventual Consistency來交換,看以下例子:

當一個新的的服務上線並且註冊了他的域名與對應的ip位址後,四散各地的DNS並不是同時同步更新,因此在另外一端的人可能第一次訪問該服務時,不一定可以正確被解析。但是最終過了一段時間DNS更新了資訊後,再次訪問便可以正確使用。

一系列從ACID, BASE到CAP看下來。可以知道設計系統的時候,CAP理論提供了一個方向,但是並不是限制。最終,使用系統的是一般使用者,必須從使用者角度出發考量。

預告

回到最前面的例子,從CAP理論我們知道必須對Consistency和Availability做出取捨,但是這個取捨應該取多少又捨棄多少?

明天將會討論各種data replication的Consistency Model,來看看你說的data要一致到底要多一致。


上一篇
Day 1 - 分散式系統筆記
下一篇
Day 3 - 從Replica Server讀到的資料一定正確嗎? Data Replication and Consistency
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言