一、分布式系统的挑战

CAP理论的核心思想是任何基于网络的数据共享系统最多只能满足数据一致性(Consistency)、可用性(Availability)和网络分区容忍(Partition Tolerance)三个特性中的两个。

Consistency 一致性一致性指“all nodes see the same data at the same time”，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致。等同于所有节点拥有数据的最新版本。

Availability 可用性

可用性指“Reads and writes always succeed”，即服务一直可用，而且是正常响应时间。对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。也就是，该系统使用的任何算法必须最终终止。当同时要求分区容忍性时，这是一个很强的定义：即使是严重的网络错误，每个请求必须终止。

Partition Tolerance 分区容忍性

在通常的分布式系统中，为了保证数据的高可用，通常会将数据保留多个副本(replica)，网络分区是既成的现实，于是只能在可用性和一致性两者间做出选择。CAP理论关注的是绝对情况下，在工程上，可用性和一致性并不是完全对立，我们关注的往往是如何在保持相对一致性的前提下，提高系统的可用性。

二、数据一致性模型

在互联网领域的绝大多数的场景，都需要牺牲强一致性来换取系统的高可用性，系统往往只需要保证“最终一致性”，只要这个最终时间是在用户可以接受的范围内即可。

强一致性：当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值。这种是对用户最友好的，就是用户上一次写什么，下一次就保证能读到什么。根据 CAP 理论，这种实现需要牺牲可用性。

弱一致性：系统并不保证续进程或者线程的访问都会返回最新的更新过的值。用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。

最终一致性：是弱一致性的一种特例。系统保证在没有后续更新的前提下，系统最终返回上一次更新操作的值。在没有故障发生的前提下，不一致窗口的时间主要受通信延迟，系统负载和复制副本的个数影响。

最终一致性模型根据其提供的不同保证可以划分为更多的模型，包括因果一致性和读自写一致性等。

三、分布式事务 ：二阶段提交协议（Two Phase Commitment Protocol）和三阶段提交协议（Three Phase Commitment Protocol）

1.二阶段提交协议

Two Phase指的是Commit-request阶段Commit阶段。

请求阶段在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。

在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。

提交阶段在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。

当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。

可以看出，两阶段提交协议存在明显的问题：

同步阻塞执行过程中，所有参与节点都是事务独占状态，当参与者占有公共资源时，第三方节点访问公共资源被阻塞。

单点问题一旦协调者发生故障，参与者会一直阻塞下去。

数据不一致性在第二阶段中，假设协调者发出了事务commit的通知，但是因为网络问题该通知仅被一部分参与者所收到并执行commit，其余的参与者没有收到通知一直处于阻塞状态，这段时间就产生了数据的不一致性。

2.三阶段提交协议

三阶段提交针对两阶段提交做了改进：

引入超时机制。在2PC中，只有协调者拥有超时机制，3PC同时在协调者和参与者中都引入超时机制。

在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。

四、Paxos算法

二阶段提交还是三阶段提交都无法很好的解决分布式的一致性问题，直到Paxos算法的提出，Paxos协议由Leslie Lamport最早在1990年提出，目前已经成为应用最广的分布式一致性算法。

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

1.节点角色

Paxos 协议中，有三类节点:

Proposer:提案者

Proposer 可以有多个，Proposer 提出议案(value)。所谓 value，在工程中可以是任何操作，例如“修改某个变量的值为某个值”、“设置当前 primary 为某个节点”等等。Paxos 协议中统一将这些操作抽象为 value。不同的 Proposer 可以提出不同的甚至矛盾的 value，例如某个 Proposer 提议“将变量 X 设置为 1”，另一个 Proposer 提议“将变量 X 设置为 2”，但对同一轮 Paxos 过程，最多只有一个 value 被批准。

Acceptor:批准者

Acceptor 有 N 个，Proposer 提出的 value 必须获得超过半数(N/2+1)的 Acceptor 批准后才能通过。Acceptor 之间完全对等独立。

Learner:学习者

Learner 学习被批准的 value。所谓学习就是通过读取各个 Proposer 对 value 的选择结果，如果某个 value 被超过半数 Proposer 通过，则 Learner 学习到了这个 value。

这里类似 Quorum 议会机制，某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准，Learner 需要至少读取 N/2+1 个 Accpetor，至多读取 N 个 Acceptor 的结果后，能学习到一个通过的 value。

2.约束条件

上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。有些文章会添加一个Client角色，作为产生议题者，实际不参与选举过程。

Paxos中 proposer 和 acceptor 是算法的核心角色，paxos 描述的就是在一个由多个 proposer 和多个 acceptor 构成的系统中，如何让多个 acceptor 针对 proposer 提出的多种提案达成一致的过程，而 learner 只是“学习”最终被批准的提案。

Paxos协议流程还需要满足几个约束条件：

Acceptor必须接受它收到的第一个提案；

如果一个提案的v值被大多数Acceptor接受过，那后续的所有被接受的提案中也必须包含v值（v值可以理解为提案的内容，提案由一个或多个v和提案编号组成）；

如果某一轮 Paxos 协议批准了某个 value，则以后各轮 Paxos 只能批准这个value；

每轮 Paxos 协议分为准备阶段和批准阶段，在这两个阶段 Proposer 和 Acceptor 有各自的处理流程。

Proposer与Acceptor之间的交互主要有4类消息通信，如下图：

这4类消息对应于paxos算法的两个阶段4个过程：

Phase 1a) proposer向网络内超过半数的acceptor发送prepare消息 b) acceptor正常情况下回复promise消息

Phase 2a) 在有足够多acceptor回复promise消息时，proposer发送accept消息 b) 正常情况下acceptor回复accepted消息

3.选举过程

Phase 1 准备阶段

Proposer 生成全局唯一且递增的ProposalID，向 Paxos 集群的所有机器发送 Prepare请求，这里不携带value，只携带N即ProposalID 。

Acceptor 收到 Prepare请求 后，判断：收到的ProposalID 是否比之前已响应的所有提案的N大：如果是，则：(1) 在本地持久化 N，可记为Max_N。(2) 回复请求，并带上已Accept的提案中N最大的value（若此时还没有已Accept的提案，则返回value为空）。(3) 做出承诺：不会Accept任何小于Max_N的提案。

如果否：不回复或者回复Error。

Phase 2 选举阶段

P2a：Proposer 发送 Accept经过一段时间后，Proposer 收集到一些 Prepare 回复，有下列几种情况：(1) 回复数量 > 一半的Acceptor数量，且所有的回复的value都为空，则Porposer发出accept请求，并带上自己指定的value。(2) 回复数量 > 一半的Acceptor数量，且有的回复value不为空，则Porposer发出accept请求，并带上回复中ProposalID最大的value(作为自己的提案内容)。(3) 回复数量 <= 一半的Acceptor数量，则尝试更新生成更大的ProposalID，再转P1a执行。

P2b：Acceptor 应答 AcceptAccpetor 收到 Accpet请求 后，判断：(1) 收到的N >= Max_N (一般情况下是 等于)，则回复提交成功，并持久化N和value。(2) 收到的N < Max_N，则不回复或者回复提交失败。

P2c: Proposer 统计投票经过一段时间后，Proposer 收集到一些 Accept 回复提交成功，有几种情况：(1) 回复数量 > 一半的Acceptor数量，则表示提交value成功。此时，可以发一个广播给所有Proposer、Learner，通知它们已commit的value。(2) 回复数量 <= 一半的Acceptor数量，则 尝试 更新生成更大的 ProposalID，再转P1a执行。(3) 收到一条提交失败的回复，则尝试更新生成更大的 ProposalID，再转P1a执行。

4.相关讨论

Paxos算法的核心思想：（1）引入了多个Acceptor，单个Acceptor就类似2PC中协调者的单点问题，避免故障（2）Proposer用更大ProposalID来抢占临时的访问权，可以对比2PC协议，防止其中一个Proposer崩溃宕机产生阻塞问题（3）保证一个N值，只有一个Proposer能进行到第二阶段运行，Proposer按照ProposalID递增的顺序依次运行(3) 新ProposalID的proposer比如认同前面提交的Value值，递增的ProposalID的Value是一个继承关系

为什么在Paxos运行过程中，半数以内的Acceptor失效都能运行？ (1) 如果半数以内的Acceptor失效时 还没确定最终的value，此时，所有Proposer会竞争 提案的权限，最终会有一个提案会 成功提交。之后，会有半过数的Acceptor以这个value提交成功。(2) 如果半数以内的Acceptor失效时 已确定最终的value，此时，所有Proposer提交前 必须以 最终的value 提交，此值也可以被获取，并不再修改。

如何产生唯一的编号呢？在《Paxos made simple》中提到的是让所有的Proposer都从不相交的数据集合中进行选择，例如系统有5个Proposer，则可为每一个Proposer分配一个标识j(0~4)，则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示提出议案的次数)。

五、Raft算法

六、拜占庭

共识机制就是在一个群体中的个体通过某种方式达成一致性的一种机制，比如在一个团队、或者一个公司里的个体意见不一致时，就需要有一个领导，由领导来做决定，保证团队达成共识。

目前的共识算法，主要有基于算力的POW，基于股权的POS和基于投票的DPOS算法，以及著名的拜占庭容错算法。

一、共识机制

团队里的共识机制延伸到普通的分布式系统里面，就是系统需要有一个master，系统的所有决定都由master来达成共识，在分布式系统里面master的选举其实就是基于某种共识机制达成共识。

到了区块链中，由于区块链是一种去中心化的分布式系统，所以区块链中是没有类似于团队里的领导，以及分布式系统中的master的角色，这样就需要有某种共识机制，以便保证系统一致性。

实际上当节点之间的通信网络不可靠的情况下，系统是无法达成共识的，具体原因请参考“两军问题"。即使在网络通信可靠的情况下，一个可扩展的分布式系统的共识问题也是无解的。这个结论被称为”FLP不可能性原理“。一般的把故障（不响应）即信道不可靠的情况称为”非拜占庭错误“,恶意响应（即系统被攻击）称为”拜占庭错误“。

二、拜占庭将军问题

拜占庭将军问题是一个共识问题: 首先由Leslie Lamport与另外两人在1982年提出，被称为The Byzantine Generals Problem或者Byzantine Failure。核心描述是军中可能有叛徒，却要保证进攻一致，由此引申到计算领域，发展成了一种容错理论。

论文地址：The Byzantine Generals Problem

一群将军想要实现某一个目标（一致进攻或者一致撤退），但是单独行动行不通，必须合作，达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。

1.两军问题和TCP协议

拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，我们已经假定了信道是没有问题的，并在这个前提下，去做一致性和容错性相关研究。

如果需要考虑信道是有问题的，这涉及到了另一个两军问题，两军问题在经典情境下是不可解的，现代通信系统中应用三次握手与TCP协议来处理此类问题，不过这也只是一种相对可靠的方式。

2.口头协议和书面协议

算法需要说明的是：

(1) 在第一轮将军会把消息发送给所有的副官，第i个副官收到的记为 Vi。如 1(这里代表的是Attack)

(2) 在第二轮里面，Li(即第i个副官)会怀疑将军发来的消息Vi是对还是错，于是他会问其余的副官。这样他就会得到剩下的(n-2)个副官的值。 i从1到n-1，所以每个副官都会得到剩余的n-2个副官手里的Vi。在这一步骤里，忠诚的副官j会直接将自己的 Vj发送给其它人。叛徒则会发假消息。

在n=7,m=2的时候 如果将军是忠臣的话，那么在第二轮忠诚的副官确实已经可以判断出要做的决定，因为他们会收到(1 1 1 0 0 )再加上将军发来的1就是 1 1 1 1 0 0 但是这个算法是递归的所有必须要到第三轮。并且如果将军是个叛徒的话，那么第二轮有情形是做不出决定的。

这里对进入第三轮的解释是，如L1收到其它L2~L6发来的Vj, 但是他要怀疑准确性，比如L1会想L2发给自己是否是正确的呢？那么就进入第三轮进行投票。

(3)在第三轮里面，接着(2)中后面的问题。L1会依次询问L3,4,5,6 ，问他们上一轮L2给他们发了什么，然后L1会得到在(2)中 L2->L3, L2->L4,L2->L5, L2->L6的值 这样再结合自己的L2->L1的值，从这5个里面用majority函数投出决定得到L2发给自己的消息值。依次再进行L3,L4,L5,L6在第二轮中发给自己的消息的确认。

这样L1就完成了第二轮的确认。之后L1再从第一步中将军发给自己的vi和第二轮中确定的5个值中投出自己的决定。

其余的L2，L3后续也进行同样的步骤。

书面协议和口头协议最大区别是，副官可以叛变并且说谎，也就是中国人讲的口说无凭。书面协议是我们给消息加上将军的签名，必须通过签名来验证，就是为了防止说谎。

在签名算法中加了两个条件：

忠诚将军的签名是不能伪造的，内容修改可检测

任何人都可以识别将军的签名，叛徒可以伪造叛徒司令的签名

三、PBFT 实用拜占庭算法

1.五个概念

client：请求（request）资源者

replica：副本，所有参与提供服务的节点

primary：承担起提供服务主要职责的节点

backup：其他副本，但相对于primary角色

view：处于存在 primary-bakup场景中的相对稳定的关系，叫视图。如果primary出现故障，这种相对稳定的视图关系就会转变（transit），某个backup转变为primary。