分布式系统一致性与共识的原理1一致性问题一致性问题是分布式领域最为基础也是最重要的问题。

如果分布式系统能实现“一致”，对外就可以呈现为一个完美的、可扩展的“虚拟节点”，相对物理节点具备更优越性能和稳定性。

这也是分布式系统希望能实现的最终目标。

1.1定义与重要性定义一致性（c o n s i s t e n c y），早期也叫a g r ee m e n t，是指对于分布式系统中的多个服务节点，给定一系列操作，在约定协议的保障下，试图使得它们对处理结果达成“某种程度”的认同。

理想情况下，如果各个服务节点严格遵循相同的处理协议，构成相同的处理状态机，给定相同的初始状态和输入序列，则可以保障在处理过程中的每个环节的结果都是相同的。

那么，为什么说一致性问题十分重要呢？举个现实生活中的例子，多个售票处同时出售某线路上的火车票，该线路上存在多个经停站，怎么才能保证在任意区间都不会出现超售（同一个座位卖给两个人）的情况呢？这个问题看起来似乎没那么难，现实生活中经常通过分段分站售票的机制。

然而，为了支持海量的用户和避免出现错误，存在很多设计和实现上的挑战。

特别在计算机的世界里，为了达到远超普通世界的高性能和高可扩展性需求，问题会变得更为复杂。

注意一致性并不代表结果正确与否，而是系统对外呈现的状态一致与否；例如，所有节点都达成失败状态也是一种一致。

1.2问题与挑战看似强大的计算机系统，实际上很多地方都比人类世界要脆弱得多。

特别是在分布式计算机集群系统中，如下几个方面很容易出现问题：·节点之间的网络通信是不可靠的，包括消息延迟、乱序和内容错误等；·节点的处理时间无法保障，结果可能出现错误，甚至节点自身可能发生宕机；·同步调用可以简化设计，但会严重降低分布式系统的可扩展性，甚至使其退化为单点系统。

仍以火车票售卖问题为例，愿意动脑筋的读者可能已经想到了一些不错的解决思路，例如：·要出售任意一张票前，先打电话给其他售票处，确认下当前这张票不冲突。

即通过同步调用来避免冲突；·多个售票处提前约好隔离的售票时间。

比如第一家可以在上午8点到9点期间卖票，接下来一个小时是另外一家……即通过令牌机制来避免冲突；·成立一个第三方的存票机构，票集中存放，每次卖票前找存票机构查询。

此时问题退化为中心化单点系统。

当然，还会有更多方案。

实际上，这些方案背后的思想，都是将可能引发不一致的并行操作进行串行化。

这实际上也是现代分布式系统处理一致性问题的基础思路。

只是因为现在的计算机系统应对故障往往不够“智能”，而人们又希望系统可以更快更稳定地工作，所以实际可行的方案需要更加全面和更加高效。

注意这些思路都没有考虑请求和答复消息出现失败的情况，同时假设每个售票处的售票机制是正常工作的。

1.3一致性要求规范地说，分布式系统达成一致的过程，应该满足：·可终止性（t e r m i n a t i o n）：一致的结果在有限时间内能完成；·约同性（a g r ee m e n t）：不同节点最终完成决策的结果是相同的；·合法性（v a li d i t y）：决策的结果必须是某个节点提出的提案。

可终止性很容易理解。

有限时间内完成，意味着可以保障提供服务（li v e n e ss）。

这是计算机系统可以被正常使用的前提。

需要注意，在现实生活中这点并不是总能得到保障的。

例如取款机有时候会出现“服务中断”；拨打电话有时候是“无法连接”的。

约同性看似容易，实际上暗含了一些潜在信息。

决策的结果相同，意味着算法要么不给出结果，任何给出的结果必定是达成了共识的，即安全性（safety）。

挑战在于算法必须要考虑的是可能会处理任意的情形。

凡事一旦推广到任意情形，往往就不像看起来那么简单。

例如现在就剩一张某区间（如北京-->南京）的车票了，两个售票处也分别刚通过某种方式确认过这张票的存在。

这时，两家售票处几乎同时分别来了一个乘客要买这张票，从各自“观察”看来，自己一方的乘客都是先到的……这种情况下，怎么能达成对结果的共识呢？看起来很容易，卖给物理时间上率先提交请求的乘客即可。

然而，对于两个来自不同位置的请求来说，要判断在时间上的“先后”关系并不是那么容易。

两个车站的时钟可能是不一致的；可能无法记录下足够精确的时间；更何况根据相对论的观点，并不存在绝对的时空观。

可见，事件发生的先后顺序十分重要，这也是解决分布式系统领域很多问题的核心秘诀：把多件事情进行排序，而且这个顺序还得是大家都认可的。

最后一个合法性看似绕口，但是其实比较容易理解，即达成的结果必须是节点执行操作的结果。

仍以卖票为例，如果两个售票处分别决策某张票出售给张三和李四，那么最终达成一致的结果要么是张三，要么是李四，而绝对不能是其他人。

1.4带约束的一致性从前面的分析可以看到，要实现绝对理想的严格一致性（strictc o n s i s t e n c y）代价很大。

除非系统不发生任何故障，而且所有节点之间的通信无需任何时间，这个时候整个系统其实就等价于一台机器了。

实际上，越强的一致性要求往往会造成越弱的处理性能，以及越差的可扩展性。

一般来讲，强一致性（s t r o n g c o n s i s t e n c y）主要包括下面两类：·顺序一致性（s e q u e n t i a l c o n s i s t e n c y）：L e s li e L a m po r t在1979年的经典论文《H o w t o M a k e a M u l t i p r o c e ss o r C o m p u t e r T h a t C o rr e c t l y E x e c u t e s M u l t i p r o c e ss P r og r a m s》中提出，是一种比较强的约束，保证所有进程看到的全局执行顺序（t o t a l o r d e r）一致，并且每个进程看自身的执行顺序（l o c a l o r d e r）跟实际发生顺序一致。

例如，某进程先执行A，后执行B，则实际得到的全局结果中就应该为A在B前面，而不能反过来。

同时所有其他进程在全局上也应该看到这个顺序。

顺序一致性实际上限制了各进程内指令的偏序关系，但不在进程间按照物理时间进行全局排序；·线性一致性（li n e a r i z a b ili t y c o n s i s t e n c y）：M a u r i c e P.H e r li h y与J e a nn e tt e M.W i n g在1990年的经典论文《L i n e a r i z a b ili t y：A C o rr e c t n e ss C o n d i t i o n f o r C o n c u rr e n t O b j e c t s》中共同提出，在顺序一致性前提下加强了进程间的操作排序，形成唯一的全局顺序（系统等价于是顺序执行，所有进程看到的所有操作的序列顺序都一致，并且跟实际发生顺序一致），是很强的原子性保证。

但是比较难实现，目前基本上要么依赖于全局的时钟或锁，要么通过一些复杂算法实现，性能往往不高。

实现强一致性往往需要准确的计时设备。

高精度的石英钟的漂移率为10-7，最准确的原子震荡时钟的漂移率为10-13。

G oog l e曾在其分布式数据库S p a nn e r中采用基于原子时钟和G P S的“T r u eT i m e”方案，能够将不同数据中心的时间偏差控制在10ms以内。

方案简单粗暴而且有效，但存在成本较高的问题。

由于强一致性的系统往往比较难实现，而且很多时候，实际需求并没有那么严格需要强一致性。

因此，可以适当地放宽对一致性的要求，从而降低系统实现的难度。

例如在一定约束下实现所谓最终一致性（e v e n t u a l c o n s i s t e n c y），即总会存在一个时刻（而不是立刻），让系统达到一致的状态。

大部分Web系统实现的都是最终一致性。

相对强一致性，这一类在某些方面弱化的一致性都笼统称为弱一致性（w e a k c o n s i s t e n c y）。

2共识算法共识（c o n s e n s u s）在很多时候会与一致性（c o n s i s t e n c y）术语放在一起讨论。

严谨地讲，两者的含义并不完全相同。

一致性往往指分布式系统中多个副本对外呈现的数据的状态。

如前面提到的顺序一致性、线性一致性，描述了多个节点对数据状态的维护能力。

而共识则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。

因此，一致性描述的是结果状态，共识则是一种手段。

达成某种共识并不意味着就保障了一致性。

实践中，要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。

共识算法解决的是对某个提案（p r opo s a l）大家达成一致意见的过程。

提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导……等等。

可以认为任何可以达成一致的信息都是一个提案。

对于分布式系统来讲，各个节点通常都是相同的确定性状态机模型（又称为状态机复制问题，state- m a c h i n e r e p li c a t i o n），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。

因此，系统中多个节点最关键的是对多个事件的顺序进行共识，即排序。

2.1问题与挑战实际上，如果分布式系统中各个单节点都能保证以十分“理想”的性能（瞬间响应、超高吞吐）无故障地运行，节点之间通信瞬时送达，则实现共识过程并不十分复杂，简单地通过广播进行瞬时投票和应答即可。

可惜的是，现实中这样的“理想”系统并不存在。

不同节点之间通信存在延迟（光速物理限制，通信处理延迟），并且任意环节都可能存在故障（系统规模越大，发生故障可能性越高）。

如通信网络会发生中断、节点会发生故障、甚至存在恶意节点故意要伪造消息，破坏系统的正常工作流程。

一般地，把出现故障（c r a s h或f a il-s t op，即不响应）但不会伪造信息的情况称为“非拜占庭错误”（non-byzantine fault）或“故障错误”（CrashF a u l t）；伪造信息恶意响应的情况称为“拜占庭错误”（B y z a n t i n eF a u l t），对应节点为拜占庭节点。

2.2常见算法根据解决的是非拜占庭的普通错误情况还是拜占庭错误情况，共识算法可以分为Crash Fault Tolerance（CFT）类算法和Byzantine Fault Tolerance （BFT）类算法。