2.1.1原子广播
分布式系 统中，原子广播把消息 发送给多个接收服务器 ，实现某种形式的组播，而且对千多条顺序消息，在多个接收服务器 侧能够保证完全顺序 ( TotalOrder)。也就是说，发送端发送消息 X, 多个接收服务器 要么 收到消息 并处理，要么都不处理。若消息 X先千消息 Y发送（表示为 X->Y) ，则多个接收服务器 都是先处理消息 X, 再处理消 息 Y, 保证完全顺序。原子广播技术 原理如图 2-8所示。
图2-8 原子广播技术原理
图 2-8(a )所示为 BirmanKenneth关千原子广播的论文架 构，其中组播层包含组 播( GroupBroadcast, GBCAST入 原子广播（AtomicBroadcast, ABCAST) 和先后广播( CausalBroadcast,
CBCAST)，实现多台服务器 之间的 Broadcast协议。
核心的交互流程如图2-8( b) 所示，每次有新 的成员加入将进行视图( View) 变换。例如，B加入 A形成新的视图 ( A、B)，或者A离开旧视图 ( A、B、C) 形成的新的视图 ( B、C) ，视图变换期间暂停客户 端请求，从而提高视图变化效率 。而当视图内部较多成员出现异常时，将基千多数派投票 ( Quorum) 机制形成新的稳定视图。例如，在系统总共有 N个成员的情况下，如果成员出现异常，那么只有出现异常的成员个数大千或等千 ( N+l) /2, 才能形成新的视图。
视图变换成功进入 稳态后，客户端就能 以原子广播形式给 视图中的成员发送信息 ，并且保证完全顺序 ，如图 2-8( b) 所示。在视图 ( A、B、C) 形成后，如果客户端 l先千客户端2发送消息给该视图，那么在保证该视图的成员 A、B、C都处理完客户端 l的消息后，再处理客户端 2的消息。
原子广播技术 可以在某种程度上解 决两将军问题，或者非拜占庭故障下的多将军共识问题 。把原子广播中 的成员当作将军，若将军间通信出现异常，则将通过多数派 投票淘汰 异常的将军，形成新的共识，一旦形成新的共识，那么后续的消息通信将保证完全 顺序。
产业界的 VCS( VeritasClusterServer) 就是基于 GAB来实现集群的共识，以及保证集群消息通信在成员间的原子性和顺序性的。
2.1.5牛见图复制
视图复制 ( Viewstamped Replication, VR) 的正式发表时间比 PAXOS 早一年，某些文章介绍两位图灵奖获得者BarbaraLiskov和 LeslieLamport各自独立发表，并未相互借鉴。不过从工程理解维度看 ，VR是设计完 备度非常 好的高质量论文，甚至可以直接指导 开发工作，这可能和BarbaraLiskov擅长编程和计算机科学，而 LeslieLamport更擅长理论研究有关，毕竟 Barba raLiskov因其面向对象编程的杰 出贡献而获得图灵奖 ，著名的里 氏替换原则(LiskovSubstitutionPrinciple) 就是她的杰作。从笔者的角度看，VR绝对是被低估的论文 ，值得认真研究和分 析。
基千原子广播技术 之所以无法实现数据复制，是因为在原子广播的固定视图内只保证消息 的顺序性。为了保证在成员 出现异常后数据的持久度和可用 性，VR在原子广播视图 的基础上 针对数据复制进 行了优化，可以用千数据复 制系统。如图 2-9( a) 所示，VR描述了架构组件。
· 副本 ( Replica)。通过分层的 VR复制代码 CVRCode) 和业务层代码 ( ServiceCode),
实现复制逻辑的解耦，并且会选举某 个副本为主 ( Primary) 。
· 客户端。它由用户代码 ( UserCode) 和 VR复制代理 CVRProxy) 组成，VR复制代理负责给 VR发送请求。
图 2-9( b) 描述 VR复制的核心逻辑，它由副本中的主统一负责处理客户端的请求顺序来实现请求顺序性，并结合复制的日志支撑发生主节点故障后 的数据恢复，从而提供完备的数据复 制系统。
图 2-9 VR技术原理
VR在发生成员故障后 ，会在 正常的副本中选主。
· 选主是基千日志 做恢 复，而原子广播没有日志恢复的过程。
· 选主会基千视图的逻辑时钟序号和日志的顺序号完成。
· 客户端复制代理发送请求时会携带缓存的视图序号，主会比对本地视图序号和请求视图序号，只有相同才允许执行，从而避免视图切换时请求到不匹配的数据。
VR的全流程围绕视图序号和日志顺序号展开 ，是数据复 制的核心技术，常被用千分布式存储和数据库，但原子广播无法实现该功能。
2.1.6 PAXOS
基千维基百科 的描述，PAXOS是一组解决共识问题的协议集 ，它 详细描述需要持久化
( Durab山 ty) 处理的共识实现过程。PAXOS技术原理如图 2-10所示。
图 2-10PAXOS技术原理
PAXOS协议运行在网 络环境，对于N个成员的系统，能够容忍F个成员的崩溃停机故障 ( CrashStop)，但是必须满 足 N?=2F+I。PAXOS包含如下角色 。
· 客户端。该角色负 责发送请求给 PAXOS分布式系 统，然后等待返回 响应。
· 接收者 ( Acceptor或Voter)。该角色起到容错的作用 ，多个接收者形成 投票组 ，所有客户端请求必须被发送到投票组的接收者。
· 提案者 ( Proposer)。该角色负责响应客户 端请求，当它收到请求后 ，会把请求发送给所有接收者 并达成一致，提案者起到协调的作用，并推动协议的状态 机运行，同时通过协调控制多个请求写入同一对象的冲突。
· 学习者 ( Learner) 。该角色负责处理如何响应客户 端，目的是提高可用性和支撑一致性模型。
· 领导者 ( Leader) 。该角色 由 PAXOS选取某个提案 者担当 ，成员 都必须信任它。在出现故障后，多个成员希望成为领导者 ，此时会选取出 新的领导者，通过它实现选主。
在实际部署中，PAXOS的成员可能同时担任提案者 、接收者、学习者，而领导者就是承担主角色的成员，和VR的角色定义形成对应关系，如图2-11( a) 所示。VR的副本和 PAXOS的成员（提案者、接收者、学习者）对应，VR 的主和 PAXOS 的领导者对应，VR 用重配置(Reconfiguration) 重新选主，而PAXOS用提案者扮演领导者实现选主 ，如图2-11( b) 所示。
图2-11 PAXOS和VR架构组件对比
PAXOS采用类似两阶段提交 ( 2PhaseCommit, 2PC) 技术实现某请求在提案者、接收者中达成一致。2PC有两个阶段，共四个步 骤分别为 Phasela: Prepare、Phase1b:Promise、Phase2a:Accept、Phase2b:Accepted。而 VR在实现请求达成一致的过程中 ，采用的是基千日志的复制，通过日志顺序号和业务代码结合解决故障时的重做 ( Redo)、回滚 ( Undo) 等问题。
经过 VR和 PAXOS经典论文对共识的探索 ，业界发表了 大量相关文章。1990年，SchneiderFred在论文 Implementing Fault-Tolerant Services Using the State Machine ApproachATutorial中将状态机复制 ( StateMachineReplication) 作为共识的关键解决方案。
