一种基于Paxos算法的高可用分布式锁服务系统

杨春明 杜 炯

(西南科技大学计算机科学与技术学院 四川绵阳 621010)

随着企业应用系统对计算能力需求的增长，传统单节点处理的服务模式逐渐达到了一个瓶颈。为了缓解单点的网络带宽、存储、计算等压力以及解除单点故障(当服务中心出现软硬件故障的时候整个服务不可用)等问题，越来越多的大型系统逐渐从单节点模式转向分布式的云计算模式。

在分布式的计算环境中，解决计算节点之间的数据同步、分布式资源竞争以及单节点故障自主恢复等问题是系统正确性和可靠性的基本保证。其中最基本的是节点之间的数据一致性问题，即保证节点之间互通情况下从各个节点请求到的数据必须是一致的，同时外部请求对数据做出的修改在各个节点之间也必须同步。Paxos系列算法的出现解决了分布式设计中一致性的问题，可以应用在数据复制、命名服务、配置管理、权限设置和号码分配等场合［1－2］。然而很多时候系统在设计之初并没有考虑到在分布式环境下的高可用和一致性的问题，当系统逐渐变大之后，系统的一致性和高可用性变得尤为重要。一些系统采用主从复制模式(Master/slave)来解决该问题［3］，但主从复制模式的一致性主要依赖主节点，主节点故障后导致各从节点之间的数据不能同步。

本文分析了Paxos算法的基本原理，设计了一个外部的锁服务系统，可以使网络节点间的同步能够像进程间的同步一样简单、可靠。该分布式锁服务除了具有锁原语的基本操作(创建、锁定、释放)外，还提供了处理共享资源的简单数据存储以及实时的锁事件通知(锁的释放、数据修改)等操作，可以简化分布式应用的设计。

1 Paxos算法

Paxos算法是用来解决在不可靠的网络环境中多个网络节点达成可靠一致性共识的算法。假设现在有一个可以提出提案的节点集合。一个一致性算法保证在这些提案中只有一个能被选中，如果没有提案被提出则没有提案被选中。如果一个提案被选中了，那么其他的节点应该能够知道这个被选中的提案。需要达成这个共识的安全需求有:

(1)只有某个提案被提出才能被选中;

(2)只能有一个提案被选中;

(3)一个节点永远不会得知某个提案被选中除非它真的被选中了。

算法中将不同的节点用3个角色来表示:Proposers，Acceptors 和 Learners［4］，其 中，Proposer 向Acceptor提交提案(proposal)，提案中含有决议(value);Acceptor审批提案;Learner获取并执行已经通过审批的提案中含有的决议。

一个节点可以扮演多个角色，不同的角色仅表示其在算法中的不同职能。不同的节点之间可以发送消息进行交流，发送的消息可能会丢失、延迟或重复，但是不能被破坏，即每次接收到的消息都是完整的、没有被篡改。

算法的操作流程分为2个阶段:(1)准备阶段:Proposer选择一个提案号n，并发送一个带有n的Prepare请求给大部分的Acceptor。如果一个Acceptor收到的Request中的n大于任何一个它收到且回复的Prepare请求的n，则回复Proposer保证不会接受任何小于n的请求。(2)批准阶段:如果Proposer收到了大部分Acceptor的回应，则向这些Acceptor发送一个Accept请求，请求包含数字n和值v。如果一个Acceptor收到了一个包含n的Accept请求而且它没有回复一个比n大的Prepare请求，则接受这个Accept请求。通过这两个阶段的消息传递和实例执行，可保证数据和操作的一致性。Paxos算法采用了投票选举的形式，通过数学归纳的思想进一步保障了majority机制，保证了2F+l的容错能力，即具备2F+l个结点的系统最多允许F个结点同时出现故障［5］。但该算法也存在一些局限，如在两个Proposer可能陷入活锁、随机等待时间较长、通信负载等，许子灿等人［6］对此进行了一系列的优化。

2 基于Paxos算法的分布式锁服务

2.1 分布式锁服务的结构

在分布式环境中，相同的应用或数据会部署在不同的节点上，用户或其他应用的请求也会分流到不同的节点，为了提供不间断的服务及保证各节点数据的一致性，需要一个分布式的锁服务来提供上述功能。本文了采用Paxos算法构建了一个分布式环境下的锁服务，其系统结构如图1所示。

图1 分布式锁服务系统结构Fig.1 The structure of distributed lock service system

图中的圆形节点构成了服务集群的锁节点，应用或数据将部署在该类节点上，客户端向服务集群发出服务请求，服务集群将采用Paxos算法选择响应请求的节点，并将对数据的操作同步到其他各节点。图中Leader和Follower的网络地位一致，从长时间跨度来看，服务集群中没有中心单点。锁节点有如下3种角色:

(1)Leader:主要负责提出数据写提案和数据写操作请求;

(2)Follower:提供数据读服务和向Leader提出数据写申请;

(3)Learner:接受数据写提案和向数据库提交写操作。

分布式的锁服务中每个锁节点对外提供一个带锁的Key/Value数据接口，主要的接口功能如表1所示。

表1 分布式锁服务接口Table 1 The interface of distributed lock service

2.2 Leader选举算法

在Paxos算法中每个成员都是Proposer，根据算法一个编号更大的提案会终止之前的提案过程，如果2个Proposer在这种情况下都转而提出一个编号更大的提案，那么就可能陷入活锁。这就难免会产生冲突，增加系统的时间延迟。

为了避免提案的冲突，在所有的Proposer中选举一个Leader，所有的提案只能由Leader提出，其他Proposer就跟随Leader，称为 Follower。Leader通过 Fast－ Leader－ Election 算法［7－8］进行选举，系统在以下几种情况使用该算法进行Leader的选举:

(1)系统启动后，所有节点角色都是相同的;

(2)Leader无法跟一半以上的Follower进行正常通信;

(3)Follower无法跟Leader进行正常通信;

(4)Leader的周期达到，进行计划的 Leader选举;

(5)人工干预Leader选举。

此时锁节点有以下3种状态:

(1)Looking:节点执行 FastLeaderElection算法时，选举Leader;

(2)Leading:Leader节点的状态;

(3)Following:Follower节点的状态。

3种状态之间的转换关系如图2所示。

为了保证选举到的Leader拥有最新的锁状态，选举时需要锁节点包含以下属性:

(1)myid:锁节点ID号，需要人工在配置文件中指定;

(2)view:每次选举后所有锁节点的状态称为一个view，初始为0，每次选举后view自增1;

(3)trans:提案事务序号，初始为0，每一次提案通过后trans自增1;

(4)clock:锁服务的选举计数，初始为0。

图2 锁节点之间的状态转移Fig.2 The state transition between locked nodes

选举出的Leader必须保证trans和view是所有锁节点中最大的，如果两者都一样就取myid最大的。因此，Leader的选举流程如下:

锁节点之间通过投票来选举Leader，每次投票包含 leaderid，state，view，trans和 myid，其中 leaderid是本次投票Leader的ID号，state是投票者的状态。

投票按投票者的状态分为普通投票和稳定投票，节点状态为Looking的投票为普通投票，否则为稳定投票(此时对应的锁节点已结束选举)，两类投票分别用states和stable_votes集合记录。

在开始选举时，首先将节点状态设为Looking，推举自己作为Leader，通知所有的锁节点;然后只要当前服务器状态为Looking且不为stop，进入循环，不断地读取其它锁节点发来的投票、进行比较、更新自己的投票、发送自己的投票、统计投票结果，直到Leader选出或出错退出。具体作法是接收一个投票，根据投票者的状态进行相应的处理，其选举流程如图3、图4所示。

2.3 数据同步算法

锁服务中数据同步主要有两类:数据初始化同步、数据写同步。锁数据的所有操作都记录在日志中，每个操作有一个事务ID来标识自己，记为trans。

在锁节点选举出Leader之后需要对锁数据进行同步，确保所有锁节点在开始工作之前的锁数据是一致的。

同步流程如下:

(1)Follower向Leader发送同步请求，在请求中附上自己最后一次数据操作的trans;

(2)Leader把 Follower的 trans和自己的 trans比较，向Follower发送缺失的数据操作日志;

图3 投票者为Looking状态的选举流程Fig.3 The election process of voters in“Looking”state

图4 投票者为Leading或Following状态的选举流程Fig.4 The election process of voters in“Leading”or“Following”state

(3)Follower把收到的数据操作日志与本地的操作日志合并并将其应用于数据。

数据写操作包括新建键、修改键、删除键以及锁的相关操作，这里使用Paxos算法来同步数据，但是只允许Leader提出议案，具体流程如下:

(1)Leader或Follower向Leader提交一个写操作请求;

(2)Leader检查该写操作是否合法(比如写入数据请求时对应的键值被锁定);

(3)Leader向所有Follower发送写操作的提案;

(4)Follower同意议案，告知Leader;

(5)Leader得到半数Follower的同意后向所有锁节点发送写操作提交请求;

(6)Leader或Follower收到写操作提交请求记录日志并向数据库中提交数据。

3 实验及结果分析

实验主要在单台机器下使用多个终端来模拟多个节点，验证分布式锁服务的有效性，同时进行性能分析。实验环境为 PC机，Intel Core i5 CPU，2.5 GHz，6 GB 内存，操作系统为 Linux Kernel 3.964位，使用 Python 2.7，gevent，leveldb 实现了分布式锁服务。

分布式锁服务主要解决分布式环境中高并发访问时的容错性和响应速度，数据的容错性主要由锁服务的功能及节点故障后数据的一致性来体现，响应速度则主要看多个客户端在多次读写情况下不同数据量的时间消耗。

容错性测试主要测试提供的锁服务功能是否满足要求，同时测试在节点故障(半数以上节点存活)时是否能提供不间断服务，因此，实验中在模拟5个客户端下，做了锁服务的有效性和可用性测试，结果如表2、表3所示。

表2 锁服务有效性测试Table 2 The lock service effectiveness testing

表3 锁服务可用性测试Table 3 The Lock service usability testing

表2和表3的测试结果表明，本文实现的分布式锁服务具有容错性，对于一个具有2F+1个节点的系统，能保证在故障节点小于F+1的情况下集群正常提供服务，且能保证各节点间数据读写的一致性。

锁服务设计的目标是能处理高并发情况下的数据一致性问题，所以响应速度也是反映锁服务可用性的一个指标。锁服务的响应速度主要体现在不同客户端并发情况下多次读写不同大小数据的时间消耗，因此，实验时在客户端调用锁服务的接口进行以下4个方面的测试。

(1)不同并发下5000次读取的时耗，反映等量读取下，不同并发的时耗;(2)不同并发下单个客户端读取100次的时耗，反映并发增长时单客户端读取的时耗;(3)不同并发下写入1000次的时耗，反映等量写入时，不同并发下的时耗;(4)10个并发，每个客户端在100次写入不同数据大小下的时耗，反映等量并发和写入下不同数据量的时耗。本文采用Paxos算法实现了一个分布式锁服务系统，并对其中产生冲突时带来的延时进行了改进。为了验证改进的有效性，在上述(4)的测试中，对基本算法和本文算法的时间消耗进行了实验对比。上述测试结果如图5、图6所示。

图5 等量读写下不同并发的时耗Fig.5 The different concurrent time consumption under the same amount of read and write

图6 等量并发及写时不同数据大小的时耗Fig.6 The different time consumption of data under the same amount of concurrent and write

图5表明，实现的锁服务在高并发等量读取下，低并发和高并发的耗时比较接近。因为低并发时建立Session的时间比较少，而读取不需要整个集群交互;高并发下单个客户端读取的次数较少，大量的客户端可以并发读取，因此消耗的总时间比较少。随着并发客户端的增加，读取的时间消耗是近似成正比增加的。在等量写入下，随着并发的增加消耗的时间也随之增加，这个结果与读取结果不同的原因在于数据的写入必须保证原子性，无法发挥并发的优势，消耗时间随着并发增高是因为Session的建立会更多，结果中消耗时间的差异主要是Session数量的差异。

图6反映了在不同锁数据容量下写入的性能，可以看出1000次写入的时间差距十分小，但是有缓慢上升的总趋势。同时也可以看出，本文改进后的算法，可以将写数据时的一致性时间消耗提高4%～7%，其原因是本文改进的算法中，避免了冲突产生时的延迟。

上述的实验结果表明，本文实现的分布式锁服务具有较高容错性，在服务集群硬件有限的情况下，能为高并发下分布式环境中的应用提供高可用的数据一致性服务。

4 结束语

文章深入分析了Paox算法的特点，针对分布式环境下的应用程序保证数据一致性的场景，设计了一个分布式锁服务，为分布式应用对共享资源的访问提供了一种同步方式，使得节点间的同步和进程间的同步一样简单、可靠。该分布式锁服务除了具有锁原语的基本操作(创建、锁定、释放)外，还提供了方便分布式应用处理共享资源的简单数据存储以及实时的锁事件通知(锁的释放、数据修改等操作)，简化了分布式应用的设计。

［1］LAMPORT L.Fast paxos［J］.Distributed Computing，2006，2(19):79－103.

［2］RAO J，SHEKITA E J，TATA S.Using Paxos to build a scalable，consistent，and highly available datastore［J］.Proc.VLDB Endow.，2011，4(4):243－254.

［3］BUENO A M，RIGON A G，FERREIRA A A，et al.Design constraints for third－order PLL nodes in masterslave clock distribution networks［J］.Communications in Nonlinear Science and Numerical Simulation，2010，15(9):2565－2574.

［4］MARZULLO K，MELING H，MEI A.Brief Announcement:When You Don’t Trust Clients:Byzantine Proposer Fast Paxos［C］.The 25th International Symposium，DISC 2011，Rome，Italy，2011.143－144.

［5］SANTOS N，SCHIPER A.Tuning Paxos for high －throughput with batching and pipelining［C］.The 13th International Conference，ICDCN 2012，Hong Kong，China，2012.153－167.

［6］许子灿，吴荣泉.基于消息传递的Paxos算法研究［J］.计算机工程，2011，37(21):287－290.

［7］MEDEIROS A.Zoo Keeper’s Atomic Broadcast Protocol:Theory and Practice［R］.2012.1 －19.

［8］MARANDI P J，MARCO PRIMI N S，PEDONE F.Ring Paxos:A High－throughput Atomic Broadcast Protocol［A］.In Dependable Systems and Networks(DSN)［C］.2010 IEEE/IFIP International Conference， 2010.527－536.