的协议是加密+拜占庭将军_分布式协议之拜占庭问题

分布式协议笔记

常用的分布式算法

分布式算法的四度空间

为了更好地理解最常用的分布式算法的特点，作者从拜占庭容错、一致性、性能和可用性四个纬度整理了一张表

拜占庭容错

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

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

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

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

一致性

一般我们将一致性分为三类：

1.弱一致性: 写操作完成后，系统不能保证后续的访问都能读到更新后的值

2.强一致性: 保证写操作完成后，任何后续访问都能读到更新后的值。

3.最终一致性: 保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值

强一致性具有多种含义：在埃里克·布鲁尔的猜想中，CAP 中的强一致性(也就是 C)是指 ACID 的 C，系统状态的一致性，而这种一致性，可以通过二阶段提交协议来实现。

其次，在 CAP 定理中，CAP 中的强一致性(也就是 C)是指原子一致性(也就是线性一致性)。其中，Paxos、Raft 能实现线性一致性，而 ZooKeeper 基于读性能的考虑，它通过 ZAB 协议提供的是最终一致性。

可用性

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

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

性能

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

拜占庭将军问题

使用计算机中的节点为例：一个计算机系统拥有多个节点，但是节点间需要通过网络通信，消息不一定能及时、准确的传达到各个节点手中。

现在假设有一个拥有三个分别为A、B、C的节点的系统，节点会发出A消息与B消息,按照少数服从多数节点接受1号或2号消息并执行指令。但是在节点传输信息时，可能会有以下情况：

•节点发生故障传输了误导信息。•发生通讯故障、信息丢失•发生通讯被中间人攻击，攻击者恶意伪造信息和 劫持通讯。

此时如果有任意一个节点故障，发送给另外两个节点的消息不一致，若其他两个节点本身是正常的，就会导致其他两个节点因为少数服从多数而执行不一致的命令。例如B发生了故障，给A发送了1号消息，给C节点发送了2号消息，而A和C都正常的发送给其他节点1号或者2号消息，那么A和C最后1号和2号消息的比例分别为：2：1 和 1：2，而导致不一致的产生。

原文中使用战国之间的信使来比喻，信息则分为进攻和撤退

解决方案：

口信消息型拜占庭问题之解: •第一轮：首先应当增加一个节点D作为主节点，并令其最先发送消息节点，其他作为从节点，主节点向从节点发送信息，若从节点未收到信息则默认收到信息B。•第二轮：除了第一轮的主节点以外，所有的节点都将自己作为主节点向剩余节点发送消息，之后按照少数服从多数来执行指令。

具体演示：假设D节点向从节点发送了1号消息，而其他的节点都收到了消息，但是在第二轮中B节点发生了故障，发送给A、C两个节点2号消息，此时A和C收到的消息中1号和2号的比例都是 2 : 1，从而保证了消息的一致性。

而若是主节点发生了故障，向B节点发送了2号消息，因为其他剩余节点会互相之间通信保证消息一致，也不会产生错误。

那么如果故障节点数为 m，总节点数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了。

不过，这个算法虽然能解决拜占庭将军问题，但它有一个限制：如果故障节点数为 m，那么节点总数必须不小于 3m + 1。那么有没有办法，在不增加节点数的时候，直接解决二正一误的难题呢？

签名消息型拜占庭问题之解：•其实也可以通过签名的方式来保证消息的正确性，任何人都能验证消息真伪，并且不能伪造消息。如果发生故障，让消息按一定方式排序并选取中间的某个一同执行。

加密算法可以采用https使用的RSA加密(公钥加密)

非拜占庭场景

在计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错算法(Crash Fault Tolerance，CFT)。

CFT解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。也就是说，这个场景可能会丢失消息，或者有消息重复，但不存在错误消息，或者伪造消息的情况。常见的算法有 Paxos 算法、Raft算法、ZAB 协议