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

行業(yè)新聞

分布式強一致性算法

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

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

Raft是一種基于Paxos的分布式一致性協(xié)議，相比于Paxos，它更加容易理解和實現(xiàn)，并且能夠保證正確性和算法性能。Raft在最初就是從工程的角度設(shè)計的，充分考慮了在現(xiàn)實中實現(xiàn)時可能存在的問題，并予以優(yōu)化或規(guī)避。當集群系統(tǒng)內(nèi)某個節(jié)點出現(xiàn)故障時，只要集群內(nèi)仍存在多數(shù)節(jié)點，就能保證分布式系統(tǒng)的可用性和數(shù)據(jù)一致性。

Raft將分布式數(shù)據(jù)庫系統(tǒng)的節(jié)點進行抽象，稱為復(fù)制狀態(tài)機（Replicated State Machine）。假設(shè)狀態(tài)機的初始狀態(tài)相同，在系統(tǒng)運行期間，只要每個狀態(tài)機按照完全相同的序列執(zhí)行同樣的操作，那么它們的最終狀態(tài)就是一致的。如果映射到網(wǎng)絡(luò)操作系統(tǒng)中，操作即網(wǎng)絡(luò)狀態(tài)變化、流表變化，操作序列即網(wǎng)絡(luò)狀態(tài)變化、流表增刪的順序。因此，保證操作和操作序列的一致性，就能保證狀態(tài)機節(jié)點數(shù)據(jù)的一致性。

在分布式系統(tǒng)中，每個節(jié)點均對設(shè)備具有感知、管控的權(quán)利，針對每個設(shè)備，彈性通信網(wǎng)絡(luò)操作系統(tǒng)或為Master角色或為Slave角色，由彈性通信網(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)之間采用單點更新的方式實現(xiàn)集群節(jié)點數(shù)據(jù)的一致性。集群節(jié)點之間通過選舉產(chǎn)生一個主節(jié)點，該主節(jié)點只作為集群節(jié)點之間的數(shù)據(jù)提交決策節(jié)點，所有變化的數(shù)據(jù)均需要通過該主節(jié)點進行決策是否滿足集群內(nèi)的同步狀態(tài)，完成系統(tǒng)內(nèi)的數(shù)據(jù)同步。集群節(jié)點的狀態(tài)分為三種：主節(jié)點（Leader）、從節(jié)點（Follower）、候選節(jié)點（Candidate）。

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

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

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



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

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

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

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

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

（5）候選節(jié)點收到來自大多數(shù)（過半）從節(jié)點的投票后，則成為新的主節(jié)點。

為保證集群內(nèi)彈性通信網(wǎng)絡(luò)操作系統(tǒng)拓撲信息、流表信息的一致性，需要實現(xiàn)上述信息的同步，其具體的信息同步流程如下。

（1）某一節(jié)點發(fā)現(xiàn)拓撲改變或流表改變，向主節(jié)點發(fā)送寫請求。

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

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

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

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

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

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

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

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

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

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

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

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

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

<
在線咨詢 ×

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