面向云计算基础课程的Paxos算法教学设计研究

杨立君 郭林

摘要：云计算作为一种新型计算模型，自诞生以来受到了业界与学术界广泛关注，市场规模迅速扩大，国內许多大学的计算机专业都开始关注云计算课程教学。针对云计算课程技术内容新、涉及理论多、应用范围广，以及与商业运营模式结合紧密等特点，以谷歌公司的云计算核心技术分布式锁服务Chubby所采用的Paxos算法为例，对云计算教学內容与教学方法进行设计探究。详细阐述了Paxos算法工作原理，并设计了具体教学案例，该教学方案在实际教学实践中获得了良好的教学效果，加深了学生对Paxos算法的理解。

关键词：云计算;教学设计;Chubby;Paxos算法

DOI：10.11907/ejdk.191376开放科学（资源服务）标识码（OSID）：

中图分类号：G434文献标识码：A 文章编号：1672-7800（2019）010-0191-04

0引言

随着计算机网络技术的发展以及Web 2.0网络革命的到来，谷歌首席执行官埃里克施密特于2006年8月在搜索引擎大会上首次提出了“云计算”概念，并将其阐述为谷歌公司的战略核心，同时作出预言：“在未来10-15年，当前以PC为核心的时代将被云计算时代所取代。”

云计算概念一经提出，由于其具有低成本、高性能、易于扩展及按需服务的特性，很快吸引了工业界与学术界的广泛关注，并在海量、高速增长、多样性大数据等传统单服务器环境下数据存储和计算模式难以处理的应用场景中显示出独特优势。如何充分利用云计算技术特性对大规模数据集进行高效的分布式计算、存储及分析已成为当前计算机科学领域最受关注的研究与应用方向之一。

为了满足业界对云计算技术开发与大数据处理领域高素质人才的迫切需求，目前很多大学的计算机相关专业都已在本科及研究生培养阶段开设了云计算技术与大数据处理相关课程，以培养学生掌握该领域理论知识与应用开发技术。授课教师针对云计算课程技术跨越度大、覆盖面广、对计算机算法等方面知识基础要求较高的特点，设计了很多针对性的教学方案，使学生对云计算包含的各项技术有更深入的了解。本文针对谷歌云计算集群用来解决分布式一致性问题的Paxos算法的教学重点与难点展开讨论，以期对云计算基础技术的教学及科研提供支持与帮助。

1一致性问题

对于传统单服务器计算模式，执行程序与目标数据都存储在同一个节点上，一致性机制非常直观。但云计算平台通常运行于大规模计算集群之上，需要调动成千上万的节点协同工作。要保证系统中初始状态相同的节点在执行相关操作时能看到完全一致的指令队列，并得到完全一致的执行结果，此类分布式系统的一致性机制实现则非常复杂。解决一致性问题有两种方法：消息传递与共享内存，Paxos算法是Leslie Lamport提出的一种基于消息传递的一致性算法，也是目前已知的一致性算法中最常用的一种。Paxos算法输入是各个计算机的全局请求（整个集群知道的消息），输出是请求的全局执行顺序。假如各个计算机内对各消息的解释代码都相同，通过执行带编号的全局请求，各机器则可以得到同样的结果。

分布式一致性问题与一致性算法是云计算集群分布式计算及传统服务器计算最重要的区别之一，也是云计算技术研究的核心问题之一，以及云计算教学过程中一个非常抽象、难以理解的知识模块。通过对Paxos一致性算法工作原理与教学案例的探讨，将为教师开展分布式锁服务Chubby教学建立一个坚实的算法知识基础。

2Paxos算法工作原理

在分布式系统中，采用消息传递方式提供通信服务，不可避免地会出现以下情况：系统进程可能遇到异常情况，例如运行缓慢、进程阻塞及重新启动等，消息传递过程中也可能产生延迟、丢失以及重复发送等异常。在可能发生上述异常的分布式系统中，如何就某个值达成一致，以确保上述任何异常不会损害系统一致性，则需要引入“一致性算法”。

在集群中设置一个决策节点，所有部分操作都要先向其发起请求，由该节点接受第一个到达的请求内容作为接下来的操作，从而确保该系统只有唯一的一个操作序列。但该机制在运行中存在单点失效问题，一旦唯一的决策节点失效，整个系统则可能出现不一致的情况。因此，Lamp-ort提出了Paxos算法，该算法在集群中设置多个节点以确定操作顺序。

为了更直观地描述Paxos算法，Lamport假想了一个名为Paxos的小岛。该岛通过民主议会制度颁布法律，但每个人都非常忙碌，随时都会离开众议院。因此，无法保证其他人在需要时能够为自己提供服务，也无法保证他们会及时传递消息或批准决议。假设岛上没有拜占庭指挥官的问题，也即是說，每个人经手的消息不会被篡改，只要时间足够长，消息则会正确传递，但不能保证即时性。此外，Paxos岛的成员非常聪明，他们提出的决议不会被其他成员拒绝。在这里，议员等同于系统中的节点，议员制定法律的行为等同于系统状态转换条件。系统中的节点之间需要一致性，即只有一个版本的法律规定，议员和信使的兼职性质对应于节点与渠道的可用性。

Paxos算法将节点分成3类：Proposers、Aeceptors和Learners。Proposers提出决议（也即系统下一步执行操作value），Aceeptors批准决议，Learners接收并执行已批准的决议。

算法需要满足3个条件才能保证一致性：①决议只有被Proposers提出后才能批准;②每次只批准一个决议;③只有决议确定被批准后，Learners才能获取该决议。由此推导出以下约束条件：

P1：Acceptor必须接受其接收到的第一个提议。

P2：如果选择了某个value为v的提议，则Acceptor接受的每个较高编号提议的value也必须为v。

P2a：如果选择了某个value为v的提议，则Aeceptor接受的每个较高编号提议的value也必须为v。

P2b：如果选择了某个value为v的提案，则Proposer提议的任何更高编号提案的value也必须是v。

P2c：对于任何N和v，如果提议为[N，V]，则存在一个超过Acceptor半数的集合S，满足以下两个条件之一：①S中每个Acceptor都没有接受编号小于N的提议;②S中Acceptor接受过最大编号提案的value为V。

完整的Paxos算法执行过程如下：

（1）准备阶段（prepare）：①Proposer选择一个提案编号n，并向全体Aeeeptors发出Prepare请求;②如果一个Ac-ceptor收到的prepare请求编号n大于任何其已响应的prepare请求，则Acceptor将自己已接受编号最大的提案反馈给Proposer，并向其承诺不会再接受任何编号小于n的提案请求。

（2）批准阶段（chosen）：①如果某个Proposer收到多数Acceptor的prepare请求响应，其需要向这些Acceptor发出接受（accept）请求，包括编号n和根据P2c约束确定的val-ue（如果系统尚无已接受的value，则Proposer可自由决定提案的Value）;②如果某个Aeeeptor收到的提案接受请求包含编号n，只要不违反其对其它Proposer的承诺，Aeeep-tor将立即接受该提案。

一个Proposer可以提出多个提案，并且可以随时中断提案。当某个Aceeptor接收到更大编号的prepare请求时，应当立即通知该Proposer中断本次提案，以优化整个算法流程。该实现过程不影响系统的正确性。

3Paxos算法教学案例

由于Paxos算法的数学证明与执行过程非常复杂，通常情况下高年级本科生难以充分理解，需要精心设计教学内容和方法。首先假设一个3节点的计算机集群，各节点首先作为Client产生操作请求，再作为Proposer提出操作请求，然后作为Acceptor批准操作请求，最后作为Learner执行被批准的操作，则算法执行逻辑如图1所示。

这里每个Acceptors的数量必须为奇数，才能确保在每次投票过程中产生“多数派”并生成决议，而Proposers的数量则是灵活的，一个Proposer也不需要每次都把提案发送给所有的Acceptors，只需让Acceptors中的“多数派”接收并批准决议即可交由Learners执行。

接下来通过设计一个让学生亲自参与的案例，可以将原本较抽象的计算机算法转化为较为直接、具体的现实场景，以帮助学生理解Paxos算法。假设山谷中有一个恐怖分子营地，因地形复杂，营地有3条道路通向外界，反恐指挥部派出甲、乙、丙3个反恐分队前去反恐作战。为完成作战目标，将恐怖分子一网打尽，3支分队需要同时向山谷发起进攻，如图2所示。

为协同3支队伍发起进攻的时间，总指挥部两位作战参谋1和2制定并提出最佳进攻时间计划，编号分别为1、2，每队的指挥官甲、乙、丙接收指挥部计划并批准进攻时间。为保证行动隐蔽，整个行动过程实行无线电静默，由指挥部派出通讯员传达参谋作战计划。通讯员A、B、C、D、E、F分别携带指挥部编号1和编号2的计划上路，经过不同路径找到指挥官传达计划。为帮助学生理解Paxos算法工作原理，可以选择一些学生分别扮演作战参谋、指挥官和通讯员进行模拟实验。本文按照作战参谋发起提案的先后顺序不同分为两种场景。

3.1场景1实验设计

首先假设作战参谋1和作战参谋2先后发起提案的场景，设计实验流程如下：

（1）作戰参谋1发起提案，派通讯员A、B、C送信给3名指挥官，内容为（number 1）。

（2）3名指挥官收到作战参谋1的提案，由于没有已保存的编号，因此保存（number 1），同时让通讯员带消息回去，内容为（ok）。

（3）作战参谋1收到不少于两名指挥官的回复，再次派通讯员送信给3名指挥官，内容为（number 1，attack time 1）。

（4）3名指挥官收到作战参谋1发来的进攻时间，保存（number 1，attack time 1），同时让通讯员送信回去，内容为（Accepted）。

（5）作战参谋1收到至少2名指挥官的（Accepted）回复，确认大家都收到了攻击时间。

（6）作战参谋2发起提案，派通讯员D、E、F送信给3名指挥官，内容为（number 2）。

（7）3名指挥官收到作战参谋2的提案，由于2>1，因此每人都保存（number 2），又由于已接受了作战参谋1的提案，则让通讯员送信回去，内容为（number 1，attacktime 1）。

（8）作战参谋2收到至少两名指挥官的回复，因为答复为已接收作战参谋1的提案，作战参谋2则不再提出新的进攻时间，并接受作战参谋1提议的时间。

最终批准的“多数派”提案为（number 1，attack time 1），投票过程如图3所示。

在两位作战参谋先后发起提案的场景中，由于指挥官必须批准最先收到的决议，整个投票过程较为简单、清晰。

3.2场景2实验设计

接下来模拟两位作战参谋同时发起提案的场景，设计实验流程如下：

（1）作战参谋1发起提案，派通讯员A、B、C送信给3名指挥官，内容为（number 1）。

（2）3名指挥官情况如下：①指挥官甲和指挥官乙都收到作战参谋1的提案，指挥官甲和指挥官乙将（number1）记录下来，并直接拒绝其他作战参谋提出的更小编号，同时让通讯员送信回去，内容为（ok）;②负责通知指挥官丙的通讯员C走错道路后自行返回指挥部，因此指挥官丙未收到作战参谋1的提案。

（3）作战参谋2也在同一时间发起提案，派通讯员D、E、F送信给3名指挥官，内容为（number 2）。

（4）3名指挥官情况如下：①指挥官乙和指挥官丙都收到作战参谋2的提案，指挥官乙和指挥官丙将（number2）记录下来，并直接拒绝其他作战参谋提出的更小编号，同时让通讯员带信回去，内容为（ok）;②负责通知指挥官甲的通讯员D走错道路后自行返回指挥部，因此指挥官甲未收到作战参谋2的提案。

（5）作战参谋1收到不少于两名指挥官的答复，再派通讯员送信给有答复的两名指挥官，内容为（number 1，at-tack time 1）。

（6）两名指挥官情况如下：①指挥官甲收到（number1，attack time 1），该编号与其已保存的编号相同，因此将（number 1，attack time 1）保存下来，同时让通讯员A带信回去，内容为（Accepted）;②指挥官乙收到（number 1，at-tack time 1），由于乙处已保存编号2，1<2，则让通讯员B送信回去，内容为（Rejected，number2）。

（7）作战参谋2收到不少于两名指挥官的答复，再派通讯员送信给这两名指挥官，内容为（number2，attacktime2）。

（8）指挥官乙和丙收到（number 2，attack time 2），与已保存的编号相同，则保存（number 2，attack time 2），并让通讯员送信回去，内容为（Accepted）。

（9）作战参谋2收到不少于两名指挥官的（Accepted）答复，确认多数派已接受了提议的进攻时间。

（10）作战参谋1只接收1名指挥官的（Accepted）答复，同时接收到一个（Rejected，number2）的答复。作战参谋1再次发起提案，派通讯员A、B、C送信给3名指挥官，内容为（number 3）。

（11）3名指挥官情况如下：①指挥官甲接收作战参谋l的提案，由于之前保存了（number 1），3>1，因此保存（number 3），而指挥官甲已回复接受作战参谋1之前的提案，则让通讯员A送信回去，内容为（number 1，attack time1）;②指挥官乙接收作战参谋1的提案，由于之前已保存（number 2），3>2，因此保存（number 3），而指挥官乙已回复接受作战参谋2之前的提案，则让通讯员B送信回去，内容为（number 2，attack time 2）;③負责通知指挥官丙的通讯员C走错道路后自行返回指挥部，因此指挥官丙未收到作战参谋1的提案。

（12）作战参谋1接收了不少于两名指挥官的答复，比较其编号大小，选择较大编号对应的进攻时间并发起新的提案。因此，作战参谋1派通讯员A、B送信给这两名指挥官，内容为（number 3，attack time 2）。

（13）指挥官甲和乙接收（number 3，attack time 2），与已保存的编号相同，因此保存（number 3，attack time 2），并让通讯员送信回去，内容为（Accepted）。

（14）作战参谋1接收不少于两名指挥官的（Accepted）回复，确认提案的进攻时间已被多数派接受。

最终指挥部和3支作战部队利用Paxos算法统一了发起进攻的时间，实现了分布式系统的指令一致性。投票过程如图4所示。

4结语

云计算作为一种新型计算模式，为了使大规模计算机集群能够有效协同工作，针对海量数据实现高性能计算，采用了向量时钟技术、改进的一致性哈希算法等较为复杂的关键技术。其中谷歌云计算集群用来解决分布式一致性问题的Paxos算法既是云计算课程教学中的重点又是难点。在本学院的云计算课程教学过程中试行本文给出的设计方案，之后进行的测试表明，学生们对原本难以理解的Paxos算法工作原理有了较为清晰的认识。该设计得到了学生的广泛认同，在教学实践中取得了很好的效果，并为其它部分的知识难点教学提供了有益借鉴。