高石玉，艾中良，劉忠麟

華北計算技術(shù)研究所總體部，北京 100083

應(yīng)用Paxos算法構(gòu)建自組織網(wǎng)絡(luò)

高石玉，艾中良，劉忠麟

華北計算技術(shù)研究所總體部，北京 100083

著重闡述如何利用Paxos算法構(gòu)建多節(jié)點自組織網(wǎng)絡(luò)，提出利用該算法完成實時更新、同步節(jié)點全局視圖的工作。結(jié)合該算法的開源實現(xiàn)開發(fā)出功能完善的原型系統(tǒng)，彌補開源實現(xiàn)中部分功能缺失所帶來的應(yīng)用缺陷。通過相關(guān)實驗測定其具有在秒級時間內(nèi)完成節(jié)點快速加入以及退出的能力。證明其具備在實際應(yīng)用場景中進行部署的能力，可以滿足各種分布式應(yīng)用程序?qū)Φ讓幼越M織網(wǎng)絡(luò)的高可靠性以及高可用性要求。

自組織網(wǎng)絡(luò)；Paxos算法；網(wǎng)絡(luò)自動重組

1 引言

分布式計算技術(shù)具有大規(guī)模，分散控制以及動態(tài)改變的特點，同時作為分布式計算技術(shù)的基礎(chǔ)組成部分，節(jié)點自組織網(wǎng)絡(luò)的構(gòu)建設(shè)計也應(yīng)貼合上層的應(yīng)用場景和特點[1]。隨著云計算技術(shù)的快速發(fā)展，分布式計算也朝著低成本，高可用性，高擴展性的特點發(fā)展，每一個計算節(jié)點也從高穩(wěn)定性、高成本的高性能計算機轉(zhuǎn)變?yōu)樾阅芤话?，不可靠但成本低廉的商用PC機的方向發(fā)展[2]。而同時支撐多個節(jié)點的自組織網(wǎng)也應(yīng)針對底層設(shè)備的變化使其具有快速組建，迅速重組的能力保證上層的應(yīng)用的高可靠性及高可用性。

同時節(jié)點自組織網(wǎng)絡(luò)應(yīng)能夠針對節(jié)點的加入和退出，節(jié)點管理的抗干擾性以及可伸縮性作出保證。從本質(zhì)上說每一個節(jié)點在運行過程中均需要對網(wǎng)絡(luò)中的所運行的拓?fù)浣Y(jié)構(gòu)進行穩(wěn)定的維護。而拓?fù)浣Y(jié)構(gòu)所描述的即是節(jié)點所能夠直接訪問的其他鄰居節(jié)點，在原型系統(tǒng)構(gòu)建中定義所有節(jié)點所見的鄰居節(jié)點視圖即為網(wǎng)絡(luò)的全局節(jié)點視圖，每一個節(jié)點在平穩(wěn)運行狀態(tài)中應(yīng)能夠通過網(wǎng)絡(luò)訪問所有節(jié)點，與所有節(jié)點進行通信。

本文中所設(shè)計的自組織網(wǎng)絡(luò)主要面向大規(guī)模分布式系統(tǒng)中底層基礎(chǔ)網(wǎng)絡(luò)的構(gòu)建，具有輕量級，加入網(wǎng)絡(luò)延遲時間短，節(jié)點退出后網(wǎng)絡(luò)重組延遲小，節(jié)點視圖快速同步的特點。并與傳統(tǒng)的主從式架構(gòu)以及P2P架構(gòu)相區(qū)別但又具有主從式架構(gòu)中系統(tǒng)穩(wěn)定性強，全局狀態(tài)感知迅速的特點亦具有P2P系統(tǒng)安全性強的特點。

借助于開源軟件Zookeeper（Zookeeper為Google所開發(fā)的分布式一致性服務(wù)Chuppy[3]的開源仿制軟件）中所實現(xiàn)的Paxos算法以保證所有節(jié)點因為加入或退出而引起的網(wǎng)絡(luò)快速重組時相互通信次數(shù)最少，時間延遲最低，并且開發(fā)全局配置同步工具以完善系統(tǒng)整體功能。在Lamport的論文[4-5]論述了相關(guān)的算法，并且在其論文[6]中論述了該算法改進算法Fast Paxos，該算法可以有效減少節(jié)點在達成狀態(tài)一致的過程中所需的通信次數(shù)。不同于傳統(tǒng)的Master-Slaves架構(gòu)方式或完全分布式P2P架構(gòu)，Paxos算法實現(xiàn)中采用了Master-Slaves架構(gòu)與P2P架構(gòu)相混合的方式。在網(wǎng)絡(luò)構(gòu)建過程之初和構(gòu)建過程中所有節(jié)點均是對等節(jié)點，當(dāng)網(wǎng)絡(luò)構(gòu)建過程完成后即產(chǎn)生Master節(jié)點（以下將其稱為Leader），其他節(jié)點即為Slave節(jié)點（以下將其稱為Follower）。當(dāng)網(wǎng)絡(luò)組建或重組時每個節(jié)點在最壞情況下只需進行三次通信即可完成組網(wǎng)，即Leader選舉過程。之后Leader每隔0.5 s向所有Follower節(jié)點發(fā)送心跳信息以判斷每個Follower節(jié)點的存活狀態(tài)。若某一節(jié)點對心跳信息未作出回應(yīng)則Leader節(jié)點隨即通知其他存活節(jié)點進入網(wǎng)絡(luò)重組過程。若各Follower節(jié)點定期未收到從Leader發(fā)來的心跳請求信息則認(rèn)為Leader節(jié)點發(fā)生故障，亦進入網(wǎng)絡(luò)重組過程，具體過程在第3章著重論述。

2 相關(guān)工作

分布式自組織覆蓋網(wǎng)絡(luò)構(gòu)建模式的變化經(jīng)歷了集中式、分布式兩個階段。

2.1 集中式自組織網(wǎng)絡(luò)構(gòu)建技術(shù)

集中式對等網(wǎng)絡(luò)模式由一個中心服務(wù)器來負(fù)責(zé)維護自組織網(wǎng)絡(luò)環(huán)境中的全局節(jié)點視圖，所有的節(jié)點通過注冊的方式登陸網(wǎng)絡(luò)更新全局視圖，并以向中心服務(wù)器心跳方式聲明存活狀態(tài)。這種形式具有中心化的特點，而集中式P2P模式[7]中心服務(wù)器只進行全局節(jié)點列表服務(wù)，此外服務(wù)器與對等實體以及對等實體之間都具有交互能力，中心服務(wù)器不會干涉所有對等節(jié)點之間的通信，也不會對通信進行轉(zhuǎn)發(fā)。

集中式自組織網(wǎng)絡(luò)最主要的問題表現(xiàn)為中央服務(wù)器的癱瘓容易導(dǎo)致整個網(wǎng)絡(luò)的崩潰，可靠性和安全性較低。

2.2 分布式對等網(wǎng)絡(luò)構(gòu)建技術(shù)

在分布式對等網(wǎng)絡(luò)中[7-8]，對等機通過與相鄰對等機之間的連接遍歷整個網(wǎng)絡(luò)體系。每個對等機在功能上都是相似的，并沒有專門的服務(wù)器，而對等機必須依靠它們所在的分布網(wǎng)絡(luò)來定位其他對等機。

分布式對等網(wǎng)絡(luò)模型也存在很多弊端，主要表現(xiàn)在以下方面：

（1）在上層的應(yīng)用中每一次的搜索請求要經(jīng)過整個網(wǎng)絡(luò)或者至少是一個很大的范圍才能得到結(jié)果。因此，這種模式占用很多帶寬，而且需要花費很長時間才能有返回結(jié)果。

（2）隨著網(wǎng)絡(luò)規(guī)模的擴大，通過擴散方式定位對等點方法將會造成網(wǎng)絡(luò)流量急劇增加，從而導(dǎo)致網(wǎng)絡(luò)擁塞，使得查詢訪問只能在網(wǎng)絡(luò)很小的范圍內(nèi)進行，因此，網(wǎng)絡(luò)的可擴展性不好。

（3）純分布式的P2P模式很難被企業(yè)所利用，因為它缺少對網(wǎng)絡(luò)上的用戶節(jié)點數(shù)以及對它們提供的資源的一個總體把握[9]。

2.3 自組織網(wǎng)絡(luò)相關(guān)研究進展

集中式自組織網(wǎng)絡(luò)構(gòu)建模式有利于網(wǎng)絡(luò)資源的快速檢索，并且只要服務(wù)器能力足夠強大就可以無限擴展，但是其中心化的模式容易遭到直接的攻擊；分布式自組織網(wǎng)絡(luò)構(gòu)建模式解決了抗攻擊問題，但是又缺乏快速搜索和可擴展性。自組織網(wǎng)絡(luò)構(gòu)建的最新模式結(jié)合了集中式和分布式自組織網(wǎng)絡(luò)構(gòu)建模式的優(yōu)點，在設(shè)計思想和處理能力上都得到了進一步的優(yōu)化，它在分布式模式的基礎(chǔ)上，將用戶節(jié)點按能力進行分類，使某些節(jié)點擔(dān)任特殊的任務(wù)，這些節(jié)點共分為三種：

（1）用戶節(jié)點：普通節(jié)點，它不具有任何特殊的功能。

（2）搜索節(jié)點：處理搜索請求，從它們的“孩子”節(jié)點中搜索文件列表。

（3）索引節(jié)點：連接速度快、內(nèi)存充足的節(jié)點可以作為索引節(jié)點。索引節(jié)點用于保存可以利用的搜索節(jié)點信息，并搜集狀態(tài)信息，維護網(wǎng)絡(luò)結(jié)構(gòu)信息。

這種新型的架構(gòu)主要使用于文件共享以及信息搜索等應(yīng)用場景但在維護節(jié)點視圖的功能上仍存在不足，不能使所有節(jié)點均具備快速感知能力，并且節(jié)點的角色劃分亦需要從全局的應(yīng)用進行考慮，應(yīng)盡量使其部署分散化，提高系統(tǒng)整體的運行效率。故在實際應(yīng)用之前該種架構(gòu)仍需要不斷完善。

3 Paxos算法以及Zookeeper實現(xiàn)

Paxos算法最初的應(yīng)用場景為在一個分布式環(huán)境中如何就某個值（決議）達成一致。一個典型的場景是，在一個分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點的初始狀態(tài)一致，每個節(jié)點都執(zhí)行相同的操作序列，那么它們最后能得到一個一致的狀態(tài)。為保證每個節(jié)點執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個“一致性算法”以保證每個節(jié)點看到的指令一致。一個通用的一致性算法可以應(yīng)用在許多場景中，是分布式計算中的重要問題。Paxos算法就是一種基于消息傳遞模型的一致性算法。

本文使用Apache開源基金會的Zookeeper項目的源代碼進行修改，主要使用其Fast Paxos算法的相關(guān)實現(xiàn)，并去掉了其自身的輕量級數(shù)據(jù)庫模塊。以下分析論述其詳細(xì)的實現(xiàn)原理以及過程。

在系統(tǒng)中Leader節(jié)點選舉的過程即為各個節(jié)點狀態(tài)同步過程也即網(wǎng)絡(luò)自組過程。每一個節(jié)點的全局視圖將在該過程后保持一致并且在此過程之后可與任一節(jié)點通信。

Leader節(jié)點的選舉算法按照Fast Paxos算法所述，將通過每個節(jié)點之間的相互三次通信完成節(jié)點選舉工作，在最后一步通信過程中每一個節(jié)點都將會知道所選舉出的Leader節(jié)點的id以及IP地址等信息。并且當(dāng)選舉過程結(jié)束后每個節(jié)點的狀態(tài)也將由Looking狀態(tài)更改為Leading狀態(tài)或者Following狀態(tài)。同時進入相應(yīng)子模塊所維護的運行狀態(tài)。

當(dāng)某一節(jié)點進入選舉過程之中后首先向所有在配置文件中peer發(fā)送選舉開始請求notification，該消息中存在peer的zxid（節(jié)點運行過程編號，根據(jù)節(jié)點運行了的時間所確定）以及本節(jié)點id號；進入選舉過程所定義的循環(huán)體，該循環(huán)體的跳出條件為已經(jīng)選舉出了結(jié)果或者該節(jié)點停止運行；循環(huán)體中首先從異步消息隊列中提取消息，根據(jù)消息中的顯示的狀態(tài)進行不同的處理。在消息中存在用于表示當(dāng)前選舉的編號的epoch變量。

第二步該節(jié)點判斷消息中的epoch值是否與自己的epoch相同，若小于則認(rèn)定該消息已經(jīng)過期進行丟棄處理。若大于則更新自身所保存的epoch變量的值，接下來判斷消息中的zxid以及id是否大于自己的zxid（運行時間越久的節(jié)點應(yīng)為Leader）以及id并根據(jù)判斷結(jié)果更新下一輪投票的選票中的zxid值以及id值，并向所有其他的節(jié)點發(fā)出自己的選票消息，并且在該消息中加入節(jié)點自身的消息狀態(tài)即Looking如圖1所示。

圖1 Fast Paxos Leader選舉流程

結(jié)束該過程后，讀取消息隊列中其他節(jié)點發(fā)送給自身的選票消息并判斷是否收到了全部的選票且所有其他節(jié)點均認(rèn)為自身為Leader，如果是則更新自己的狀態(tài)為Leading，并向其他節(jié)點發(fā)送通知，跳出循環(huán)。如果否則判斷是否有其他節(jié)點被推舉為Leader，如果滿足亦跳出循環(huán)，結(jié)束選舉會收到某一節(jié)點所發(fā)出的其當(dāng)選為Leader的消息，更新相應(yīng)的變量的值，記錄Leader節(jié)點的id，ip地址信息。

當(dāng)Leader節(jié)點選舉結(jié)束之后，各個節(jié)點進入平穩(wěn)運行狀態(tài)除非發(fā)生新節(jié)點加入或者其他節(jié)點失效的情況下則其狀態(tài)不會變更。

程序會判斷節(jié)點的運行狀態(tài)如圖2所示，如果為Following狀態(tài)則會定期向Leader節(jié)點發(fā)送心跳信息的回應(yīng)信息通報該節(jié)點的存活狀態(tài)。如果為Leading狀態(tài)則定期向每個節(jié)點發(fā)送心跳并檢查每個節(jié)點的心跳回傳信息，如果有節(jié)點在一定時間內(nèi)沒有向其發(fā)送心跳信息則認(rèn)為該節(jié)點已經(jīng)斷開連接則將狀態(tài)切換為Looking狀態(tài)，重新開始選舉Leader節(jié)點。

圖2 選舉過程結(jié)束后節(jié)點狀態(tài)變化

4 配置同步模塊設(shè)計

經(jīng)過源碼級別的調(diào)研以及相關(guān)的實驗后發(fā)現(xiàn)在Zookeeper的組網(wǎng)模式中如果一個節(jié)點的配置文件中所寫入的關(guān)于其他節(jié)點的IP地址以及各個通信端口號不全或者不正確則會出現(xiàn)節(jié)點之間不能夠通信并且無法組建自組織覆蓋網(wǎng)絡(luò)的問題。為了解決這種問題使節(jié)點能夠在配置信息不全甚至出現(xiàn)一定錯誤的情況下能夠具有糾錯能力的加入或者組建自組織覆蓋網(wǎng)絡(luò)設(shè)計了配置同步子模塊。該子模塊將會在節(jié)點組建或加入網(wǎng)絡(luò)之前與配置文件中聲明的第一個存活節(jié)點（該節(jié)點可為任意狀態(tài)）的節(jié)點視圖配置同步模塊通信，保證其對于配置中的全局視圖的完整性以及正確性。

如圖3所示節(jié)點視圖維護子模塊運行模式，當(dāng)節(jié)點結(jié)束配置過程后進入運行模式，會根據(jù)在配置中聲明的其他各個節(jié)點的IP地址以及相應(yīng)的維護視圖數(shù)據(jù)端口號發(fā)送連接請求，其他節(jié)點當(dāng)監(jiān)聽到有連接請求后即會作出反應(yīng)并建立連接，之后更新本節(jié)點配置信息。請求節(jié)點會接收該配置信息并更新自己的配置文件與配置變量，完成后會向被連接節(jié)點回傳其更新后的配置信息，被連接節(jié)點也會更新其配置信息，如果未發(fā)現(xiàn)其配置信息不全或不正確則直接向所有節(jié)點發(fā)送Leader節(jié)點重選命令，如果有新的配置信息項則根據(jù)自身所處狀態(tài)作出適當(dāng)反應(yīng)，之后均會進入節(jié)點重選過程。該過程亦只需要新加入節(jié)點與處于網(wǎng)絡(luò)中節(jié)點的三次通信即可完成，不會對加入過程增加時間上的巨大延遲與性能上的嚴(yán)重影響，相應(yīng)的實驗結(jié)果在第5章中給出。

圖3 節(jié)點配置同步流程

5 實驗

為了驗證系統(tǒng)性能設(shè)計了兩個實驗分別測試節(jié)點的加入性能以及節(jié)點退出后的網(wǎng)絡(luò)重組性能。實驗的硬件環(huán)境如下：18臺商用臺式計算機，CPU為Intel Core2 Q9500主頻為2.83 GHz，1.96 GB內(nèi)存，250 GB硬盤，千兆以太網(wǎng)環(huán)境。

在實驗1中設(shè)計將有18個節(jié)點逐個加入到自組織網(wǎng)絡(luò)之中，且每個節(jié)點只具有自身的配置信息以及比其ID小的任一節(jié)點的配置信息，即節(jié)點1只具有其自身配置信息，沒有其他節(jié)點的IP地址以及端口號的配置信息。節(jié)點2只具有自身以及節(jié)點1的配置信息，以此類推，節(jié)點6只具有自身以及節(jié)點1～5的任意節(jié)點配置信息。

每隔5 s啟動一個節(jié)點，確保每個節(jié)點加入時自組織網(wǎng)已結(jié)束Leader選舉過程。實驗結(jié)果如圖4中所示2號節(jié)點以656 ms與1號節(jié)點即組成網(wǎng)絡(luò)，3～6號節(jié)點加入時間均在1 s以下，從7號節(jié)點到第20號節(jié)點均用1～ 1.2 s時間加入到已有的自組織網(wǎng)絡(luò)中。從結(jié)果中可以看出由于配置信息不全需要首先進行配置同步工作，隨著配置信息數(shù)量的增長，從第6號節(jié)點到第18號節(jié)點均受其影響，但隨著節(jié)點數(shù)目的增加，性能波動不劇烈，在0～1.2 s之間。

圖4 節(jié)點加入性能實驗結(jié)果圖

實驗2中測試當(dāng)某一節(jié)點斷開連接時自組織網(wǎng)絡(luò)重組的性能。從第18號節(jié)點逆序逐個將節(jié)點進程關(guān)閉直到最后剩下兩個節(jié)點，每隔5 s關(guān)閉一個節(jié)點，迫使原有自組織網(wǎng)絡(luò)進行重組并測試其性能，如圖5所示，網(wǎng)絡(luò)重組時間隨節(jié)點數(shù)目減少而降低，均低于800 ms，滿足網(wǎng)絡(luò)快速重組的性能要求。

圖5 節(jié)點退出與網(wǎng)絡(luò)重構(gòu)時間圖

6 結(jié)束語

分布式環(huán)境中每一個計算節(jié)點與存儲節(jié)點均處于相對的不穩(wěn)定環(huán)境之中，這就要求互聯(lián)每一個節(jié)點的自組織網(wǎng)絡(luò)能夠根據(jù)底層硬件資源的變化而變化，針對節(jié)點的加入、退出進行成員發(fā)現(xiàn)與網(wǎng)絡(luò)重組，并要求每一個處于自組織網(wǎng)絡(luò)中的節(jié)點成員視圖保持一致。為了達到該目的研究了Paxos算法預(yù)期相關(guān)的實現(xiàn)，并針對其不足設(shè)計相應(yīng)的功能模塊彌補其由于配置信息不全所造成的組網(wǎng)功能不完善的缺陷。并通過實驗證明在小規(guī)模網(wǎng)絡(luò)中節(jié)點的加入、退出與網(wǎng)絡(luò)重組功能達到了較優(yōu)的性能，并使得節(jié)點全局視圖能夠根據(jù)環(huán)境變化及時地調(diào)整滿足上層應(yīng)用需求。

[1]黃遠強，欒鐘治，錢德沛.一種面向大規(guī)模P2P環(huán)境的成員管理機制[J].計算機研究與發(fā)展，2011（7）.

[2]Armbrust M，F(xiàn)ox A，Griffith R，et al.Above the clouds：a berkeley view of cloud computing，UCB/EECS-2009-28[R]. EECS Department，University of California，Berkeley，2009.

[3]Burrows M.The chubby lock service for loosely-coupled distributed systems[C]//Proceedings of OSDI’06：Seventh Symposium on Operating System Design and Implementation，Seattle，WA，2006.

[4]Lamport L.The part-time parliament，tech rep 49[R].Digital Equipment Corporation Systems Research Center，Palo Alto，Calif，1989.

[5]Lamport L.Paxos made simple[J].ACM SIGACT News，2001，32：18-25.

[6]Lamport L.Fast Paxos[J].Distributed Computing，2006，19（2）：79-103.

[7]Das A，Gupta I，Motivala A.SWIM：scalable weakly consistent infection-style process group membership protocol[C]// Proc of IEEE Int Conf on Dependable Systems and Networks.Piscataway，NJ：IEEE，2002：303-312.

[8]Stoica I，Morris R，Karger D，et al.Chord：a scalable peerto-peer lookup service for internet applications[C]//Proc of SIGCOMM.New York：ACM，2001：149-160.

[9]Ratnasamy S，F(xiàn)rancis P，Handley M，et al.A scalable content-addressable network[C]//Proc of the Conf on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York：ACM，2001：161-172.

GAO Shiyu,AI Zhongliang,LIU Zhonglin

General Department,North China Institute of Computer Technology,Beijing 100083,China

This paper focuses on how to build multi-node sub-network using the Paxos algorithm.It uses the algorithm to complete real-time updates and synchronization of the node’s status in the global view.And it develops a fully functional prototype system based on the related open source implementation to make up for defects in partial loss of function of the open-source.Through the relevant experiment it is proved the nodes can join and exit in seconds.Besides that it is proved the system can meet a variety of distributed applications on the underlying self-organizing network of high reliability and high availability requirements.

self-organizing network;Paxos algorithm;network automatic reorganizing

A

TP316

10.3778/j.issn.1002-8331.1204-0625

GAO Shiyu,AI Zhongliang,LIU Zhonglin.Constructing self-organizing network using Paxos algorithm.Computer Engineering and Applications,2014,50（6）：88-91.

高石玉（1986—），男，助理工程師，研究領(lǐng)域為分布式計算技術(shù)。E-mail：gig05281215@gmail.com

2012-05-03

2012-07-03

1002-8331（2014）06-0088-04