应用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