从传统分布式一致性算法到区块链技术的共识机制

1、传统分布式一致性

在一个分布式系统中,如何保证集群中所有节点中的数据完全相同并且能够对某个提案(Proposal)达成一致是分布式系统正常工作的核心问题,而共识算法就是用来保证分布式系统一致性的方法。

然而分布式系统由于引入了多个节点,所以系统中会出现各种非常复杂的情况;随着节点数量的增加,节点失效、故障或者宕机就变成了一件非常常见的事情,解决分布式系统中的各种边界条件和意外情况也增加了解决分布式一致性问题的难度。

在一个分布式系统中,除了节点的失效是会导致一致性不容易达成的主要原因之外,节点之间的网络通信收到干扰甚至阻断以及分布式系统的运行速度的差异都是解决分布式系统一致性所面临的难题。

 

1.1 CAP理论

在 1998 年的秋天,加州伯克利大学的教授 Eric Brewer在 PODC 2000 研讨会提出CAP 理论,2002 年被 Seth Gilbert 和 Nancy Lynch 证明为定理(引用的这篇论文1999 年论文 Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services ),其中总结了 Eric Brewer 提出的 CAP 理论。这篇论文证明了两个非常有意思的理论,首先是在异步的网络模型中,所有的节点由于没有时钟仅仅能根据接收到的消息作出判断,这时完全不能同时保证一致性、可用性和分区容错性,每一个系统只能在这三种特性中选择两种。

不过这里讨论的一致性其实都是强一致性,也就是所有节点接收到同样的操作时会按照完全相同的顺序执行,被一个节点提交的更新操作会立刻反映在其他通过异步或部分同步网络连接的节点上,如果想要同时满足一致性和分区容错性,在异步的网络中,我们只能中心化存储所有数据,通过其他节点将请求路由给中心节点达到这两个目的。

但是在现实世界中其实并不存在绝对异步的网络环境,如果我们允许每一个节点拥有自己的时钟,这些时钟虽然有着完全不同的时间,但是它们的更新频率是完全相同的,所以我们可以通过时钟得知接收消息的间隔时间,在这种更宽松的前提下,我们能够得到更强大的服务。

然而在部分同步的网络环境中,我们仍然没有办法同时保证一致性、可用性和分区容错性,证明的过程其实非常简单,可以直接阅读 论文 的 4.2 节,然而时钟的出现能够让我们知道当前消息有多久没有得到回应,通过超时时间就能在一定程度上解决信息丢失的问题。

由于网络一定会存在延时,所以没有办法在分布式系统中做到强一致性的同时保证可用性,不过我们可以通过降低对一致性的要求,在一致性和可用性之间做出权衡,而这其实也是设计分布式系统首先需要考虑的问题,由于强一致性的系统会导致系统的可用性降低,仅仅将接受请求的工作交给其他节点对于高并发的服务并不能解决问题,所以在目前主流的分布式系统中都选择最终一致性

最终一致性允许多个节点的状态出现冲突,但是所有能够沟通的节点都能够在有限的时间内解决冲突,从不一致的状态恢复到一致,这里列出的两个条件比较重要,一是节点直接可以正常通信,二是冲突需要在有限的时间内解决,只有在这两个条件成立时才能达到最终一致性。

1.2 拜占庭将军问题(Byzantine Generals Problem )

拜占庭将军问题是 Leslie Lamport 在 The Byzantine Generals Problem 论文中提出的分布式领域的容错问题,它是分布式领域中最复杂、最严格的容错模型。

在该模型下,系统不会对集群中的节点做任何的限制,它们可以向其他节点发送随机数据、错误数据,也可以选择不响应其他节点的请求,这些无法预测的行为使得容错这一问题变得更加复杂。

拜占庭将军问题描述了一个如下的场景,有一组将军分别指挥一部分军队,每一个将军都不知道其它将军是否是可靠的,也不知道其他将军传递的信息是否可靠,但是它们需要通过投票选择是否要进攻或者撤退:

黄色代表状态未知,绿色代表进攻,蓝色代表撤退,最后红色代表当前将军的信息不可靠

在这时,无论将军是否可靠,只要所有的将军达成了统一的方案,选择进攻或者撤退其实就是没有任何问题的:

上述的情况不会对当前的战局有太多的影响,也不会造成损失,但是如果其中的一个将军告诉其中一部分将军选择进攻、另一部分选择撤退,就会出现非常严重的问题了。

由于将军的队伍中出了一个叛徒或者信息在传递的过程中被拦截,会导致一部分将军会选择进攻,剩下的一部分会选择撤退,它们都认为自己的选择是大多数人的选择,这时就出现了严重的不一致问题。

拜占庭将军问题是对分布式系统容错的最高要求,然而这不是日常工作中使用的大多数分布式系统中会面对的问题,我们遇到更多的还是节点故障宕机或者不响应等情况,这就大大简化了系统对容错的要求;不过类似 Bitcoin、Ethereum 等分布式系统确实需要考虑拜占庭容错的问题,我们会在下面介绍它们是如何解决的。

1.3 FLP不可能定理

FLP 不可能定理是分布式系统领域最重要的定理之一,它给出了一个非常重要的结论:在网络可靠并且存在节点失效的异步模型系统中,不存在一个可以解决一致性问题的确定性算法

In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable it delivers all messages correctly and exactly once.

这个定理其实也就是告诉我们不要浪费时间去为异步分布式系统设计在任意场景上都能够实现共识的算法,异步系统完全没有办法保证能在有限时间内达成一致,在这里作者并不会尝试去证明 FLP 不可能定理,读者可以阅读相关论文 Impossibility of Distributed Consensuswith One Faulty Process 了解更多的内容。

2、传统分布式共识算法

2.1 Paxos

Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法,其解决的问题是分布式系统如何就某个值(决议)达成一致。通过Paxos可以实现多副本一致性、分布式锁、名字管理、序列号分配等。比如,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点执行相同的操作序列,那么他们最后得到的状态就是一致的。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。后续又增添多个改进版本的Paxos,形成了Paxos协议家族,但其共同点是不容易工程实现。Lamport在2011年的论文Leaderless Byzanetine Paxos中表示,不清楚实践中是否有效,考虑Paxos本身实现的难度以及复杂程度,此方案工程角度不是最优,但是系统角度应该是最好的。

我们先来简单介绍一下 Paxos 究竟是什么,Paxos 其实是一类能够解决分布式一致性问题的协议,它能够让分布式网络中的节点在出现错误时仍然保持一致;Leslie Lamport 提出的 Paxos 可以在没有恶意节点的前提下保证系统中节点的一致性,也是第一个被证明完备的共识算法,目前的完备的共识算法包括 Raft 本质上都是 Paxos 的变种。

作为一类协议,Paxos 中包含 Basic Paxos、Multi-Paxos、Cheap Paxos 和其他的变种,在这一小节我们会简单介绍 Basic Paxos 和 Multi-Paxos 这两种协议。

2.1.1 Basic Paxos

Basic Paxos 是 Paxos 中最为基础的协议,每一个 Basic Paxos 的协议实例最终都会选择唯一一个结果;使用 Paxos 作为共识算法的分布式系统中,节点都会有三种身份,分别是 Proposer、Acceptor 和 Learner。

我们在这里会忽略最后一种身份 Learner 简化协议的运行过程,便于读者理解;Paxos 的运行过程分为两个阶段,分别是准备阶段(Prepare)和接受阶段(Accept),当 Proposer 接收到来自客户端的请求时,就会进入如下流程:

以上截图取自 Paxos lecture (Raft user study) 的第 12 页。

在整个共识算法运行的过程中,Proposer 负责提出提案并向 Acceptor 分别发出两次 RPC 请求,Prepare 和 Accept;Acceptor 会根据其持有的信息 minProposalacceptedProposal 和 acceptedValue 选择接受或者拒绝当前的提案,当某一个提案被过半数的 Acceptor 接受之后,我们就认为当前提案被整个集群接受了。

 

我们简单举一个例子介绍 Paxos 是如何在多个提案下保证最终能够达到一致性的,上述图片中 S1 和 S5 分别收到了来自客户端的请求 X 和 Y,S1 首先向 S2 和 S3 发出 Prepare RPC 和 Accept RPC,三个服务器都接受了 S1 的提案 X;在这之后,S5 向 S3 和 S4 服务器发出 Prepare(2.5) 的请求,S3 由于已经接受了 X,所以它会返回接受的提案和值 (1.1, X),这时服务器使用接收到的提案代替自己的提案 Y,重新向其他服务器发送 Accept(2.5, X) 的 RPC,最终所有的服务器会达成一致并选择相同的值。

想要了解更多与 Paxos 协议在运行过程中的其他情况可以看一下 Paxos lecture (Raft user study) 视频。

2.1.2 Multi-Paxos

由于大多数的分布式集群都需要接受一系列的值,如果使用 Basic Paxos 来处理数据流,那么就会导致非常明显的性能损失,而 Multi-Paxos 是前者的加强版,如果集群中的 Leader 是非常稳定的,那么我们往往不需要准备阶段的工作,这样就能够将 RPC 的数量减少一半。

上述图片中描述的就是稳定阶段 Multi-Paxos 的处理过程,S1 是整个集群的 Leader,当其他的服务器接收到来自客户端的请求时,都会将请求转发给 Leader 进行处理。

当然,Leader 角色的出现自然会带来另一个问题,也就是 Leader 究竟应该如何选举,在 Paxos Made Simple一文中并没有给出 Multi-Paxos 的具体实现方法和细节,所以不同 Multi-Paxos 的实现上总有各种各样细微的差别。

2.2 Zab

1.ZAB架构设计
Architecture of ZAB – ZooKeeper Atomic Broadcast protocol

2.ZAB 与 Paxos比较
ZAB vs Paxos

Paxos算法的确是不关系请求之间的逻辑顺序,而只考虑数据之间的全序,但很少有人直接使用paxos算法,都会经过一定的简化、优化。
一般Paxos都会有几种简化形式,其中之一便是,在存在Leader的情况下,可以简化为1个阶段(Phase2)。仅有一个阶段的场景需要有一个健壮的Leader,因此工作重点就变为Leader选举,在考虑到Learner的过程,还需要一个”学习“的阶段,通过这种方式,Paxos可简化为两个阶段:
  • 之前的Phase2
  • Learn
如果再考虑多数派要Learn成功,这其实就是Zab协议。Paxos算法着重是强调了选举过程的控制,对决议学习考虑的不多,Zab恰好对此进行了补充。

Zookeeper使用了一种称为Zab(Zookeeper Atomic Broadcast)的协议作为其一致性复制的核心,据其作者说这是一种新发算法,其特点是充分考虑了Yahoo的具体情况:高吞吐量、低延迟、健壮、简单,但不过分要求其扩展性。

Zookeeper的实现是有Client、Server构成,Server端提供了一个一致性复制、存储服务,Client端会提供一些具体的语义,比如分布式锁、选举算法、分布式互斥等。从存储内容来说,Server端更多的是存储一些数据的状态,而非数据内容本身,因此Zookeeper可以作为一个小文件系统使用。数据状态的存储量相对不大,完全可以全部加载到内存中,从而极大地消除了通信延迟。

Server可以Crash后重启,考虑到容错性,Server必须“记住”之前的数据状态,因此数据需要持久化,但吞吐量很高时,磁盘的IO便成为系统瓶颈,其解决办法是使用缓存,把随机写变为连续写。

考虑到Zookeeper主要操作数据的状态,为了保证状态的一致性,Zookeeper提出了两个安全属性(Safety Property)

  • 全序(Total order):如果消息a在消息b之前发送,则所有Server应该看到相同的结果
  • 因果顺序(Causal order):如果消息a在消息b之前发生(a导致了b),并被一起发送,则a始终在b之前被执行。
为了保证上述两个安全属性,Zookeeper使用了TCP协议和Leader。通过使用TCP协议保证了消息的全序特性(先发先到),通过Leader解决了因果顺序问题:先到Leader的先执行。因为有了Leader,Zookeeper的架构就变为:Master-Slave模式,但在该模式中Master(Leader)会Crash,因此,Zookeeper引入了Leader选举算法,以保证系统的健壮性。归纳起来Zookeeper整个工作分两个阶段:
  • Atomic Broadcast
  • Leader选举

2.2.1 Atomic Brodadcast

同一时刻存在一个Leader节点,其他节点称为“Follower”,如果是更新请求,如果客户端连接到Leader节点,则由Leader节点执行其请求;如果连接到Follower节点,则需转发请求到Leader节点执行。但对读请求,Client可以直接从Follower上读取数据,如果需要读到最新数据,则需要从Leader节点进行,Zookeeper设计的读写比例是2:1。
Leader通过一个简化版的二段提交模式向其他Follower发送请求,但与二段提交有两个明显的不同之处:
  • 因为只有一个Leader,Leader提交到Follower的请求一定会被接受(没有其他Leader干扰)
  • 不需要所有的Follower都响应成功,只要一个多数派即可
通俗地说,如果有2f+1个节点,允许f个节点失败。因为任何两个多数派必有一个交集,当Leader切换时,通过这些交集节点可以获得当前系统的最新状态。如果没有一个多数派存在(存活节点数小于f+1)则,算法过程结束。但有一个特例:
如果有A、B、C三个节点,A是Leader,如果B Crash,则A、C能正常工作,因为A是Leader,A、C还构成多数派;如果A Crash则无法继续工作,因为Leader选举的多数派无法构成。

2.2.2 leader 选举

Leader选举主要是依赖Paxos算法,具体算法过程请参考其他博文,这里仅考虑Leader选举带来的一些问题。Leader选举遇到的最大问题是,”新老交互“的问题,新Leader是否要继续老Leader的状态。这里要按老Leader Crash的时机点分几种情况:
  1. 老Leader在COMMIT前Crash(已经提交到本地)
  2. 老Leader在COMMIT后Crash,但有部分Follower接收到了Commit请求
第一种情况,这些数据只有老Leader自己知道,当老Leader重启后,需要与新Leader同步并把这些数据从本地删除,以维持状态一致。
第二种情况,新Leader应该能通过一个多数派获得老Leader提交的最新数据
老Leader重启后,可能还会认为自己是Leader,可能会继续发送未完成的请求,从而因为两个Leader同时存在导致算法过程失败,解决办法是把Leader信息加入每条消息的id中,Zookeeper中称为zxid,zxid为一64位数字,高32位为leader信息又称为epoch,每次leader转换时递增;低32位为消息编号,Leader转换时应该从0重新开始编号。通过zxid,Follower能很容易发现请求是否来自老Leader,从而拒绝老Leader的请求。
因为在老Leader中存在着数据删除(情况1),因此Zookeeper的数据存储要支持补偿操作,这也就需要像数据库一样记录log。

ZAB集群机器越多,写性能会有所降低、读性能得到水平扩展。然而基于Paxos实现的Chubby读写相对ZK复杂。
同时ZK的每一个操作都具有隐形事务要求,通过强一致性保证数据节点的数据的顺序性(FIFO)。Paxos协议无法实现多个写操作的顺序性,或者通过串行操作实现,如此则以牺牲效率为代价。使用Zab协议可以实现如下功能:

1. ZK可以实现发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master选举、分布式锁和分布式队列等功能。

  • 发布/订阅模式:
    • 在处理自定义事件时,观察者模式和发布/订阅模式经常使用,起初不了解这两个模式的实现时,在网上看一些资料,很多介绍都将两种模式混淆在一起,认为他们是同一个模式、一样的实现。后来看了一些设计模式的书籍,感觉两种模式还是有本质的区别,具体如下:
      • 观察者模式至少需要维护两个对象
        • 顾名思义:有观察者对象,肯定也得有观察者需要关注的目标对象,在观察者模式实习的时候,观察者对象需要定义一个统一的接口,在目标对象发生某些改变时,调用(触发)观察者的对应的方法,通知观察者到底发生了那些变化。
        • 而发布订阅模式,只需要注册订阅器上的一个事,而订阅器发生某些事件,则会触发事件通道里面的函数,触发器并不会关心其他任何对象和任何接口
      • 在实现自定义事件方面我觉得使用发布/订阅模式更为合适,简单、耦合性比较低。使用发布订阅模式时,我们关注那个对象,只需要在这个注册这个对象的对应的事件即可,降低了订阅者和发布者直接的耦合。
  • 负载均衡:
    • 本质是利用zookeeper的配置管理功能
    • 步骤为:
      • 服务提供者把自己的域名及IP端口的映射注册到zk中
      • 服务消费者通过域名从zk中获取到对应的IP及端口,这个IP及端口有多个,只是获取其中一个
      • 当服务宕机时,对于的域名与IP的对于就会减少一个映射
  • 命名服务:
    • Zookeeper 的 Name Service 与 JNDI 能够完成的功能是差不多的,它们都是将有层次的目录结构关联到一定资源上。也许你并不需要将名称关联到特定资源上,你可能只需要一个不会重复名称,就像数据库中产生一个唯一的数字主键一样。
  • 分布式协调/通知:
    • 通过watcher的通知机制实现
      • 通过 watcher 实现分布式数据的发布/订阅功能
      • watcher 包括客户端线程,客户端 WatcherManager , Zookeeper 服务器三个部分
      • 客户端在向 zk 服务器注册 watcher 的同时,会将 watcher对象存储在客户端的WatcherManager 中,当 Zookeeper 服务器端触发 Watcher 事件后,会向客户端发送通知,客户端线程从 WatcherManager 中取出对应的 Watcher 对象来执行回调逻辑。
  • 分布式锁:共享锁,排他锁
    • 排他锁(Exclusive Locks)
      • 引申:又成为写锁或独占锁,Java 中使用 synchronized 机制和 JDK5提供的 ReentrantLock 定义锁,数据对一个事务可见。
      • Zookeeper 使用数据节点(ZNode)表示一个锁,即只存在/exclusive_lock/lock。
    • 共享锁(Shared Locks)
      • 引申:又成为读锁,数据对所有事务可见。
      • 存在/shard_lock/lock_no1,/shard_lock/lock_no2等多个临时顺序节点
      • 读写请求:
        • 读请求:如果没有比自己序号小的子节点,或者所有比自己序号小的子节点都是读请求,表明自己获取到了共享锁,开始读取逻辑。如果比自己序号小的子节点中有写请求,则进入等待
        • 写请求:如果自己不是序号最小的子节点,则进入等待
        • 如图,可以避免 ZooKeeper 发送节点变更 Watcher 通知给所有机器,即『羊群效应』。

  • 分布式事务
  • 案例:

    1.引申:基于MQ的分布式事务补偿机制
    2.应用:交易和资金对资源回滚不做同步 RPC调用,而是通过MQ(事务 MQ 或 Mysql+Canal+RocketMQ)交互,通过将消息发送到MQ,然后由资源应用自己去监听MQ的事件

  • 集群管理
    • 通过管理 zk 临时节点的顺序子节点,实现集群管理
  • Master选举
    • 原理:
      • 服务器争抢创建标志为Master的临时节点
      • 服务器监听标志为Master的临时节点,当监测到节点删除事件后展开新的一轮争抢
      • 某个服务器成功创建则为Master

  • 分布式队列
    • 业界参考Alibaba RocketMQ
    • FIFO队列:利用zk的共享锁机制实现
    • 分布式系统协调:如合并计算结果等

2.ZK可以保证顺序一致性、原子性、单一视图、可靠性、实时性的功能。

3.Zookeeper并发控制

  • Zookeeper 版本号机制,通过乐观锁进行并发控制
    • 乐观锁又成为乐观并发控制,适用于数据并发竞争不大,事务冲突较少的应用中
    • 悲观所适用于数据更新竞争十分激烈的场景,如分布式 DB SequenceID 申请
    • 乐观锁事务分为三个阶段:数据读取,写入校验,数据写入
    • 写入校验阶段是乐观锁的关键,事务会检查数据在读取阶段后是否有其他事务对数据进行过更新,以确保数据更新的一致性。通过 JDK 中的 CAS 乐观锁实现

4.Zookeeper角色

  • Leader(设计模式:责任链模式)
    • 事务请求的唯一调度和处理者,保证集群事务处理的顺序性
    • 集群内部各个服务器的调度者
  • Follower(设计模式:责任链模式)
    • 处理客户端非事务请求,转发事务请求给Leader服务器
    • 参与事务请求Proposal投票
    • 参与Leader选举投票
  • Observer
    • 只提供非事务服务,事务请求(Proposal投票与Leader选举)会转发给Leader服务器
    • 用于不影响集群事务处理能力条件下提升集群的非事务处理能力

5.集群间消息通信
6.znode的类型

  • persistent znode,如/path,只能通过zk的api删除(delete)
  • ephemeral znode,当创建该节点的客户端崩溃或关闭了与zk的连接时,这个节点就会被删除。
  • 有序节点:一个有序znode节点被分配唯一一个单调递增的整数。

7.zk服务器端运行在两种模式下:独立模式(standalone)和仲裁模式(quorum)。standalone下zk状态无法复制,quorum下会有一组zk服务器,即zk集合,可以进行状态复制

2.3 raft

斯坦福大学的博士生Diego Ongaro把对其的研究作为了自己的博士课题。2014年秋天,他正式发表了博士论文CONSENSUS: BRIDGING THEORY AND PRACTICE,并给出了分布式一致性协议的一个实现算法,即Raft。在论文正式发表前,Diego Ongaro还把与Raft相关的部分摘了出来,形成了一篇十多页的文章In Search of an Understandable Consensus Algorithm,即人们俗称的Raft论文。Raft算法主要注重协议的落地性和可理解性,让分布式一致性协议可以较为简单地实现。Raft和Paxos一样,只要保证n/2+1节点正常就能够提供服务;同时,Raft更强调可理解性,使用了分而治之的思想把算法流程分为选举、日志复制、安全性三个子问题。

在一个由Raft协议组织的集群中有三类角色:Leader(领袖)、Follower(群众)、Candidate(候选人)。Raft开始时在集群中选举出Leader负责日志复制的管理,Leader接受来自客户端的事务请求(日志),并将它们复制给集群的其他节点,然后负责通知集群中其他节点提交日志,Leader负责保证其他节点与他的日志同步,当Leader宕掉后集群其他节点会发起选举选出新的Leader。

Raft 其实就是 Multi-Paxos 的一个变种,Raft 通过简化 Multi-Paxos 的模型,实现了一种更容易让人理解的共识算法,它们两者都能够对一系列连续的问题达成一致。Raft 在 Multi-Paxos 的基础之上做了两个限制,首先是 Raft 中追加日志的操作必须是连续的,而 Multi-Paxos 中追加日志的操作是并发的,但是对于节点内部的状态机来说两者都是有序的,第二就是 Raft 对 Leader 选举的条件做了限制,只有拥有最新、最全日志的节点才能够当选 Leader,但是 Multi-Paxos 由于任意节点都可以写日志,所以在选择 Leader 上也没有什么限制,只是在选择 Leader 之后需要将 Leader 中的日志补全。

在 Raft 中,所有 Follower 的日志都是 Leader 的子集,而 Multi-Paxos 中的日志并不会做这个保证,由于 Raft 对日志追加的方式和选举过程进行了限制,所以在实现上会更加容易和简单。

从理论上来讲,支持并发日志追加的 Paxos 会比 Raft 有更优秀的性能,不过其理解和实现上还是比较复杂的,很多人都会说 Paxos 是科学,而 Raft 是工程,当作者需要去实现一个共识算法,会选择使用 Raft 和更简洁的实现,避免因为一些边界条件而带来的复杂问题。

这篇文章并不会展开介绍 Raft 的实现过程和细节,如果对 Raft 有兴趣的读者可以在 The Raft Consensus Algorithm 找到非常多的资料。

2.4 Gossip

2.5 Epidemic

3、区块链共识机制

当我们描述传统分布式一致性算法时,其实是基于一个假设——分布式系统中没有拜占庭节点(即除了宕机故障,没有恶意篡改数据和广播假消息的情况)。而当要解决拜占庭网络中的数据一致性问题时,则需要一种可以容错的算法,我们可以把这类算法统称为拜占庭容错的分布式一致性算法。而共识机制,就是在拜占庭容错的分布式一致性算法基础上,根据具体业务场景传输和同步数据的通信模型

3.1 工作量证明机制(Proof of Work, POW)

上一节介绍的共识算法,无论是 Paxos 还是 Raft 其实都只能解决非拜占庭将军容错的一致性问题,不能够应对分布式网络中出现的极端情况,但是这在传统的分布式系统都不是什么问题,无论是分布式数据库还是消息队列集群,它们内部的节点并不会故意的发送错误信息,在类似系统中,最常见的问题就是节点失去响应或者失效,所以它们在这种前提下是有效可行的,也是充分的。

这一节介绍的 工作量证明(POW,Proof-of-Work)是一个用于阻止拒绝服务攻击和类似垃圾邮件等服务错误问题的协议,它在 1993 年被 Cynthia Dwork 和 Moni Naor 提出,它能够帮助分布式系统达到拜占庭容错。

工作量证明的关键特点就是,分布式系统中的请求服务的节点必须解决一个一般难度但是可行(feasible)的问题,但是验证问题答案的过程对于服务提供者来说却非常容易,也就是一个不容易解答但是容易验证的问题。

这种问题通常需要消耗一定的 CPU 时间来计算某个问题的答案,目前最大的区块链网络 – 比特币(Bitcoin)就使用了工作量证明的分布式一致性算法,网络中的所有节点计算通过以下的谜题来获得当前区块的记账权:

SHA-256 作为一个哈希函数,想要通过 SHA-256 函数的输出推断出输入在目前来看可能性是可以忽略不计的,比特币网络就需要每一个节点不断改变 NONCE 来得到不同的结果 HASH,如果得到的 HASH 结果在小于某个范围,目前(2017.12.17)的难度是:

0x0000000000000000000000000000000000000000000000000000017268d8a21a

也就是如果只计算一次 SHA-256 的值能够小于上述结果的可能性是 1.3710651.37∗10−65,当前的全网算力也达到了 13,919 PH/s,这是一个非常恐怖的数字,随着网络算力的不断改变比特币也会不断改变当前问题的难度,保证每个区块被发现的时间在 10min 左右;在整个比特币网络中,谁先得到当前问题的答案就能够获得这个区块的记账权并将当前区块通过 Gossip 协议发送给尽可能多的比特币节点。

工作量证明的原理其实非常简单,比特币网络选择的谜题非常好的适应了工作量证明定义中的问题,比较难以寻找同时又易于证明,我们可以简单理解为工作量证明防止错误或者无效请求的原理就是增加客户端请求服务的工作量,而适合难度的谜题又能够保证合法的请求不会受到影响。

由于工作量证明需要消耗大量的算力,同时比特币大约 10min 才会产生一个区块,区块的大小也只有 1MB,仅仅能够包含 3、4000 笔交易,平均下来每秒只能够处理 5~7(个位数)笔交易,所以比特币网络的拥堵状况非常严重。

整个系统中每个节点为整个系统提供计算能力(简称算力),通过一个竞争机制,让计算工作完成最出色的节点获得系统的奖励,也就是完成新生成货币的分配。区块链是一个持续增长的顺序块组成的,每个块包含了头文件和一系列的交易信息TXi,其中头文件中保护了timestamp Ti,上一个块的索引Hi−1, 和nounce Ni−1 ,区块链是密码上的安全,对于每一轮只要找到相应的HASG的碰撞就算成功,HASG的碰撞的意思可以了解为hash值的前多少位相同,我们知道何难找到两个hash一模一样的文件,但是我们可以找到前几位相同的,我们将一个完整的挖矿过程整理如下:

f(Di)>SHA256(SHA256(Hi−1||Ti||TXi||di||Ni)))

其中Di是难度系数,可以认为是前多少位的碰撞。挖矿的过程就是在不停的尝试找Ni的过程。下面我们给出一个模拟挖矿的例子。

测试环境说明:

操作系统 RAM SWAP
Centos 6 x86 512M 256 MB

操作步骤:

  1. 运行如下脚本
1
2
3
4
5
6
7
8
9
#!/ bin/bash
n=1
while [ $n -lt 1000000 ]
do
echo -n $n j sha1sum – j cut -c 1-9 >> sha1-9-result
n=$ (( n+1 )) # increments $n
done
sort sha1-9-result > sha1-9-result -sort
uniq -d sha1-9-result -sort > sha1-9-result -uniq
  1. 对结果进行排序,找到前9位对撞成功的n的值.

实验结果如下:

“311214” sha1 value is:
ff47893a16ec612176cbb4255c7e0ce58400a828
“775478” sha1 value is:
ff47893a1f31dd5fd4220a9e8981112a2b3be2d6

虽然只是模拟实验,但是完整的反映了POW的运作原理。

3.2 POS(Proof-of-stake)

权益证明是区块链网络中的使用的另一种共识算法,在基于权益证明的密码货币中,下一个区块的选择是根据不同节点的股份和时间进行随机选择的。

由于创造新的区块并不会消耗大量的 CPU,如果它不诚实也不会失去什么,这也就给了很多节点作弊的理由,每一个节点为了最大化利益会在多条链上同时挖矿。

在早期的所有权证明算法中,整个网络只会奖励创建区块的节点,不存在任何惩罚,在这时每个节点在创造的多条链上同时投票才能够最大化利益,在这种情况下网络中的节点很难对一条链达成共识。

有两种办法能够解决缺乏利害关系(nothing-at-stake)造成的问题,一种是使用 Slasher 协议,惩罚同时在多条链上投票的节点,第二种方法时直接惩罚在错误的链上创建块的节点,总而言之就是通过算法之外的事情解决这个问题,引入激励和惩罚。

与工作量证明相比,权益证明不需要消耗大量的电力就能够保证区块链网络的安全性,同时也不需要在每个区块中创建新的货币来激励矿工参与当前网络的运行,这也就在一定程度上缩短了达成共识所需要的时间,基于权益证明的 Ethereum 每秒大概能处理 30 笔交易左右。

在 PoW 机制中,由于想要找到符合条件的 nonce. nonce 往往需要花费大量的电力和时间成本,因此,为了使每个 Block 更快被生成,PoS 机制去掉了穷举 noncenonce 这一过程,继而采用以下更快速的算法:

SHA256(SHA256(Bprev),A,t)balance(A)mSHA256(SHA256(Bprev),A,t)≤balance(A)m

H 某个哈希函数
t 为 UTC 时间戳
Bprev 指的是上一个区块
balance(A) 代表账户A 的账户的余额
唯一可以不断调整的参数是 t,等式右边 m 是某个固定的实数,因此,当balance(A)越大,找到合理 t 的概率越大。网络中,普遍对于 t 的范围有所限制,如可以尝试的时间戳不能超过标准时间戳 1 小时,也就说,一个节点可以尝试 7200 次,来找到一个符合条件的t,如果找不到即可放弃。因此,在 PoS 中,一个账户的余额越多,在同等算力下,就越容易发现下一个区块.

3.3 Ripple

 

3.4 DPOS(Delegated Proof-of-Stake)

前面介绍的权益证明算法可以将整个区块链网络理解为一家公司,出资最多、占比最大的人有更多的机会得到话语权(记账权);对于小股东来说,千分之几甚至万分之几的股份很难有什么作为,只能得到股份带来的分红和收益。

但是在这里介绍的委托权益证明(DPOS,Delegated Proof-of-Stake)能够让每一个人选出可以代表自己利益的人参与到记账权的争夺中,这样多个小股东就能够通过投票选出自己的代理人,保障自己的利益。整个网络中选举出的多个节点能够在 1s 中之内对 99.9% 的交易进行确认,使用委托权益证明的 EOS 能够每秒处理几十万笔交易,同时也能够比较监管的干预。

 

3.5 PBFT (Practical Byzantine Fault Tolerance)

BFT是一种状态机副本复制算法,即服务作为状态机进行建模,状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态,同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示,使用0到|R|-1的整数表示每一个副本。为了描述方便,假设|R|=3f+1,这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本,但是额外的副本除了降低性能之外不能提高可靠性。

基于拜占庭将军问题,一致性的确保主要分为这三个阶段:预准备(pre-prepare)、准备(prepare)和确认(commit)。流程如下图所示:

其中C为发送请求端,0123为服务端,3为宕机的服务端,具体步骤如下:
1. Request:请求端C发送请求到任意一节点,这里是0
2. Pre-Prepare:服务端0收到C的请求后进行广播,扩散至123
3. Prepare:123,收到后记录并再次广播,1->023,2->013,3因为宕机无法广播
4. Commit:0123节点在Prepare阶段,若收到超过一定数量的相同请求,则进入Commit阶段,广播Commit请求
5.Reply:0123节点在Commit阶段,若收到超过一定数量的相同请求,则对C进行反馈
根据上述流程,在 N ≥ 3F + 1 的情況下一致性是可能解決,N为总计算机数,F为有问题的计算机总数
N=4 F=0 时:
得到数据 最终数据
A 1 1 1 1 1
B 1 1 1 1 1
C 1 1 1 1 1
D 1 1 1 1 1
N=4 F=1 时:
得到数据 最终数据
A 1 1 1 0 1
B 1 1 0 1 1
C 1 0 1 1 1
D 0 1 1 1 1
N=4 F=2 时:
得到数据 最终数据
A 1 1 0 0 NA
B 1 0 0 1 NA
C 0 0 1 1 NA
D 0 1 1 0 NA
由此可以看出,拜占庭容错能够容纳将近1/3的错误节点误差,IBM创建的Hyperledger就是使用了该算法作为共识算法。

3.6 GEAR

 

Reference