7cf8375c4687e06ed2e65d4cdb69b59b
分布式一致性与共识算法

区块链技术是近几年逐渐变得非常热门的技术,以比特币为首的密码货币其实已经被无数人所知晓,但是却很少有人会去研究它们的底层技术,也就是作为一个分布式网络比特币等加密货币是如何工作的。


无论是 Bitcoin、Ethereum 还是 EOS,作为一个分布式网络,首先需要解决分布式一致性的问题,也就是所有的节点如何对同一个提案或者值达成共识,这一问题在一个所有节点都是可以被信任的分布式集群中都是一个比较难以解决的问题,更不用说在复杂的区块链网络中了。

分布式一致性

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

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

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

CAP

在 1998 年的秋天,加州伯克利大学的教授 Eric Brewer 第一次发布了 CAP 理论,在 1999 年论文 [《Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services》] (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.6951&rep=rep1&type=pdf)正式发布,其中总结了 Eric Brewer 提出的 CAP 理论。

这篇论文证明了两个非常有意思的理论,首先是在异步的网络模型中,所有的节点由于没有时钟仅仅能根据接收到的消息作出判断,这时完全不能同时保证一致性、可用性和分区容错性,每一个系统只能在这三种特性中选择两种。

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

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

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

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

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

拜占庭将军问题

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

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

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

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

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

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

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

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

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 了解更多的内容。

共识算法

在上一节中,我们已经简单了解了分布式系统中面对的问题与挑战,在这里我们会介绍不同共识算法的实现原理,包括传统分布式系统领域的 Paxos、Raft 以及密码货币中使用的工作量证明(POW)、权益证明(POS)和委托权益证明(DPOS),通过对这些共识算法原理的介绍和分析,我相信各位读者能对分布式一致性和共识算法有更深的理解。

Paxos 和 Raft

Paxos 和 Raft 是目前分布式系统领域中两种非常著名的解决一致性问题的共识算法,两者都能解决分布式系统中的一致性问题,但是前者的实现与证明非常难以理解,后者的实现比较简洁并且遵循人的直觉,它的出现就是为了解决 Paxos 难以理解并和难以实现的问题。

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

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

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 会根据其持有的信息 minProposal、acceptedProposal 和 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) 视频。


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

top Created with Sketch.