gossip協(xié)議
我們的辦公室八卦一般都是從一次交談開(kāi)始，只要一個(gè)人八卦一下撑蚌，在有限的時(shí)間內(nèi)辦公室的的人都會(huì)知道該八卦的信息挠说，這種方式也與病毒傳播類(lèi)似。因此 Gossip也有“病毒感染算法”纯命、“謠言傳播算法”之稱(chēng)西剥。
Cassandra，amazon s3亿汞，等在使用gossip協(xié)議
一般情況是這樣的瞭空，集群中的節(jié)點(diǎn)P隨機(jī)選擇另一個(gè)節(jié)點(diǎn)Q，兩個(gè)節(jié)點(diǎn)互相交換信息留夜，如果Q有消息需要更新的話匙铡，那么Q繼續(xù)去集群中尋找其他的節(jié)點(diǎn)，再次進(jìn)行信息的交換碍粥，就這樣一次次的交換鳖眼，知道所有的節(jié)點(diǎn)消息都為最新的位置.
在Q和P的信息交換，一般有以下3種方式：
- push:P講信息推送給Q嚼摩，Q判斷是否比本地信息新钦讳，如果是的話，更新本地信息
if P.value.time>Q..value.time
Q..value = P.value - pull: P從Q那拉取信息枕面，如果Q的消息比P新愿卒，則更新P的消息
if P.value.time>Q..value.time
P.value = Q..value - push-pull: P和Q同時(shí)進(jìn)行Push和pull
if P.value.time>Q..value.time
Q..value = P.value
else
P.value = Q..value
push剛開(kāi)始傳播快，后來(lái)慢潮秘，pull相反琼开。push-pull模式是最快的
PAXOS協(xié)議
Paxos算法分為兩個(gè)階段。具體如下：
階段一：
(a) Proposer選擇一個(gè)提案編號(hào)N枕荞，然后向半數(shù)以上的Acceptor發(fā)送編號(hào)為N的Prepare請(qǐng)求柜候。
(b) 如果一個(gè)Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求搞动，且N大于該Acceptor已經(jīng)響應(yīng)過(guò)的所有Prepare請(qǐng)求的編號(hào)，那么它就會(huì)將它已經(jīng)接受過(guò)的編號(hào)最大的提案（如果有的話）作為響應(yīng)反饋給Proposer渣刷，同時(shí)該Acceptor承諾不再接受任何編號(hào)小于N的提案鹦肿。階段二：
(a) 如果Proposer收到半數(shù)以上Acceptor對(duì)其發(fā)出的編號(hào)為N的Prepare請(qǐng)求的響應(yīng)，那么它就會(huì)發(fā)送一個(gè)針對(duì)[N,V]提案的Accept請(qǐng)求給半數(shù)以上的Acceptor辅柴。注意：V就是收到的響應(yīng)中編號(hào)最大的提案的value箩溃，如果響應(yīng)中不包含任何提案，那么V就由Proposer自己決定碌嘀。
(b) 如果Acceptor收到一個(gè)針對(duì)編號(hào)為N的提案的Accept請(qǐng)求涣旨，只要該Acceptor沒(méi)有對(duì)編號(hào)大于N的Prepare請(qǐng)求做出過(guò)響應(yīng)，它就接受該提案筏餐。
ZAB協(xié)議
設(shè)計(jì)目標(biāo)
- 一致性
- 有序性：有序性是 Zab 協(xié)議與 Paxos 協(xié)議的一個(gè)核心區(qū)別开泽。Zab 的有序性主要表現(xiàn)在兩個(gè)方面：
a. 全局有序：如果消息 a 在消息 b 之前被投遞，那么在任何一臺(tái)服務(wù)器魁瞪，消息 a都會(huì)在消息 b 之前被投遞穆律。
b. 因果有序：如果消息 a 在消息 b 之前發(fā)生（a 導(dǎo)致了 b），并被一起發(fā)送导俘，則 a 始終在 b 之前被執(zhí)行峦耘。 - 容錯(cuò)性：有 2f+1 臺(tái)服務(wù)器，只要有大于等于 f+1 臺(tái)的服務(wù)器正常工作旅薄，就能完全正常工作辅髓。
協(xié)議內(nèi)容
Zab 協(xié)議分為兩大塊：
- 廣播（boardcast）：Zab 協(xié)議中，所有的寫(xiě)請(qǐng)求都由 leader 來(lái)處理少梁。正常工作狀態(tài)下洛口，leader 接收請(qǐng)求并通過(guò)廣播協(xié)議來(lái)處理。
- 恢復(fù)（recovery）：當(dāng)服務(wù)初次啟動(dòng)凯沪，或者 leader 節(jié)點(diǎn)掛了第焰，系統(tǒng)就會(huì)進(jìn)入恢復(fù)模式，直到選出了有合法數(shù)量 follower 的新 leader妨马，然后新 leader 負(fù)責(zé)將整個(gè)系統(tǒng)同步到最新?tīng)顟B(tài)挺举。
raft協(xié)議
leader選舉：
leader周期性地heartbeat到所有的follower。follower如果能收到leader發(fā)來(lái)的消息烘跺，那么就保持follower狀態(tài)湘纵。如果follower一段時(shí)間收到不消息了，則開(kāi)始新的選主滤淳。
首先當(dāng)前term計(jì)數(shù)加1梧喷，然后給自己投票并向其它結(jié)點(diǎn)發(fā)投票請(qǐng)求。直到以下三種情況：
- 它贏得選舉
- 另一個(gè)服務(wù)器成為leader
- 持續(xù)一段時(shí)間沒(méi)有主機(jī)勝出
在選主期間，candidate可能收到來(lái)自其它自稱(chēng)為leader的寫(xiě)請(qǐng)求铺敌，如果該leader的term不小于candidate的當(dāng)前term绊困，那么candidate承認(rèn)它是一個(gè)合法的leader并回到follower狀態(tài)，否則拒絕請(qǐng)求适刀。
如果出現(xiàn)兩個(gè)candidate得票一樣多，則它們都無(wú)法獲取超過(guò)半數(shù)投票煤蹭。這種情況會(huì)持續(xù)到超時(shí)笔喉。然后進(jìn)行新一輪的選舉。
使用隨機(jī)的選舉超時(shí)硝皂，這樣不容易發(fā)生上面情況常挚。
日志復(fù)制
leader收到client寫(xiě)請(qǐng)求后，先寫(xiě)自己的log稽物，然后發(fā)到所有服務(wù)器奄毡，當(dāng)確認(rèn)記錄已安全復(fù)制后，回應(yīng)client贝或。
每條日志記錄會(huì)存命令以及term編號(hào)吼过，term編號(hào)用于檢測(cè)日志的不一致。
每個(gè)提交的記錄都是持久的咪奖，并且是最終一致的盗忱。當(dāng)log記錄成功復(fù)投票請(qǐng)求中包含了這個(gè)限制：請(qǐng)求中有關(guān)于candidate的log信息制到大多數(shù)服務(wù)器時(shí)，記錄被提交羊赵。如果投票者的log比它新趟佃，則拒絕請(qǐng)求。
沖突解決昧捷，leader通過(guò)強(qiáng)制follower復(fù)制自己的log來(lái)處理不一致闲昭。
安全
舉個(gè)例子，一個(gè)follower可能一段時(shí)間不可用序矩，期間leader持續(xù)提交了多次log，然后這個(gè)follower被選為leader了芹血，那么它會(huì)覆蓋掉提交的記錄。
所以要限制哪些服務(wù)器可以被選為leader幔烛。使用投票過(guò)程阻止candidate選舉中獲勝啃擦，除非它的log包含了所有已提交的記錄饿悬。
因?yàn)橐@得超過(guò)半數(shù)的投票，那么candidate至少要跟大多數(shù)的log一樣新。這樣它擁有所有提交的記錄珠叔。投票請(qǐng)求中包含了這個(gè)限制：請(qǐng)求中有關(guān)于candidate的log信息蝎宇，如果投票者的log比它新，則拒絕請(qǐng)求祷安。
如果follower或candidate崩潰了姥芥，那么發(fā)給它的請(qǐng)求會(huì)失敗，raft將無(wú)限次的重試汇鞭。當(dāng)它恢復(fù)后凉唐，會(huì)繼續(xù)收到未完成的請(qǐng)求。如果一個(gè)服務(wù)器完成了請(qǐng)求但尚未回復(fù)霍骄，接著crash了台囱，那么它重啟后會(huì)收到相同的請(qǐng)求。
