一致性问题

一致性问题是分布式领域最基础也是最重要的问题,也是数十年来的研究热点。

今天的业务场景越来越复杂,规模越来越大。在面向大规模复杂任务场景时,单点的服务往往难以解决可扩展(Scalability)和容错(Fault-tolerance)两方面的需求,就需要多台服务器来组成集群系统,虚拟为更加强大和稳定的“超级服务器”。

集群的规模越大,处理能力越强,管理的复杂度也就越高。目前在运行的大规模集群包括谷歌公司的搜索系统,通过数十万台服务器支持了对整个互联网内容的搜索服务。

通常情况下,集群系统中的不同节点可能处于不同的状态,随时收到不同的请求,要时刻保持对外响应的“一致性”,好比训练一群鸭子齐步走,难度可想而知。

定义与重要性

定义 一致性(Consistency),早期也叫(Agreement),在分布式系统领域中是指对于多个服务节点,给定一系列操作,在约定协议的保障下,使得它们对处理结果达成“某种程度”的协同。

理想情况(不考虑节点故障)下,如果各个服务节点严格遵循相同的处理协议(即构成相同的状态机逻辑),则在给定相同的初始状态和输入序列时,可以确保处理过程中的每个步骤的执行结果都相同。因此,传统分布式系统中讨论一致性,往往是指在外部任意发起请求(如向多个节点发送不同请求)的情况下,确保系统内大部分节点实际处理请求序列的一致,即对请求进行全局排序。

那么,为什么说一致性问题十分重要呢?

举个现实生活中的例子,多个售票处同时出售某线路上的火车票,该线路上存在多个经停站,怎么才能保证在任意区间都不会出现超售(同一个座位卖给两个人)的情况?

这个问题看起来似乎没那么难,现实生活中经常通过分段分站售票的机制。然而,要支持海量的用户进行并行购票,并非易事(参考 12306 的案例)。特别是计算机系统往往需要达到远超物理世界的高性能和高可扩展性需求,挑战会变得更大。这也是为何每年到了促销季,各大电商平台都要提前完善系统。

注:一致性关注的是系统呈现的状态,并不关注结果是否正确;例如,所有节点都对某请求达成否定状态也是一种一致性。

问题挑战

计算机固然很快,但在很多地方都比人类世界脆弱的多。典型的,在分布式系统中,存在不少挑战:

  • 节点之间只能通过消息来交互和同步,而网络通讯是不可靠的,可能出现任意消息延迟、乱序和错误;
  • 节点处理请求的时间无法保障,处理的结果可能是错误的,甚至节点自身随时可能发生故障;
  • 为了避免冲突,采用同步调用可以简化设计,但会严重降低系统的可扩展性,甚至使其退化为单点系统。

仍以火车票售卖问题为例,愿意动脑筋的读者可能已经想到了一些不错的解决思路,例如:

  • 要出售任意一张票前,先打电话给其他售票处,确认下当前这张票不冲突。即退化为同步调用来避免冲突;
  • 多个售票处提前约好隔离的售票时间。比如第一家可以在上午 8 点到 9 点期间卖票,接下来一个小时是另外一家……即通过令牌机制来避免冲突;
  • 成立一个第三方的存票机构,票集中存放,每次卖票前找存票机构查询。此时问题退化为中心化中介机制。

当然,还会有更多方案。

实际上,这些方案背后的思想,都是将可能引发不一致的并行操作进行串行化。这实际上也是现代分布式系统处理一致性问题的基础思路。另外,由于通常计算机硬件和软件的可靠性不足,在工程实现上还要对核心环节加强容错性。

注:这些思路假设每个售票处的售票机制都能保证正常工作;也没有考虑请求和答复消息出现失败的情况。

一致性的要求

规范来看,分布式系统达成一致的过程,应该满足:

  • 可终止性(Termination):一致的结果在有限时间内能完成;
  • 约同性(Agreement):不同节点最终完成决策的结果是相同的;
  • 合法性(Validity):决策的结果必须是某个节点提出的提案。

可终止性很容易理解。有限时间内完成,意味着可以保障提供服务(Liveness)。这是计算机系统可以被正常使用的前提。需要注意,在现实生活中这点并不是总能得到保障的。例如取款机有时候会出现“服务中断”;拨打电话有时候是“无法连接”的。

约同性看似容易,实际上暗含了一些潜在信息。决策的结果相同,意味着算法要么不给出结果,任何给出的结果必定是达成了共识的,即安全性(Safety)。挑战在于算法必须要考虑的是可能会处理任意的情形。凡事一旦推广到任意情形,往往就不像看起来那么简单。例如现在就剩一张某区间(如北京 --> 南京)的车票了,两个售票处也分别刚通过某种方式确认过这张票的存在。这时,两家售票处几乎同时分别来了一个乘客要买这张票,从各自“观察”看来,自己一方的乘客都是先到的……这种情况下,怎么能达成对结果的共识呢?看起来很容易,卖给物理时间上率先提交请求的乘客即可。然而,对于两个来自不同位置的请求来说,要判断在时间上的“先后”关系并不是那么容易。两个车站的时钟时刻可能是不一致的;时钟计时可能不精确的……根据相对论的观点,不同空间位置的时间是不一致的。因此追求绝对时间戳的方案是不可行的,能做的是要对事件的发生进行排序。

事件发生的先后顺序十分重要,确定了顺序,就没有了分歧。这也是解决分布式系统领域很多问题的核心秘诀:把不同时空发生的多个事件进行全局唯一排序,而且这个顺序还得是大家都认可的

注:Leslie Lamport 在 1978 年发表的论文《Time, Clocks and the Ordering of Events in a Distributed System》中首次将分布式系统中顺序与相对论进行对比,提出了偏序关系的观点。

最后的合法性看似绕口,但其实比较容易理解,即达成的结果必须是节点执行操作的结果。仍以卖票为例,如果两个售票处分别决策某张票出售给张三和李四,那么最终达成一致的结果要么是张三,要么是李四,而不能是其他人。

带约束的一致性

从前面的分析可以看到,要实现绝对理想的严格一致性(Strict Consistency)代价很大。除非系统不发生任何故障,而且所有节点之间的通信无需任何时间,此时整个系统其实就等价于一台机器了。实际上,越强的一致性要求往往意味着带来越弱的处理性能,以及越差的可扩展性。根据实际需求的不用,人们可能选择不同强度的一致性,包括强一致性(Strong Consistency)和弱一致性(Weak Consistency)。

一般地,强一致性主要包括下面两类:

  • 顺序一致性(Sequential Consistency):Leslie Lamport 1979 年经典论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出,是一种比较强的约束,保证所有进程看到的全局执行顺序(total order)一致,并且每个进程看自身的执行顺序(local order)跟实际发生顺序一致。例如,某进程先执行 A,后执行 B,则实际得到的全局结果中就应该为 A 在 B 前面,而不能反过来。同时所有其它进程在全局上也应该看到这个顺序。顺序一致性实际上限制了各进程内指令的偏序关系,但不在进程间按照物理时间进行全局排序。
  • 线性一致性(Linearizability Consistency):Maurice P. Herlihy 与 Jeannette M. Wing 在 1990 年经典论文《Linearizability: A Correctness Condition for Concurrent Objects》中共同提出,在顺序一致性前提下加强了进程间的操作排序,形成唯一的全局顺序(系统等价于是顺序执行,所有进程看到的所有操作的序列顺序都一致,并且跟实际发生顺序一致),是很强的原子性保证。但是比较难实现,目前基本上要么依赖于全局的时钟或锁,要么通过一些复杂算法实现,性能往往不高。

实现强一致性往往需要准确的计时设备。高精度的石英钟的漂移率为 ,最准确的原子震荡时钟的漂移率为 。Google 曾在其分布式数据库 Spanner 中采用基于原子时钟和 GPS 的“TrueTime”方案,能够将不同数据中心的时间偏差控制在 10ms 以内。在不考虑成本的前提下,这种方案简单、粗暴,但是有效。

强一致的系统往往比较难实现,而且很多场景下对一致性的需求并没有那么强。因此,可以适当放宽对一致性的要求,降低系统实现的难度。例如在一定约束下实现所谓最终一致性(Eventual Consistency),即总会存在一个时刻(而不是立刻),让系统达到一致的状态。例如电商购物时将某物品放入购物车,但是可能在最终付款时才提示物品已经售罄了。实际上,大部分的 Web 系统为了保持服务的稳定,实现的都是最终一致性。

相对强一致性,类似最终一致性这样在某些方面弱化的一致性,被笼统称为弱一致性。

results matching ""

    No results matching ""