基础概念

1、容错

系统运行的过程中对故障的容忍程度。在分布式环境中，通常会出现成员故障、网络分区和网络丢包的问题，分布式容错是指在允许发生这些问题的情况下，系统依然能正常工作

2、共识

在对等的成员集合中，让每个成员都认可某一个值。与一致有差别，一致要求每个成员的数据完全一致，但共识并不要求数据完全一致，只要求客户端从任意成员处获取的值相同即可。

共识与集群的区别：

共识与集群的最大区别是成员之间数据处理方式不同。集群通常需要引入一个额外的存储服务来保证数据的一致性；而共识算法是为了解决数据的一致性而存在的，因此共识系统不需要依赖外部的存储服务。例如ZooKeeper就不需要额外的存储服务，而是依赖自身的ZAB协议就能使各成员之间的数据保持一致。但是在我们的业务系统重，通常需要引入一个公共的数据库服务，如Redis、DB等。

举个例子：在业务开发中，我们可以借助Redis完成应用集群之间的数据共享，达到数据共识的效果。但是如果只有一台Redis，会存在单点问题，所以大多数时候都是引入Redis主从。在Redis的主从架构中，多个Redis实例之间也会出现数据共识问题，毕竟对外部而言Redis只有一个访问入口，这个时候从不可能再给Redis主从架构再添加一层共享存储，因为这样的套娃无法解决问题。此时就需要主从架构的各个节点在不借助外部存储保证数据共识，所以就出现了各种共识算法。

3、拜占庭将军问题

在分布式环境中，也可能存在一些恶意成员，它们会伪造处理结果，甚至散播不正确的消息，这在区块链的应用中很常见。而在后端的分布式应用中，排除人为的故障为之，我们开发的系统也有可能存在漏洞，黑客趁机植入木马，从而破坏系统的安全性，虽然出现这些情况的可能性很低，但是人不能绝对排除。

虽然拜占庭问题不好解决，但是并非不可解决，涉及容错和密码学等专业领域。Lamport证明了在同步网络下，通过验证消息真伪且背叛数量不超过1/3的情况下才有可能达成共识。即需要3F+1的成员总数来保证算法的安全性，其中F位能够容忍的背叛者的数量。

在后端的生产实践中，拜占庭故障的解决成本非常高且出现概率极低。通常，我们在设计算法时，默认不会发生拜占庭故障。后续的分布式共识算法也都是在没有考虑拜占庭问题的环境下设计出来的。

4、多数派

当成员个数为N时，那么多数派的数量为N/2（向下取整）+1，这是Paxos、ZAB、Raft等分布式算法选择Leader时的策略。

集群成员的数量推荐为奇数。原因是因为，当成员总数为5时，多数派的数量需要达到3个（5/2+1），允许出现故障的成员数量为2。当成员个数为6时，多数派的数量需要达到4个（6/2+1），允许出故障的成员数量也为2。因此从节约资源的角度看，没有必要部署6（偶数）个成员。

5、共识算法分类

参考资料

拜占庭类：
1）拜占庭容错（Byzantine Fault Tolerance, BFT）：背叛数量不超过1/3的情况下能够达共识

1. 实用拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）
2. 联邦拜占庭协议（FBA，Federated Byzantine Agreement）
3. 授权拜占庭容错算法（dBFT，DelegatedByzantine Fault Tolerance）
4. BFT-SMaRt
5. Tendermint
6. Hyperledger Fabric

2）工作量证明（Proof of Work，PoW）：以每个节点或服务器的计算能力来竞争记账权的机制，即使用工作量证明机制的共识算法
3） 权益证明（Proof of Stake，PoS）：由系统权益代替算力来决定区块记账权，拥有的权益越大获得记账权的概率就越大。权益，即每个节点占有货币的数量和时间，而货币就是节点所获得的奖励由系统权益代替算力来决定区块记账权，拥有的权益越大获得记账权的概率就越大。权益，即每个节点占有货币的数量和时间，而货币就是节点所获得的奖励

1. 委托权益证明（DPoS）：由被社区选举的可信账户（受托人，比如得票数排行前 101位）来拥有记账权。为了成为正式受托人，用户要去社区拉票，获得足够多的信任。用户根据自己持有的货币数量占总量的百分比来投票。根据自己拥有的权益，投票选出可代表自己的受托节点，受托节点之间竞争记账权
2. 租赁权益证明（LPoS）

4）权威证明（PoA）
5）有向无环图（DAG）
6）容量证明（PoC）
7）燃烧证明 (PoB)
8）身份证明 (PoI)
9）活动证明（PoA）：它是一种混合共识机制，结合了工作量证明（PoW）和权益证明（PoS），以实现更安全和高效的区块链网络。PoA 的开发是为了替代传统的 PoW 和 PoS 机制，这些机制因高能耗和中心化风险而受到批评
10）经过时间证明（PoET）
11）重要性证明

非拜占庭类，故障容错算法（Crash Fault Tolerance，CFT）：

1）Paxos 算法
2）Raft 算法
3）ZAB 协议

比特币中如果采用 Raft 算法实现共识而不是 Pow 算法的区块链会发生什么?

当恶意节点当选为领导者后，可以不断地告诉其他节点，这些比特币都是我的，按照 Raft 的约定，其他节点也就只能接受这种情况，最终就会出现，所有的比特币都被恶意节点盗走的情况.

PoW的容错机制实现了相对的公平，它允许全网 50% 的节点出错，如果要破坏系统，则需要投入极大成本（若你有全球 51% 的算力，则可尝试攻击比特币）

6、ACID&BASE&CAP

ACID：最求一致性

在数据库系统中，保证了数据的完整性

1. 原子性
2. 一致性
3. 隔离性
4. 持久性

BASE：最求可用性

在某些场景中，无需做到强一致，以保证系统的可用性，同时每个应用可以采用适当的方式去使系统数据达到最终一致性。允许存在软状态的基础上，只需要保证整个事务的基本可用性和最终的一致性即可，而并不需要实时保证强一致性。实现这个方案，通常采用异步补偿机制

1）基本可用：分布式系统出现故障时，允许损失部分可用心，但不等于系统不可用。损失部分可用包括：

1. 响应时间的损失
2. 在功能上降级

2）软状态：允许系统中的数据存在中间状态，并认为该状态不会影响系统的张提可用性，即允许节点之间的数据同步存在延迟
3）最终的一致性：系统的所有副本在经历一个时间期限后最终达成一致的状态

CAP：C（ACID）+A（BASE）+P=CAP

CAP：

1. 一致性（C）：所有节点的数据时时保持一致
2. 可用性（A）：任何情况下能够处理客户端的每一个请求
3. 分区容错性（P）：发生分区时，系统应该持续提供服务

对ACID和BASE理论的总结，即任何人不是系统都可归为这三类架构：

1. CP（锁定事务资源）
2. AP（尽最大能力提供服务）
3. CA（本地一致性）：由于分区P永远会发生，所以选择CA的系统通常会在发生分区时让各个子分区满足CA

---

Paxos

1、相关概念

1. Instance：一个单调递增的存储列表，存放后续达成共识提案
2. 提案编号：单调递增的全局唯一Id
3. 提案：由提案编号和提案指令组成，提案指令是指需要达成共识的内容
4. 通过、批准、选择：Acceptor同意Prepare请求时使用“通过”，Acceptor同意Accept请求时使用“批准”，多数派Acceptor同意某一个Accept请求时，则意味着该提案达成共识，使用“选择”
5. 角色：Proposer（提案者）、Acceptor（接受者）、Learner（学习者）
6. 阶段：Prepare阶段、Accept阶段、Learn阶段
7. 活锁：指多个Proposer同时发起提案时，每个提案的Prepare请求和Accept请求交叉运行，互相干扰，导致最终选不了任何一个提案。

2、三种角色

Proposer（提案者）：

整个算法的发起者，驱动协商的进程。在收到客户端的请求后将其封装为一个提案（Proposal），并将该提案发送给所有的接受者，根据接受者的响应情况，驱动算法决定是否需要继续往下运行；

Acceptor（接受者）：

对提案进行决策，它在收到Proposer发来的提案后，根据预先约定的规则对提案进行投票，向Proposer反馈自己的投票结果

Learner（学习者）：

不参与算法的决策过程，不是Paxos集群的重要组成部分，可以全部失败也可以与集群断开链接，而不损害Paxos的正确性。可用于扩展读性能和同步落后的数据

3、运行阶段

1、Prepare阶段

略

2、Accept阶段

略

3、Learn阶段

略

4、Multi Paxos

在Basic Paxos的基础上进行优化：

1. 引入Leader角色，只能有Leader发起提案，减少了出现活锁的概率
2. 在没有提案冲突的情况下，省略Prepare阶段，优化成一阶段，减少RPC调用的次数

5、总结

共识算法：在分布式系统中，如何让集群的每个成员都认同某个值 （提案指令），“一致”是要求每个成员的数据完全相同；而 “共识”并不要求数据相同，只要求从任意成员上获取的值是相同的即可。

Paxos是一个具有高度容错性的共识算法，它的容错性来源于只需要多数派的正常响应。达成有效共识的关键在于，提案指令直到第二阶段才会被真正提出。

Paxos分为两个阶段，即Prepare阶段和Accept阶段，如果在两阶段都获得多数派的支持，则视为提案通过。

1. Prepare阶段：不发送提案指令，只发送提案编号，意义在于争取Acceptor的承诺，并获取在Acceptor中己被批准的提案指令。
2. Accept阶段：真正提出提案指令，使该提案指令在集群中达成共识。

Paxos的局限性：

1. 活锁：提案之间互相冲突，导致最终没有任何一个提案被选择。
2. RPC交互次数多，在没有发生提案冲突的情况下，最少需要进行四轮RPC交互才能达成共识。

Paxos 的应用场景：

1. 多副本存储。
2. 分布式状态机，由Paxos来确定操作顺序，并按照顺序输入状态机执行状态转移，从而使每个状态机最终的状态是一致的。

为了解决Paxos的局限性，Multi Paxos引入了Leader角色，提升了协商效率，降低了活锁概率。

1. 只能由 Leader 发起提案，由手允许多个Ieader 存在，所以只是减少了活锁的概率，并不能完全杜绝活锁。
2. 在没有提案冲突的情況下，省略Prepare 阶段，优化成一阶段。

6、演化

Paxos的发展历程：

1. Disk Paxos
2. Cheap Paxos
3. Fast Paxos
4. Generalized Paxos
5. Stoppable Paxos
6. Mencius
7. Vertical Paxos
8. Egalitarian Paxos
9. Speeder Paxos

---

ZAB

Paxos的确是一个不错的共识算法，但存在活锁、RPC交互次数多、实现难度大和部分工程实现方案不完善等问题，尽管Multi Paxos对其有进行了一部分优化，但也只是提供了大致的实现思路，没有描述具体的实现细节，这就导致在工程实现上，只能由工程师根据自己的经验在实践中不断试错。即业界没有一个完成的Multi Paxos实现标准，但是共识算法问题急需解决，于是便诞生了许多机遇Paxos多数派思想的共识算法，ZAB就是其中的一员。并且用于ZooKeeper的共识算法基石。

1、相关概念

1. 提案（Proposal）：进行协商的最小单元，常被称为操作（Operation）、指令（Command）
2. 事务（Transaction）：指提案，常出现在代码中，并非指具有ACID特性的一组操作
3. 已提出的提案：广播的第一阶段所提出的但未提交到状态机的提案。在集群中，可以能有多数派成员已拥有了该提案，也可能仅Leader拥有该提案
4. 已提交的提案：指广播的第二阶段已提交到状态机的提案。在集群中，可能有多数派成员已提交改提案，也可能仅Leader提交了改提案
5. 角色：Leader、Follower、Observer
6. 成员状态：Election、Following、Leading、Observing

2、三种角色

1）Leader：领导者。Leader是整个ZAB算法的核心，其工作内容如下：

1. 事务操作的唯一处理者，将每个事务请求封装成提案广播给每个跟随者，根据跟随者的执行结果控制提案的提交
2. 维护和调度Zookeeper内部各个成员

2）Follower：跟随者。Follwer类似Paxos的Accepter，其工作内容可以分为三部分

1. 接受并处理非事务请求，也就是读请求。如果Follower收到客户端的事务请求，则会将其转发给Leader进行处理
2. 参与提案的决策，对Leader提出的提案进行投票
3. 参与Leader选举投票

3）Observer：观察者。Observer不参与提案的决策，不参与Leader的选举，像是一个没有投票权的Follower，其工作内容如下

1. 可以为客户端提供非事务请求（读请求）
2. 在跨地域场景中，增加Observer，可以降低所在地域读请求的网络延迟
3. 在读性能不佳时，增加Observer，可以在不影响集群写性能的情况下提升读性能

3、成员状态

Leader选举隐含的一个系件就是集群部署，在只有多个成员的前提下，选举Leader才有意义。为了区分选举的进展，每个成员在每个阶段都有特定的状态，这些状态也隐含了当前成员所扮演的角色。

1. ELECTION：已丢失与Leader的连接。该状态可能在集群中没有Leader、Leader出现故障或者由于网络原因感知不到Leader存在时出现，此时当前成员的状态就会更新为ELECTION，在该状态下，当前成员会发起Leader选举。
2. FOLLOWING：跟随状态。暗示当前成员扮演着Follower的角色，明确知道Leader是谁，并且和Leader保持稳定的连接。
3. OBSERVING：观察状态。暗示当前成员扮演着Observer的角色，明确知道Leader是谁，并且和Leader 保持稳定的连接。
4. LEADING：领导状态。暗示当前成员是Leader，并且和多数派的Follower保持稳定的连接。

4、运行阶段

ZAB 的另一个重要目标是在集群崩溃时能自动恢复至正常状态，因此整个运行过程可划分为四个阶段：

1）崩溃恢复：

1. Leader选举（ELECTION）：该阶段处于崩溃恢复之初。当集群中不存在Leader（集群启动时）或者Follower感知不到Leader存在时，则会通过该阶段重新选举数据最完成的Follower作为新一任的准Leader；
2. 成员发现（DISCOVERY）：选举出准Leader后集群所处的状态，用于成员协商沟通Leader的合法性；
3. 数据同步（SYNCHRONIZATION）：选取在Follower中最完整的数据作为基础，修复各个成员的数据一致性。完成该阶段后，准Leader正式晋升为Leader

2）消息广播：

1. 消息广播（BROADCAST）：属于集群良好运行阶段，即Leader拥有多数派的Follower且彼此心跳感知正常。在此阶段，Leader可以向客户端提供正常的服务。类似于二阶段（2PC）的过程，针对客户端事务请求，Leader将其生成对应的Proposal，并发给所有的Follower。Leader收集多数派Follower的选票后，决定是否提交该Proposal

任何一个成员都可能处于ELECTION、FOLLOWING或者LEADING中的任意一个状态，当一个新成员启动时，会先进入ELECTION状态，然后开始尝试选举一个Leader (包括自己）。如果它发现已存在Ieader，则会进入FOLLOWING状态并追随该Leader；如果它自己被选为Leader，则会进入LEADING状态，晋升为Leader。接着集群将依次完成成员发现阶段和数据同步阶段，然后停留在消息广播阶段。

当处于FOLLOWING状态的成员丢失与Leader的连接，或者处于LEADING状态的成员丢失与多数派Follower的连接时，都会回到ELECTION状态开始新的一轮选举。

• 成员发现：准Leader收集多数派Q中的epoch，发起新的epoch，防止Q中的Follower继续接收并处理来自上一个epoch的提案，同时收集Q中每个Follower的历史提案
• 数据同步：准Leader提出自己作为新epoch的Leader，并携带新epoch的初始提案集。一旦准Leader收到多数派Follower的确认（即ACK-LD），就正式晋升为Leader，然后通知Follower完成初始提案集的提交
• 消息广播：处理客户端的事务请求，类似一个基于多数派思想、没有回滚操作的二阶段提交协议

5、ZooKeeper流程

选举阶段：

1. 逻辑时钟：用于表示选举的提案编号，每轮选举后都会自增1
2. 发起投票
3. 处理选票
4. 选票比较

成员发现阶段：

1. 发送Followerinfo消息
2. 发送Leaderinfo消息
3. 发送Ackepoch消息

数据同步阶段：

1. 准备同步数据
2. 同步数据
3. 发送Newleader消息
4. 发送Uptodate消息

消息广播阶段：

1. Proposal消息
2. Ack消息
3. Commit消息

6、总结

ZAB并不是一个独立的类库，而是一个为Zookeeper量身定做的共识问题的解块方案，它的诞生是为了解决Paxos的活锁、实现难度高等问题，同时结合自身业务实现提案的有序性。ZAB实现了日志对齐、数据快照及崩溃恢复等功能，使集群更加稳定、可靠。

整个ZAB分为Leader选举＋三个阶段(成员发现阶段、数据同步阶段、消息广播阶段）。其中，Leader 选举可以通过任意算法实现，ZAB规范了后面三个阶段的实现方案。

在ZAB的工程实现中，Leader选举采用选票比较方式能快速地选举出具有最完整数据的成员成为Leader。选举过程大致如下：

1. 各个成员广播自己的选票（第一轮选票都支持自己成为Leader)；
2. 在收到其他成员的选票后，与自己的选票进行比较，依次对比epoch、zxid、myid；
3. 根据比较结果更新自己的选票并重新广播选票；
4. 直到收到多数派选票支持同一成员，退出选举，Leader诞生。

后三个阶段对于ZAB论文和ZAB实现，他们在消息交互和消息内容上有很大的区别。其中消息广播阶段是一个基于多数派思想并移除了回滚操作的二阶段提交协议，Follower要么接受提案，要么放弃Leader。

ZAB和Multi Paxos的联系

不同点：

1. Leader作用不同：ZAB在Multi Paxos基础上添加了Leader选举限制，简化了实现过程，更易让人理解，但强依赖Leader使灵活性略逊于Multi Paxos。虽然二者都存在Leader，但是作用不同。Multi Paxos中的Leader主要用于限制Proposer数量，降低出现活锁的概率；而ZAB规定了单一的Leader，主要用于保证提案的有序性。
2. 出发目的不同：Paxos 的目的是构建一个分布式的一致性状态机系统，而ZAB的目的是设计一个高可用的分布式协调服务。二者的设计理念不在同一个层次，ZAB 更倾向于顶层应用。

相同点：

1. 都是多数派决策的算法；
2. 都是两阶段处理；
3. 都有类似Leader周期的变量，在Multi Paxos中是提案编号，在ZAB中是epoch。

---

Raft

1、相关概念

1）多数派：同前
2）任期：Raft将时间分割为不同长度的任期，记作term。term可以类比ZAB的epoch，term使用连续的的整数进行单数递增，并随着RPC消息在成员之间交换。Raft并没有强制要求集群只能存在一个Leader，而是规范了一个term只会存在一个Leader。Raft使用term作为Leader的任期号并遵守以下规则：

1. 每个Raft成员在本地维护自己的term
2. 在每轮Leader选举之前递增自己本地的term
3. 每个RPC消息都将携带自己本地的term
4. 每个Raft成员拒绝处理小于自己本地term的RPC消息

3）成员状态：Follower（跟随者）、Candidate（候选人）、Leader（领导者）、无投票权角色、Witness成员
4）运行阶段：

1. Leader选举阶段：在集群启动的时候或Leader出现故障的时候，需要选出一个新的Leader，接替上一份Leader的工作
2. 日志复制阶段：在该阶段中，Leader可以接收客户端请求并进行正常处理，由Leader向Follower同步日志项

5）RPC消息：

1. RequestVote：请求投票消息，用于选举Leader

2. AppendEntries：追加条目消息，用于下列场景：

   2.1 Leader用该消息向Follower执行日志复制
   2.2 Leader与Follower之间的心跳检测
   2.3 Leader与Follower之间的日志对齐

3. InstallSnapshot：快照传输消息

4. TimeoutNow：快速超时消息，用于Learner切换，可立即发起Leader选举

2、成员状态

任何时候任意节点成员都会处在Follower、Candidate和Leader三种状态之一

1. Follower（跟随者）：只会处理来自Leader和Candidate的请求。如果一个客户端和Follower通信，Follower会将请求重定向给Leader，可以类比为ZAB中的Follower
2. Candidate（候选人）：如果Leader出现故障或者Follower等待心跳超时，则Follower会变更为Candidate，新的Leader只能从Candidate中产生
3. Leader（领导者）：当某个Candidate获得多数派的选票时，该成员晋身为Leader，负责处理接下来的客户端请求、日志复制管理及心跳消息管理
4. 无投票权角色：当新成员上线的时候，以学习者的身份加入集群，在不影响集群的情况下，快速和Leader完成数据对齐。无投票权成员也可用于在不影响协商效率的基础上提供额外的数据备份
5. Witness成员：一个只投票但不存储数据的成员，它对存储资源的需求较小

3、运行阶段

1、Leader选举

略

2、日志复制

略

3、日志对齐

略

4、幽灵日志

略

5、安全性

略

4、总结

Raft是强Leader模型的算法，日志项只能由Leader复制到其他成员，这意味着日志复制是单向的，Leader从来不会覆盖自己的本地日志项，即所有日志项以Leader为基准的。

Raft和Paxos的区别：

1. Raft引入了强Leader模型，规避了Basic Paxos活锁问题，Multi Paxos只降低了活锁的概率。
2. 协商过程：Multi Paxos在大多数情况下可以优化为在一阶段内提交，但是达到一阶段提交的条件仍然是需要进入Prepare阶段，而Raft通过心跳机制替代了提交阶段
3. 日志连续性：Paxos允许乱序提交，同样允许存在空洞日志。而Raft通过Leader严格规定了日志的连续性。换句话说，Paxos只保证每个提案（日志项）达成共识的安全性，而Raft 在此基础上还保证了日志项的连线性，这特性表明在两个成员之间，相同日志索引且term相同，那么该日志项之前所有的日志项也必然相同。
4. 非事务消求：虽然 Multi Paxos可以让Leader 为每个提案（日志项）记录Confim日志，但是对于未记录Confirm日志的提案，必须重新走一遍 Paxos 流程，才能知道该提案是否已达成共识。而 Raft在日志连续的特性上，也要求了日志项提交的顺序。因此，Raft只需要明确committedIndex，即可推测在此之前所有日志项都已达成共识。
5. 日志压缩：Paxos 没有明确这个细节，但是在 Paxos 的工程实现中往往也会采用类似Raft 提到的快照方式进行日志压缩。
6. 日志存储：Paxos 并不要求每个成员拥有完整的数据，而 Raft要求成员加入集群时先和Leader完成数据对齐。
7. 崩溃恢复：这一点在 Paxos 中并没有那么重要，每个成员都具有对等性，成员崩溃后重启即可。而Raft成员崩溃后，再次加入集群时，需要以Leader的数据为基准恢复数据，然后才可以加入集群。

Raft与ZAB的区别：

1. 协商提案时：ZAB中的Follower会参与提案的决策，而在Raft中，Follower只会被动地接收日志项。
2. 日志流向时：在Raft中，日志只能从Leader流向Follower，而在ZAB中，当Leader晋升时，需要收集所有 Follower的数据来生成 Initial History。
3. Leader选举不同：Raft引入了随机超时，降低了选举沖突的可能性，而ZAB通过增加员工ID来解决选举冲突的问题。Raft的每个成员在一个term上只能投一票，而ZAB的每个成员在一轮选举中可以投出多票。
4. 上一任Leader的数据处理不同：Raft认为之前term不明确提交状态的日志都是未提交的，需要等待当前Leader提出新的日志项且达成共识后，才认为之前的日志项已提交。ZAB 认为上一任 Leader提出的不明确提交状态的日志都是己提交的，并且会将这些日志复制到其他成员中。
5. 在ZAB中，协商分为两个阶段，而Raft以心跳机制+日志连续记录的特性将协商优化成一个阶段

FLP定理

FLP又叫FLP Impossibility和FLP不可能性。它描述了一个现象，即在达成共识的关键时候，总会出现一个东西，让某个成员停止工作，进而导致系统无法达成共识。

完整定理为，在不考虑拜占庭故障，并且网络非常稳定，所有的消息都能被正常传递的情况下，也不存在一个完全异步的共识算法能容忍哪怕只有一个成员发生故障的情况。

FLP定理基于完全的异步模型，这是一个对网络环境要求极低的模型（不同于网络I/O中的概念）：

• 异步模型：指消息延迟无限大且没有任何辅助程序，不能使发送者和接受者保持同步，从而无法做出消息超时的判断，也无法探测消息是否发送失败。一个消息未能到达接受者，接受者就无法判断消息是延迟还是丢失了，或者发送者根本没有发送
• 同步模型：所有成员的时钟偏移量都是有上限的，消息传输的延迟是有限的。这意味着可以参考过往经验为消息设置最大的延迟时间，以此探测消息状态和成员状态

由FLP定理可知在异步模型下，这类问题的理论极限。在现实世界中，人们更倾向于用同步模型，纯异步模型的使用场景较少。

FLP定理表明，在完全异步的网络环境中，安全（Safety）、活性（Liveness）、容错（Fault Tolerance）三者只能选择其二，与CAP相似，但是并不相同：

1. 安全：所有成员必须认同已达成共识的值是同一个值，这是系统运行的最低要求
2. 活性：算法在有限的时间内达成共识，而不能无限循环下去，永远处于中间状态
3. 容错：允许部分成员发生故障，这不影响算法的正确运行

---

Gossip

利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致(实现最终一致性)，在极端情况下（比如集群中只有一个节点在运行）也能运行

1、相关概念

Paxos、Raft、ZAB 等分布式算法经常会被称作是“强一致性”的分布式共识协议，其实这样的描述抠细节概念的话是很别扭的，会有语病嫌疑，但我们都明白它的意思其实是在说“尽管系统内部节点可以存在不一致的状态，但从系统外部看来，不一致的情况并不会被观察到，所以整体上看系统是强一致性的”。与它们相对的，还有另一类被冠以“最终一致性”的分布式共识协议，这表明系统中不一致的状态有可能会在一定时间内被外部直接观察到。一种典型且极为常见的最终一致的分布式系统就是DNS 系统，在各节点缓存的 TTL 到期之前，都有可能与真实的域名翻译结果存在不一致。在比特币网络和许多重要分布式框架中都有应用的另一种具有代表性的“最终一致性”的分布式共识协议：Gossip 协议。

Gossip只能称作是“共识协议”（或者称之为复制算法），它所解决的问题并不是直接与 Paxos、Raft这些共识算法等价的，只是基于Gossip之上可以通过某些方法去实现与 Paxos、Raft相类似的目标而已。一个最典型的例子是比特币网络中使用到了Gossip协议，用它来在各个分布式节点中互相同步区块头和区块体的信息，这是整个网络能够正常交换信息的基础，但并不能称作共识；比特币使用工作量证明（Proof of Work，PoW）来对“这个区块由谁来记账”这一件事情在全网达成共识，这个目标才可以认为与 Paxos、Raft 的目标是一致的。

2、复制方式

直接邮寄(Direct Mail)：

直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。即只采用直接邮寄是无法实现最终一致性的

反熵(Anti-entropy)：

集群中的节点周期性地随机选择某个其它节点，然后通过互相交换自己的所有数据来消除两者之间的差异，直到整个网络中节点数据一致

谣言传播(Rumor mongering)：

各节点周期性的，向随机的一组节点广播更新数据。其他节点收到更新的数据后，继续周期性的，向随机的一组节点广播更新数据，知道所有节点都处理了新数据。为了使谣言传播能够停止（避免广播风暴），Gossip增加了removed状态，当节点收到谣言并且该谣言处理removed（之前已经处理过的谣言）时，该节点将不继续传播该谣言

3、优劣势

优势：

1. 简单
2. 可扩展、容错：由于各个节点之间的对等性，允许节点之间任意的增加和减少
3. 天然的去中心化
4. 传播速度快，适用于非常庞大的集群

劣势：

1. 达成最终一致性的时间不确定
2. 消息延迟，只能实现最终一致性，传播过程中，数据不一致
3. 广播RPC消息量大，对网络有一定的压力
4. 会出现拜占庭将军问题，且无法解决