分布式系統概念--第一篇 一緻性協定、一緻性模型、拜占庭問題、租約、副本協定

1，一緻性協定

兩階段送出協定與Raft協定、Paxos協定

①兩階段送出協定

在分布式系統中，每個節點雖然可以知曉自己的操作時成功或者失敗，卻無法知道其他節點的操作的成功或失敗。當一個事務跨越多個節點時，為了保持事務的ACID特性，需要引入一個作為協調者的元件來統一掌控所有節點(稱作參與者)的操作結果并最終訓示這些節點是否要把操作結果進行真正的送出(比如将更新後的資料寫入磁盤等等)。是以，二階段送出的算法思路可以概括為： 參與者将操作成敗通知協調者，再由協調者根據所有參與者的回報情報決定各參與者是否要送出操作還是中止操作。

是以，系統包含兩類節點，一類是協調者，一類是參與者，協定的執行由兩個階段組成：

具體參考：二階段送出：維基百科

兩階段協定是阻塞的，節點在等待對方的應答消息時，它不能做其他事情且持有的資源也不釋放。它主要是用來保證跨多個節點的操作的原子性--要麼都操作，要麼都不操作，而像Raft協定則諸如用來保證操作的一緻性，即各個節點都執行相同的操作。

兩階段協定的舉例參考：兩階段送出協定

②Raft協定和Paxos協定

Raft與Paxos 在分布式應用中的基本功能相似，但是Paxos難于了解，相對而言Raft算法要簡單一些。關于Raft協定有一篇經典的論文：

《In Search of an Understandable Consensus Algorithm (Extended Version)》

其中文翻譯位址參考：尋找一種易于了解的一緻性算法（擴充版）

還有一篇文章詳細解釋了Raft算法的相關實作：Raft論文的第 31 号參考文獻。

下面僅記錄一下看論文過程中出現的一個問題：

為什麼 “大多數規則” 能夠保證對于一個給定的任期，隻會有一個候選人最終赢得選舉成為Leader？

在Raft中，對于一個給定的任期号，每一台Server按照先來先服務原則對該任期号最多隻投一張票，若某Candidate發送的請求投票RPC帶有的任期号獲得超過半數的Server的同意，則該Candidate成為Leader。

正是由于每個Server對某個任期隻最多投一次票，且獲得的投票要超過半數才能成為Leader，故在一個給定的任期投票中，最終隻會有一個Candidate成為Leader。

關于Raft協定中的Leader選舉步驟參考：Raft系列文章之二：Leader選舉

2，分布式系統中常見的三種一緻性模型

①強一緻性：當更新操作在某個副本上執行成功後，之後所有的讀操作都要能夠獲得最新的資料。對于單副本而言，讀寫操作都是在同一資料上執行，很容易保證一緻性；而對于多副本資料，則需要使用分布式協定如2PC協定。

②弱一緻性：當更新某資料時，使用者讀到最新的資料需要一段時間。

③最終一緻性：它是一種特殊形式的弱一緻性。它不能保證當某個資料Ｘ更新後，在所有後續對Ｘ的操作能夠看到新資料，而是需要一個時間片段，在經過該時間片段之後，則能保證。在這個時間片段内，資料可能是不一緻的，該片段稱“不一緻視窗“。

參考：資料一緻性模型

3，拜占庭将軍問題

在分布式理論中，經常看到”在非拜占庭錯誤情況下，算法是有效的……“ 或者說 ”...可以容忍非拜占庭失效“。那麼什麼是拜占庭将軍問題呢？

在分布式計算上，不同的計算機透過訊息交換，嘗試達成共識；但有時候，系統上協調計算機（Coordinator / Commander）或成員計算機 （Member / Lieutanent）可能因系統錯誤并交換錯的訊息，導緻影響最終的系統一緻性。參考：維基百科：拜占庭将軍問題

也即，在系統不同的機器之間會傳遞錯誤的消息，這種情況即為拜占庭問題。這與”網絡分割、機器崩潰...”是不同的。比如Raft協定不能容忍拜占庭問題，但是能夠 在非拜占庭錯誤情況下，有網絡延遲、分區、丢包、備援和亂序等錯誤情況出現時，都可以保證其操作的正确性。

4，租約，心跳包(heartbeat)

①租約

這裡主要列舉租約可以用來幹什麼？

a,進行故障檢測。這類似于ZooKeeper中master 與 slaver 之間發送的心跳包的作用。在ZK中， master 和 slaver 之間通過交換心跳包來檢測它們是否還存活。一個具體的例子參考：故障檢測

b,維護緩存一緻性維護緩存的一緻性，第一種辦法是輪詢：每次讀取資料時都先詢問伺服器資料是不是最新的，若不是，則先讓伺服器傳輸新資料，然後再讀取該新資料。第二種方法是回調：由伺服器記錄有哪些用戶端讀取了資料，當伺服器對資料做修改時先通知記錄下來的這些用戶端，上次讀取過的資料已經失效。這二種方法都有一定的缺陷，參考：租約機制簡介

是以，可以引入租約機制。在租約期限内，可以保證用戶端緩存的資料是最新的。當租約過期後，用戶端需要重新向伺服器詢問資料，重新續約。

租約的定義：租約就是在一定期限内給予持有者特定權力的 協定。每個租約都有一個期限，正是這個期限可以保證租約機制容忍機器失效和網絡分割。

租約機制優化背景資料庫通路的一個例子：使用租約機制解決緩存資料更新的問題

5，副本協定

副本協定是控制副本讀寫行為的規則，使得副本滿足可用性和一緻性。

副本協定分為兩類，①中心化的副本控制協定：由一個中心節點協調副本資料的更新，維護副本資料的一緻性。這裡重點介紹下常用的Primary-Secondary中心化副本控制協定：假設資料是以資料段(segment/partition)為機關分布在叢集各台機器上的，每個資料段指定一個作為主副本，其餘的資料段則為從副本，對該資料段的更新（讀寫）而言，由主副本來負責。比如，當多個Client同時需要更新某個資料段時，所有的更新操作都發送到該資料段所對應的主副本所在的機器上，由它來确定更新的順序，負責協調一緻性。

那麼，Client如何找到主副本所在的機器呢？？？這需要一個中繼資料伺服器，它專門用來記錄主副本的位置及相關資訊，記錄叢集個各個資料段的主副本的位置資訊，副本配置設定情況……該中繼資料伺服器應該相當于GFS中的Master。

注意：由于上面是假設資料不是以機器為機關分布在叢集中，而是以資料段為機關分布在叢集中，當某個資料段被指定為主副本時，該主副本也是按照以資料段為機關的資料分布方式分布到叢集中的，即各個Primary副本的位置在叢集中是随機配置設定的。

要将Primary副本所在的機器與Master機器區分開來：應該在GFS中，Primary副本所在的機器可能是某台Slaver機器，它用來存儲各個資料塊。而Master是用來存儲中繼資料資訊的。

②去中心化的副本控制協定：各個節點之間是平等的，通過協商方式來達成某些操作。

學習材料參考：《分布式系統原理介紹  劉傑》