分布式系統(tǒng)中有個(gè)著名的原則CAP原則，C為Consistency(一致性)、A為Availability(可用性)、P為Partition tolerance(分區(qū)容錯(cuò)性)。這里主要介紹下分布式環(huán)境下如果達(dá)到一致性。
說到一致性不得不說下經(jīng)典的拜占庭問題。
拜占庭問題
話說一組拜占庭將軍分別各率領(lǐng)一支軍隊(duì)共同圍困一座城市。為了簡(jiǎn)化問題，將各支軍隊(duì)的行動(dòng)策略限定為進(jìn)攻或撤離兩種。因?yàn)椴糠周婈?duì)進(jìn)攻部分軍隊(duì)撤離可能會(huì)造成災(zāi)難性后果，因此各位將軍必須通過投票來達(dá)成一致策略，即所有軍隊(duì)一起進(jìn)攻或所有軍隊(duì)一起撤離。因?yàn)楦魑粚④姺痔幊鞘胁煌较?，他們只能通過信使互相聯(lián)系。在投票過程中每位將軍都將自己投票給進(jìn)攻還是撤退的信息通過信使分別通知其他所有將軍，這樣一來每位將軍根據(jù)自己的投票和其他所有將軍送來的信息就可以知道共同的投票結(jié)果而決定行動(dòng)策略。
系統(tǒng)的問題在于，將軍中可能出現(xiàn)叛徒，他們不僅可能向較為糟糕的策略投票，還可能選擇性地發(fā)送投票信息。假設(shè)有9位將軍投票，其中1名叛徒。8名忠誠的將軍中出現(xiàn)了4人投進(jìn)攻，4人投撤離的情況。這時(shí)候叛徒可能故意給4名投進(jìn)攻的將領(lǐng)送信表示投票進(jìn)攻，而給4名投撤離的將領(lǐng)送信表示投撤離。這樣一來在4名投進(jìn)攻的將領(lǐng)看來，投票結(jié)果是5人投進(jìn)攻，從而發(fā)起進(jìn)攻；而在4名投撤離的將軍看來則是5人投撤離。這樣各支軍隊(duì)的一致協(xié)同就遭到了破壞。
拜占庭問題其實(shí)是指在一個(gè)可妥協(xié)的通信網(wǎng)絡(luò)中實(shí)現(xiàn)分布式協(xié)議的問題，也就是在不可靠的環(huán)境中建立一個(gè)可靠的系統(tǒng)的問題。
假始那些忠誠（或是沒有出錯(cuò)）的將軍仍然能通過多數(shù)決策來決定他們的戰(zhàn)略，便稱達(dá)到了拜占庭容錯(cuò)。
PBFT
PBFT是Practical Byzantine Fault Tolerance的縮寫，意為實(shí)用拜占庭容錯(cuò)算法，復(fù)雜度過高O(N^2)。PBFT是一種狀態(tài)機(jī)副本復(fù)制算法，即服務(wù)作為狀態(tài)機(jī)進(jìn)行建模，狀態(tài)機(jī)在分布式系統(tǒng)的不同節(jié)點(diǎn)進(jìn)行副本復(fù)制。每個(gè)狀態(tài)機(jī)的副本都保存了服務(wù)的狀態(tài)，同時(shí)也實(shí)現(xiàn)了服務(wù)的操作。
PBFT是一個(gè)三階段算法，分為Pre-Prepare、Prepare和Commit。
PBFT中有幾個(gè)概念需要了解下，所有的節(jié)點(diǎn)稱為副本，這些副本有兩個(gè)角色，分別為主節(jié)點(diǎn)(primary)和備份節(jié)點(diǎn)(backups)，所有的副本在一個(gè)被稱為視圖(View)的輪換過程中運(yùn)作。主節(jié)點(diǎn)和備份節(jié)點(diǎn)是針對(duì)視圖而言，視圖是連續(xù)編號(hào)的整數(shù)。在某個(gè)視圖中，從副本中選出一個(gè)副本為主節(jié)點(diǎn)，選擇算法為p = v mod |R|，其中v是視圖編號(hào)，|R|為副本個(gè)數(shù)，p為副本編號(hào)，除主節(jié)點(diǎn)之外所有的節(jié)點(diǎn)都為備份節(jié)點(diǎn)。當(dāng)主節(jié)點(diǎn)失效的時(shí)候就需要啟動(dòng)視圖更換過程。
知道上述概念之后，來看下算法的具體流程：
其中0為主節(jié)點(diǎn)，123為備份節(jié)點(diǎn)，3宕機(jī)無法響應(yīng)請(qǐng)求
主節(jié)點(diǎn)0接收到客戶端C發(fā)來的請(qǐng)求request，給請(qǐng)求分配一個(gè)序列號(hào)n，然后向所有備份節(jié)點(diǎn)群發(fā)預(yù)準(zhǔn)備消息，預(yù)準(zhǔn)備消息的格式為<<PRE-PREPARE,v,n,d>,m>，這里v是視圖編號(hào)，m是客戶端發(fā)送的請(qǐng)求消息，d是請(qǐng)求消息m的摘要。
備份節(jié)點(diǎn)收到主節(jié)點(diǎn)廣播的消息之后，check下自己是否接受，接受之后向其它副本進(jìn)行prepare廣播
某個(gè)副本在接收到2f個(gè)prepare信息之后，向其它副本廣播commit
某個(gè)副本在接收到2f+1個(gè)commit信息之后，向客戶端C發(fā)送reply
客戶端C在接收到f+1個(gè)相同的reply之后則達(dá)成共識(shí)
拜占庭問題是一個(gè)理論性的模型，解決起來比較困難，工程實(shí)踐上可以將其模型的某些條件進(jìn)行假設(shè)，這樣可以解決一些特定的問題。
將集群中是否存在背叛者作為一個(gè)已知條件來將拜占庭問題細(xì)分下：
假如集群中存在背叛者，也就是有一些偽造信息，這種情況稱為拜占庭錯(cuò)誤，偽造信息的節(jié)點(diǎn)稱為拜占庭節(jié)點(diǎn)。其一致性算法為BFT（Byzantine Fault Tolerance），上文介紹的PBFT就是一個(gè)拜占庭容錯(cuò)算法。
如果集群中不存在背叛者，都是忠誠者，只是這些忠誠者由于某種原因無法正常工作，這種情況稱為非拜占庭錯(cuò)誤。其一致性算法為CFT（Crash Fault Tolerance）。
下面我們就介紹兩個(gè)非拜占庭一致性算法Paxos和Raft。
Paxos
Paxos算法為非拜占庭一致性算法，運(yùn)行在允許宕機(jī)故障的異步系統(tǒng)中，不要求可靠的消息傳遞，可容忍消息丟失、延遲、亂序以及重復(fù)。它利用大多數(shù)機(jī)制保證了2F+1的容錯(cuò)能力，即2F+1個(gè)節(jié)點(diǎn)的系統(tǒng)最多允許F個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)故障。
Paxos算法中的角色分為Proposer和Acceptor，Proposer是提案者，用來發(fā)起提案（Proposal），Acceptor是決策者，用來接收和響應(yīng)Proposer提出的提案。這個(gè)算法的場(chǎng)景是一個(gè)或多個(gè)提議進(jìn)程（Proposer）可以發(fā)起提案（Proposal），需要在所有提案中選取某一個(gè)提案，使其在所有進(jìn)程中達(dá)成一致。系統(tǒng)中的多數(shù)派同時(shí)認(rèn)可該提案，即達(dá)成了一致。最多只針對(duì)一個(gè)確定的提案達(dá)成一致。
Paxos算法流程分為兩階段，第一階段為Prepare階段，第二階段為Commit階段。兩階段提交算法的思路大致可以概括為決策者將提案的結(jié)果通知提案者，再由提案者根據(jù)所有決策者反饋的結(jié)果決定是提交操作還是終止操作。
Paxos算法大致流程為Proposer詢問Acceptors是否可以發(fā)起提案，Acceptors將結(jié)果返回給Proposer(第一階段)，再由Proposer根據(jù)Acceptors反饋的結(jié)果決定提案內(nèi)容以及提案是提交還是終止(第二階段)。具體流程如下：
第一階段Prepare階段：
Proposer提出一個(gè)提案時(shí)，每次提案時(shí)都生成一個(gè)全局唯一且遞增的ID，向Acceptors發(fā)送PrepareRequest請(qǐng)求，PrepareRequest請(qǐng)求只攜帶提案ID，而無需攜帶提案內(nèi)容。
Acceptors收到Proposer的請(qǐng)求后，判斷PrepareRequest中的ID是否大于Acceptors記錄的值，如果大于則檢查下是否有已經(jīng)Accept過的提案，有則返回提案中ID最大的那個(gè)提案的value和ID，沒有則返回空值，如果小于Acceptors記錄的值則不響應(yīng)。
第一階段結(jié)束，開始第二階段Commit階段：
Proposer接收到多數(shù)Acceptors的PrepareResponse應(yīng)答之后，從應(yīng)答中選擇提案ID最大對(duì)應(yīng)的value作為本次要發(fā)起的提案。 如果所有應(yīng)答的提案value均為空值，則可以自己隨意決定提案value。然后攜帶當(dāng)前ID，向所有Acceptors發(fā)送AccpetRequest請(qǐng)求。
Accpetors收到AccpetRequest后，判斷AccpetRequest中的ID是否大于等于Acceptors記錄的值，是則持久化當(dāng)前ID和提案內(nèi)容，然后返回給Proposer響應(yīng)AcceptResponse
Proposer收到多數(shù)Acceptors的AcceptResponse后，決議形成。
整個(gè)流程中Acceptors的行為可以概括為兩個(gè)承諾，一個(gè)應(yīng)答。
兩個(gè)承諾：
不再應(yīng)答PrepareRequest中ID小于等于當(dāng)前請(qǐng)求PrepareRequest中ID的請(qǐng)求(是因?yàn)楫?dāng)前PrepareRequest中ID已經(jīng)賦值給minProposal)
不再應(yīng)答AcceptRequest中ID小于當(dāng)前請(qǐng)求AcceptRequest中ID的請(qǐng)求(因?yàn)楫?dāng)前AcceptRequest中ID是上次PrepareRequest請(qǐng)求中ID，所以不再應(yīng)答小于的ID)
一個(gè)應(yīng)答：
不違背之前作出的承諾下，返回自己已經(jīng)Accept過的提案中ID最大的那個(gè)提案的內(nèi)容，如果沒有則返回空值
結(jié)合下面的偽代碼能夠更加深刻理解這兩個(gè)承諾一個(gè)應(yīng)答的含義
算法邏輯為：
獲取一個(gè)ProposalID n，為了保證ProposalID唯一，可采用時(shí)間戳+ServerID生成；
Proposer向所有Acceptors廣播Prepare(n)請(qǐng)求；
Acceptor比較n和minProposal，如果n>minProposal，則minProposal=n，并且將acceptedProposal和acceptedValue返回；
Proposer接收到過半數(shù)回復(fù)后，如果發(fā)現(xiàn)有acceptedValue返回，將所有回復(fù)中acceptedProposal最大的acceptedValue作為本次提案的value，否則可以任意決定本次提案的value；
到這里可以進(jìn)入第二階段，廣播Accept(n,value) 到所有節(jié)點(diǎn)；
Acceptor比較n和minProposal，如果n>=minProposal，則acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否則，返回minProposal。
提議者接收到過半數(shù)請(qǐng)求后，如果發(fā)現(xiàn)有返回值result>n，表示有更新的提議，跳轉(zhuǎn)到1；否則value達(dá)成一致。
原始的Paxos算法(Basic Paxos)只能對(duì)一個(gè)值形成決議，決議的形成至少需要兩次網(wǎng)絡(luò)來回，在高并發(fā)情況下可能需要更多的網(wǎng)絡(luò)來回，極端情況下甚至可能形成活鎖(活鎖–多個(gè)Proposer交替向Acceptors提交PrepareRequest請(qǐng)求，在發(fā)送AccpetRequest請(qǐng)求時(shí)，都因?yàn)镮D發(fā)生更新，Acceptors無法接受AccpetRequest請(qǐng)求，返回ID，是Proposer再次向Acceptors發(fā)送PrepareRequest請(qǐng)求，如此反復(fù)，無法形成共識(shí)。)。更重要的是如果想連續(xù)確定多個(gè)值，Basic Paxos無法確定了。因此Basic Paxos幾乎只是用來做理論研究，并不直接應(yīng)用在實(shí)際工程中。
實(shí)際應(yīng)用中幾乎都需要連續(xù)確定多個(gè)值，而且希望能有更高的效率。Multi-Paxos正是為解決此問題而提出。Multi-Paxos基于Basic Paxos做了兩點(diǎn)改進(jìn)：
針對(duì)每一個(gè)要確定的值，運(yùn)行一次Paxos算法實(shí)例（Instance），形成決議。每一個(gè)Paxos實(shí)例使用唯一的Instance ID標(biāo)識(shí)。
在所有Proposers中選舉一個(gè)Leader，由Leader唯一的提交提案給Acceptors進(jìn)行表決。僅有一個(gè)Leader進(jìn)行value提交的情況下，Prepare階段就可以跳過，從而將兩階段變?yōu)橐浑A段，提高效率。同時(shí)這樣沒有Proposer競(jìng)爭(zhēng)，也解決了活鎖問題。
Paxos確實(shí)很強(qiáng)大，而且也可以應(yīng)用于實(shí)際工程中，但是其理論真的很難理解，于是Raft算法出現(xiàn)了，以簡(jiǎn)單著稱，并在工業(yè)上也得到了廣泛的使用。
Raft
Raft也是兩階段提交算法，類似于Multi-Paxos。算法中的角色分為L(zhǎng)eader、Follower和Candidate，但是這三種角色并不是同時(shí)出現(xiàn)的，正常運(yùn)行時(shí)只有Leader和Follower，candidate只作為選舉leader時(shí)的一個(gè)臨時(shí)角色出現(xiàn)。
Leader: 接受客戶端請(qǐng)求，并向Follower同步請(qǐng)求日志，當(dāng)日志同步到大多數(shù)節(jié)點(diǎn)上后告訴Follower提交日志。
Follower: 接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
Candidate: Leader選舉過程中的臨時(shí)角色。
系統(tǒng)在初始化時(shí)，同為Follower，在election timeout之后(各節(jié)點(diǎn)在150-300ms之間隨機(jī))，由Follower轉(zhuǎn)化為Candidate進(jìn)行選舉Leader
Raft算法主要用于管理多副本狀態(tài)機(jī)的日志復(fù)制，并且其將一致性分解為多個(gè)子問題：Leader選舉(Leader election)、日志同步(Log replication)、安全性(Safety)、日志壓縮(Log compaction)、成員變更(Membership change)等。同時(shí)，Raft算法使用了更強(qiáng)的假設(shè)來減少了需要考慮的狀態(tài)，使之變的易于理解和實(shí)現(xiàn)。Raft算法支持最大的容錯(cuò)故障節(jié)點(diǎn)是F，集群總數(shù)為2F+1。
關(guān)注我的公眾號(hào)，后臺(tái)回復(fù)【JAVAPDF】獲取200頁面試題！
5萬人關(guān)注的大數(shù)據(jù)成神之路，不來了解一下嗎？
5萬人關(guān)注的大數(shù)據(jù)成神之路，真的不來了解一下嗎？
5萬人關(guān)注的大數(shù)據(jù)成神之路，確定真的不來了解一下嗎？
