分布式协议与算法实战

拜占庭错误是莱斯利兰百特在《拜占庭将军问题》提出一个错误模型，描述了一个完全不可信的场景，除了存在故障的行为，还存在恶意行为，顾名思义，拜占庭容错（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭错误了

非拜占庭容错，又叫故障容错（Crash Fault Tolerance，CFT），解决的是分布式系统中存在故障，但不存在恶意节点的共识问题，比如进程奔溃，服务器硬件故障等等。

一般而言，在可信环境（比如企业内网）中，系统具有故障容错能力就可以了，常见的算法有二阶段提交协议（2PC）、TCC（Try-Confirm-Cancel）、Paxos 算法、ZAB 协议、Raft 算法、Gossip 协议、Quorum NWR 算法。

而在不可信的环境（比如有人做恶）中，这时系统需要具备拜占庭容错能力，常见的拜占庭容错算法有 POW 算法、PBFT 算法。

分类

首先，在埃里克·布鲁尔的猜想中，CAP 中的强一致性（也就是 C）是指 ACID 的 C，系统状态的一致性，而这种一致性，可以通过二阶段提交协议来实现。其次，在 CAP 定理中，CAP 中的强一致性（也就是 C）是指原子一致性（也就是线性一致性）。其中，Paxos、Raft 能实现线性一致性，而 ZooKeeper 基于读性能的考虑，它通过 ZAB 协议提供的是最终一致性。

一般而言，在需要系统状态的一致性时，你可以考虑采用二阶段提交协议、TCC。在需要数据访问是的强一致性时，你可考虑 Raft 算法。在可用性优先的系统，你可以采用 Gossip 协议来实现最终一致性，并实现 Quorum NWR 来提供强一致性。

可用性说的是任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据，可用性强调的是服务可用。

一般来讲，采用 Gossip 协议实现最终一致性系统，它的可用性是最高的，因为哪怕只有一个节点，集群还能在运行并提供服务。其次是 Paxos 算法、ZAB 协议、Raft 算法、Quorum NWR 算法、PBFT 算法、POW 算法，它们能容忍一定数节点故障。

最后是二阶段提交协议、TCC，只有当所有节点都在运行时，才能工作，可用性最低。

一般来讲，采用 Gossip 协议的 AP 型分布式系统，具备水平扩展能力，读写性能是最高的。其次是 Paxos 算法、ZAB 协议、Raft 算法，因为它们都是领导者模型，写性能受限于领导者，读性能取决于一致性实现。最后是二阶段提交协议和 TCC，因为在实现事务时，需要预留和锁定资源，性能相对低。

通过一定工作量证明你是好人

通过签名消息约束叛变行为

二阶段提交协商

提交请求阶段

提交执行阶段

Try(预留)

Confirm(确认)

Cancel(撤销)

准备阶段（Prepare）

接受阶段（Accept）

以Master为准

故障恢复后，通过catch-up机制进行数据恢复

成员变更时，新加入节点，先同步状态和数据，不具有投票权

请求投票（RequestVote）RPC

日志复制（AppendEntries）RPC

任期编号

Raft算法中任期，不只是时间段，而且，任期编号的大小，会影响领导者选举和请求处理

领导者的心跳信息，能阻止跟随着发发起新的选举

指定时间内，未接收到领导者信息，跟随者推荐自己为候选者，发起选举

赢得大多数选票的候选人，将晋升为领导者

在一次选举中，每一个服务器节点，最多会对一个任期编号，投出一张选票

当任期编号相同时，日志完整性高的跟随者，将拒绝投票给日志完整性低的候选人

第一种

第二种