2.共识算法

一文看懂共识机制和11个主流共识算法

基础

共识算法是指在分布式系统中，多个节点为了达成相同的数据状态或决策而运行的一种分布式算法。它能够容忍网络丢包、时钟漂移、节点宕机、节点作恶等故障情况，确保多个节点取得相同的数据状态或决策结果。

1.分类

其实公式算法一直是以去中心化的共识算法为主的，而中心化目前主流的只有Paxos一脉了。

【中心化】CFT 类共识算法（Crash Fault Tolerance非拜占庭错误）
- 适用于节点信任程度高的网络。包括 Paxos（Basic Paxos、Multi Paxos），Zab，Raft。
【去中心化】BFT 类共识算法，检查节点是否具有恶意的拜占庭错误倾向于去中心化的结构，但是其算法核心还是离不来中心化的核心。
- 工作量证明（PoW）：如比特币所使用的，通过节点消耗计算资源来解决复杂的数学问题，从而证明其工作量，并有机会将新的区块添加到区块链上。
- 权益证明（PoS）：如以太坊（部分版本）所使用的，根据节点持有的代币数量（即"权益"）来决定其参与共识的权重，减少了能源消耗。
- 委托权益证明（DPoS）：如EOS等系统所采用的，允许节点将自己的投票权委托给"代表"节点，由这些代表节点来进行共识决策，进一步提高了效率和去中心化程度。
- 实用拜占庭容错（PBFT）：主要用于联盟链场景，通过多轮投票来达成共识，对节点数量有一定要求，但能够容忍一定数量的恶意节点。

2.作用

共识机制可以有效解决两个问题：拜占庭将军问题（恶意节点篡改数据）和双花问题（一笔钱被花了两次）。

1.拜占庭将军问题

典故：如何在"有内奸、信使不可靠"的情况下，确保首都决策的正确性。
落地到分布式集群中就是：如何在不可靠的分布式系统中，快速且正确地使各节点能够达成一致状态。也就是大部分集群达成共识。

2.双花问题（Double spend attack）

典故:猫鼠游戏中，小李子通过做假支票进行了双花行为，因为支票的验证需要时间，所以在这个时间差内他多次用同一张支票的信息购买物品。
主要针对区块链技术。

解决双花问题，两种方案：

在确认前的双花。零确认的交易本来就可能最后没有写入区块链。除非小额，最好至少等确认即可规避此类双花。
在确认后的双花。这就要控制超50%算力才能实施。即类似于一个小分叉，将给一个商店的交易放入孤立区块中。这种确认后双花，很难实施，只是理论上可行。

Paxos

1.基础

1.1.介绍

Paxos 1990 年被提出。作用是解决分布式系统中数据一致性问题，尤其是在网络延迟、分区和节点故障的情况下。

应用：Paxos 被广泛应用于需要高可用性和数据一致性的分布式系统中，如分布式数据库、分布式存储系统、分布式锁服务等。

Chubby: Google提出的一种分布式锁服务。应用于 GFS和Bigtable等大型系统
Spanner：是一个功能强大、可扩展性高的全球分布式数据库，强一致性、事务支持
OceanBase：使用Paxos实现强一致性的分布式数据库。

1.2.发展

Paxos 最初也是少有人知的。直到后面被谷歌发现并实现后，Paxos时隔十几年才被人们重新提起

Paxos 1990最初论文 Paxos 2001简化后的论文-Paxos Made Simple

Paxos 算法也因其复杂性而闻名。它的协议步骤和角色交互相对复杂，使得理解和实现起来都具有一定的挑战性。因此，在实际应用中，人们通常会选择使用 Paxos 的变种或简化版本，如 Multi-Paxos、Raft 等，这些算法在保持 Paxos 核心思想的同时，通过简化协议步骤和角色交互来降低实现的复杂性。

Paxos的主要分类如下：

Basic-Paxos：兰伯特论文中提到的Paxos算法，只具备单决策能力；
Multi-Paxos：《Paxos Made Simple》论文最后拓展提到的算法，具备多决策能力。
其他变种：Zab和Raft

1.3.关键特性

多数派原则：确保在任何时候，只有得到多数节点支持的提案才能被接受为选定提案。这有助于防止网络分区导致的数据不一致性问题。
安全性：一旦某个提案被选定，它将永远保持选定状态，不会被后续的提案所覆盖或撤销（除非系统完全重置）。
活性：只要系统中存在多数节点是活动的且能够相互通信，那么系统就能够持续处理新的提案并最终达成一致。

2.Basic-Paxos

2.1.核心思想

提案：将数据、日志等任意的事物抽象为提案。
核心思想：通过协议让集群各节点就某个提案（Proposal）达成一致。
节点角色：Proposer（提案者）、Acceptor（接受者）、Learner（学习者）
提案状态：Prepare、Propose、Learn

2.2.角色

Paxos 有三种角色：

Proposer（提案者）：发起提案；整个集群只有一个节点作为Proposer，负责所有的写操作。
Acceptor（接受者）：通知Proposer自己是否接受提案
Learner（学习者）：学习通过的提案。

2.3.提案编号

提案编号是全局唯一的，可自增的变量。由Proposer维护，Acceptor和Learner用于校验Proposer的提案是否有效。

2.4.议会决策

Prepare 阶段：提案者向所有接受者发送 Prepare请求（包括提案 + 编号n）。接受者已经接受的编号与提案请求中的编号进行对比。接受者只同意接受大于等于本地编号的提案，并向提案者返回自己当前已接受的最大提案编号。
Accept 阶段：如果提案者收到大多数接受者的同意的响应，那么提案者就会生成一个新的提案（n+1），向所有接受者发送 Accept请求（包括提案 + 编号n+1）。
Learn 阶段：提案被大多数接受者接受，提案者会将提案发送给所有学习者，以便它们了解并应用这个提案。提案者不关注学习者是否应用提案。

2.5.缺点

Basic-Paxos 没有明确提案者的数量，如果有多个提案者，整个处理流程就会陷入混乱。所以解决方案就是：只有一个提案者

3.Multi-Paxos

Basic-Paxos是一种单决策算法，一轮决策中只能确认一个Value，并且至少经过Prepare、Accept两个阶段，这样的模式效率太低了。

Multi-Paxos是对Basic-Paxos一种优化形式。

增加leader概念，表示只有一个提案者。在Baseic Paxos 中，提案者是随机选择的。
删除Prepare阶段。先通过一次完整的 Prepare/Accept 选出稳定的主节点，然后由该主节点跳过 Prepare 阶段、直接对后续日志条目执行 Accept。减少通讯次数，也降低了提案编号的维护难度。
脑裂：当发生时，会退化为Basic-Paxos模式，进行选举。

4.对比

维度	Base-Paxos	Multi-Paxos
目标	就单个值达成共识	就一系列值（日志/命令序列）达成共识
阶段	每决议一次都要完整两阶段（Prepare + Accept）	选出稳定 Leader 后，对后续值跳过 Prepare，只保留 Accept
RPC 次数	2 轮广播（高延迟）	稳定后 1 轮广播，性能接近 Raft
冲突风险	多个 Proposer 易死锁	单一 Leader 避免冲突
工程实现	理论完备，代码量少	需额外实现 Leader 选举与租约机制（例：Chubby、Raft 都是 Multi-Paxos 思想落地）

Raft

Raft官网，可以可视化观察选举和日志复制: https://raft.github.io/
Raft论文：https://raft.github.io/raft.pdf
深度解析 Raft 分布式一致性协议
从0开始实现Raft

1.基础

1.1.介绍

Raft是Paxos的一个变种，比Paxos更易理解和实现。相比Paxos做出了以下简化

Raft将共识算法拆分成3个模块：leader选举、日志复制、安全性，使其更易理解和工程实现。
Raft简化了节点的状态，节点只继续状态切换。

2.2.应用

目前很多中间件都开始使用Raft协议，例如：etcd、 consul、nacos 和 TiKV。

etcd。基于Raft实现的分布式kv存储。
consul 和 nacos，都是将Raft作为可选的一致性协议
TiKV，作为分布式数据库TiDB的底层实现，采用了Multi Raft，将数据划分为多个region，每个region都是一个Raft集群。
Kafka Raft（KRaft）。用于替换zookeeper在kafka集群中的作用，简化操作，降低程序的维护成本，提升故障恢复速度。

缺点：

Raft不适合大数据量存储
节点数量并非越多越好

2.选举

Raft采用Quorum机制，将对Raft的操作称之提案，每当发起一个提案，都必须得到超过半数（>N/2）的节点同意才能提交。

2.1.节点状态

节点状态：leader（发出提案）、follower（参与决策）、candidate（选举中的临时状态）。

每个节点只有一个状态，只需考虑状态切换，不向paxos存在状态共存的情况。

2.2.任期term

任期的就是从开始选举开始计算，直到下一次选举。即，任期是发起两次选举的时间间隔。

任期以整数计算，每经过一次任期（每发起一次选举），任期+1。任期期间可能无法选举出leader就立即进入下一个任期，重新选举，任期+1。所以任期期间，可能没有leader，即使有leader也是不可靠的，candidate状态不会接受选举期间leader的写日志。

2.3.节点间通讯

Raft定义了节点间通讯采用rpc协议。根据通讯的内容可以分为两类：

RequestVote：请求投票，由candidate节点在选举期间发起，向所有的节点发生自己的投票信息。
AppendEntries：追加条目，由leader发起，用于日志复制以及心跳检查。

通讯的内容会携带当前节点的任期号。根据角色不同，做出反应也不同

candidate和leader发现接收到的任期号小于收到的，会判定自己任期号过期了，会立即进入follower状态。
- 原因：例如发生了脑裂或者其他问题，导致其他节点已经完成了选举，所以先进入follower进行通讯，再进行下一步操作（参与选举或者作为follower工作）
follower 接收到的任期号小于自己的，判断收到的信息是过期的，拒绝这条消息。
如果当前节点任期号小了，就会更新自己的任期号。

2.4.心跳机制

心跳机制：leader周期性地发送心跳给所有的follower，follower收到后就保持follower状态，如果超时没有收到心跳， follower节点切换到candidate状态，并发起投票。

follower超时时间：每个节点的心跳超时时间通常是随机的，论文中是介于150ms到300ms之间。

2.5.领导选举

选举发生场景

服务启动时，所有节点都是follower，当超时没法收到leader的心跳，就切换到candidate进行选举。
运行期间，leader因为宕机或网络问题中断心跳，follower心跳超时，就切换到candidate进行选举。

选举过程如下：

首先把当前term计数加1，自己的状态切换到candidate。
然后给自己投票并向其它结点发投票请求（term, index）。直到以下三种情况：
- 它赢得选举，立即切换到leader状态，并向所有节点发送心跳，告诉大家我是leader。
- 另一个节点成为leader。收到leader的心跳，且任期大于等于自己的任务。
- 一段时间没有节点成为leader。选举超时，默认为150~300ms。
在选举期间，candidate可能收到来自其它自称为leader的写请求，如果该leader的term不小于candidate的当前term，那么candidate承认它是一个合法的leader并切换到follower状态，否则拒绝请求。
如果出现两个candidate得票一样多，则它们都无法获取超过半数投票，这种情况会持续到超时，然后进行新一轮的选举，这时失败的概率就很低了，那么首先发出投票请求的的candidate就会得到大多数同意，成为leader。

特点：raft投票一轮只投一次票，投票后就等待新leader发送通知，如果等待超时就开启新一轮投票term+1。

选举的消息，伪代码

//请求投票RPCRequest
type RequestVoteRequest struct {
    term int            //自己当前的任期号
    candidateld int     //自己的ID
    lastLogIndex int    //自己最后一个日志号
    lastLogTerm int     //自己最后一个日志的任期
}

//请求投票RPCResponse
type RequestVoteResponse struct {
    term int       //自己当前任期号
    voteGranted bool //自己会不会投票给这 candidate
}    
  

如果某个follower超时发起选举，其他follower也会跟着选举吗？

follower状态切换到candidate的条件：follower心跳超时才会转换为candidate状态并发起选举。如果集群中某个节点因为一些原因，切换状态并发起选举，其他节点不会跟随他一起选举，并返回拒绝投票。该节点无法正常选举，会一直重试尝试发起选举，无法正常工作。

选票逻辑

比较term，term最大的当选
term最大有多个相同的时候，lastLogIndex 最大的当选
lastLogIndex最大有多个相同的时候，收到的第一条选票中的节点当选

所以在第一次服务启动时，第一个发起选举的节点会当选leader。

3.日志复制

3.1.复制过程

集群中所有写入操作都在leader进行。写入操作过程如下：

当leader接收到写入请求后，leader 并发向所有follower发送AppendEntries（term1,index1）请求，要求它们复制日志。
当收到过半的节点的回复（不需要全部节点）时，leader会将日志项应用到自己的状态机，然后向给客户端返回成功。
leader并不会通知follower节点提交，follower 中的日志状态是未提交的。
leader发送心跳（100ms）给所有follower（term1,index2），follower检查心跳，发现在同一个term1中。
- 如果：index2>=节点最大index1，则提交现有所有所有未提交的日志。
- 如果：index2< 节点最大index1，则提交小于等于index1的日志。

LogIndex 也是全局唯一的自增整数，且一旦服务启动，这个数字只会增加（可能存在回退），不会重置。 LogIndex 与 term 一起组成一个全局唯一标识。

PS: 缺点，论文中的日志复制，leader 和 follower 之间数据是有延迟的。

3.2.客户端连接

客户端是如何知道leader节点的？常用的方式，启动后向任意节点发生连接请求，会出现三种情况

这个节点就是leader，就建立连接
这个节点是Follower，Follower会保存其他节点的信息，会告诉客户端leader的地址，客户端重新连接。
这个节点不可用，客户端会循环尝试其他的节点，直到找到leader。

3.3.数据一致性检查

follower的一致性检查：

leader发送AppendEntries时，会发送上一条的LogIndex与 term。
follower如果找不到这个LogIndex与 term，说明follower延迟了，就会拒绝掉这些复制请求
leader收到拒绝请求后，会向follower发送一个日志列表
follower 收到列表后，逐一对比，找到自己需要同步的位置，并发起同步请求。

follower与leader数据不一致？

每个节点随时都有奔溃、缓慢的情况出现，所以Raft必须保证发生以上情况，日志复制任然可以继续，要保证每一个副本中的日志顺序一致。

原因：

follower 同步缓慢。
- leader发送AppendEntries命令是，follower 由于某些原因，没有及时响应（超时），leader会不断的重试，直到成功。这个过程中，leader可能已经提交了日志。
follower 崩溃。
- follower恢复后，会启动一致性检查，与leader对比term 与 commitLogIndex，找到需要同步的开始位置，进行同步。
leader 崩溃。
- 可能是奔溃，或者网络问题导致脑裂，恢复期间，可能已经经过多轮任期，数据已经不是最新的。
- 可能恢复后，新的leader数据也不是最新的。脑裂的时候，旧leader继续写入数据，导致commitLogIndex大于新leader。

3.4.日志压缩

就是定期生成日志快照。快照一般包含以下内容：

日志的元数据：最后一条被该快照 apply 的日志 term 及 index
状态机：前边全部日志 apply 后最终得到的状态机

日志同步：

当 leader 需要给某个 follower 同步一些旧日志，但这些日志已经被 leader 做了快照并删除掉了时，leader 就需要把该快照发送给 follower。
同样，当集群中有新节点加入，或者某个节点宕机太久落后了太多日志时，leader 也可以直接发送快照，大量节约日志传输和回放时间。

4.安全

raft为了便于理解，简化了很多操作，所以在这些操作的过程中，存在一些问题，需要优化。

选举中的限制：每个 candidate 必须在 RequestVote RPC 中携带自己本地日志的最新 (term, index)，如果 follower 发现这个 candidate 的日志还没有自己的新，则拒绝投票给该 candidate。
日志复制的限制：Leader 只允许 commit 包含当前 term 的日志。因为可能选举过程中，上一个leader有数据没有提交，导致follower中的数据也没有提交。所以新选举的leader中可能有未提交的数据。选举中选票的index是已提交，而未提交的日志，在后续新leader日志复制过程中，被leader覆盖掉。

5.集群成员变更

raft允许不停机变更集群成员。集群节点的增删操作，一定会有延迟，延迟的过程，就会出现节点之间配置不一致的情况，就可能发生脑裂问题。

5.1.联合发布(两阶段切换集群成员配置)

论文中提供的方案，阶段一：

提供变更命令，从leader写入新的配置：C-new
leader将新旧配置进行并集操作，生成一个联合配置 C-old,new
leader以日志的方式发送给所有follower。
follower 收到 C-old,new 后立即 apply，当超过半数节点都切换后，leader 将该日志 commit。

阶段二：

leader 提交日志后，立即发送C-new给所有follower。
follower 接收都C-new后立即应用，如果发现自己被移除了，就会可以退出集群。
leader 收到当超过半数节点切换成功的响应后，立即返回客户端操作结果。

5.2.渐进式变更

一次只变更一个节点。参考具体实现： https://github.com/ongardie/dissertation

6.读性能优化

6.1.主写从读

raft协助中，leader写操作，日志复制时大部分通过即可，且follower本地日志提交依赖于leader下一次心跳消息。所以follower中日志是有延迟的，且存在不一致的情况。所以这种主写从读的方式是不成立的。

6.2.主写主读

也是存在问题。例如：

日志未提交（还在日志复制过程中），被读取到的话就产生了脏读。
网络分区导致脏读，此时如果连接的是旧leader，用户写入数据后，可能被连接旧leader的其他用户读取到。当集群恢复后这些数据都没了，这就产生了脏读。

从leader读取数据是有必要的，所以以上问题需要优化，方案如下，这些方案任选其一即可。一致性也逐渐降低。

Raft log read：leader发起，向所有节点都读一遍。
Read Index：leader发起，将心跳和读一起发送一遍。
Lease Read：leader发起，客户端本地存在一个续期，通过心跳刷新。当续期小于阈值，则信任leader有效，否则使用Read Index。
Follower Read：Follower发起，并主动向leader同步index，然后返回数据。

目标：

保证在读取时的最新 commit index 已经被 follower 提交。
保证在读取时 leader 仍拥有领导权。

6.2.1.Raft log read

读操作也作为一种提案，在raft集群中走一遍日志复制过程，这样可以很大程度上保证连接到的leader节点是有效的，且数据也是最新的。

缺点：读操作与写操作一样耗时，性能不好。

6.2.2.Read Index

Leader 接收到读操作，记录下当前的 commit index，称之为 read index。
为了确保领导权，主动让 Leader 向所有 follower 发起一次心跳，同时也是为了让follower上未提交的数据提前提交。
当大半follower都回复成功后，即 apply index 大于等于 read index
执行读请求，将结果返回给客户端。

就是将心跳与读操作合并一起，很多程度的提升读取性能，这么做为了保证Leader有效，follower数据即使提交。

6.2.3.Lease Read

设置一个比选举超时更短的时间作为租期，在租期内我们可以相信其它节点一定没有发起选举，集群也就一定不会存在脑裂。
在租期内可以直接读主，而租期过期后使用Read Index。
下一次读操作使用Read Index后，刷新租期，续租。

缺点：依赖于系统时间，为算法带来一些不确定性，如果时钟发生漂移会引发一系列问题，因此需要谨慎的进行配置。

6.2.4.Follower Read

Follower 在收到客户端的读请求时，向 leader 询问当前最新的 commit index，反正所有日志条目最终一定会被同步到自己身上， follower 只需等待该日志被自己 commit 并 apply 到状态机后，返回给客户端本地状态机的结果即可。

7.Raft与Paxos对比

Multi-Paxos 在 Basic-Paxos 之上先通过一次完整的 Prepare/Accept 选出稳定的主节点，然后由该主节点跳过 Prepare 阶段、直接对后续日志条目执行 Accept，从而把"逐条一致性决议"变成"连续日志复制"，但仍允许空洞且需自行补充选主、日志索引等细节。

而 Raft 把"选主、日志复制、安全约束"全部显式化：先通过独立的选举 RPC 产生唯一的强领导者，再由该领导者按严格顺序向所有节点复制日志并强制一致性检查，天然连续无空洞，并提供内建的成员变更机制，因而更易理解和实现。

Zab

三种角色：

领导者（Leader）：作为主（Primary）节点，在同一时间集群只会有一个领导者。所有的写请求都必须在领导者节点上执行。
跟随者（Follower）：作为备份（Backup）节点，集群可以有多个跟随者，它们会响应领导者的心跳，并参与领导者选举和提案提交的投票。需要注意的是，跟随者可以直接处理并响应来自客户端的读请求，但对于写请求，跟随者需要将它转发给领导者处理。
观察者（Observer）：作为备份（Backup）节点，类似跟随者，但是没有投票权，也就是说，观察者不参与领导者选举和提案提交的投票。

四种状态：

LOOKING：选举状态，该状态下的节点认为当前集群中没有领导者，会发起领导者选举。
FOLLOWING ：跟随者状态，意味着当前节点是跟随者。
LEADING ：领导者状态，意味着当前节点是领导者。
OBSERVING：观察者状态，意味着当前节点是观察者。

选举过程

每个节点先投自己一票。假设投票信息的格式是 <proposedLeader(提议选的leader), proposedEpoch(提议的任期), proposedLastZxid(提议leader的zxid)，node(投票节点)>
节点每一张接收到的选票，节点都需要进行比较，优先级：Epoch大的 > zxid大的 > myid大的。
节点比较之后，拿到一个合适的leader，修改选票，再次广播出去。
每个节点统计收到的投票信息，如果某个节点获得超过半数的票，则该节点被选为领导者。
领导者确认选举完成后，新的领导者会向所有节点发送确认消息，其他节点收到确认消息后，会向领导者发送确认响应，表示接受其作为领导者。

与raft对比

触发时机：raft是心跳超时就变成Candidate，zab是仅leader宕机（通过session机制判断的）才进入looking阶段。
投票规则：raft最少投票一次(投自己后等待新leader通知)，zab最少两次（先投自己再修改选票再投一次）。
选举确认：raft投票后就等待新leader，选不出就开启新一轮选举。zab新leader发送确认消息，其他节点收到后，再次广播确认响应。
设计目标：raft为了保证日志的一致性，zab是强顺序性。
使用场景；raft适合分布式存储例如etcd等，zab适合服务间协调。

原子广播

ZAB所有写操作必须在主节点上执行。如果follower节点收到写请求会转发给主节点执行。
领导者收到写请求后，将其封装为提案（Proposal），并使用全局唯一自增事务iD(zxid)，向所有follower发送提案消息。
follower收到提案后，会先检查提案的zxid是否大于自己的zxid，如果是则接受提案。
leader收到指定提案的"大多数"的确认响应后，该提案将处于提交状态（Committed），通知所有follower提交该提案。

读操作

follower节点也是顺序执行提交操作的，并且可能提案还没有提交过来，为了保障读取数据最新，客户端会先发送sync命令，follower节点会先向leader发送一个查询最新zxid的请求。

Gossip

一致性算法-Gossip协议详解

1.介绍

Gossip协议又被称为流行病协议（Epidemic Protocol），也有人叫它反熵（Anti-Entropy）。

Gossip协议于1987年在ACM上发表的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出，主要用在分布式数据库系统中各个副本节点间的数据同步，这种场景的一个最大特点就是组成网络的节点都是对等的，网络中即使有的节点因宕机而重启，或有新节点加入，但经过一段时间后，这些节点的状态也会与其他节点达成一致。

简而言之，Gossip是一种数据复制算法，并不是共识算法。作用是在将数据传播到集群各个节点，因此Gossip也算是一种带冗余的分布式容错的算法，可以实现数据的最终一致性。

使用场景：最终一致性的场景（也就是AP场景）：

失败检测
路由同步
Pub/Sub
动态负载均衡。

Gossip 协议被广泛应用在多个知名项目中，使用案例

Bitcoin:使用 Gossip 协议来传播交易和区块信息，
Redis： cluster方式使用Gossip进行检活和数据同步
Consul：集群间状态同步
Apache Cassandra
AWS Dynamo。

缺点也很明显：

消息延迟：节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播才能遍布集群。
消息冗余：节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤。节点越多，对带宽和CPU的消耗越大。
拜占庭问题：如果有一个恶意传播消息的节点，Gossip协议的分布式系统就会出问题。

2.六度分隔理论

原文："你与任何一个陌生人之间间隔的人不会超过6个"
案例：Facebook研究发现已经注册的15.9亿用户，网络半径为4.57。

3.节点状态

S:Suspective(病原)：处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。
I:Infective(感染)：处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点。
R:Removed(愈除):其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。

R状态的引入，是为了避免产生传播风暴，及时出现也会在可控的时间范围内自行恢复。

4.复制方式

Gossip将数据复制协议分为两种

反熵传播：定时随机选择节点，几个节点相互交换全部数据来消除数据差异。
- 参与节点只有两种状态(SI)
- 缺点：交换数据会带来很大的通讯负担，通常不会频繁使用
- 使用场景：通常用于新加入集群的节点初始化数据
谣言传播：定时随机选择节点，将某段时间内最新的数据进行发送（同一条数据可能发送多次），直到消息被标记为R，就停止传播。
- 参与节点有三种状态(SIR)
- 缺点：有一定的概率出现数据不一致的情况
- 使用场景：通常用于节点间数据增量同步

Gossip实际使用中，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。启动是反熵传播，之后谣言传播。

5.通讯方式

Gossip 协议最终目的是将数据分发到网络中的每一个节点。节点间通信方式：Push、Pull 以及 Push&Pull：

Push: 产生新数据的节点作为发起节点。发起信息交换的节点 A 随机选择联系节点 B，并向其发送自己的信息，节点 B 在收到信息后更新比自己新的数据。
Pull：无新数据的节点作为发起节点。发起信息交换的节点 A 随机选择联系节点 B，并从对方获取信息。
Push&Pull：发起信息交换的节点 A 向选择的节点 B 发送信息，同时从对方获取数据，用于更新自己的本地数据。

如果把两个节点数据同步一次定义为一个周期，则在一个周期内，Push 需通信 1 次，Pull 需 2 次，Push&Pull 则需 3 次。虽然消息次数多了，但从效果上来讲，Push&Pull 最好，理论上一个周期内可以使两个节点完全一致。直观上，Push&Pull 的收敛速度也是最快的。

区块链中的共识算法

1.工作量证明（Proof of Work, PoW）

算法简介：最早用来对抗垃圾邮件的一种计算机技术。2008年，中本聪在《比特币：一种点对点的电子现金系统》比特币白皮书中提出了比特币与区块链，创新的设计了 PoW算法，被应用在比特币上，用来解决一个数学难题来参与共识。

使用案例：Bitcoin, ETH1.0, Litecoin, Conflux, Dogecoin。

算法核心：是利用算力来寻找一个满足区块哈希的 nonce 值。但是人们很快发现这种共识机制的问题，即能耗大，以及被大矿池把持算力之后，仍然会导致中心化问题。
算法原理：工作量证明系统主要特征是客户端需要做一定难度的工作得出一个结果，验证方却很容易通过结果来检查客户端是不是做了相应的工作。工作量证明（PoW）通过计算寻找一个数值 Nonce，使得拼凑上交易数据后内容的 hash 值满足规定的上限。在节点成功找到满足的 hash 值后，会马上对全网进行广播打包区块，网络的节点收到广播打包区块，会立刻对其进行验证。

这种方案的一个核心特征是不对称性：工作对于请求方是适中的，对于验证方是易于验证的。它与验证码不同，验证码的设计出发点是易于被人类解决而不是被计算机解决。

优缺点：

缺点：速度慢；耗能巨大，对环境不好；易受"规模经济"（economies of scale）的影响。
优点：自 2009 年以来得到了广泛测试，目前依然得到广泛的使用。

2.权益证明（Proof of Stake, PoS）

算法简介：2011年，Quantum 在 Bitcointalk 论坛上提出。2012年8月，首个基于 PoS共识的区块链项目点点币（Peercoin）诞生，点点币（Peercoin）是第一个实现 PoS 算法的应用。点点币中权益即为币龄，币龄是节点所持币的数量与其持有时间的乘积，发起交易会消耗一定的币龄，每消耗365币龄时也将获得年利率5%的利息。

使用者： Ethereum(2.0), Conflux, Peercoin。

算法原理：例如某人在一笔交易中持有点点币100个，共持有30天，那么币龄为3000，后来发现了一个 PoS块，币龄被清空为0，获得利息为0.05*3000/365=0.41币。共识过程中节点通过消耗的币龄来获取记账权，节点消耗的币龄越多，获得记账权的机会越大。算法设定的主链原则为：消耗币龄最多的链为系统中正确有效的链。

优缺点：

优点：不需要强大、昂贵的挖矿设备。减少资源消耗，减少51%攻击的可能性。
缺点：可能导致富人囤积加密货币，形成马太效应，可能产生加密货币通胀问题。

3.历史证明（Proof of History, PoH）

算法简介：历史证明是 Solana 创建，这是一个高吞吐量区块链，于2018年启动，历史证明使网络参与者可以通过使用可验证的延迟功能在时间上达成共识，从而避免了"最长链"规则。

使用者：Solana

工作过程：

PoH是网络的时钟，而 TowerBFT是其守望台，其任务是防止恶意节点欺骗时间参数。对某个区块进行投票的任何验证者都必须等待下一个区块的产生，并从历史证明中获得"时间已经过去"的确认，然后才能再次投票。
Solana 则巧妙将基于哈希的时间链和状态分离，不是将每个区块的哈希链接在一起，而是网络中验证者对于区块内的哈希本身进行哈希，这种机制就是 PoH。PoH通过使用高频可验证延迟函数（VDF），随着时间的推移建立可通过密码验证的事件顺序。
从本质上讲，这意味着 PoH就像一个加密时钟，可以帮助网络就时间和事件顺序达成一致，而无需等待其他节点的消息。
历史证明的区块链状态哈希的连续输出能够给出可验证的事件顺序。

算法原理： Leader 给每个签名数据（待证明的交易）生成一个时间戳，直接将交易排序，这样就避免了 PoS中时间排序的问题，每个保证验证者都可以独立进行验证，这样大大缩短了验证时时间重排序的问题，只要进行交易证明的验证即可。

优缺点：

优点：费用低，每笔交易的费用只有几分之一美分，交易速度快，可延展性好，
缺点：中心化的担忧，Solana 目前有不到1200个验证者来验证其网络上的交易。

更少的去中心化应用程序：常被称为以太坊杀手。根据其网站，在 Solana 上创建了350多个 Dapp,相比之下以太坊上有近3000个 Dapp，而这正是 Defi 目前需要更多开发时间和创新的地方。

4.权威证明（Proof of Authority, PoA）

算法简介：由以太坊（ETH）和 Parity Technologies 公司的联合创始人Gavin Wood 于2017年提出。

PoA 机制不挖矿也不需要 Token。在基于次 PoA的区块链网络中，所有的交易和区块均由验证人处理。 PoA平台维护成本低，但是在 PoA中，交易和验证区块链的验证人，必须是能通过可靠性审查的人。所以，PoA的验证人必须非常关注自身声誉。声誉在 PoA里就是非常重要的资产。一般情况下，验证人会公开自己的实际身份。目前，这种共识机制形成的区块链技术主要应用在行业特征明显的联盟链、私有链上。

使用者： PoA、 Ethereum Kovantestnet、 xDai、 VeChain 和沃尔玛的物流链。

算法原理：

选择权威证明者;
由若干个验证人来生成区块记录交易，并获得区块奖励和交易费用。
在 PoA中，验证者是整个共识机制的关键，验证者通过放置这个身份来获得担保网络的权利，从而换取区块奖励。
若是验证者在整个过程中有恶意行为，或与其他验证者勾结，那通过链上管理可以移除和替换恶意行为者。
现有的法律反欺诈保障会被用于整个网络的参与者免受验证者的恶意行为。

优缺点：

优点：a. 需要更少的算力，不需要挖矿，节能环保;b. 验证速度快，支持更快的事务;c. 整个网络验证者互相监督，随时可以投票加入心得验证者或者剔除不合格验证者d. 硬分叉受法律保护，每个 Validator 均签订法律协议。
缺点：a. 公开身份，隐私和匿名性将减少b. 验证人特定为法律支持的集中的权威节点

5.延迟工作量证明（Delayed Proof-of-Work， dPoW）

算法简介：解释DPoW前，需要先说明什么叫PoB。PoB（Proof of Burn）叫做焚烧证明机制，是一种通过焚烧自己手中的代币来表决谁拥有对网络的领导地位的承诺。焚烧代币的数量越多，获得网络领导地位的概率越高。

在基于dPoW的区块链中，矿工挖矿所获得的不再是奖励的代币，而是可以焚烧的"wood"——燃木。矿工使用自己的算力，通过哈希算法，最终证明自己的工作量之后，获取对应的wood，wood不可交易。当wood积攒到一定量之后，可以前往燃烧场地燃烧wood。通过一组算法计算后，燃烧较多wood的人或者BP或者一组BP可以获取下个事件段出块的权利，成功出块后获取奖励（Token）。由于一个时间段内可能会有多人燃烧wood，下一个时间段出块的概率由自己燃烧wood数量决定。焚烧的越多，下一段时间可以获得出块权利的概率越高。这样可以让算力和出矿权利达到一个平衡。不一定非要庞大算力的矿工、矿池才能成为区块生产者。小矿工也有春天，只要辛勤劳动，积攒一定数量的wood，也能出块。保证效率，人人参与，最平民化的参与方式保证了去中心化的理念，避免拥有算力的组织或者持币大户把持网络。

使用者：Komodo

算法原理：dPoW 系统中有两种类型的节点：公证人节点和正常节点。

64 个公证人节点是由 dPoW 区块链的权益持有者（stakeholder）选举产生的，它们可从 dPoW 区块链向所附加的 PoW 区块链添加经公证确认的块。一旦添加了一个块，该块的哈希值将被添加到由 33 个公证人节点签署的 Bitcoin 交易中，并创建一个哈希到 Bitcoin 区块链的 dPow 块记录。

该记录已被网络中的大多数公证人节点公证。为避免公证人节点间在挖矿上产生战争，进而降低网络的效率，Komodo 设计了一种采用轮询机制的挖矿方法，该方法具有两种运行模式。

在"无公证人"（No Notary）模式下，支持所有网络节点参与挖矿，这类似于传统 PoW 共识机制。
而在"公证人激活"（Notaries Active）模式下，网络公证人使用一种显著降低的网络难度率挖矿。 "公证人激活"模式下，允许每位公证人使用其当前的难度挖掘一个区块，而其它公证人节点必须采用 10 倍难度挖矿，所有正常节点使用公证人节点难度的 100 倍挖矿。

优缺点：

优点：节能；安全性增加；可以通过非直接提供 Bitcoin（或是其它任何安全链），添加价值到其它区块链，无需付出 Bitcoin（或是其它任何安全链）交易的代价。
缺点：只有使用PoW或PoS的区块链，才能采用这种共识算法；在"公证员激活"（Notaries Active）模式下，必须校准不同节点（公证员或正常节点）的哈希率，否则哈希率间的差异会爆炸。

6.授权 PoS（DPoS，Delegated Proof-of-Stake）

算法简介：DPoS机制，又叫做「股份授权证明机制」和「受托人机制」，是2014年4月由Bitshares 的首席开发者 Dan Larimer（BM）提出的。从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。

为了方便理解，可以再举个例子。想象有这样一家公司：公司员工总数有1000人，每个人都持有数额不等的公司股份。每隔一段时间，员工可以把手里的票投向自己最认可的10个人来领导公司，其中每个员工的票权和他手里持有的股份数成正比。等所有人投完票以后，得票率最高的10个人成为公司的领导。如果有领导能力不胜任或做了不利于公司的事，那员工可以撤销对该领导的投票，让他的得票率无法进入前10名，从而退出管理层。

使用者：BitShares、Steemit、EOS、Lisk、Ark。

优缺点：

优点：节能；快速；高流量博客网站 Steemit 就使用了它。EOS 的块时间是 0.5 秒。
缺点：略中心化；拥有高权益的参与者可投票使自己成为一名验证者（这是近期已在 EOS 中出现的问题）。

7.实用拜占庭容错（Practical Byzantine Fault Tolerance, PBFT）

算法简介：PBFT 算法中，有一个节点会被当做主节点，而其他节点都是备份节点。系统内的所有节点都会相互通信，最终目标是大家能以少数服从多数的原则达成共识。

共识过程：

客户端发送一个请求给主节点去执行某个操作
主节点广播这个请求到各个备份节点
所有节点执行操作并把结果返回客户端
当客户端收到 f+1个来自不同节点的相同的结果后，过程结束。
代表可能撒谎的节点的最大值。

使用者： HyperLedgerFabric, Stellar, Ripple, Dispatch

优缺点：

优点：高速、可扩展。
缺点：通常用于私有网络和许可网络。

8.授权拜占庭容错（dBFTDelegated Byzantine Fault Tolerance，dBFT）

算法简介：中国区块链社区 NEO (原名小蚁) 提出一种改进的拜占庭容错算法 dBFT, 该算法在 PBFT 的基础上借鉴了 PoS 设计思路, 首先按照节点的权益来选出记账人, 然后记账人之间通过拜占庭容错算法来达成共识。该算法改进了 PoW 和 PoS 缺乏最终一致性的问题, 使得区块链能够适用于金融场景。

同样是为了解决拜占庭将军问题，「授权拜占庭容错」机制，是一种在NEO区块链内部实现的保证容错的共识算法。在这个机制当中，存在两个参与者，一个是专业记账的"记账节点"，一个是系统当中的普通用户。

普通用户基于持有权益的比例来投票决定记账节点，当需要通过一项共识时，在这些记账节点中随机推选出一名发言人拟定方案，然后由其他记账节点根据拜占庭容错算法，即少数服从多数的原则进行表态，如果超过66%的节点表示同意发言人方案，则共识达成；否则，重新推选发言人，重复投票过程。由于所有代表都可以验证区块提案，因此很容易理解议长发送的数据是有效还是无效。因此，如果议长不诚实并向三分之二的代表发送无效提案，则块将不匹配，节点所有者将不会对其进行验证。以三分之二的票数达成共识，并选出新的议长。

使用者：Neo

共识过程：

任何人都可以成为代表，只要他或她符合要求。所有 NEO 代币持有者都可以投票，代表不是匿名的，并且成为节点所有者需要 1,000 GAS。
从代表中随机选出一名发言人。
发言人从等待验证的交易中构建一个新区块。然后，议长将提案发送给当选的代表。他们应该跟踪所有交易并将它们记录在网络上。
代表们可以自由分享和比较他们收到的提案，以测试数据的准确性以及演讲者的诚实度。如果超过三分之二的代表达成共识并验证，则该区块被添加到区块链中。

优缺点：

优点：快速(生成一个块需要15-20秒)；交易吞吐量大，无需消耗能量，可扩展，没有分叉。
缺点：没有匿名性，需要真实身份运作才能被选举。每个人都争相成为根链。其中可能存在多个根链。

9.轮流拜占庭容错（Rotation Practical Byzantine Fault Tolerance， RBPFT）

算法简介：dBft 和 RPBFT 原理和 PBFT 相似，只是不是所有的节点都参与共识，而是将节点分为两种：

共识节点：执行 PBFT 共识流程的节点，有轮流出块的权限
验证节点：不执行共识流程，验证共识节点是否合法、区块验证，经过若干轮共识后，会切换为共识节点轮流拜占庭容错中轮流将共识节点替换为验证节点。

使用案例：Fisco-BCOS

优缺点：

优点：传播速度比gossip快，无冗余消息包分而治之，每个节点出带宽为O(1)，可扩展性强
缺点：中间节点是单点，需要额外的容错策略

文章信息

本文作者：zhangxue
本文链接：https://lucksnow1989.github.io/article/8.微服务/2.共识算法.html
版权声明：本文为本人原创文章，遵循 CC 4.0 BY-NC-SA版权协议，转载请附上原文出处链接和本声明。