分布式事务与一致性算法Paxos amp; raft amp; zab
要想數據高可用，就得寫多份數據
寫多分數據就會導致數據一致性問題
數據一致性問題會引起性能問題
2.一致性模型
弱一致性
最終一致性（一段時間達到一致性）
強一致
1、2 異步冗余；3是同步冗余
3.? 擴展服務的方案
數據分區： uid % 16
數據鏡像：讓多有的服務器都有相同的數據，提供相當的服務（冗余存儲，一般3份為好）
4.兩種方案的事務問題
A向B匯錢，兩個用戶不在一個服務器上
鏡像：在不同的服務器上對同一數據的寫操作如何保證一致性。?
5. 解決一致性事務問題的技術
1. Master -Slave
讀寫請求由Master負責
寫請求寫到Master后，由Master同步到Slave上
由Master push or Slave pull
通常是由Slave 周期性來pull，所以是最終一致性
問題： 若在 pull 周期內（不是期間？），master掛掉，那么會導致這個時間片內的數據丟失
若不想讓數據丟掉，Slave 只能成為 ReadOnly方式等Master恢復
若容忍數據丟失，可以讓 Slave代替Master工作
如何保證強一致性？
Master 寫操作，寫完成功后，再寫 Slave，兩者成功后返回成功。若 Slave失敗，兩種方法
標記 Slave 不可用報錯，并繼續服務（等恢復后，再同步Master的數據，多個Slave少了一個而已）
回滾自己并返回失敗
2. Master-Master
數據同步一般是通過 Master 間的異步完成，所以是最終一致
好處： 一臺Master掛掉，另外一臺照樣可以提供讀寫服務。當數據沒有被賦值到別的Master上時，數據會丟失。
對同一數據的處理問題：Dynamo的Vector?Clock的設計（記錄數據的版本號和修改者），當數據發生沖突時，要開發者自己來處理
3.兩階段提交? Two? Phase Commit?? _ 2PC
第一階段：針對準備工作
協調者問所有節點是否可以執行提交
參與者開始事務，執行準備工作：鎖定資源（獲取鎖操作）
參與者響應協調者，如果事務的準備工作成功，則回應"可以提交"，否則，拒絕提交
第二階段：
若都響應可以提交，則協調者項多有參與者發送正式提交的命令（更新值），參與者完成正式提交，釋放資源，回應完成。協調者收到所有節點的完成響應后結束這個全局事務.。若參與者回應拒絕提交，則協調者向所有的參與者發送回滾操作，并釋放資源，當收到全部節點的回滾回應后，取消全局事務
存在的問題：若一個沒提交，就會進行回滾
第一階段：若消息的傳遞未接收到，則需要協調者作超時處理，要么當做失敗，要么重載
第二階段：若參與者的回應超時，要么重試，要么把那個參與者即為問題節點，提出整個集群
在第二階段中，參與者未收到協調者的指示（也許協調者掛掉），則所有參與者會進入“不知所措” 的狀態（但是已經鎖定了資源），所以引入了三段提交
4. 三段提交：把二段提交的第一階段 break 成了兩段
詢問
鎖定資源（獲取鎖）
提交
核心理念：在詢問的時候并不鎖定資源，除非所有人都同意了，才開始鎖定
好處：當發生了失敗或超時時，三段提交可以繼續把狀態變為Commit 狀態，而二段提交則不知所措？
5. Raxos 算法（少數服從多數）
解決的問題：在一個可能發生異常的分布式系統中如何就某個值達成一致，讓整個集群的節點對某個值的變更達成一致
任何一個節點都可以提出要修改某個數據的提案,是否通過這個提案取決于這個集群中是否有超過半數的節點同意（所以節點數總是單數）—— 版本標記。雖然一致性，但是只能對一個操作進行操作啊？？
當一個Server接收到比當前版本號小的提案時，則拒絕。當收到比當前大的版本號的提案時，則鎖定資源，進行修改，返回OK.?? 也就是說收到超過一半的最大版本的提案才算成功。
核心思想：
在搶占式訪問權的基礎上引入多個acceptor，也就是說當一個版本號更大的提案可以剝奪版本號已經獲取的鎖。
后者認同前者的原則：
在肯定舊epoch 無法生成確定性取值時，新的 epoch 會提交自己的valu
一旦 舊epoch形成確定性取值，新的 epoch肯定可以獲取到此取值，并且會認同此取值，不會被破壞。
步驟
P1 請求Acceptor的 #1,Acceptor 這時并沒有其他線程獲取到鎖，所以把鎖交給 P1，并返回這時 #1 的值為null
然后 P1 向 第一個 Acceptor 提交 #1 的值，Acceptor 接受并返回 OK
這個時候，P2向Acceptor請求#1上的鎖，因為版本號更大，所以直接搶占了 P1 的鎖。這時 Acceptor 返回了 OK并且返回了 #1 的值
這時 P1 P向 后面兩個 Acceptor 提交 #1 的值，但是由于中間的那個Acceptor 版本號已經更改為 2 了，所以拒絕P1。第三個 Acceptor 接受了，并且返回了 OK
由于后者認同前者的原則，這時 P1 已經形成確定性取值了 V1 了，這時新的 P2 會認同此取值，而不是提交自己的取值。所以，P2會選擇最新的那個取值 也就是V1 進行提交。這時Acceptor 返回 OK
6.ZAB 協議 ( Zookeeper Atomic? Broadcast) 原子廣播協議：保證了發給各副本的消息順序相同
定義：原子廣播協議 ZAB 是一致性協議，Zookeeper 把其作為數據一致性的算法。ZAB 是在 Paxos 算法基礎上進行擴展而來的。Zookeeper 使用單一主進程 Leader用于處理客戶端所有事務請求，采用 ZAB 協議將服務器狀態以事務形式廣播到所有 Follower 上，由于事務間可能存在著依賴關系，ZAB協議保證 Leader 廣播的變更序列被順序的處理，一個狀態被處理那么它所依賴的狀態也已經提前被處理
核心思想：保證任意時刻只有一個節點是Leader，所有更新事務由Leader發起去更新所有副本 Follower，更新時用的是 兩段提交協議，只要多數節點 prepare 成功，就通知他們commit。各個follower 要按當初 leader 讓他們 prepare 的順序來 apply 事務
協議狀態
Looking:系統剛啟動時 或者 Leader 崩潰后正處于選舉狀態
Following：Follower 節點所處的狀態，Follower與 Leader處于數據同步狀態
Leading：Leader 所處狀態，當前集群中有一個 Leader 為主進程
ZooKeeper啟動時所有節點初始狀態為Looking，這時集群會嘗試選舉出一個Leader節點，選舉出的Leader節點切換為Leading狀態；當節點發現集群中已經選舉出Leader則該節點會切換到Following狀態，然后和Leader節點保持同步；當Follower節點與Leader失去聯系時Follower節點則會切換到Looking狀態，開始新一輪選舉；在ZooKeeper的整個生命周期中每個節點都會在Looking、Following、Leading狀態間不斷轉換。
選舉出Leader節點后 ZAB 進入原子廣播階段，這時Leader為和自己同步每個節點 Follower 創建一個操作序列，一個時期一個 Follower 只能和一個Leader保持同步
階段
Election： 在 Looking狀態中選舉出 Leader節點，Leader的LastZXID總是最新的（只有lastZXID的節點才有資格成為Leade,這種情況下選舉出來的Leader總有最新的事務日志）。在選舉的過程中會對每個Follower節點的ZXID進行對比只有highestZXID的Follower才可能當選Leader
每個Follower都向其他節點發送選自身為Leader的Vote投票請求，等待回復；
Follower接受到的Vote如果比自身的大（ZXID更新）時則投票，并更新自身的Vote，否則拒絕投票；
每個Follower中維護著一個投票記錄表，當某個節點收到過半的投票時，結束投票并把該Follower選為Leader，投票結束；
Discovery:Follower 節點向準 Leader推送 FollwerInfo,該信息包含了上一周期的epoch，接受準 Leader 的 NEWLEADER 指令
Sync：將 Follower 與 Leader的數據進行同步，由Leader發起同步指令，最終保持數據的一致性
Broadcast：Leader廣播 Proposal 與 Commit，Follower 接受 Proposal 與 commit。因為一個時刻只有一個Leader節點，若是更新請求，只能由Leader節點執行（若連到的是 Follower 節點，則需轉發到Leader節點執行；讀請求可以從Follower 上讀取，若是要最新的數據，則還是需要在 Leader上讀取）
消息廣播使用了TCP協議進行通訊所有保證了接受和發送事務的順序性。廣播消息時Leader節點為每個事務Proposal分配一個全局遞增的ZXID（事務ID），每個事務Proposal都按照ZXID順序來處理（Paxos 保證不了）
Leader節點為每一個Follower節點分配一個隊列按事務ZXID順序放入到隊列中，且根據隊列的規則FIFO來進行事務的發送。
Recovery?：根據Leader的事務日志對Follower 節點數據進行同步更新
同步策略：
Follower將所有事務都同步完成后Leader會把該節點添加到可用Follower列表中；
Follower接收Leader的NEWLEADER指令，如果該指令中epoch比當前Follower的epoch小那么Follower轉到Election階段
SNAP?：如果Follower數據太老，Leader將發送快照SNAP指令給Follower同步數據；
DIFF?：Leader發送從Follolwer.lastZXID到Leader.lastZXID議案的DIFF指令給Follower同步數據；
TRUNC?：當Follower.lastZXID比Leader.lastZXID大時，Leader發送從Leader.lastZXID到Follower.lastZXID的TRUNC指令讓Follower丟棄該段數據；（當老Leader在Commit前掛掉，但是已提交到本地）
7. Raft 算法
Raft 算法也是一種少數服從多數的算法，在任何時候一個服務器可以扮演以下角色之一：
Leader：負責 Client 交互 和 log 復制，同一時刻系統中最多存在一個
Follower：被動響應請求 RPC，從不主動發起請求 RPC
Candidate : 由Follower 向Leader轉換的中間狀態
在選舉Leader的過程中，是有時間限制的，raft 將時間分為一個個 Term，可以認為是“邏輯時間”：
每個 Term中至多存在1個 Leader
某些 Term由于不止一個得到的票數一樣，就會選舉失敗，不存在Leader。則會出現 Split Vote? ，再由候選者發出邀票
每個 Server 本地維護 currentTerm
選舉過程：
獲得超過半數的Server的投票，轉換為 Leader，廣播 HeatBeat
接收到 合法 Leader 的 AppendEnties RPC，轉換為Follower
選舉超時，沒有 Server選舉成功，自增 currentTerm ,重新選舉
自增 CurrentTerm，由Follower 轉換為 Candidate，設置 votedFor 為自身，并行發起 RequestVote RPC,不斷重試，直至滿足下列條件之一為止：
當Candidate 在等待投票結果的過程中，可能會接收到來自其他Leader的 AppendEntries RPC ,如果該 Leader 的 Term 不小于本地的 Current Term，則認可該Leader身份的合法性，主動降級為Follower，反之，則維持 candida 身份繼續等待投票結果
Candidate 既沒有選舉成功，也沒有收到其他 Leader 的 RPC (多個節點同時發起選舉，最終每個 Candidate都將超時)，為了減少沖突，采取隨機退讓策略，每個 Candidate 重啟選舉定時器
日志更新問題：
如果在日志復制過程中，發生了網絡分區或者網絡通信故障，使得Leader不能訪問大多數Follwers了，那么Leader只能正常更新它能訪問的那些Follower服務器，而大多數的服務器Follower因為沒有了Leader，他們重新選舉一個候選者作為Leader，然后這個Leader作為代表于外界打交道，如果外界要求其添加新的日志，這個新的Leader就按上述步驟通知大多數Followers，如果這時網絡故障修復了，那么原先的Leader就變成Follower，在失聯階段這個老Leader的任何更新都不能算commit，都回滾，接受新的Leader的新的更新。
流程：
解決辦法：Client 賦予每個 Command唯一標識，Leader在接收 command 之前首先檢查本地log
Client 發送command 命令給 Leader
Leader追加日志項，等待 commit 更新本地狀態機，最終響應 Client
若 Client超時，則不斷重試，直到收到響應為止（重發 command，可能被執行多次，在被執行但是由于網絡通信問題未收到響應）
9. paxos 算法與 raft 算法的差異
raft強調是唯一leader的協議，此leader至高無上
raft：新選舉出來的leader擁有全部提交的日志，而 paxos 需要額外的流程從其他節點獲取已經被提交的日志，它允許日志有空洞
相同點：得到大多數的贊成，這個 entries 就會定下來，最終所有節點都會贊成
NWR模型
N： N個備份
W：要寫入至少 w 份才認為成功
R : 至少讀取 R 個備份
W+ R > N??? ——>??? R > N - W(未更新成功的) ，代表每次讀取，都至少讀取到一個最新的版本（更新成功的），從而不會讀到一份舊數據
問題：并非強一致性，會出現一些節點上的數據并不是最新版本，但卻進行了最新的操作
版本沖突問題：矢量鐘 Vector Clock ： 誰更新的我，我的版本號是什么（對于同一個操作者的同一操作，版本號遞增）
參考資料：
http://www.tuicool.com/articles/IfQR3u3
http://blog.csdn.net/chen77716/article/details/7309915
http://www.infoq.com/cn/articles/distributed-system-transaction-processing/
http://www.jdon.com/artichect/raft.html
http://blog.csdn.net/cszhouwei/article/details/38374603
原文地址：http://blog.csdn.net/followmyinclinations/article/details/52870418
.NET社區新聞，深度好文，微信中搜索dotNET跨平臺或掃描二維碼關注
總結
以上是生活随笔為你收集整理的分布式事务与一致性算法Paxos amp; raft amp; zab的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： asp.net core mvc实现伪静
- 下一篇： Xamarin的坑 - 绑定(二) -