Day 15 - 共識演算法 - 先喘口氣做一個複習

11th鐵人賽分散式系統一致性 cloud cap

Jack Lin

2019-09-30 17:49:25

2597 瀏覽

分享至

前言

今天鐵人30天已經走了一半了！
沒想到我們還在討論Consistency與Availability的問題。就知道其實分散式系統最大的問題，便是在保持系統可用性的情況下，使用著讀取資料的一致性，這個tradeoff可以說佔了分散式系統一半以上的篇章，從這30天的內容你大概也可以理解(笑

我們前面針對Consistency，已經介紹了很多的方法，比方說Quorum System、2PC\3PC、Paxos與Raft，每一個都有一定的複雜性，因為要保持一致性必須考量各種可能發生錯誤的情境。今天我們來做一個小整理。

以下的內容整理自2009年的Transactions Across Datacenters演講，更推薦直接看影片了解。

整理

首先我們直接看出自演講統整比較的一張圖

Backups

最基本的備份，就像手幾電腦一樣，每一次有更新就備份起來或是採用週期性備份。

Transaction/Consistency: 備份的過程中可能有別的client又更新了資料，因為這個過程並沒有引入什麼協定(E.g. 2PC)，此時備份的資料跟系統上的資料是不一樣的，沒辦法全程保持一致。
Latency/Throuput: 當然是最好，因為只有一個系統在運作其他是做備份，所以讀寫時不用跑協定，相較於2PC/Paxos要先執行演算法做一致性處理，這邊的效能較好。
Data loss: 這邊要說明的是當系統在備份的時候，備份到一半系統失效，則備份系統也還沒備份到，因此會遺失最新的資料，只有前一次備份的snapshot。
Failover: 這邊說的是，對於Google來說，如果他一個Datacenter失效，利用將Backup資料搬到另一個Datacenter來做恢復的這段期間系統是不能運作的。

Master-Slave

這種架構下ㄧ般是指Passive Master-Slave架構，也就是讀寫請求皆由Master負責，然後再由Master將更新的資料同步到Slave身上。

Transaction/Consistency: 因為讀寫由Master負責，因此Transaction可以完成，連2PC都不用。另外，因為是由Master push資料到Slave身上，或是Slave主動pull資料來做同步，因此slave身上的資料可能不會一直保持一致，這邊的Consistency為Eventual Consistency。
Latency/Throuput: 因為讀寫由Master負責，不需等待同步，所以效能也不差。
Data loss: 如果Master在同步資料到Slave上時失效，可能造成最新的資料遺失。
Failover: 如果Master在同步資料到Slave上時失效
- 一種做法是讓Slave成為新的Master提供讀寫，則前一個Master最新的資料可能就真的遺失
- 也可以是等待Master回覆，Slave這時只能提供Read-Only服務

Master-Master

這個通常就是指Leaderless的系統，每一個replica servers都可以進行讀寫，以前面提到的DynamoDB為例。

回想DynamoDB，使用Quorum system，當讀的時候必須設定W/R參數來在Consistency/Availbility做取捨。發現有多個版本就必須Reconcile，你要有方法可以做serilaized，常見方法就是可以用Vector Clock來做，選出一個最新的事件並且merge，很像git的branch與merge。前面提到的幾種做法是最典型常見的做法，當然還有很多其他的方法。

如果你今天的系統大到橫跨好幾個州與好幾個Datacenter，其中資料會被備份到別的Datacenter，一來可以做備份，二來可以讓使用者直接選擇較近的Datacenter做讀寫避免傳輸的latency。

但是也因此，兩個Datacenters的writes操作幾乎是獨立，你沒辦法保證這邊針對資料的writes不會互相影響到另一邊的writes，也就是說你雖然橫跨了好幾個Datacenters，反而 增加了global transaction的難度 。

也因此你會發現DynamoDB這樣的NoSQL DB沒辦法提供以前RDBMS那種等級的ACID Transaction。

不過Amazon也是不斷修正，在近期提供了Transaction操作，雖然有很一些限制，可以感覺是在他的設計底下做了一點workaround來提供transaction，可以去看看他們的文件確認一下這個等級的Transaction符不符合你的需求。
https://aws.amazon.com/tw/blogs/aws/new-amazon-dynamodb-transactions/

Transaction/Consistency: Transaction可以看Amaozon怎麼在Dynamo實作Transaction，可以做到，但是有限制，一般來說只能在Local的這個Master先實作Transaction在同步到其他的Master。Consistency就像之前提到的是Eventual Consistency。
Latency/Throuput: 採用Quorum System，因此不需要等待所有的Master執行完某個協定或是取的所有Master的Lock才能讀寫(W/R個數)，所以也不差。
Data loss: 就像之前提到的使用 Read-Repair 或是 Anti-Entropy 來同步資料到其他的Master上，但是同理，如果同步過程節點失效，則仍然有機會導致資料遺失。
Failover: Quorum System 搭配 Hinted Handoff 在有Master失效時仍能正常運作。

2PC

Transaction/Consistency: Strong Consistency 且本來就是為了 Transaction 而生的。
Latency/Throuput: 很差
Data loss: 寫入成功則資料會一致且不會丟失，要不就一開始就2PC失敗導致寫入失敗。
Failover: 這邊可以參考之前提到的2PC Coordinator與Participants失效的情境。這邊比較圖表示仍然可以Read-Write是建立於: 「2PC執行完，就算有節點失效，且Transaction只發生在單一個DB上仍然可以運作。」，而非2PC中間發生失效問題。

Paxos

而Google當年在設計App Engine Datastore的時候，認為Eventual Consistency 在某些使用情境下不是一個很好的特性，因此朝向Strong Consistency設計，而2PC最大的問題便是他的throughput實在是太低了，Coordinator和Participants必須一來一往兩次的訊息傳遞，已經是跨Datacenters的情況下，這個問題就變得非常嚴重，因此決定使用前面提到的Paxos。每當他們的任何一個服務，要從一個state進入到下一個state，都會使用Paxos在Datacenters間作協調。

另外仔細研究2PC與Paxos的過程，其實非常相似，甚至可以說Paxos是優化了2PC後得到的最佳解。最一開始都是由一個節點提出了Prepare，得到大家的回覆後，再進行下一輪的確認一致性。只是Paxos考量了更多細節，比方說Proposers可以有很多個，並且使用Proposal Number來協調多個Proposers。

也因此Google Chubby 的作者 Mike Burrows (我們以後會提到他)說到:

"There is only one consensus protocol, and that's Paxos. Others are either Paxos, or Paxos with cruft, or broken." 多霸氣的發言XD

Transaction/Consistency: Strong Consistency 是一個完整的共識演算法流程，可以拿來在Transaction做協調，保證最終對於v值是一致的。
Latency/Throuput: 只要保證半數達成一致，則一致性已經完成。
Data loss: 寫入(commited)成功則資料會一致且不會丟失，要不就一就Paxos失敗導致寫入失敗。
Failover: 只要還有過半數的節點存活就可以執行Paxos演算法，提供讀寫。

大家可以想想看Raft跟Paxos從本質上是否也是相似的呢？

總結

回到第二篇的分散式系統的開始，我們希望將儲存的資料做replication儲存到多個servers上，來增加系統的Availability。而一個資料被複製到多個servers上，就會出現一致性的問題。而CAP理論的誕生也宣告了沒有一個最佳的解決辦法，因此出現了各種情境應運而生的理論，也就生出這15天的內容。

原本以為寫一個總結的文章，可以輕鬆一點，結果也是一場硬仗...

如果對於到目前為止的整理有哪一個名詞不熟悉的，就再回去前面看一下吧xD