分布式強(qiáng)一致性算法
發(fā)布時(shí)間：
2022-11-10
分布式強(qiáng)一致性算法以Raft算法為基礎(chǔ)進(jìn)行設(shè)計(jì)，在保證分布式節(jié)點(diǎn)狀態(tài)一致的前提下，相比其他算法邏輯簡(jiǎn)單、實(shí)現(xiàn)方便，能夠保證控制器集群實(shí)現(xiàn)的簡(jiǎn)單性，產(chǎn)生錯(cuò)誤的概率大為降低。
Raft是一種基于Paxos的分布式一致性協(xié)議，相比于Paxos，它更加容易理解和實(shí)現(xiàn)，并且能夠保證正確性和算法性能。Raft在最初就是從工程的角度設(shè)計(jì)的，充分考慮了在現(xiàn)實(shí)中實(shí)現(xiàn)時(shí)可能存在的問題，并予以優(yōu)化或規(guī)避。當(dāng)集群系統(tǒng)內(nèi)某個(gè)節(jié)點(diǎn)出現(xiàn)故障時(shí)，只要集群內(nèi)仍存在多數(shù)節(jié)點(diǎn)，就能保證分布式系統(tǒng)的可用性和數(shù)據(jù)一致性。
Raft將分布式數(shù)據(jù)庫系統(tǒng)的節(jié)點(diǎn)進(jìn)行抽象，稱為復(fù)制狀態(tài)機(jī)（Replicated State Machine）。假設(shè)狀態(tài)機(jī)的初始狀態(tài)相同，在系統(tǒng)運(yùn)行期間，只要每個(gè)狀態(tài)機(jī)按照完全相同的序列執(zhí)行同樣的操作，那么它們的最終狀態(tài)就是一致的。如果映射到網(wǎng)絡(luò)操作系統(tǒng)中，操作即網(wǎng)絡(luò)狀態(tài)變化、流表變化，操作序列即網(wǎng)絡(luò)狀態(tài)變化、流表增刪的順序。因此，保證操作和操作序列的一致性，就能保證狀態(tài)機(jī)節(jié)點(diǎn)數(shù)據(jù)的一致性。
在分布式系統(tǒng)中，每個(gè)節(jié)點(diǎn)均對(duì)設(shè)備具有感知、管控的權(quán)利，針對(duì)每個(gè)設(shè)備，彈性通信網(wǎng)絡(luò)操作系統(tǒng)或?yàn)镸aster角色或?yàn)镾lave角色，由彈性通信網(wǎng)絡(luò)操作系統(tǒng)之間協(xié)商針對(duì)設(shè)備的角色狀態(tài)，Master角色的彈性通信網(wǎng)絡(luò)操作系統(tǒng)具有對(duì)設(shè)備的資源管控、狀態(tài)獲取的權(quán)利，而Slave角色的彈性通信網(wǎng)絡(luò)操作系統(tǒng)只有狀態(tài)獲取的權(quán)利。
彈性通信網(wǎng)絡(luò)操作系統(tǒng)之間采用單點(diǎn)更新的方式實(shí)現(xiàn)集群節(jié)點(diǎn)數(shù)據(jù)的一致性。集群節(jié)點(diǎn)之間通過選舉產(chǎn)生一個(gè)主節(jié)點(diǎn)，該主節(jié)點(diǎn)只作為集群節(jié)點(diǎn)之間的數(shù)據(jù)提交決策節(jié)點(diǎn)，所有變化的數(shù)據(jù)均需要通過該主節(jié)點(diǎn)進(jìn)行決策是否滿足集群內(nèi)的同步狀態(tài)，完成系統(tǒng)內(nèi)的數(shù)據(jù)同步。集群節(jié)點(diǎn)的狀態(tài)分為三種：主節(jié)點(diǎn)（Leader）、從節(jié)點(diǎn)（Follower）、候選節(jié)點(diǎn)（Candidate）。
每個(gè)節(jié)點(diǎn)在同一時(shí)刻只能擔(dān)任其中一個(gè)角色，但在算法運(yùn)行過程中角色可以發(fā)生改變。分布式系統(tǒng)處于非選舉狀態(tài)時(shí)，彈性通信網(wǎng)絡(luò)操作系統(tǒng)只存在兩種角色的節(jié)點(diǎn)，即主節(jié)點(diǎn)和從節(jié)點(diǎn)。整個(gè)算法的實(shí)現(xiàn)流程包括主節(jié)點(diǎn)選舉（Leader Election）和信息復(fù)制 （Log Replication）兩個(gè)階段。主節(jié)點(diǎn)選舉就是通過選舉確定集群的主節(jié)點(diǎn)，并在后面的信息復(fù)制階段中承擔(dān)起主節(jié)點(diǎn)的工作。
圖1展示了選舉過程中三種節(jié)點(diǎn)角色狀態(tài)的轉(zhuǎn)換情況，這是一個(gè)不確定性有限自動(dòng)機(jī)（Non-deterministic Finite Automation，NFA）。隨著選舉的推進(jìn)，節(jié)點(diǎn)可能轉(zhuǎn)變?yōu)槿我唤巧?br>
選舉算法的本質(zhì)是多數(shù)派決議。節(jié)點(diǎn)在選舉開始時(shí)會(huì)向所有節(jié)點(diǎn)提出預(yù)案，即希望自己能成為新任期內(nèi)的主節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)會(huì)對(duì)預(yù)案進(jìn)行投票，如果該預(yù)案獲得包括自己在內(nèi)的半數(shù)以上節(jié)點(diǎn)的認(rèn)可，那么該節(jié)點(diǎn)就能成功當(dāng)選。
選舉過程中，任何一個(gè)節(jié)點(diǎn)都可能收到多個(gè)節(jié)點(diǎn)的預(yù)案投票請(qǐng)求（Request Vote），最終節(jié)點(diǎn)會(huì)投票給任期編號(hào)最大的預(yù)案。另外，選舉算法規(guī)定在同一任期內(nèi)，每個(gè)節(jié)點(diǎn)只有一次投票權(quán)，優(yōu)先到達(dá)的預(yù)案將得到選票，而后來的預(yù)案將被該節(jié)點(diǎn)否決。可以看出，在不考慮日志的情況下，節(jié)點(diǎn)對(duì)預(yù)案進(jìn)行投票依據(jù)兩個(gè)因素：預(yù)案的任期編號(hào)和節(jié)點(diǎn)已投票情況。下面根據(jù)圖1簡(jiǎn)要介紹選舉算法的第一輪選舉流程。
圖1 角色狀態(tài)轉(zhuǎn)換圖
（1）一開始，所有的彈性通信網(wǎng)絡(luò)操作系統(tǒng)節(jié)點(diǎn)都是從節(jié)點(diǎn)，此時(shí)它們并沒有所屬的主節(jié)點(diǎn)。
（2）當(dāng)從節(jié)點(diǎn)在一段時(shí)間內(nèi)未收到主節(jié)點(diǎn)的心跳消息，則定時(shí)器超時(shí)，變?yōu)楹蜻x節(jié)點(diǎn)。
（3）候選節(jié)點(diǎn)為自己投一票，同時(shí)向所有從節(jié)點(diǎn)發(fā)起請(qǐng)求投票。
（4）從節(jié)點(diǎn)收到請(qǐng)求投票消息，如果發(fā)現(xiàn)自己在這個(gè)任期還沒有投票，就同意投票，否則不投票，即先到先得的原則。
（5）候選節(jié)點(diǎn)收到來自大多數(shù)（過半）從節(jié)點(diǎn)的投票后，則成為新的主節(jié)點(diǎn)。
為保證集群內(nèi)彈性通信網(wǎng)絡(luò)操作系統(tǒng)拓?fù)湫畔?、流表信息的一致性，需要?shí)現(xiàn)上述信息的同步，其具體的信息同步流程如下。
（1）某一節(jié)點(diǎn)發(fā)現(xiàn)拓?fù)涓淖兓蛄鞅砀淖?，向主?jié)點(diǎn)發(fā)送寫請(qǐng)求。
（2）主節(jié)點(diǎn)收到寫請(qǐng)求后，首先在本地日志中增加一條寫操作記錄，但不提交，接著主節(jié)點(diǎn)把該條日志記錄發(fā)送至分布式系統(tǒng)中的所有節(jié)點(diǎn)。
（3）主節(jié)點(diǎn)等待收到過半其他節(jié)點(diǎn)的寫日志記錄成功的回復(fù)，然后響應(yīng)請(qǐng)求節(jié)點(diǎn)一個(gè)寫請(qǐng)求成功的回復(fù)。
（4）主節(jié)點(diǎn)在本地提交日志記錄，同時(shí)向所有其他節(jié)點(diǎn)發(fā)起提交日志的請(qǐng)求。
（5）各節(jié)點(diǎn)在本地提交日志記錄。
通過以上步驟保證彈性通信網(wǎng)絡(luò)操作系統(tǒng)集群內(nèi)的拓?fù)錉顟B(tài)、流表狀態(tài)的一致性。
當(dāng)一個(gè)節(jié)點(diǎn)從故障中恢復(fù)或剛啟動(dòng)時(shí)，其角色為從節(jié)點(diǎn)，同時(shí)啟動(dòng)一個(gè)定時(shí)器（Follower Timer）。若從節(jié)點(diǎn)接收到主節(jié)點(diǎn)發(fā)送的心跳消息，會(huì)重置定時(shí)器，保持從節(jié)點(diǎn)角色狀態(tài)不變。否則，定時(shí)器最終會(huì)超時(shí)，而從節(jié)點(diǎn)認(rèn)為此時(shí)集群中沒有有效的主節(jié)點(diǎn)存在，因此，它將轉(zhuǎn)變?yōu)楹蜻x節(jié)點(diǎn)，準(zhǔn)備競(jìng)爭(zhēng)成為新的主節(jié)點(diǎn)。
候選節(jié)點(diǎn)首先提升自己的任期編號(hào)，重置自己的定時(shí)器，然后向其他節(jié)點(diǎn)發(fā)出投票請(qǐng)求并等待回復(fù)。之后，候選節(jié)點(diǎn)將可能出現(xiàn)三種情況：
（1）獲得同一任期內(nèi)的過半節(jié)點(diǎn)選票，成為主節(jié)點(diǎn)。
（2）等待期間接收到心跳消息，說明集群中已經(jīng)有節(jié)點(diǎn)當(dāng)選，此時(shí)轉(zhuǎn)變?yōu)閺墓?jié)點(diǎn)。
（3）如果前面兩種情況都沒有發(fā)生，候選節(jié)點(diǎn)將持續(xù)等待，直到定時(shí)器超時(shí)，然后重新發(fā)起新一輪選舉。
某一節(jié)點(diǎn)成為主節(jié)點(diǎn)后，便開始發(fā)送日志信息，并重置其他節(jié)點(diǎn)的定時(shí)器。只要主節(jié)點(diǎn)沒有在與其他節(jié)點(diǎn)通信時(shí)發(fā)現(xiàn)具有更大任期編號(hào)的節(jié)點(diǎn)，會(huì)一直保持主節(jié)點(diǎn)這一角色。
上一篇：
分布式最終一致性算法
下一篇：
可重構(gòu)網(wǎng)絡(luò)基礎(chǔ)設(shè)施架構(gòu)
騰科IT教育
