應用Paxos算法構建自組織網絡

高石玉，艾中良，劉忠麟

華北計算技術研究所總體部，北京 100083

應用Paxos算法構建自組織網絡

高石玉，艾中良，劉忠麟

華北計算技術研究所總體部，北京 100083

著重闡述如何利用Paxos算法構建多節點自組織網絡，提出利用該算法完成實時更新、同步節點全局視圖的工作。結合該算法的開源實現開發出功能完善的原型系統，彌補開源實現中部分功能缺失所帶來的應用缺陷。通過相關實驗測定其具有在秒級時間內完成節點快速加入以及退出的能力。證明其具備在實際應用場景中進行部署的能力，可以滿足各種分布式應用程序對底層自組織網絡的高可靠性以及高可用性要求。

自組織網絡；Paxos算法；網絡自動重組

1 引言

分布式計算技術具有大規模，分散控制以及動態改變的特點，同時作為分布式計算技術的基礎組成部分，節點自組織網絡的構建設計也應貼合上層的應用場景和特點[1]。隨著云計算技術的快速發展，分布式計算也朝著低成本，高可用性，高擴展性的特點發展，每一個計算節點也從高穩定性、高成本的高性能計算機轉變為性能一般，不可靠但成本低廉的商用PC機的方向發展[2]。而同時支撐多個節點的自組織網也應針對底層設備的變化使其具有快速組建，迅速重組的能力保證上層的應用的高可靠性及高可用性。

同時節點自組織網絡應能夠針對節點的加入和退出，節點管理的抗干擾性以及可伸縮性作出保證。從本質上說每一個節點在運行過程中均需要對網絡中的所運行的拓撲結構進行穩定的維護。而拓撲結構所描述的即是節點所能夠直接訪問的其他鄰居節點，在原型系統構建中定義所有節點所見的鄰居節點視圖即為網絡的全局節點視圖，每一個節點在平穩運行狀態中應能夠通過網絡訪問所有節點，與所有節點進行通信。

本文中所設計的自組織網絡主要面向大規模分布式系統中底層基礎網絡的構建，具有輕量級，加入網絡延遲時間短，節點退出后網絡重組延遲小，節點視圖快速同步的特點。并與傳統的主從式架構以及P2P架構相區別但又具有主從式架構中系統穩定性強，全局狀態感知迅速的特點亦具有P2P系統安全性強的特點。

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

2 相關工作

分布式自組織覆蓋網絡構建模式的變化經歷了集中式、分布式兩個階段。

2.1 集中式自組織網絡構建技術

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

集中式自組織網絡最主要的問題表現為中央服務器的癱瘓容易導致整個網絡的崩潰，可靠性和安全性較低。

2.2 分布式對等網絡構建技術

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

分布式對等網絡模型也存在很多弊端，主要表現在以下方面：

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

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

（3）純分布式的P2P模式很難被企業所利用，因為它缺少對網絡上的用戶節點數以及對它們提供的資源的一個總體把握[9]。

2.3 自組織網絡相關研究進展

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

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

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

（3）索引節點：連接速度快、內存充足的節點可以作為索引節點。索引節點用于保存可以利用的搜索節點信息，并搜集狀態信息，維護網絡結構信息。

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

3 Paxos算法以及Zookeeper實現

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

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

在系統中Leader節點選舉的過程即為各個節點狀態同步過程也即網絡自組過程。每一個節點的全局視圖將在該過程后保持一致并且在此過程之后可與任一節點通信。

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

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

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

圖1 Fast Paxos Leader選舉流程

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

當Leader節點選舉結束之后，各個節點進入平穩運行狀態除非發生新節點加入或者其他節點失效的情況下則其狀態不會變更。

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

圖2 選舉過程結束后節點狀態變化

4 配置同步模塊設計

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

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

圖3 節點配置同步流程

5 實驗

為了驗證系統性能設計了兩個實驗分別測試節點的加入性能以及節點退出后的網絡重組性能。實驗的硬件環境如下：18臺商用臺式計算機，CPU為Intel Core2 Q9500主頻為2.83 GHz，1.96 GB內存，250 GB硬盤，千兆以太網環境。

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

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

圖4 節點加入性能實驗結果圖

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

圖5 節點退出與網絡重構時間圖

6 結束語

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

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

[2]Armbrust M，Fox 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，Francis 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—），男，助理工程師，研究領域為分布式計算技術。E-mail：gig05281215@gmail.com

2012-05-03

2012-07-03

1002-8331（2014）06-0088-04