SCRY技术分享常见共识协议和算法

在区块链开发中，较为核心的点有三个：共识协议、加密算法、点对点通信协议。当然还有存储，只是存储技术相对成熟，现阶段存储不是重要的研究方向。

本文目的是整理出常见的分布式共识协议和算法，记录对应的特性和使用场景。关于相关的具体实现，还需要结合其他更详细的资料来理解。

拜占庭将军问题

拜占庭将军问题，它是分布式领域共识问题的解决思路。

1. 口信消息型拜占庭问题的解：如果叛将人数为m，将军人数不能少于3m + 1 ，那么拜占庭将军问题就能解决了这个算法的限制，就是说能容忍的叛将数m，是已知的，叛将数 m 决定递归循环的次数

2. 签名消息型拜占庭问题的解：依赖于两个特性实现。特性（1）签名无法伪造，而且对签名内容的更改都会被发现；特性（2）任何人都能验证将军签名的真伪

在计算机分布式系统中，最常用的是故障容错算法CFT（Crash Fault Tolerance）（属于非拜占庭容错算法）

容错的区别：对应到要容错的问题节点类型，就分别是1、恶意节点2、故障节点

CAP 理论

CAP理论，对分布式系统的特性做了很好的抽象。一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）

CAP不可能三角：记住结论就好，具体论证流程，需要查看相关的论文。

分布式系统中，节点间的分区故障是必然发生的。就是说，技术选型中，分区容错性P是前提。选型就是在AP和CP之间了。

CP模型：为了防止数据不一致，集群将拒绝新数据的写入，典型的应用是Etcd。

AP模型：出现分区故障时，相同的读操作访问不同的节点，得到响应数据可能不一样。

根据特性技术选型：以influxDB为例，meta节点要求数据一致性，用的CP架构，data节点保证业务可用，用的AP架构

分布式事务

分布式系统的ACID的实现方案：1、二阶段提交协议2、TCC

二阶段提交协议：不仅是协议，也是种非常经典的思想。目的是达成提交操作的共识，如TCC、Paxos、Raft协议，MySQL中的redolog机制等。

幂等性：指同一操作对同一系统的多次执行，所产生的影响均与一次执行的影响相同。

ACID的特性，可以理解为CAP中的最强的一致性。

一般在开发实现分布式系统，如果不是必须，尽量不要实现事务，可以考虑采用最终一致性。

BASE 理论

Base理论属于AP模型的延伸，是对 CAP 中一致性和可用性权衡的结果。核心就是基本可用（Basically Available）、软状态（Soft state）和最终一致性（Eventually consistent）

基本可用BA的实现策略：流量削峰、延迟响应、体验降级、过载保护

最终的一致的实现方案：1.读时修复2.写时修复3.异步修复。其中，由于写时修复策略，可以不需要做一致性对比，写入失败时，只需节点记录下来，定时再重传即可，相对开销较小。在实现最终一致性的时候，同时实现自定义写一致性级别（All、Quorum、One、Any）

Base理论，可以关联到一个具体的算法---Quorum NWR

Quorum NWR算法

一个非常实用的算法，能有效弥补在AP型系统中，缺乏强一致性的痛点。Quorum NWR的三个重要元素。

N：表示副本数

W：表示成功完成W个副本更新，才完成写操作

R：表示读取一个数据对象时，需要读R个副本

通过调整写入或者查询的方式，当 W + R > N 时，就可以实现强一致性。

实际用例：在kafka的保证数据一致性的同步写入机制中，就用到了类似的思路。保证写入到N个节点成功，才返回给客户端，此次写入成功。在influxDB中，也有类型规则。

Raft算法

Raft 算法是现在分布式系统开发首选的共识算法。Raft算法是在Paxos算法基础上来的，在实现和理解上，都比Paxos算法要好很多。

Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

节点的三个角色：领导者（Leader）、跟随者（Follower）和候选人（Candidate）

三个核心步骤：领导者选举、日志复制、成员变更。具体步骤的实现分析不写了，内容篇幅太多，需要额外花时间去仔细学习。这儿只记录Raft共识算法的特性。

Raft不是一致性算法，而是共识算法。区别：一致性强调各个节点状态一致。在raft节点同步状态的通信流程中，并不能保证强一致性，虽然都是可达最终一致性的。

Raft算法动态演示教程http://thesecretlivesofdata.com/raft/

Gossip算法

Gossip也是实现最终一致性。

实现的三个方案：直接邮寄（Direct Mail）、反熵（Anti-entropy）和谣言传播（Rumor mongering）

直接邮寄：就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。

反熵：节点间每隔段时间，就随机选择某个其他节点，然后交换自己的所有数据，来消除两者之间的差异，实现数据的最终一致性。实现反熵，主要有推、拉和推拉三种方式。

谣言传播：当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。

其中反熵方案最为实用，其适用的场景是：相关的节点都已知，且节点数量不能太多。但反熵需要做一致性对比，很消耗系统性能的。在动态变化或节点数较多的分布式环境，谣言传播方案更为合适。

POW算法

工作量证明（Proof of Work）算法中，恶意攻击者需要控制全网51%的算力，成本是非常高的。

在比特币的区块链中，PoW算法，是通过SHA256进行哈希运算，计算出符合指定条件的哈希值，来证明工作量的。

51%攻击，本质是因为比特币的区块链约定了“最长链胜出，其它节点在这条链基础上扩展”，攻击者可以通过优势算力实现对最长链的争夺。

除了通过PoW算法，增加坏人作恶的成本，比特币还通过“挖矿得币”奖励好人，最终保持了整个系统的运行稳定。

—-

编译者/作者：scry

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。