廣州總校區(qū)切換校區(qū)
復(fù)制成功
微信號:togogoi
添加微信好友, 詳細(xì)了解課程
已復(fù)制成功，如果自動跳轉(zhuǎn)微信失敗，請前往微信添加好友
打開微信
圖片

行業(yè)新聞

分布式強(qiáng)一致性算法

發(fā)布時間： 2022-11-10

分布式強(qiáng)一致性算法以Raft算法為基礎(chǔ)進(jìn)行設(shè)計(jì)，在保證分布式節(jié)點(diǎn)狀態(tài)一致的前提下，相比其他算法邏輯簡單、實(shí)現(xiàn)方便，能夠保證控制器集群實(shí)現(xiàn)的簡單性，產(chǎn)生錯誤的概率大為降低。

Raft是一種基于Paxos的分布式一致性協(xié)議，相比于Paxos，它更加容易理解和實(shí)現(xiàn)，并且能夠保證正確性和算法性能。Raft在最初就是從工程的角度設(shè)計(jì)的，充分考慮了在現(xiàn)實(shí)中實(shí)現(xiàn)時可能存在的問題，并予以優(yōu)化或規(guī)避。當(dāng)集群系統(tǒng)內(nèi)某個節(jié)點(diǎn)出現(xiàn)故障時，只要集群內(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)行期間，只要每個狀態(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)中，每個節(jié)點(diǎn)均對設(shè)備具有感知、管控的權(quán)利，針對每個設(shè)備，彈性通信網(wǎng)絡(luò)操作系統(tǒng)或?yàn)镸aster角色或?yàn)镾lave角色，由彈性通信網(wǎng)絡(luò)操作系統(tǒng)之間協(xié)商針對設(shè)備的角色狀態(tài)，Master角色的彈性通信網(wǎng)絡(luò)操作系統(tǒng)具有對設(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)生一個主節(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）。

每個節(jié)點(diǎn)在同一時刻只能擔(dān)任其中一個角色，但在算法運(yùn)行過程中角色可以發(fā)生改變。分布式系統(tǒng)處于非選舉狀態(tài)時，彈性通信網(wǎng)絡(luò)操作系統(tǒng)只存在兩種角色的節(jié)點(diǎn)，即主節(jié)點(diǎn)和從節(jié)點(diǎn)。整個算法的實(shí)現(xiàn)流程包括主節(jié)點(diǎn)選舉（Leader Election）和信息復(fù)制 （Log Replication）兩個階段。主節(jié)點(diǎn)選舉就是通過選舉確定集群的主節(jié)點(diǎn)，并在后面的信息復(fù)制階段中承擔(dān)起主節(jié)點(diǎn)的工作。

圖1展示了選舉過程中三種節(jié)點(diǎn)角色狀態(tài)的轉(zhuǎn)換情況，這是一個不確定性有限自動機(jī)（Non-deterministic Finite Automation，NFA）。隨著選舉的推進(jìn)，節(jié)點(diǎn)可能轉(zhuǎn)變?yōu)槿我唤巧?br>
選舉算法的本質(zhì)是多數(shù)派決議。節(jié)點(diǎn)在選舉開始時會向所有節(jié)點(diǎn)提出預(yù)案，即希望自己能成為新任期內(nèi)的主節(jié)點(diǎn)，各個節(jié)點(diǎn)會對預(yù)案進(jìn)行投票，如果該預(yù)案獲得包括自己在內(nèi)的半數(shù)以上節(jié)點(diǎn)的認(rèn)可，那么該節(jié)點(diǎn)就能成功當(dāng)選。

選舉過程中，任何一個節(jié)點(diǎn)都可能收到多個節(jié)點(diǎn)的預(yù)案投票請求（Request Vote），最終節(jié)點(diǎn)會投票給任期編號最大的預(yù)案。另外，選舉算法規(guī)定在同一任期內(nèi)，每個節(jié)點(diǎn)只有一次投票權(quán)，優(yōu)先到達(dá)的預(yù)案將得到選票，而后來的預(yù)案將被該節(jié)點(diǎn)否決?？梢钥闯觯诓豢紤]日志的情況下，節(jié)點(diǎn)對預(yù)案進(jìn)行投票依據(jù)兩個因素：預(yù)案的任期編號和節(jié)點(diǎn)已投票情況。下面根據(jù)圖1簡要介紹選舉算法的第一輪選舉流程。



圖1　角色狀態(tài)轉(zhuǎn)換圖

（1）一開始，所有的彈性通信網(wǎng)絡(luò)操作系統(tǒng)節(jié)點(diǎn)都是從節(jié)點(diǎn)，此時它們并沒有所屬的主節(jié)點(diǎn)。

（2）當(dāng)從節(jié)點(diǎn)在一段時間內(nèi)未收到主節(jié)點(diǎn)的心跳消息，則定時器超時，變?yōu)楹蜻x節(jié)點(diǎn)。

（3）候選節(jié)點(diǎn)為自己投一票，同時向所有從節(jié)點(diǎn)發(fā)起請求投票。

（4）從節(jié)點(diǎn)收到請求投票消息，如果發(fā)現(xiàn)自己在這個任期還沒有投票，就同意投票，否則不投票，即先到先得的原則。

（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ā)送寫請求。

（2）主節(jié)點(diǎn)收到寫請求后，首先在本地日志中增加一條寫操作記錄，但不提交，接著主節(jié)點(diǎn)把該條日志記錄發(fā)送至分布式系統(tǒng)中的所有節(jié)點(diǎn)。

（3）主節(jié)點(diǎn)等待收到過半其他節(jié)點(diǎn)的寫日志記錄成功的回復(fù)，然后響應(yīng)請求節(jié)點(diǎn)一個寫請求成功的回復(fù)。

（4）主節(jié)點(diǎn)在本地提交日志記錄，同時向所有其他節(jié)點(diǎn)發(fā)起提交日志的請求。

（5）各節(jié)點(diǎn)在本地提交日志記錄。

通過以上步驟保證彈性通信網(wǎng)絡(luò)操作系統(tǒng)集群內(nèi)的拓?fù)錉顟B(tài)、流表狀態(tài)的一致性。

當(dāng)一個節(jié)點(diǎn)從故障中恢復(fù)或剛啟動時，其角色為從節(jié)點(diǎn)，同時啟動一個定時器（Follower Timer）。若從節(jié)點(diǎn)接收到主節(jié)點(diǎn)發(fā)送的心跳消息，會重置定時器，保持從節(jié)點(diǎn)角色狀態(tài)不變。否則，定時器最終會超時，而從節(jié)點(diǎn)認(rèn)為此時集群中沒有有效的主節(jié)點(diǎn)存在，因此，它將轉(zhuǎn)變?yōu)楹蜻x節(jié)點(diǎn)，準(zhǔn)備競爭成為新的主節(jié)點(diǎn)。

候選節(jié)點(diǎn)首先提升自己的任期編號，重置自己的定時器，然后向其他節(jié)點(diǎn)發(fā)出投票請求并等待回復(fù)。之后，候選節(jié)點(diǎn)將可能出現(xiàn)三種情況：

（1）獲得同一任期內(nèi)的過半節(jié)點(diǎn)選票，成為主節(jié)點(diǎn)。

（2）等待期間接收到心跳消息，說明集群中已經(jīng)有節(jié)點(diǎn)當(dāng)選，此時轉(zhuǎn)變?yōu)閺墓?jié)點(diǎn)。

（3）如果前面兩種情況都沒有發(fā)生，候選節(jié)點(diǎn)將持續(xù)等待，直到定時器超時，然后重新發(fā)起新一輪選舉。

某一節(jié)點(diǎn)成為主節(jié)點(diǎn)后，便開始發(fā)送日志信息，并重置其他節(jié)點(diǎn)的定時器。只要主節(jié)點(diǎn)沒有在與其他節(jié)點(diǎn)通信時發(fā)現(xiàn)具有更大任期編號的節(jié)點(diǎn)，會一直保持主節(jié)點(diǎn)這一角色。

上一篇： 分布式最終一致性算法

下一篇： 可重構(gòu)網(wǎng)絡(luò)基礎(chǔ)設(shè)施架構(gòu)

<
在線咨詢 ×

您好，請問有什么可以幫您？我們將竭誠提供最優(yōu)質(zhì)服務(wù)！