分布式系统的一致性与共识（一）

本文作者为原本区块链算法工程师cblk

原文链接：https://zhuanlan.zhihu.com/p/68743917

分布式系统中有两个重要的研究问题：一致性（consistency）和共识（consensus）。许多人常常把它们混为一谈，本文试图解释两者的定义和区别

分布式系统利用多个节点的硬件资源，完成了本可以在单点系统上实现的任务。从用户的角度看，分布式系统就好像一个单独的计算机一样，只不过拥有更好的性能和稳定性，同时又易于扩展。为了达到这一目的，同样的一份数据会以副本（Replication）的形式保存在多个节点上。在分布式系统中，我们常说的一致性问题就是：对于同一个数据的多个副本之间，如何保持其对外表现的数据一致性。举例来说明：

数据X有两个副本，分别保存在节点M和节点N上；客户端A修改了节点N上的数据X；一段时间后，客户端B读取在M节点上的数据X；一致性问题就是要研究客户端B怎样能读取到客户端A做的修改，然后两者之间的数据可以达成一致。

而共识则不同。分布式共识问题，简单说，就是在一个或多个进程提议了一个值应当是什么后，采用一种大家都认可的方法，使得系统中所有进程对这个值达成一致意见。

这样的协商过程在分布式系统中很常用，比如说选主（Leader election）问题中所有进程对Leader达成一致；互斥（Mutual exclusion）问题中对于哪个进程进入临界区达成一致；原子组播（Atomic broadcast）中进程对消息传递（delivery）顺序达成一致。对于这些问题有一些特定的算法，但是，分布式共识问题试图探讨这些问题的一个更一般的形式，如果能够解决分布式共识问题，则以上的问题都可以得以解决。[1]

一致性有强弱之分，可大致分为严格一致性、强一致性、弱一致性等，其对外表现为分布式系统最终以何种形式到达一致性。共识问题则没有强弱之分，因为共识最终目标是所有节点都要达成一致，只要能够达成一致，就是共识。

 | 一致性的分类

分布式系统中的一致性按照对一致性要求的不同，主要分为，严格一致性，强一致性（线性一致性），顺序一致性，弱一致性（最终一致性）这几类。

严格一致性

假如有人说他设计了一个满足严格一致性的分布式系统，那么这个系统的外部表现就应该完全等价于一台计算机。这意味着，对于这个系统中任意数据项x的任何读操作将返回最近一次对x进行的写操作的结果所对应的值。对于所有的进程来说，所有写操作都是瞬间可见的，系统维持着一个绝对的全局时间顺序。如果一个数据项被改变了，那么无论数据项改变之后多久执行 读操作，无论哪些进程执行读操作，无论这些进程的位置如何，所有在该数 据项上执行的后续读操作都将得到新数值。

事实上，严格一致性要求系统不发生任何故障，而且所有节点之间的通信无需任何时间这种理想的条件下，才能达到。因此现实世界中，这样的分布式系统是不存在的。

顺序一致性

在讲强一致性之前，首先要讲一下顺序一致性，它虽然不满足强一致性，但是又优于弱一致性，是一种过渡状态。

Leslie Lamport 在1979年提出了顺序一致性，对系统提出了两条访问共享对象时的约束：

1. 从单个处理器（线程或者进程）的角度上看，其指令的执行顺序以编程中的顺序为准；

2.从所有处理器（线程或者进程）的角度上看，指令的执行保持一个单一的顺序；约束 1 保证了单个进程的所有指令是按照程序中的顺序来执行；而约束 2 保证了所有的内存操作都是原子的或者说实时地。顺序一致性的关键在于找到一个满足现实情况的全局执行顺序，使其同时又能符合每个单独进程内部的操作顺序。

我们用一个例子来更加清楚地展示顺序一致性的概念。下图中横轴表示程序中的顺序（注意不再是时间序），观察如下的两种执行结果是否满足顺序一致性要求：

通过简单分析就可以发现，这两种情况我们都可以找到一个满足上述两个约 束的执行顺序，即：P1 x.write(2) -> P1 x.write(3) -> P2 x.write(5) -> P1 x.read(5)，这表明其执行结果满足顺序一致性。

我们再来看一个不满足顺序一致性的例子：

不管你怎么安排这四个进程的读写操作，要使其既满足各自的编程顺序，又得到相应的执行结果是不可能的。

强一致性

当一个数据副本的更新操作完成之后，任何多个后续节点对这个数据的任意副本的访问都会返回最新的更新过的值。这种一致性对系统可用性的影响较大，因为这意味着，只要上次的操作没有处理完，就不能让用户读取数据。

Maurice P. Herlihy 与 Jeannette M. Wing在 1990 年共同提出了线性一致性，是一种强一致性，在顺序一致性前提下加强了进程间的操作排序，形成唯一的全局顺序（ 系统等价于是顺序执行，所有进程看到的所有操作的序列顺序都一致）。线性一致性假设操作具有一个全局有效时钟的时间戳，但是这个时钟仅具有有限的精确度，要求时间戳在前的进程先执行。线性化是根据一系列同步时钟确定序列顺序的，但是很难实现，基本上要么依赖于全局 的时钟或锁（ 原子钟是个简单粗暴但有效的主意），要么性能比较差。

弱一致性

弱一致性是指系统并不保证后续进程或线程的访问都会返回最新的更新的值。系统在数据成功吸入之后，不承诺立即可以读到最新写入的值，也不会具体承诺多久读到。但是会尽可能保证在某个时间级别（秒级）之后。可以让数据达到一致性状态。也就是说，如果能容忍后续的部分或者全部访问不到，则是弱一致性。

最终一致性是弱一致性的一种特例。某个 进程更新了副本的数据，如果没有其他进程更新这个副本的数据，系统最终一定能够保证后续进程能够读取到A进程写进的最新值。但是这个操作存在一个不一致性的窗口，也就是A进程写入数据，到其他进程读取 A 写进去的值所用的时间。在最终一致性 的要求下，如果没有故障发生，不一致窗口的时间主要受通信延迟，系统负 载和复制副本的个数影响。

达到最终一致状态的系统，被称为收敛系统（converged systen），或者是达到副本收敛（replica convergence）。最终一致性提供了一个弱保证：在系统达到收敛之前，可能会返回任意值。

| 共识

分布式共识问题的定义如下图所示：

为了达到共识，每个进程都提出自己的提议（propose），最终通过共识算法，所有正确运行的进程决定（decide）相同的值。

共识算法的正确性要求是在运行中满足以下条件：

协定性（Agreement）：所有正确进程决定相同的值。

终止性（Termination）：所有正确进程最后都能完成决定。

完备性（Integrity）：如果正确的进程都提议同一个值，那么所有正确进程最终决定该值。

在一些文献中，完备性又被称作合法性（validity），本质上是一个意思。但是完备性有多种不同形式的表达，对应了不同的共识算法。上述定义的共识算法有个隐藏的前提：所有进程都有自己的初始值。

如果只有一个进程拥有初始值，这个进程被称为源进程，那么这就是一个拜占庭共识问题。此时的完备性表述就是：如果源进程是“不作恶”（non-faulty）的，那么所有不作恶节点的决定值应该和源进程的初始值相同。

可以证明这些共识算法的不同表达实际上是等价的。

对于分布式系统来讲，各个节点通常都是确定性的状态机模型（又称为状态机复制问题，state-machine replication），只要保证从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。因此，系统中多个节点最关键的是对多个事件的顺序进行共识，即排序。

根据解决的是非拜占庭的普通共识问题还是拜占庭共识问题（是否允许系统内节点作恶，以及对完备性的不同要求），共识算法可以分为Crash Fault Tolerance（CFT）类算法和Byzantine Fault Tolerance（BFT）类算法。

针对常见的非拜占庭错误的情况，已经存在一些经典的解决算法，包括Paxos、Raft及其变种等。这类容错算法往往性能比较好，处理较快，容忍不超过一半的故障节点。

对于要能容忍拜占庭错误的情况，一般包括PBFT（Practical Byzantine Fault Tolerance）为代表的确定性系列算法、PoW为代表的概率算法等。对于确定性算法，一旦达成对某个结果的共识就不可逆转，即共识是最终结果；而对于概率类算法，共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，成为事实上的最终结果。拜占庭类容错算法往往性能较差，容忍不超过1/3的故障节点。[2]

| 总结

一致性往往指分布式系统中多个副本对外呈现的数据的状态。如前面提到的顺序一致性、线性一致性，描述了多个节点对数据状态的维护能力。

共识则描述了分布式系统中多个节点之间，彼此对某个提案达成一致结果的过程。因此，一致性描述的是结果，共识则是一种手段。

有的人会说一致性和共识实际上是一个问题的一体两面，某种程度上来说，共识方法确实可以看作是实现强一致性的一种方法。事实上在工业界有许多以共识算法作为核心组件的多副本状态机(Replicated State Machine)实现，本质上利用了共识算法保证了所有副本的操作日志具有完全相同的顺序，从而实现了副本的一致性。但是，即使是在这样的场景下，讨论一个共识算法的一致性也是不合适的，因为整个分布式系统最终的一致性并不单单取决于共识算法，共识算法只是解决了其中一个问题。

“ 本文经「原本」原创认证，作者cblk，访问http://yuanben.io查询【LVX98C91】获取授权信息。

| 参考

1.^http://blog.kongfy.com/2016/08/%E8%A2%AB%E8%AF%AF%E7%94%A8%E7%9A%84%E4%B8%80%E8%87%B4%E6%80%A7/

2. ^https://www.iminho.me/wiki/docs/blockchain_guide/distribute_system-consensus.md