最近在學(xué)習(xí)關(guān)于一致性算法的相關(guān)知識(shí)，重點(diǎn)學(xué)習(xí)了Paxos算法以及Zab協(xié)議。Paxos算法是Lamport提出來(lái)的，主要為了解決分布式系統(tǒng)的一致性問(wèn)題，即每臺(tái)機(jī)子看到的值應(yīng)該是一致的。Zab協(xié)議主要使用在zk上，主要場(chǎng)景在故障恢復(fù)與信號(hào)廣播。
Paxos協(xié)議
主要目標(biāo)
多個(gè)節(jié)點(diǎn)之間就某個(gè)值（提案value）達(dá)成一致（決議）的通信協(xié)議，也就是說(shuō)，每個(gè)節(jié)點(diǎn) 提出的提案 會(huì) 對(duì) 同一個(gè)提案內(nèi)容 達(dá)成一。下面簡(jiǎn)稱提案ID為 ProposalID，提案內(nèi)容為value。
主要過(guò)程
在Paxos協(xié)議中，主要有兩個(gè)角色Proposal和Acceptor，除此之外還有Learners。一臺(tái)機(jī)器同時(shí)都會(huì)有這三個(gè)角色。它在提交提案時(shí)是Proposer，接受別人的提案時(shí)候是Acceptor。當(dāng)達(dá)成一致時(shí)，又是Learners。
Paxos算法分為兩個(gè)階段
- prepare階段
1.1
proposer生成全局唯一的ProposalId m，將m發(fā)送給所有的Acceptor
1.2
所有的Acceptor收到提案后，將該提案與已經(jīng)接受的最大提案Id n進(jìn)行判斷
（1）如果 n不存在，即acceptor第一次接受提案，則接受該提案（minProposalID=m），返回空
（2）如果n存在，且n < m，則接受該提案，將m記錄下來(lái)，并將m記錄下來(lái)。（minProposalID=m)，返回最近一個(gè)接受的提案及其值（n，v1)
（3）如果n存在，且n >m， 則拒絕該提案，不返回。
此外acceptor作出承諾，拒絕接受小于m的提案 -
Acceptor階段
經(jīng)過(guò)一段時(shí)間后，Processor接受到Acceptor的回復(fù)。
2.1
如果回復(fù)數(shù)量大于一半機(jī)器，則第一階段成功，proposer向acceptor發(fā)出accept請(qǐng)求<m, value>，value等于回復(fù)中最大ProposalId對(duì)應(yīng)的value，如果所有的機(jī)器都沒(méi)有回復(fù)值，則value由propossor進(jìn)行指定
2.2
如果回復(fù)數(shù)量沒(méi)有超過(guò)一半機(jī)器，則proposer重新生成proposalId，重新進(jìn)行提案。
DX-20200308@2x.png
Zab協(xié)議
zab協(xié)議應(yīng)用于zk系統(tǒng)，zk是分布式系統(tǒng)一致性的解決方案。而zk本身依賴zab協(xié)議進(jìn)行一致性保證。
zab協(xié)議中，有個(gè)關(guān)鍵概念：zxid。zxid是一個(gè)64位的數(shù)字，高32位是當(dāng)前l(fā)eader周期的編號(hào)，也即用來(lái)當(dāng)前是哪一個(gè)leader周期。低32位為事務(wù)Id，隨著事務(wù)提交而遞增。
zk機(jī)器被分為三種：leader，follower以及observer。其中l(wèi)eader負(fù)責(zé)處理寫(xiě)請(qǐng)求，follower負(fù)責(zé)處理讀請(qǐng)求，并將寫(xiě)請(qǐng)求轉(zhuǎn)發(fā)給leader，以及在故障恢復(fù)階段參與選舉，而observer與follower類似，但是沒(méi)有選舉權(quán)。
當(dāng)leader失聯(lián)時(shí)，整個(gè)集群進(jìn)入leader選舉階段。在leader選舉階段，所有的機(jī)子將狀態(tài)標(biāo)記為looking。
1.每臺(tái)follower機(jī)子都申請(qǐng)自己為leader，傳播自身的zxid
2.收到其他機(jī)子的回復(fù)后，選擇zxid最大機(jī)子，并在下一輪投票中，將票投給該機(jī)子。
- 在每輪投票中，票數(shù)超過(guò)一半的機(jī)器勝出，當(dāng)選準(zhǔn)leader。
當(dāng)前階段的leader其實(shí)還只是準(zhǔn)leader，此后需要進(jìn)行同步階段，follower將最大的zxid同步給準(zhǔn)leader，leader收到zxid后確定同步點(diǎn)，并同步給其他follower，補(bǔ)齊缺失的日志，最終達(dá)到整個(gè)集群狀態(tài)一致。最后leader通知follower進(jìn)入update狀態(tài)，又開(kāi)始接受請(qǐng)求。
