一致性与共识

有某些场景下我们希望一些任务只在一个实例执行，最常用的可以考虑用MQ实现，但例如定时任务，到时间后执行一个任务，同一时间任务只能执行一次，在没有分布式调度服务的前提下我们更倾向于用一个特定的节点执行，但如何确定这个节点呢？显然我们不能只部署一个实例，这违反了高可用性要求，再考虑实例可能会宕机所以我们其实需要有一个机制可以动态找到一个特殊节点用于执行特定工作，并且在这一节点宕机后可以快速重新指定新的特殊节点，而这就是领导者选举所应对的一个典型场景。

我前面讲了分布式事务、分布式锁，其实它们都隐含了一个重要概念，那就是共识机制，领导者选举就是其最直接的应用之一。

共识机制按是否有允许存在恶意节点而分为拜占庭与非拜占庭问题。

两个将军问题 很形象地描述了非拜占庭问题：有两个军队，每个军队都由不同的将领率领，他们袭击一座城市，但只有两军共同发起攻击才能获胜，不幸的他们要派信使协商攻击时间时必须经过敌军阵地并有可能被抓获从而导致消息无法传递到友军。两个将军问题就是讨论在这种情况下如何达成一致的问题。

我们可以设想：将军A派信使1通知将军B，告知一同进攻的时间

• 信使1被抓，导致将军A发起攻击时将军B的军队还在原地，即无法达成一致

• 将军B收到了信使1的通知，但它要确保将军A知道自己收到了，否则可能会是自己发起攻击了而将军A以为自己没有收到而原地不动，所以将军B要派信使2去告知将军A自己确认收到了，但这过程信使2被抓，导致了无法达成一致

• 再往下，将军A收到了信使2的确认通知，但他还要让将军B知道自己收到确认，否则也会出现将军B以为将军A没有收到确认而待在原地，所以这里将军A又要再派信使1告知将军B自己收到确认了，但这又回到一开始，信使1可能被抓

• ……

所以两个将军问题无解，它证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。

与此类似，后来出现的[FLP Impossibility](http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/ （FLP不可能性）论证了在异步协议下没有一种一致性协议可以容忍哪怕是只有一个进程死亡的情况。进一步而言其结论是在异步通信场景中，没有任何算法能保证一致性。这听起来很不可思议，抛开严格的数学论证，举个很简单的例子：有3个节点A、B、C参与针对某一问题的投票，其中只要有任意节点无论是由于网络还是节点自身的故障而不法接收或发送投票都会导致整个投票失败，而这种故障是在分布式环境下不可避免的。当然有读者会发现这是有解决方法的：少数服从多数，只要在规定的时间内收到多数的投票就可以视为投票有效。这的确可以解决问题，但要注意“规定的时间内”这个限定就意味着将异步改成同步了，FLP Impossibility中强调的异步是指任意长的时间，不完全是我们工程实施中所指的异步。

所以FLP Impossibility是告诉我们最坏的情况，而正如上面的解决方法一样在工程实践中我们可以有所变通将不可能变成可能。FLP Impossibility的现实意义是为分布式一致性协议的设计指明了方向：别试图去实现理想化的一致性方案，这是做不到的，可行的一致性协议必定是有所妥协的。

说到一致性协议，那必须要讲[Paxos](https://en.wikipedia.org/wiki/Paxos_(computer_science))，这是公认的最伟大的分布式一致算法，可能没有之一。 Paxos协议见于Leslie Lamport在1998年发的《The Part-Time Parliament》 ，在此论文中它假设了一个叫Paxos的小岛，岛上的各项决定要经议会同意，议会成员都是兼职的，议员的核心角色分为提案者（Proposers）、表决/投票者（Acceptors）。Proposer 提出提案（Proposal），提案信息包括提案编号和提议的值（Value），Acceptor 收到提案后可以接受（Accept）提案，若提案获得多数 Acceptors 的接受，则称该提案被批准（Chosen）。

图片来源Implementing Replicated Logs with Paxos”

上图是Paxos基础算法说明，通过一个决议需要两个阶段：

• Prepare阶段

  • Proposer选择一个提案编号n并将 Prepare(n) 请求广播给Acceptors

  • Acceptor收到 Prepare(n) 请求后，先比较n和自己存储的 minProposal ，如果n>minProposal ，表示有更新的提议，则更新自己的 minProposal=n ，如果提案的编号大于它已经回复的所有Prepare请求则Acceptor将自己上次接受的提案回复给Proposer return(acceptedProposal,acceptedValue) ，并承诺不再回复小于n的提案，反之认可这个提案返回OK

  • Proposer收到了半数Acceptors对Prepare的回复后，如发现有 acceptedValue 返回，表示有认可的提议，保存最高acceptedProposal 编号的 acceptedValue

• Accepted阶段

  • Proposer向收到回复的Acceptors发送Accept请求 Accept(n,value) ，如果没有 acceptedValue 则value可以由Proposer自己决定，反之则为 acceptedValue

  • Acceptor收到 Accept(n,value) 请求后，比较n与 minProposal ，如果 n>=minProposal ,则 acceptedProposal=minProposal=n，acceptedValue=value ，返回接受，否则拒绝并且返回 minProposal

  • Proposer接收到过半数请求后，如果发现有 返回值>n ，表示有更新的提议，跳转1重新发起提议，反之则value达成一致，完成选举

以上Paxos简单的描述，实际会更复杂很多，以至于很多专业人士也一头雾水，所以Lamport在2001年又发表了《Paxos Made Simple》 以简化说明，但这还是过于晦涩，推荐这篇博客 ，其举例的三军问题可以很形象地表述Paxos的流程，另外也可以参考此文进一步了解，了解Paxos基本流程相对简单，但要真正理解Paxos很难，有兴趣的读者建议还是直接阅读Paxos的论文及Lamport的简化版论述。

基于Paxos衍生出了很多协议，比如著名的以[Raft](https://en.wikipedia.org/wiki/Raft_(computer_science))、Zab，Raft可以简单理解成是对Paxos的简化，被各分布式系统广泛地采用，Zab是Zookeepr的核心协议。但这些协议都有一个重要前提：参与者Acceptor是善良的，不作恶的，即参与者都按规则办事，不会上报虚假信息，所以这些都是非拜占庭算法。这类算法多用于可控集群间的一致性处理，是当下的主流，不过我们也看有一些场景会存在跨机构、公司间的需要关注一致性的数据交互，这之中最著名的就是现在大红大紫的区块链。

区块链技术的核心在于解决不同组织内的信任问题，而之中共识算法又是核心中的核心，这些算法要面对的是部分节点可能作恶的情况，比如A转了100元给B，这个记录会被写入所有节点并持久化，但由于区块链的节点不受某个中心化机构控制（联盟链及部分公链除外），我们不能排除某些节点记假账，将钱转到自己账户上，要解决这个问题我们就要先了解下拜占庭问题的由来及常用的算法协议。

拜占庭将军问题（Byzantine Generals Problem），是由Lamport在其同名论文中提出的分布式对等网络通信容错问题。它的问题如下：

几支拜占庭军队共同攻打一座城市。如果部分军队进攻部分军队撤退可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤退。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将进攻还是撤退的投票通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

到这听起来很像上文提及的两将军问题，但拜占庭将军问题聚焦的点是：将军中可能出现叛徒，他们可能投虚假票。例如有3位将军投票，其中1名叛徒。2名忠诚的将军中分别投了进攻和撤退，而叛徒可能故意给赞成进攻的将军投票进攻，而给赞成撤退的将军投票撤退。这样一来在投进攻的将领看来，投票结果是2人投进攻从而发起进攻，而在投撤退的将军看来则是2人投撤退从而撤退，这破坏了一致性。拜占庭将军问题并不考虑信使是否会被截获导致的无法传达信息的问题，即前提是消息传递的信道可靠的（上文已经提到过在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的）。

就是拜占庭将军问题，如果在消息可能被伪造的情况下仍然达成了一致，就称实现了“拜占庭容错”。

拜占庭将军问题的解法有个前提，那就是通信可靠、少数服从多数，叛徒的数量不能大于等于1/3。这个值怎么得出来的呢？我们用最小化的模型举例说明：假设有3个将军A、B、C，有一个是叛徒，则A发出进攻命令：

• 如果B是叛徒，B可能告诉C他收到的是撤退，这时C会收到一个进攻一个撤退，于是C无法判断真实命令，如果C是叛徒，也类似，导致B无法判断真实命令

• 如果A是叛徒，他告诉B进攻，告诉C撤退。当C告诉B，他收到撤退命令时，B由于收到了A进攻的命令，而无法与C保持一致

所以如叛徒数等于或大于1/3，拜占庭问题便不可解。但如果小于1/3时大家设想下每个将军都知道了其他将军手里的投票，如果有一半以上的将军说进攻，那么就可以进攻。即便是有叛徒，只要听大部分人的就可以保证达成一致。

在实现有口头协定和书面协定，口头协定的将军间使用口信传递信息，书面协定要求使用书信，书信上要签名，相比而言，后者的签名可以确定将军身份，使得消息可以追溯、保证消息不被篡改，而这正是区域链共识算法的核心。

实现上超级账本的核心算法PBFT（实用拜占庭容错，Practical Byzantine Fault Tolerance）也正是基于拜占庭问题衍生而来，PBFT将拜占庭算法的复杂度简化到相对可实用的程度，这是目前拜占庭的主流算法。相对于非拜占庭算法，拜占庭算法之所以复杂的核心在于提案的成本太低了进而导致“作恶”的成本很低，所以解决拜占庭问题的另一个思路是提高提案的成本，而这正是诸如比特币网络、以太坊等区块链所选择的PoW （Proof of Work）工作量证明方案，PoW要求每个节点解决一个带有一定困难度的密码难题，难题的解决方法是把参与节点做Hash运算，给定一个Hash要求，找到符合要求的原始值，比如需要找到前导4个0的Hash对应的原始值，此计算根据不同的Hash实现会占用一定的算力（如内存、CPU、GPU资源）而算力的占用就意味着成本支出（硬件、网络、电力、运维等）。由Hash算法正向快速（给定原始值和Hash算法可快速计算Hash值）、逆向困难（在有限时间内几乎不可能通过Hash值推算出原始值）、输入敏感（只原始值稍微改动就会出现差别很大的Hash值）等特性使得Hash计算成为众多PoW实现的首选，PoW让提案的成本高于成功后所能获得的经济利益从让“作恶”变得不“经济”进而变相地解决了拜占庭问题。后续出现的POS（Proof of Stake）股权证明、DPOS（Delegated Proof of Stake）委任权益证明等都是基于这一思想的延续。

可以说共识机制是分布式技术核心中的核心，是多种重要理论的基石，大家在做相关架构设计时对此应该要有所了解。

📖 Leslie B. Lamport：上文我们多次提及此人，1941年出生于美国纽约，是知名的拜占庭将军问题、Paxos算法的作者，2008年·冯诺依曼奖及2013年图灵奖得主，是分布式系统研究的先驱者。