背景介紹
對于一個分布式系統(tǒng)，雖然每一個機器節(jié)點都可以明確知道自己進行事務(wù)操作過程的結(jié)果是成功或失敗，但是無法直接獲取其他分布式節(jié)點的操作結(jié)果。因此，當(dāng)一個事務(wù)操作需要跨越多個分布式節(jié)點的時候，為了保持事務(wù)處理的ACID特性：
- 原子性（atomicity）
- 一致性（consistency）
- 隔離性（isolation）
- 容錯性（durablity）
，需要引入一個被稱為協(xié)調(diào)者（Coordinator）的組件來統(tǒng)一調(diào)度所有分布式節(jié)點的執(zhí)行邏輯，這些被調(diào)度的分布式節(jié)點叫做參與者（Participant）?？傊?，由協(xié)調(diào)者來負責(zé)調(diào)度參與者的行為，并最終決定這些參與者是否要真正提交事務(wù)。
為了以容錯方式達成一致，不可能要求所有服務(wù)器都100%達到一致狀態(tài)，只需要超過半數(shù)的服務(wù)器達成一致就行了。
Paxos算法就是谷歌提出的一種基于消息傳遞且具有高度容錯特性、一致性的算法。
下面展開的Paxos算法和Raft算法一般應(yīng)用于中心化的分布式系統(tǒng)，或者受限應(yīng)用的私有區(qū)塊鏈。
一、Paxos算法
在Paxos算法中，有3種角色：
- Proposer
- Acceptor
- Learners
在具體實現(xiàn)中，一個進程可能同時充當(dāng)多個角色，甚至三者都兼任。
還有一個很重要的概念——提案（Proposal）。最終要達成一致的value就在提案例。
1.階段一
1）Proposer 選擇一個提案編號N，然后向半數(shù)以上的Acceptor發(fā)送編號為N的Prepare請求
2）如果一個Acceptor收到一個編號為N的Prepare請求，且N大于該Acceptor已經(jīng)響應(yīng)過的所有Prepare請求的編號，那么它就會將它已經(jīng)接收過的編號最大的提案（如果有的話）作為響應(yīng)反饋給Proposer，同時該Acceptor承諾不再接收任何編號小于N的提案
2.階段二
1）如果Proposer收到半數(shù)以上Acceptor對其編號為N的Prepare請求的響應(yīng)，那么它就會發(fā)送一個針對[N, V]提案的Accept請求給半數(shù)以上的Acceptor
2）如果Acceptor收到一個針對編號為N的提案的Accept請求，只要該Acceptor沒有對編號大于N的Prepare請求做出過響應(yīng)，它就接收該提案
3.總結(jié)
Paxos算法的特點是一致性>可用性，由于這個算法比較復(fù)雜且難以理解，也不容易實現(xiàn)，所以有下面的Raft算法。
二、Raft算法
Raft本質(zhì)上跟Paxos類似，在Raft中，在任何時候一個服務(wù)進程都可以扮演下面角色之一：
- Leader：處理所有客戶端交互、日志復(fù)制等，一般一次只有一個Leader
- Follower：類似選民
- Candidate：候選人，可以被選為一個新的Leader
Raft算法的大致過程可以總結(jié)為：首先是Leader選舉過程，其次在選舉出來的Leader的基礎(chǔ)上完成正常操作，例如日志復(fù)制和記賬等。
1.任何一個服務(wù)器都可以成為一個Candidate，它向其他服務(wù)器Follower發(fā)出要求選舉自己的請求；
2.其他服務(wù)器同意了，發(fā)出OK；
3.Candidate就成為了Leader，它可以向選民也就是Follower發(fā)出指令，比如進行日志復(fù)制；
4.以后通過心跳進行日志復(fù)制的通知；
5.一旦這個Leader宕機崩潰了，那么Follower中有一個成為Candidate，發(fā)出邀票選舉；
6.Follower同意后，其成為Leader，繼續(xù)承擔(dān)日志復(fù)制等指導(dǎo)工作。
