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

高石玉，艾中良，劉忠麟

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

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

高石玉，艾中良，劉忠麟

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

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 Fast Paxos Leader選舉流程

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)

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

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

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

圖4 節(jié)點(diǎn)加入性能實(shí)驗(yàn)結(jié)果圖

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

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

6 結(jié)束語

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

[1]黃遠(yuǎn)強(qiáng)，欒鐘治，錢德沛.一種面向大規(guī)模P2P環(huán)境的成員管理機(jī)制[J].計(jì)算機(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)域?yàn)榉植际接?jì)算技術(shù)。E-mail：gig05281215@gmail.com

2012-05-03

2012-07-03

1002-8331（2014）06-0088-04