什么是一致性

一致性是指分布式系统中的多个服务节点，给定一系列操作，在特定协议的保障下，使这些节点对外呈现的状态是一致的，即保证集群中所有服务节点中的数据完全相同并且能够对某个提案达成一致

CAP Theorem

根据FLP不可能结论，在一个异步系统中，网络时延无上限，即使只有一个成员是有问题的，也不可能达成共识。

Consistency一致性、Availability可靠性、Partition tolerance容错性，任何一个分布式系统中，最多只能满足其中两个性质（指满足表示两个之后再考虑第三个）。

强一致性

任何一次读都能读到某个数据的最近一次写的数据。
系统中的所有进程，看到的操作顺序，都和全局时钟下的顺序一致。
简言之，在任意时刻，所有节点中的数据是一样的。

如：Paxos，raft，zab

弱一致性

数据更新后，如果能容忍后续的访问只能访问到部分或者全部访问不到，则是弱一致性。

如：DNS，Gossip

CFT（非拜占庭容错算法）

Basic Paxos

角色

Client：系统外部角色，请求发起者。

Propser：接受Client请求，向集群提出提议（propose）。并在冲突发生时起到冲突调节作用。

Accpetor(Voter)：提议投票和接收者，只有在形成法定人数（一般为多数派）时，提议才会最终被接受。

Learner：提议接受者，backup,备份，对集群一致性没有影响。

阶段

1a Preapre

Propser提出一个提案，编号为N，此N大于这个proposer之前提出的提案编号。请求acceptors接受。

1b Promise

如果N大于此acceptor之前接受的任何提案编号则接受，否则拒绝。

2a Accept

如果达到了多数派，Propser会发出accept请求，此请求包含提案编号N，以及提案内容。

2b Accepted

如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。

成功流程：

Multi Paxos

引入新概念：Leader，唯一的propser，所有请求都需经过此Leader。

先”竞选“，对于之后只需要Accept而不需要prepare。

Raft

Raft实现了和Paxos一样的功能，将分布式一致性分解为三个子问题：

  • Leader选举（Leader election）
  • 日志同步（Log replication）
  • 安全性（Safety）

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

  • Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
  • Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
  • Candidate：Leader选举过程中的临时状态。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

leader选举

follow服务器如果长时间没有接收到leader服务器的请求，他会成为一个candidate并开始一次leader选举，收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。

leader选举需要某个节点发起投票，在确定哪个节点向其他节点发起投票之前，每个节点会分配一个随机的选举超时时间，在这个时间内，节点必须等待，不能成为Candidate状态，节点在成为candidate状态后会向其他节点发送投票请求，希望其他节点投票选举自己为leader，在此过程中会出现三种情况：

  • 该节点得到大多数节点的投票，成为leader
  • 该节点收到了leader的心跳包，表示有其它服务器已经抢先当选了Leader；
  • 没有服务器赢得多数的选票，Leader选举失败，等待下一次选举。

选举出leader后，leader通过定期发送心跳包保持自己的leader状态，如果follower在一段时间内没有收到leader的心跳包则认为leader可能已经挂了，就会再次发起leader选举

日志复制

当选举出leader后，follow不再接受客户端的请求，客户端的所有请求都会由leader去处理，leader会将接收到请求写入到leader的日志中，然后向其他并行的服务器发起请求让follow对日志进行复制，当这些日志被复制到大多数服务器上后，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

ZAB

与raft基本相同，在名词叫法上，ZAB将某个leader的周期称为epoch，而raft则称为term。

实现上有些不同：raft保证日志连续性，心跳方向为leader至follower。ZAB则相反。

PoW

工作量证明(Proof Of Work，简称POW)，比特币使用的共识机制。

PoS

​ PoW机制存在明显的弊端。 一是算力不公平，矿场的竞争力比单个节点大，还有就是随着硬件的发展，特别是量子计算机的出现，可能几秒就破解了Hash。 二是PoW算法太浪费了，比特币网络每秒可完成数百万亿次SHA256计算， 但这些计算除了使恶意攻击者不能轻易地伪装成几百万个节点和打垮比特币网络，并没有更多实际或科学价值。

​ 权益证明（ Proof of Stake，PoS） ，最早在 2013 年被提出，最早在 Peercoin 系统中被实现，类似现实生活中的股东机制，拥有股份越多的人越容易获取记账权（ 同时越倾向于维护网络的正常工作） 。

BFT

拜占庭容错（Byzantine Fault Tolerance, BFT）共识算法，3种版本，每种版本都具有各自的优缺点。这些版本分别是：

1. 实用拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）

2. 联邦拜占庭协议（FBA，Federated Byzantine Agreement）

3. 授权拜占庭容错算法（dBFT，Delegated Byzantine Fault Tolerance）

实用拜占庭容错（PBFT）

优点：高速、可扩展。

缺点：通常用于私有网络和许可网络。

实用拜占庭容错PBFT是首个解决拜占庭将军问题的方案，当前已被 Hyperledger Fabric 采用（特殊情况下才用)。PBFT 使用了较少（少于 20 个，之后会稍有增加）的预选定将军数，因此运行非常高效。它的优点是高交易通量和吞吐量，但是不足之处在于是中心化的，并用于许可网络。使用拜占庭容错机制是一种采用“许可投票、少数服从多数”来选举领导者并进行记账的共识机制，该共识机制允许拜占庭容错，允许强监督节点参与，具备权限分级能力，性能更高，耗能更低，而且每轮记账都会由全网节点共同选举领导者，允许33%的节点作恶，容错率为33%。换句话说，PBFT假设区块链上总的节点数是3f+1个，那么网络中可以容忍整个网络中最多f个节点出现拜占庭错误而不影响正确的共识。