在很久很久以前菲宴，拜占庭是東羅馬帝國(guó)的首都。那個(gè)時(shí)候羅馬帝國(guó)國(guó)土遼闊趋急，為了防御目的喝峦，因此每個(gè)軍隊(duì)都分隔很遠(yuǎn)，將軍與將軍之間只能靠信使傳遞消息宣谈。

在打仗的時(shí)候愈犹，拜占庭軍隊(duì)內(nèi)所有將軍必需達(dá)成一致的共識(shí)键科，才能更好地贏得勝利闻丑。但是漩怎，在軍隊(duì)內(nèi)有可能存有叛徒，擾亂將軍們的決定嗦嗡。

這時(shí)候勋锤，在已知有成員不可靠的情況下，其余忠誠(chéng)的將軍需要在不受叛徒或間諜的影響下達(dá)成一致的協(xié)議侥祭。

萊斯利·蘭伯特（?Leslie Lamport?）通過(guò)這個(gè)比喻叁执，表達(dá)了計(jì)算機(jī)網(wǎng)絡(luò)中所存在的一致性問(wèn)題。這個(gè)問(wèn)題被稱為拜占庭將軍問(wèn)題矮冬。

如何解決拜占庭將軍問(wèn)題谈宛，目前業(yè)界有很多成熟的解決方案，其中[Raft算法]是比較具有代表性的胎署，又比較好理解的算法吆录。

什么是 Raft 算法？

Raft 算法是一種簡(jiǎn)單易懂的共識(shí)算法琼牧。它依靠狀態(tài)機(jī)?和?主從同步的方式恢筝，在各個(gè)節(jié)點(diǎn)之間實(shí)現(xiàn)數(shù)據(jù)的一致性。

在學(xué)習(xí)Raft算法的時(shí)候巨坊，大家需要了解Raft的兩個(gè)核心要點(diǎn)：

1.選取主節(jié)點(diǎn)

2.同步數(shù)據(jù)

不難理解撬槽，使用主從同步的方式，可以讓集群各個(gè)節(jié)點(diǎn)的數(shù)據(jù)更新以主節(jié)點(diǎn)為準(zhǔn)趾撵，從而保證了一致性侄柔。那么，如何選取主節(jié)點(diǎn)呢占调？

Raft算法在選擇主節(jié)點(diǎn)的過(guò)程中勋拟，也是通過(guò)多個(gè)節(jié)點(diǎn)之間的投票競(jìng)爭(zhēng)。

說(shuō)到這里妈候，不得不說(shuō)一下Raft算法的狀態(tài)機(jī)敢靡。Raft算法為節(jié)點(diǎn)定義了三種角色：

1.Leader（主節(jié)點(diǎn)）

2.Follower（從節(jié)點(diǎn)）

3.Candidate（參與投票競(jìng)爭(zhēng)的節(jié)點(diǎn)）

讓我們來(lái)看一看選主的具體流程：

第一步，在最初苦银，還沒(méi)有一個(gè)主節(jié)點(diǎn)的時(shí)候啸胧，所有節(jié)點(diǎn)的身份都是Follower。每一個(gè)節(jié)點(diǎn)都有自己的計(jì)時(shí)器幔虏，當(dāng)計(jì)時(shí)達(dá)到了超時(shí)時(shí)間（Election Timeout）纺念，該節(jié)點(diǎn)會(huì)轉(zhuǎn)變?yōu)镃andidate。

第二步想括，成為Candidate的節(jié)點(diǎn)陷谱，會(huì)首先給自己投票，然后向集群中其他所有的節(jié)點(diǎn)發(fā)起請(qǐng)求，要求大家都給自己投票烟逊。

第三步渣窜，其他收到投票請(qǐng)求且還未投票的Follower節(jié)點(diǎn)會(huì)向發(fā)起者投票，發(fā)起者收到反饋通知后宪躯，票數(shù)增加乔宿。

第四步，當(dāng)?shù)闷睌?shù)超過(guò)了集群節(jié)點(diǎn)數(shù)量的一半访雪，該節(jié)點(diǎn)晉升為L(zhǎng)eader節(jié)點(diǎn)详瑞。Leader節(jié)點(diǎn)會(huì)立刻向其他節(jié)點(diǎn)發(fā)出通知，告訴大家自己才是老大臣缀。收到通知的節(jié)點(diǎn)全部變?yōu)镕ollower坝橡，并且各自的計(jì)時(shí)器清零。

這里需要說(shuō)明一點(diǎn)精置，每個(gè)節(jié)點(diǎn)的超時(shí)時(shí)間都是不一樣的驳庭。比如A節(jié)點(diǎn)的超時(shí)時(shí)間是3秒，B節(jié)點(diǎn)的超時(shí)時(shí)間是5秒氯窍，C節(jié)點(diǎn)的超時(shí)時(shí)間是4秒饲常。這樣一來(lái)，A節(jié)點(diǎn)將會(huì)最先發(fā)起投票請(qǐng)求狼讨，而不是所有節(jié)點(diǎn)同時(shí)發(fā)起贝淤。

為什么這樣設(shè)計(jì)呢？設(shè)想如果所有節(jié)點(diǎn)同時(shí)發(fā)起投票政供，必然會(huì)導(dǎo)致大家的票數(shù)差不多播聪，形成僵局，誰(shuí)也當(dāng)不成老大布隔。

那么离陶，成為L(zhǎng)eader的節(jié)點(diǎn)是否就坐穩(wěn)了老大的位置呢？并不是衅檀。Leader節(jié)點(diǎn)需要每隔一段時(shí)間向集群其他節(jié)點(diǎn)發(fā)送心跳通知招刨，表明你們的老大還活著。

一旦Leader節(jié)點(diǎn)掛掉哀军，發(fā)不出通知沉眶，那么計(jì)時(shí)達(dá)到了超時(shí)時(shí)間的Follower節(jié)點(diǎn)會(huì)轉(zhuǎn)變?yōu)镃andidate節(jié)點(diǎn)，發(fā)起選主投票杉适，周而復(fù)始......

讓我們來(lái)看一看數(shù)據(jù)同步的流程：

第一步谎倔，由客戶端提交數(shù)據(jù)到Leader節(jié)點(diǎn)。

第二步猿推，由Leader節(jié)點(diǎn)把數(shù)據(jù)復(fù)制到集群內(nèi)所有的Follower節(jié)點(diǎn)片习。如果一次復(fù)制失敗，會(huì)不斷進(jìn)行重試。

第三步藕咏，F(xiàn)ollower節(jié)點(diǎn)們接收到復(fù)制的數(shù)據(jù)状知，會(huì)反饋給Leader節(jié)點(diǎn)。

第四步侈离，如果Leader節(jié)點(diǎn)接收到超過(guò)半數(shù)的Follower反饋，表明復(fù)制成功筝蚕。于是提交自己的數(shù)據(jù)卦碾，并通知客戶端數(shù)據(jù)提交成功。

第五步起宽，由Leader節(jié)點(diǎn)通知集群內(nèi)所有的Follower節(jié)點(diǎn)提交數(shù)據(jù)洲胖，從而完成數(shù)據(jù)同步流程。

共識(shí)算法的應(yīng)用場(chǎng)景坯沪？

在用于共享配置和服務(wù)發(fā)現(xiàn)的K-V存儲(chǔ)系統(tǒng)[etcd]中绿映，使用的就是Raft算法來(lái)保證分布式的一致性。

還有其他算法腐晾，如下：

Paxos 算法：

早期的共識(shí)算法叉弦，由拜占庭將軍問(wèn)題的提出者Leslie Lamport?所發(fā)明。谷歌的分布式鎖服務(wù)?Chubby 就是以 Paxos 算法為基礎(chǔ)藻糖。

ZAB 算法：

Zookeeper 所使用的一致性算法淹冰，在流程上和 Raft 算法比較接近。

PBFT 算法：

區(qū)塊鏈技術(shù)所使用的共識(shí)算法之一巨柒，適用于私有鏈的共識(shí)樱拴。

轉(zhuǎn)載：程序員小灰