distributed consensus - paxos

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。

基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础 Paxos 场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos 算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

拜占庭将军问题

拜占庭将军问题是 Leslie Lamport 在The Byzantine Generals Problem论文中提出的分布式领域的容错问题，它是分布式领域中最复杂、最严格的容错模型。

拜占庭将军问题描述了一个如下场景：

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

https://zh.wikipedia.org/wiki/拜占庭将军问题

系统的问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

上述的故事映射到计算机系统里，将军便成了计算机，而信差就是通信系统。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况。

Paxos/Raft

Paxos 和 Raft 是目前分布式系统领域中两种非常著名的解决一致性问题的共识算法，两者都能解决分布式系统中的一致性问题，但是前者的实现与证明非常难以理解，后者的实现比较简洁并且遵循人的直觉，它的出现就是为了解决 Paxos 难以理解并和难以实现的问题。

There is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos.
世界上只有一种一致性协议，就是Paxos，其它一致性算法都是Paxos算法的不完整版本。

无论是 Paxos 还是 Raft 其实都只能解决非拜占庭将军容错的一致性问题，不能够应对分布式网络中出现的极端情况，但是这在传统的分布式系统都不是什么问题，无论是分布式数据库还是消息队列集群，它们内部的节点并不会故意的发送错误信息，在类似系统中，最常见的问题就是节点失去响应或者失效，所以它们在这种前提下是有效可行的，也是充分的。

POW(区块链中的工作量证明算法)

POW（Proof-of-Work）是一个用于阻止拒绝服务攻击和类似垃圾邮件等服务错误问题的协议，它在 1993 年被 Cynthia Dwork 和 Moni Naor 提出，它能够帮助分布式系统达到拜占庭容错(节点中出现类似叛徒的情况)。

Paxos - The Consensus Algorithm

paxos其实是个很容易理解的算法，建议直接读原文：

1. paxos中的角色

假设分布式系统一组节点想要对某个Value(共享值)达成一致，Paxos把节点分为三种角色：proposers，acceptors，和 learners（每个节点可以身兼多种角色）

• Proposer: 可以提出新的Value(共享值)。
• Proposal: Proposer提出新的Value，称作一个提案。
• Acceptor: 对Proposal进行投票表决。
• Learner：无投票权，从Learner那里得知哪个Proposal被选中。

2. paxos的特点

在非拜占庭错误的条件下，paxos可以实现如下几点：

• 一个或多个节点可以提出Proposal
• 系统必须针对所有提案中的某个Proposal达成一致 (超过半数的Acceptor同意该提案)
• 最多只能对一个确定的Proposal达成一致
• 只要超半数的节点存活并且可互相通信，整个系统就能达成一致状态，即选择一个确定的Proposal

3. paxos的实现过程

Paxos达成共识分成两个阶段：

Prepare阶段

• (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
• (b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Accept阶段

• (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an acceptrequest to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
• (b) If an acceptor receives an accept request for a proposal numberedn, it accepts the proposal unless it has already responded to a preparerequest having a number greater than n.

4. paxos实现过程图解

假设现在有五个节点的分布式系统，此时 A 节点打算提议 X 值，E 节点打算提议 Y 值，其他节点没有提议。

假设现在 A 节点广播它的提议（也会发送给自己），由于网络延迟的原因，只有 A，B，C 节点收到了。注意即使 A，E 节点的提议同时到达某个节点，它也必然有个先后处理的顺序，这里的“同时”不是真正意义上的“同时”。

A，B，C接收提议之后，由于这是第一个它们接收到的提议，acceptedProposal 和 acceptedValue 都为空。

由于 A 节点已经收到超半数的节点响应，且返回的 acceptedValue 都为空，也就是说它可以用 X 作为提议的值来发生 Accept 请求，A，B，C接收到请求之后，将 acceptedValue 更新为 X。

A，B，C 会发生 minProposal 给 A，A 检查发现没有大于 1 的 minProposal 出现，此时 X 已经被选中。等等，我们是不是忘了D，E节点？它们的 acceptedValue 并不是 X，系统还处于不一致状态。至此，Paxos 过程还没有结束，我们继续看。

此时 E 节点选择 Proposal ID 为 2 发送 Prepare 请求，结果就和上面不一样了，因为 C 节点已经接受了 A 节点的提议，它不会三心二意，所以就告诉 E 节点它的选择，E 节点也很绅士，既然 C 选择了 A 的提议，那我也选它吧。于是，E 发起 Accept 请求，使用 X 作为提议值，至此，整个分布式系统达成了一致，大家都选择了 X。

参考链接：