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

先看一個例子

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

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

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

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

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

CAP Theorem 介紹

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

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

而CAP Theorem說的是

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

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

1. Consistency 與 Availability:

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

2. Consistency 與 Partition Tolerance:

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

3. Availability 與 Partition 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要一致到底要多一致。