CAP 定理

CAP 定理，又称布鲁尔定理（Brewer's theorem），它支出对于一个分布式计算系统来说，不可能同时满足以下三点：

1. 一致性（Consistency），等同于所有节点访问同一份最新的数据副本；

2. 可用性（Availability），每次请求都能获取到非错的响应，但是不保证获取的数据为最新的数据；

3. 分区容错性（Partition tolerance），以实际效果而言，分区相当于对通讯的时限要求。系统如果不能再时限内打成数据一致性，就意味着发生了分区的情况，必须就当前操作在 C 和 A 直接做出选择。

根据定理，分布式系统只能满足三项中的两项，而不可能满足全部三项。

共识机制

共识机制（consensus），常见于区块链领域，即达成共识的机制。在分布式系统中，依据系统对故障组件的容错能力，分为崩溃容错协议（crash fault tolerant，CFT）和拜占庭容错协议（Byzantine fault tolerant，BFT）。

由于加密货币多数采用去中心化的区块链设计，节点是各处分散且平行的，所以必须设计一套制度，来维护系统运作顺序与公平性，统一区块链版本，并奖励提供资源维护区块链的使用者，以及惩罚恶意的危害者。这样的制度，必须依赖某种方式来证明，是由谁取得了一个区块链的打包权（或记账权），并且可以获取打包这一区块的奖励，又或者是谁意图进行危害，就会获得一定的惩罚，这就是共识机制

常见的共识机制

• 工作量证明（Proof-of-Work，Pow），典型案例：比特币
• 权益证明（Proof-of-Stake，PoS，又译持有量证明），典型案例：以太坊
• 股份授权证明（Delegated-Proof-of-Stake，DPoS），典型案例：EOS
• 容量证明（Proof-of-space，PoSpace，又称 Proof-of-Capacity，PoC），典型案例：Filecoin
• Paxos 算法
• Raft
• PBFT
• LibraBFT（Byzantine fault-tolerance）：Libra 上使用

Paxos

Paxos 算法是分布式算法的代名词，一些常见的算法都是基于它改进的：例如：Fast Paxos 算法，Cheap Paxos 算法，Raft 算法，ZAB 协议等等

Paxos 算法是莱斯利-兰伯特于 1990 年提出的一种基于消息传递，且具有高度容特性的共识（consensus）算法。

注意：Paxos 是一个共识（consensus）算法，而不是一致性（consistency）算法

参考博客 (opens new window)

Raft

Raft 是一种用于替代 Paxos 的共识算法。Raft 的名字来源于 Reliable，Replicated，Redundant，And Fault-Tolerantl；即（可靠、可复制、可冗余、可容错）首字母的缩写。Raft 通过选举领袖（leader）的方式做共识算法。

Raft 集群中的三种身份：

• 领袖，leader
• 追随者，follower
• 候选人，candidate

正常情况下会有一个领袖，其他都是追随者。领袖通过心跳消息，让追随者知道领袖还在运作。每个追随者都有超时机制，当超过一定时间没有心跳，集群就会进入选举状态。

心跳事件 << 超时时限 << 平均故障间隔

Raft 将问题拆解成数个子问题分开解决：

1. 领袖选举（Leader Election）
2. 记录复写（Log Replication）
3. 安全性（Safety）

领袖选举

1. 在起始算法或领袖宕机、断线的时候，就需要选举出新的领袖。
2. 此时集群进入新的任期，并开始选举；如果选举成功则新的领袖开始运行工作，反之则任期终止，开始新的任期并开始下一场选举。
3. 选举由候选人发起。当领袖的心跳超时的时候，追随者会把自己的任期编号加 1，宣告竞选，投自己一票，并向其他服务器拉票。每个服务器在每个任期之会投一票，固定投给最早拉票的服务器。
4. 如果候选人收到其他候选人的拉票，而且拉票的任期编号不小于自己的任期编号，就会自认落选，成为追随者，并认定来拉票的候选人为领袖；如果有候选人收到过半的选票就当选为新的领袖。如果超时仍没有选出新的领袖，此任期自动终止，开始新的任期，并开始下一场选举。
5. Raft 每个服务器的超时时限是随机的，这降低了服务同时竞选的几率，也降低因两个竞选人得票都不过半而选举失败的几率。

记录复写

1. 记录复写的责任在领袖身上
2. 整个集群有个复写状态机，可执行外来的指令。领袖接收指令，将之写入自己记录中的新指令部分，然后把指令转发给追随者。如果追随者没反应，领袖会不断重发指令，直到每个追随者都成功将新指令写入记录为止。
3. 当领袖收到过半追随者确认写入的消息，就会把指令视为已存储（committed）。当追随者发现指令状态变成已存储，就会在其状态机上运行该指令。
4. 当领袖死机时，领袖的某些指令可能还没复写到集群整体，造成集群的记录处于不一致的状态。新领袖会担起重返一致的责任，让每个追随者的记录都和它的一致。做法是：和每个追随者对比记录，找出两者一致的最后一笔指令，删除追随者之后的指令，把自己之后的指令拷贝给追随者。这个机制完成时，每个服务器的记录就会一致。

安全性

Raft 的安全性规则如下：

• 选举安全性：每个任期最多只能选出一个领袖
• 领袖附加刑：领袖只能把新指令附加在记录尾端，不会改写或删除已有的指令
• 记录符合性：如果某个指令在两个记录中的任期和指令序号一样，则保证序号较小的指令也完全一样。
• 领袖完整性：如果某个指令在某个任期中存储成功，怎保证存在于领袖该任期之后的记录中
• 状态机安全性：如果某服务器在其状态机上运行了某个指令，其他服务器保证不会在同个状态上运行不同的指令。

状态机安全性，由下面的选举流程限制达到：

1. 追随者死机

   当某台追随者死机时，所有给它的转发指令和拉票消息都会因没有回应而失败，此时发送端会持续重发。当这台追随者重新加入集群，就会收到这些消息，追随者会重新回应，如果转发的指令已经写入，不会重复写入。

2. 领袖死机

   领袖死机或断线，每个已存储指令必定已经写入到过半的服务器中，此时选举流程会让记录最完整的服务器胜选。其中一个因素是 Raft 候选人拉票时会揭露自己记录最新的一笔信息，如果服务器自己的记录比较新，就不会投票给候选人。

3. 超时限和可用性

   因为 Raft 引导选举是基于超时，是的超时的期限的选择至为关键。若遵守算法的实现需求，就能达到稳定性。

   心跳时间 << 超时时限 << 平均故障间隔

   这三个时间定义如下：

   • 心跳时间，是单一服务器发送消息给集群中每台服务器并得到回应的平均时间，需测量得到。
   • 超时时限，是发动选举的超时时限，由部署 Raft 集群的人选定。
   • 平均故障间隔，是服务器发生付账之间的平均时间，可以测量或估计得到。

   广播时间典型是 0.5ms 到 20ms，平均故障间隔通常是用周或月来计算的，所以可以将超时时限设置在 10ms 到 500ms