当前位置: 首页 > >

《数据密集型应用系统设计》读书笔记??第二部分 分布式数据系统(二)

发布时间:

第8章 分布式系统的挑战
故障与部分失效

当你在?台计算机上编写一个程序时,它通常会以一种确定的方式运?:?论是?作还是不工作。充满错误的软件可能会让人觉得电脑有时候是“糟糕的一天”(这个问题通常是重新启动的问题), 但这主要是软件写得?好的结果。
单个计算机上的软件没有根本性的不可靠原因:当硬件正常?作时,相同的操作总是产?相同的结果 (这是确定性的)。如果存在硬件问题(?如,内存损坏或连接器松动),其后果通常是整个系统故障 (?如,内核崩溃,“蓝屏死机”,启动失败)。装有良好软件的个人计算机通常要么功能完好,要么完全失效,??是介于两者之间。
这是计算机设计中的?个慎重的选择:如果发?内部错误,我们宁愿电脑完全崩溃,??是返回错误的结果,因为错误的结果很难处?。因为计算机隐藏?模糊不?清的物理实现,并呈现出?个理想化的系统模型,并以数学一样的完美的方式运作。 CPU指令总是做同样的事情;如果将一些数据写?内存或磁盘,那么这些数据将保持不变,并且不会被随机破坏。
当你编写运?在多台计算机上的软件时,情况有本质上的区别。在分布式系统中,我们不再处于理想化的系统模型中,我们别无选择,只能面对现实世界的混乱现实。而在现实世界中,各种各样的事情都可能会出现问题。
在分布式系统中,尽管系统的其他部分工作正常,但系统的某些部分可能会以某种不可预知的?式被破坏。这被称为部分失效。难点在于部分失效是不确定性的 :如果你试图做任何涉及多个节点和?络的事情,它有时可能会?作,有时会出现不可预知的失败。正如我们将要看到的,你甚??知道是否成功了,因为消息通过?网络传播的时间也是?确定的。
这种?确定性和部分失效的可能性,使得分布式系统难以?作。


云计算与超算

关于如何构建?型计算系统有?系?的哲学:


规模的?端是?性能计算(HPC)领域。具有数千个CPU的超级计算机通常用于计算密集型科学计算任务,如天?预报或分子动?学。另?个极端是云计算,云计算并不是?个良好定义的概念,但通常有一下特点:多租户数据中心,通用计算机,用IP以太网链接,弹性/按需资源分配,并按需收费。传统企业数据中?位于这两个极端之间。
?同的哲学会导致不同的故障处理方式。在超级计算机中,作业通常会不时地会将计算的状态存盘到持久存储中。如果一个节点出现故障,通常的解决?案是简单地停?整个集群的工作负载。故障节点修复后,计算从上一个检查点重新开始。因此,超级计算机?像是?个单节点计算机??是分布式系统:通过让部分失败升级为完全失败来处理部分失败??如果系统的任何部分发?故障,只是让所有的东?西都崩溃(就像单台机器上的内核崩溃一样)。
我们将重点放在实现互联?服务的系统上,这些系统通常与超级计算机看起来有很??同:许多与互联?有关的应?程序都是24小时在线的,因为它们需要能够随时以低延迟服务?户。使服务不可用是不可接受的。相比之下,像天?模拟这样的离线工作可以停止并重新启动,影响相当小。超级计算机通常由专用硬件构建?成,每个节点相当可靠,节点通过共享内存和远程直接内存访问 进?通信。另??面,云服务中的节点是由商品机?构建而成的,由于规模经济,可以较低的成本提供相同的性能,?且具有较?的故障率。大型数据中?网络通常基于IP和以太网,以闭合*伺?,以提供更高的二等分带宽。超级计算机通常使用专?的?络?扑结构,这为具有已知通信模式的HPC?工作负载提供了?好的性能。
系统越大,其组件之一就越有可能发生变化。随着时间的推移,破碎的东西得到修复,新的东西被破坏,但是在一个有成千上万个节点的系统中,有理由认为总是有?些东西被破坏。当错误处理策?由简单的放弃组成时,?个大的系统最终会花费??时间从错误中恢复,??是做有用的工作。如果系统可以容忍发生故障的节点,并继续保持整体?作状态,那么这对于操作和维护非常有用::?如,可以执?滚动升级,一次重新启动一个节点,而服务继续服务?户?中断。 在云环境中,如果?台虚拟机运??佳,可以杀死它并请求?台新的虚拟机。在地理位置分散的部署中(保持数据在地理位置上接*?户以减少访问延迟),通信很可能通过互联?进?,与本地?络相比,通信速度缓慢且不可靠。超级计算机通常假设它们的所有节点都靠*在一起。

如果要使分布式系统工作,就必须接受部分故障的可能性,并在软件中建?容错机制。换句话说,我们需要从?可靠的组件构建一个可靠的系统。
即使在只有少数节点的小型系统中,考虑部分故障也是很重要的。在一个小系统中,很可能大部分组件在?部分时间都正常工作。然?,迟早会有?部分系统出现故障,软件必须以某种方式处?。故障处?必须是软件设计的?部分,并且作为软件的运维,需要知道在发生故障的情况下,软件可能会表现出怎样的?为。
简单地假设缺陷很罕见,只是希望始终保持最好的状况是?明智的。考虑?系列可能的错误(甚?是?太可能的错误),并在测试环境中?为地创建这些情况来查看会发??么是?常重要的。在分布式系统中,怀疑,悲观和偏执狂才能生存。


不可靠的网络

我们关注的分布式系统是无共享的系统,即通过?络连接的一堆机?。?络是这些机?可以通信的唯?途径??我们假设每台机器都有?己的内存和磁盘, 一台机器?能访问另?台机?的内存或磁盘(除了通过?络向服务器发出请求)。
?共享并?是构建系统的唯一方式,但它已经成为构建互联?服务的主要方式,其原因如下:相对便宜,因为它不需要特殊的硬件,可以利用商品化的云计算服务,通过跨多个地理分布的数据中心进?冗余,可以实现高可靠性。
互联网和数据中心(通常是以太?)中的?多数内部网络都是异步分组?络。在这种?络中,一个节点可以向另?个节点发送?个消息,但是网络不能保证它什么时候到达,或者是否到达。如果发送请求并期待响应,则很多事情可能会出错:


    请求可能已经丢失(可能有?拔掉了网线)。请求可能正在排队,稍后将交付(也许?络或收件人超载)。远程节点可能已经失效(可能是崩溃或关机)。远程节点可能暂时停??响应(可能会遇到?时间的垃圾回收暂停),但稍后会
    再次响应。远程节点可能已经处??请求,但是?络上的响应已经丢失(可能是网络交换机配置错误)。远程节点可能已经处??请求,但是响应已经被延迟,并且稍后将被传递(可能是?络或者你?己的机?过载)。

发送者甚??能分辨数据包是否被发送:唯一的选择是让接收者发送响应消息,这可能会丢失或延迟。
这些问题在异步?络中难以区分:所拥有的唯?信息是,尚未收到响应。如果向另?个节点发送请求并且没有收到响应,则?法说明原因。
处?这个问题的通常?法是超时:在?段时间之后放弃等待,并且认为响应不会到达。但是,当发生超时,仍然?知道远程节点是否收到?请求(如果请求仍然在某个地方排队,那么即使发件人已经放弃?该请求,仍然可能会将其发送给收件?人)。


检测故障

许多系统需要自动检测故障节点。例如:


负*胶馄餍枰V瓜蛞阉劳龅慕诘阕⑶肭笤诘ブ鞲粗乒δ艿姆植际绞菘庵校绻骺馐В蛐枰涌庵簧段轮骺狻

?幸的是,?络的不确定性使得很难判断?个节点是否工作。在某些特定的情况下,你可能会收到一些反馈信息,明确告诉您某些事情没有成功:


如果你可以登录运?节点的机?,但没有进程正在侦听?标端口(?如,因为进程崩溃),操作系统将通过发送FIN或RST来关闭并重?TCP连接。但是,如果节点在处理请求时发生崩溃,则?法知道远程节点实际处理?多少数据。如果节点进程崩溃(或被管理员杀死),但节点的操作系统仍在运?,则脚本可以通知其他节点有关该崩溃的信息,以?另?个节点可以快速接管,?无需等待超时到期。如果你有权访问数据中?网络交换机的管理界面,则可以查询它们以检测硬件级别的链路故障(?如,远程机器是否关闭电源)。如果你通过互联?连接,或者如果你处于共享数据中心?无法访问交换机,或者由于网络问题?无法访问管理界?,则排除此选项。如果路由?确认你尝试连接的IP地址不可用,则可能会使用ICMP目标?可达数据包回复你。但是,路由器?具备神奇的故障检测能???它受到与?络其他参与者相同的限制。
关于远程节点关闭的快速反馈很有用,但不是万能的。即使TCP确认已经传送了一个数据包,应?程序在处理之前可能已经崩溃。如果你想确保?个请求是成功的,就需要应用级别的回复。
相反,如果出了?么问题,你可能会在堆栈的某个层次上得到?个错误响应,但总的来说,你必须假设你根本就没有得到任何回应。你可以重试?次(TCP重试是透明的,但是你也可以在应?程序级别重试),等待超时过期,并且如果在超时时间内没有收到响应,则最终声明节点已经死亡。
超时与无限期的延迟

如果超时是检测故障的唯?可靠?方法,那么超时应该等待多久??幸的是没有简单的答案。
?时间的超时意味着?时间等待,直到?个节点被宣告死亡(在这段时间内,?户可能?得?等待,或者看到错误信息)。短暂的超时可以更快地检测到故障,但是实际上它只是经历了暂时的性能波动(?如,由于节点或?络上的负载峰值)而导致错误地宣布节点失效的?险更高。
过早地声明?个节点已经死了是有问题的:如果这个节点实际上是活着的,并且正在执?一些动作(?如,发送?封电子邮件),?另一个节点接管,那么这个动作可能会最终执?两次。
当?个节点被宣告死亡时,它的职责需要转移到其他节点,这会给其他节点和?络带来额外的负担。如果系统已经处于?负荷状态,则过早宣告节点死亡会使问题更严重。尤其是可能发生,节点实际上并没有死亡,?是由于过载导致响应缓慢;将其负载转移到其他节点可能会导致级联失效,在极端情况下,所有节点都宣告对?死亡,并且所有节点都停?工作。
我们所使用的大多数系统都没有确定时间的保证:异步网络具有?限的延迟(即尽可能快地传送数据包,但数据包到达可能需要的时间没有上限),并且?多数服务?实现并不能保证它们可以在一定的最?时间内处理请求。对于故障检测,系统部分时间快速运?是?够的: 如果你的超时时间很短,往返时间只需要一个瞬时尖峰就可以使系统失衡。


网络拥塞与排队

在驾驶汽车时,由于交通拥堵,道路交通网络的通?时间往往?尽相同。同样,计算机?络上数据包延迟的可变性通常是由于排队:


如果多个不同的节点同时尝试将数据包发送到同?目的地,则网络交换机必须将它们排队并将它们逐个送?目标?络链路。在繁忙的?络链?上,数据包可能需要等待?段时间才能获得一个插槽(这称为?络连接)。如果传入的数据太多,交换机队列填满,数据包将被丢弃, 因此需要重新发送数据包??即使?络运?良好。当数据包到达?标机器时,如果所有CPU内核当前都处于繁忙状态,则来自?络的传?请求将被操作系统排队,直到应?程序准备好处理它为止。根据机?上的负载,这可能需要?段任意的时间。在虚拟化环境中,CPU核会切换虚拟机,正在运?的操作系统会暂停?十毫秒。在这段时间内,虚拟机?能从?络中接收任何数据,所以传入的数据被虚拟机管理器排队缓冲,进一步增加了网络延迟的可变性。TCP执?流量控制,其中节点限制?己的发送速率以避免?络链路或接收节点过载。这意味着甚至在数据至进入网络之前,在发送者处就需要进?额外的排队。

如果TCP在某个超时时间内没有被确认(这是根据观察的往返时间计算的),则认为数据包丢失,丢失的数据包将自动重新发送。尽管应?程序没有看到数据包丢失和重新传输,但它看到?延迟(等待超时到期,然后等待重新传输的数据包得到确认)。
更好的一种做法是,系统?是使?配置的常量超时,而是连续测?响应时间及其变化,并根据观察到的响应时间分布自动调整超时。


不可靠的时钟

在分布式系统中,时间是一件棘手的事情,因为通信?是即时的:消息通过?络从?台机?传送到另一台机?需要时间。收到消息的时间总是晚于发送的时间,但是由于?络中的可变延迟,精确测量面临很多挑战。这个事实有时很难确定在涉及多台机器时发生事情的顺序。
?且,网络上的每台机?都有?己的时钟,这是一个实际的硬件设备:通常是石英晶体振荡?。这些设备?是完全准确的,所以每台机器都有?己的时间概念,可能比其他机?稍快或?慢。可以在一定程度上同步时钟:最常?的机制是网络时间协议(NTP),它允许根据一组服务器报告的时间来调整计算机时钟。服务器则从更?确的时间源(如GPS接收机)获取时间。


单调时钟与墙上时钟

现代计算机?少有两种?同的时钟:墙上时钟和单调时钟。尽管它们都衡?时间,但区分这两者很重要,因为它们有不同的?目的。


墙上时钟

墙上时钟是你直观地?解时钟的依据:它根据某个日历返回当前日期和时间。?如,Linux上的clock_gettime(CLOCK_REALTIME) 和Java中的
System.currentTimeMillis() 返回?epoch(1970年?1月1日 午夜 UTC,格???历)以来的秒数(或毫秒),根据公历?历,不包括闰秒。有些系统使用其他日期作为参考点。
时钟通常与NTP同步,这意味着来?一台机器的时间戳(?想情况下)与另一台机?上的时间戳相同。但是时钟也具有各种各样的奇特之处。特别是,如果本地时钟在NTP服务器之前太远,则它可能会被强制重置,看上去好像跳回了先前的时间点。这些跳跃以及他们经常忽略闰秒的事实,使时钟不能?于测量时间间隔。
时钟还具有相当粗?的精度,例如,在较早的Windows系统上以10毫秒为单位前进。在最*的系统中这已经不是一个问题?。


单调时钟

单调时钟适?于测量持续时间(时间间隔),例如超时或服务的响应时间:Linux上的clock_gettime(CLOCK_MONOTONIC),和Java中的 System.nanoTime() 都是单调时钟。这个名字来源于他们保证总是前进的事实(而时钟可以及时跳回)。
你可以在某个时间点检查单调时钟的值,做一些事情,且稍后再次检查它。这两个值之间的差异告诉你两次检查之间经过了多长时间。但单调时钟的绝对值是毫无意义的:它可能是计算机启动以来的纳秒数,或类似的任意值。特别是?较来?两台不同计算机的单调钟的值是没有意义的,因为它们并不是一回事。
如果NTP协议检测到计算机的本地石英钟?NTP服务器要更快或?慢,则可以调整单调钟向前走的频率 。默认情况下,NTP允许时钟速率增加或减慢最高至0.05%,但NTP?能使单调时钟向前或向后跳转。单调时钟的精度通常相当好:在?多数系统中,它们能在?微秒或?短的时间内测量时间间隔。
在分布式系统中,使?单调时钟测?经过时间通常很好,因为它?假定?同节点的时钟之间存在任何同步,并且对测量的轻微?准确性不?感。


依赖同步的时钟

时钟的问题在于,虽然它们看起来简单易用,但却具有令?惊讶的缺陷:一天可能不会有精确的86400秒,时钟可能会前后跳跃,?一个节点上的时间可能与另一个节点上的时间完全不同。
前面我们讨论?网络丢包和任意延迟包的问题。尽管网络在大多数情况下表现良好,但软件的设计必须假定?络偶尔会出现故障,?软件必须正常处理这些故障。时钟也是如此:尽管大多数时间都工作得很好,但需要准备健壮的软件来处??正确的时钟。


时间戳与事件顺序

让我们考虑一个特别的情况,?件很有诱惑但也很危险的事情:依赖时钟,在多个节点上对事件进?行排序。 ?如,如果两个客户端写?分布式数据库,谁先到达? 哪一个更*?
尽管通过保?“最*”的值并放弃其他值来解决冲突是很诱惑人的,但是要注意,“最*”的定义取决于本地的时钟,这很可能是?正确的。即使用频繁同步的NTP时钟,?个数据包也可能在时间戳100毫秒(根据发送者的时钟)时发送,并在时间戳99毫秒(根据接收者的时钟)处到达??看起来好像数据包在发送之前已经到达,这是不可能的。
NTP同步是否能?够准确,以?于这种不正确的排序?会发生?也许?能,因为NTP的同步精度本身受到网络往返时间的限制,除了石英钟漂移这类误差源之外。为?进?正确的排序,你需要?个?测量对象(即?络延迟)要精确得多的时钟。
所谓的逻辑时钟是基于递增计数器而不是振荡?英晶体,对于排序事件来说是?安全的选择。逻辑时钟不测?一天中的时间或经过的秒数,而仅测量事件的相对顺序。相反,用来测量实际经过时间的时钟和单调时钟也被称为物?时钟。


时间的置信区间

你可能够以微秒或甚?纳秒的精度读取机?的时钟。但即使可以得到如此细致的测量结果,这并不意味着这个值对于这样的精度实际上是准确的。实际上,如前所述,即使你每分钟与本地网络上的NTP服务?进?同步,很可能也?会像前面提到的那样,在不精确的石英时钟上漂移几毫秒。使?公共互联网上的NTP服务?,最好的准确度可能达到?十毫秒,而且当网络拥塞时,误差可能会超过100毫秒 。
因此,将时钟读数视为一个时间点是没有意义的??它更像是一段时间范围:?如,?个系统可能以 95%的置信度认为当前时间处于本分钟内的第10.3秒和10.5秒之间,它可能没法?这更精确了。
不确定性界限可以根据你的时间源来计算。如果你的GPS接收?或原子(铯)时钟直接连接到您的计算 机上,预期的错误范围由制造商报告。如果从服务?获得时间,则不确定性取决于自上次与服务?同步以来的?英钟漂移的期望值,加上NTP服务器的?确定性,再加上到服务器的网络往返时间。


进程暂停

在分布式系统中危险使用时钟的另一个例子:假设你有一个数据库,每个分区只有一个领导者。只有领导被允许接受写?。一个节点如何知道它仍然是领导者,并
且它可以安全地接受写??
一种选择是领导者从其他节点获得?个租约,类似?个带超时的锁。任?时刻只有?个节点可以持有租约??因此,当?个节点获得?个租约时,它知道它在某段时间内?己是领导者,直到租约到期。为了保持领导地位,节点必须周期性地在租约过期前续期。
如果节点发生故障,就会停?续期,所以当租约过期时,另一个节点可以接管。
分布式系统中的节点,必须假定其执?可能在任意时刻暂停相当长的时间,即使是在?个函数的中间。
在暂停期间,世界的其它部分在继续运转,甚至可能因为该节点没有响应,而宣告暂停节点的死亡。最终暂停的节点可能会继续运?,在再次检查?己的时钟之前,甚?可能?会意识到?己进??休眠。


知识,真相与谎言
真相由多数决定

设想?个具有?对称故障的?络:一个节点能够接收发送给它的所有消息,但是来?该节点的任何传出消息被丢弃或延迟。即使该节点运?良好,并且正在接收来?自其他节点的请求,其他节点也无法听到其响应。经过?段时间后,其他节点宣布它已经死亡,因为他们没有听到节点的消息。
另一种情况,想象一个经历了长时间STW垃圾收集暂停(stop-the-world GC Pause)的节点。节点的所有线程被GC抢占并暂停一分钟,因此没有请求被处理?,也没有响应被发送。其他节点等待,重试,?耐烦,并最终宣布节点死亡。最后,GC完成,节点的线程继续,好像?么也没有发?生。其他节点感到惊讶,因为所谓的死亡节点突然从棺材中抬起头来,身体健康,开始和旁观者高兴地聊天。GC后的节点最初甚至没有意识到已经过了整一分钟,?且?已被宣告死亡。 从它?己的?度来看,从最后一次与其他节点交谈以来,?乎没有经过任何时间。
节点不一定能相信?己对于情况的判断。分布式系统?能完全依赖单个节点,因为 节点可能随时失效,可能会使系统卡死,?法恢复。相反,许多分布式算法都依赖于法定人数,即在节点之间进?投票:决策需要来?多个节点的最小投票数,以减少对于某个特定节点的依赖。这也包括关于宣告节点死亡的决定。如果法定数?的节点宣告另?个节点已经死亡,那么即使该节点仍感觉?己活着,它也必须被认为是死的。个体节点必须遵守法定决定并下线。


主节点与锁

通常情况下,?些东西在一个系统中只能有一个。?如:


数据库分区的领导者只能有一个节点,以避免脑裂。特定资源的锁或对象只允许?个事务/客户端持有,以防同时写入和损坏。一个特定的?户名只能被?个?户所注册,因为?户名必须唯一标识一个用户。

在分布式系统中实现这?点需要注意:即使?个节点认为它是“唯一的那个”,但这并不一定意味着有法定?数的节点同意!一个节点可能以前是领导者,但是如果其他节点在此期间宣布它死亡,则它可能已被降级,且另一个领导者可能已经当选。
如果一个节点继续表现为“唯一的那个”,即使大多数节点已经声明它已经死?,则在考虑?周的系统中可能会导致问题。这样的节点能以?己赋予的权能向其他节点发送消息,如果其他节点相信,整个系统可能会做一些?正确的事情。
这个问题就是我们先前讨论过的?个例子:如果持有租约的客户端暂停太久,它的租约将到期。另?个客户端可以获得同??件的租约,并开始写?文件。当暂停的客户端回来时,它认为它仍然有一个有效的租约,并继续写?文件。结果,导致客户的文件写入被破坏。


Fencing令牌

当使?锁或租约来保护对某些资源的访问时,需要确保?个被误认为?己是“唯一的那个”的节点不能影响系统的其它正常部分。实现这一目标的?个相当简单的技术就是使用防护 (fencing)令牌。
我们假设每次锁定服务?授予锁或租约时,它还会返回一个防护令牌,这个数字在 每次授予锁定时都会增加。然后,我们可以要求客户端每次向存储服务发送写?请求时,都必须包含当前的防护令牌。
如果将ZooKeeper?作锁定服务,则可将事务标识 zxid 或节点版本 cversion ?作防护令牌。由于它们保证单调递增,因此它们具有所需的属性。
请注意,这种机制要求资源本身在检查令牌?面发挥积极作用,如果发现已处理过更新的令牌,拒绝使用旧的令牌??仅仅依靠客户端检查?己的锁状态是?够的。对于不明确支持防护令牌的资源,可能仍然可以解决此问题(?如,在文件存储服务的情况下,可以将防护令牌包含在文件名 中)。总之,为?避免在锁的保护之外?请求,需要进?某种检查。
在服务?端检查一个令牌可能看起来像是一个缺点,但这可以说是?件好事:一个服务假定它的客户总是守规矩并不明智,因为使用客户端的人与运?服务的?优先级?常?一样。因此,任何服务保护?己免受意外客户的滥?是一个好主意。


拜占庭故障

常见的分布式系统中并不存在拜占庭故障(节点伪造消息),略~


第9章 一致性与共识
一致性保证

?多数复制的数据库至少提供了最终一致性,这意味着如果你停?向数据库写入数据并等待?段?确定的时间,那么最终所有的读取请求都会返回相同的值。换句话说,不一致性是暂时的,最终会??解决(假设?络中的任何故障最终都会被修复)。最终一致性的?个更好的名字可能是收敛,因为我们预计所有的副本最终会收敛到相同的值。
然?,这是?个非常弱的保证??它并没有说什么时候副本会收敛。在收敛之前,读操作可能会返回任何东?或什么都没有。
在与只提供弱保证的数据库打交道时,你需要始终意识到它的局限性,??是意外地作出太多假设。错误往往是微妙的,很难找到,也很难测试,因为应?可能在?多数情况下运?良好。当系统出现故障或高并发时,最终一致性的边缘情况才会显现出来。
本章将探索数据系统可能选择提供的?强?致性模型。它不是免费的:具有较强保证的系统可能会比保证较差的系统具有?差的性能或更少的容错性。尽管如此,更强的保证可以更吸引人,因为它们更容易用对。


可线性化

在最终?致的数据库,同时查询两个不同的副本可能会得到两个不同的答案。这会使应用层感到困惑。如果数据库可以提供只有一个副本的假象(即,只有一个数据副本),那么事情就简单太多?。
这就是可线性化(也称原子一致性,强一致性等)背后的思想。基本的想法是让?个系统看起来好像只有一个数据副本,而且所有的操作都是原子性的。有了这个保证,即使实际中可能有多个副本,应用也不需要担?它们。
在?个线性一致的系统中,只要一个客户端成功完成写操作,所有客户端从数据库中读取数据必须能够看到刚写入的值。维护数据单个副本的错觉是指,系统能保障读到的值是最*的,最新的,??是来?陈旧的缓存或副本。换?话说,可线性化是一种就*的保证。


线性化的依赖条件

线性?致性在?么情况下有用?观看体育比赛的最后得分可能是一个轻率的例?子:过了几秒钟的结果?可能在这种情况下造成任何真正的伤害。然而对于少数领域,线性?致性是系统正确?作的?个重要条件。


加锁与主节点选举

主从复制的系统,需要确保主节点只有一个,否则会产生脑裂。?种选择主节点的?法是使用锁:每个节点在启动时尝试获取锁,成功者成为主节点。不管这个锁是如何实现的,它必须是线性一致的:所有节点必须就哪个节点拥有锁达成一致,否则就没??。


约束与唯一性保证

唯?性约束在数据库中很常?:例如,用户名或电子邮件地址必须唯一标识一个?户,?在?件存储服务中,不能有两个具有相同路径和文件名的文件。如果要在写?数据时强制执?此约束,则需要线性一致性。
这种情况实际上类似于一个锁:当?个用户注册你的服务时,可以认为他们获得了?所选用户名的“锁定”。该操作与原子性的?较与设置非常相似:将?户名赋予声明它的用户,前提是用户名尚未被使用。


跨通道的时间依赖

考虑一个例子,假设有一个网站,用户可以上传照片,一个后台进程会调整照?大?,降低分辨率以加快下载速度。该系统的架构和数据流如下图所示。

图像缩放?需要明确的指令来执?尺寸缩放作业,指令是Web服务器通过消息队列?发送的。 Web服务??会将整个照?放在队?中,因为?多数消息代?都是针对较短的消息?设计的,?一张照?的空间占?可能达到?兆字节。取?代之的是,?先将照?写?文件存储服务,写?完成后再将缩放器的指令放?消息队列。
如果?件存储服务是线性一致的,那么这个系统应该可以正常工作。如果它?是线性一致的,则存在竞争条件的风险:消息队列可能?存储服务内部的复制?快。在这种情况下,当缩放器读取图像时,可能会看到图像的旧版本,或者?么都没有。如果它处理的是旧版本的图像,则文件存储中的全尺寸图和略缩图就产??永久性的不一致。
出现这个问题是因为Web服务器和缩放器之间存在两个不同的信道:文件存储与消息队列。没有线性化的就*性保证,这两个信道之间的竞争条件是可能的。


实现线性化系统
线性化的代价

考虑这样?种情况:如果两个数据中?之间发?网络中断会发??么?我们假设每个数据中心内的网络正在?作,客户端可以访问数据中心,但数据中?之间彼此?法互相连接。
使?多主数据库,每个数据中?都可以继续正常运?:由于在?个数据中?写入的数据是异步复制到另一个数据中心的,所以在恢复网络连接前,写入操作暂存在本地队列。
另?方面,如果使?单主复制,则主库必须位于其中?个数据中?。任何写入和任何线性一致的读取请求都必须发送给该主库,因此对于连接到从库所在数据中心的客户端,这些读取和写?请求必须通过网络同步发送到主库所在的数据中心。
在单主配置的条件下,如果数据中心之间的?络被中断,则连接到从库数据中心的客户端?法联系到主库,因此它们无法对数据库执?任何写入,也不能执?任何线性一致的读取。它们仍能从库读取,但结果可能是陈旧的。如果应用需要线性一致的读写,却?位于与主库网络中断的数据中心,则网络中断将导致这些应用不可用。
如果客户端可以直接连接到主库所在的数据中心,这就?是问题?,那些应用可以继续正常工作。但直到?络链接修复之前,只能访问从库数据中心的客户端会中断运?。


CAP理论

这个问题不仅仅存在于单主复制和多主复制系统中:任何线性一致的数据库都有这个问题,不管它是如何实现的。这个问题也不仅仅局限于多数据中?部署,而可能发?在任何?可靠的网络上,即使在同一个数据中?内也是如此。问题面临的权衡如下:


如果应?需要线性一致性,且某些副本因为?络问题与其他副本断开连接,那么这些副本掉线时不能处?请求。请求必须等到网络问题解决,或直接返回错误。(无论哪种?式,服务都不可?)。如果应??需要线性一致性,那么某个副本即使与其他副本断开连接,也可以处?请求。在这种情况下,应?可以在?络问题恢复前保持可用,但其?为?是线性?致的。

因此?需要线性?致性的应?对网络问题有更强的容错能?。这种?解通常被称为CAP定理。
CAP最初是作为?个经验法则提出的,没有准确的定义,目的是讨论数据库的权衡。那时候许多分布式数据库侧重于在共享存储的集群上提供线性一致性的语义,CAP定理鼓励数据库?程师向分布式?无共享系统的设计领域深?探索,这类架构?适合实现大规模的?络服务。 对于这种?化上的转变,CAP值得赞扬??它?证?自2000年以来新数据库的技术爆炸(即NoSQL)。



CAP理论是否有用
CAP有时以这种?目出现:?致性,可用性和分区可用性,三者只能择其二。不?幸的是这种说法很有误导性,因为?络分区是?种错误,所以它并?是一个选项:?管你喜不喜欢它都会发?。
在网络正常工作的时候,系统可以提供?致性和整体可用性。发?网络故障时, 你必须在线性?致性和整体可?性之间做出选择。因此,一个?好的表达CAP的?方法可以是“在网络分区的情况下,选择一致还是可用”。一个?可靠的网络需要减少这个选择,但是在某些时候选择是不可避免的。
总?言之,围绕着CAP有很多误解和困惑,并不能帮助我们?好地?解系统,所以最好避免使?CAP。



CAP定?的正式定义仅限于很狭隘的范围,它只考虑了一个一致性模型(即线性?一致性)和?种故障(网络分区,或活跃但彼此断开的节点)。它没有讨论任何关于?络延迟,死亡节点或其他权衡的事。 因此,尽管CAP在历史上有一些影响??,但对于设计系统?言并没有实际价值。 在分布式系统中有更多有趣的“?可能”的结果,且CAP定?现在已经被更精确的结果取代,所以它现在基本上成?历史古迹了。


可线性化与网络延迟

虽然可线性化是?个很有?的保证,但实际上,线性一致的系统惊?的少。例如,现代多核CPU上的内存甚至都?是线性?致的:如果一个CPU核上运?的线程写入某个内存地址,而另?个CPU核上运?的线程不久之后读取相同的地址,并不能保证一定能读到第一个线程写?的值(除非使??内存屏障或fence指令)。
这种?为的原因是每个CPU核都有?己的内存缓存和存储缓冲区。默认情况下,内存访问?先?缓存,任何变更会异步写入主存。因为缓存访问比主存要快得多,所以这个特性对于现代CPU的良好性能表现至关重要。但是现在就有?个数据副本(一个在主存中,也许还有几个在?同缓存中的其他副本),而且这些副本是异步更新的,所以就失去?线性一致性。
为什要做这个权衡?对多核内存?致性模型?言,CAP定?是没有意义的:在同?台计算机中,我们通常假定通信都是可靠的。并且我们并不指望一个CPU核能在脱离计算机其他部分的条件下继续正常?作。牺牲线性一致性的原因是性能,而?是容错。
许多分布式数据库也是如此:它们是为了提高性能?选择?牺牲线性?致性,而不是为?容错。 线性一致的速度很慢??这始终是事实,??仅是?络故障期间。
能找到一个更高效的线性?致存储实现吗?看起来答案是否定的:Attiya和Welch 证明,如果你想要线性?致性,读写请求的响应时间?少与网络延迟的?确定性成正比。在像大多数计算机?络一样具有高度可变延迟的网络中,线性读写的响应时间?可避免地会很高。更快地线性一致算法不存在,但更弱的?致性模型可以快得多,所以对延迟敏感的系统?言,这类权衡?常重要。


顺序保证

之前说过,线性一致寄存器的?为就好像只有单个数据副本一样,且每个操作似乎都是在某个时间点以原子性的?式生效的。这个定义意味着操作是按照某种良好定义的顺序执?的。
事实证明,顺序,线性一致性和共识之间有着深刻的联系。


顺序与因果关系

顺序反复出现有几个原因,其中一个原因是,它有助于保持因果关系。
因果关系对事件施加了一种顺序:因在果之前;消息发送在消息收取之前。而且就像现实生活中一样, 一件事会导致另?件事:某个节点读取了一些数据然后写?入一些结果,另一个节点读取其写入的内容, 并依次写入一些其他内容,等等。这些因果依赖的操作链定义?系统中的因果顺序,即,什么在?么之前发生。
如果一个系统服从因果关系所规定的顺序,我们说它是因果?致的。?如,快照隔离提供?因果?致性:当你从数据库中读取到?些数据时,你?定还能够看到其因果前驱(假设在此期间这些数据还没有被删除)。


因果顺序并非全序

全序允许任意两个元素进?比较,所以如果有两个元素,你总是可以说出哪个?大, 哪个更小。?如,?然数集是全序的:给定两个自然数,比如说5和13,那么你可以告诉我,13大于 5。
然而数学集合并不完全是全序的: {a, b} 比 {b, c} ??吗?好吧,你没法真正?较它们,因为二者都不是对方的子集。我们说它们是无法?较的,因此数学集合是偏序的:在某些情况下,可以说一个集合?于另一个(如果?个集*硪桓黾系乃性兀谄渌榭鱿滤鞘俏薹ū冉系摹 全序和偏序之间的差异反映在?同的数据库一致性模型中:


线性?致性
在线性一致的系统中,操作是全序的:如果系统表现的就好像只有一个数据副本,并且所有操作都是原子性的,这意味着对任何两个操作,我们总是能判定哪个操作先发生。因果性
我们说过,如果两个操作都没有在彼此之前发生,那么这两个操作是并发的。换句话说,如果两个事件是因果相关的(一个发?在另?个事件之前),则它们之间是有序的,但如果它们是并发的,则它们之间的顺序是?法比较的。这意味着因果关系定义了一个偏序,??是一个全序:一些操作相互之间是有顺序的,但有些则是无法?较的。

因此,根据这个定义,在线性一致的数据存储中是不存在并发操作的:必须有且仅有?条时间线,所有的操作都在这条时间线上,构成一个全序关系。可能有几个请求在等待处?,但是数据存储确保?每个请求都是在唯一时间线上的某个时间点?动处?的,?存在任何并发。


可线性化强于因果一致性

那么因果顺序和线性?致性之间的关系是什么?答案是线性一致性一定意味着因果关系:任何线性一致的系统都能正确保持因果性。特别是,如果系统中有多个通信通道(比如消息队?和?件存储服务),线性?致性可以?动保证因果性,系统?无需任何特殊操作(如在?同组件间传递时间戳)。
线性?致性确保因果性的事实使线性?致系统变得简单?懂,?有吸引?。然?,使系统线性?致可能会损害其性能和可用性,尤其是在系统具有严重的网络延迟的情况下。出于这个原因,?些分布式数据系统已经放弃了线性一致性,从而获得更?好的性能,但它们用起来也更为困难。
好消息是存在折衷的可能性。线性?致性并不是保持因果性的唯一途径??还有其他方法。?个系统可以是因果一致的,?无需承担线性?致带来的性能折损。实际上在所有的不会被网络延迟拖慢的一致性模型中,因果一致性是可?的最强的一致性模型。而且在网络故障时仍能保持可?。
在许多情况下,看上去需要线性一致性的系统,实际上需要的只是因果一致性,因果?致性可以更高效地实现。


序列号排序

虽然因果是一个重要的理论概念,但实际上跟踪所有的因果关系是不切实际的。在许多应用中,客户端在写入内容之前会先读取??数据,我们无法弄清写入因果依赖于先前全部的读取内容,还是仅包括其中一部分。显式跟踪所有已读数据意味着巨大的额外开销。
但还有一个?好的方法:我们可以使用序?号或时间戳来排序事件。时间戳不一定来?墙上时钟。它可以来?一个逻辑时钟,这是一个?来?成标识操作的数字序列的算法,典型实现是使用一个每次操作自增的计数?。
这样的序列号或时间戳是紧凑的(只有几个字节?小),它提供了一个全序关系:也就是说每次操作都有一个唯?的序?号,而且总是可以?较两个序?号,确定哪一个更大(即哪些操作后发生)。
特别是,我们可以使?与因果一致的全序来生成序?号:我们保证,如果操作A因果后继于操作B,那么在这个全序中A在B前(A具有比B?小的序列号)。并?操作之间可以任意排序。这样一个全序关系捕获?所有关于因果的信息,但也施加??个比因果性要求?为严格的顺序。
在单主复制的数据库中,复制?志定义?与因果?致的写操作。主库可以简单地为每个操作?增一个计数器,从而为复制日志中的每个操作分配一个单调递增的序列号。如果一个从库按照它们在复制日志中出现的顺序来应?写操作,那么从库的状态始终是因果?致的(即使它落后于领导者)。


非因果序列发生器

如果主库不存在(可能因为使??多主数据库或无主数据库,或者因为使??分区的数据库),如何为操作生成序列号就没有那么明显了?。在实践中有各种各样的?法:


每个节点都可以?成?己独立的?组序?号。例如有两个节点,?个节点只能?成奇数,而另一个节点只能?成偶数。通常,可以在序?号的二进制表示中预?一些位,用于唯一的节点标识符,这样可以确保两个不同的节点永远?会生成相同的序列号。可以将墙上时钟时间戳附加到每个操作上。这种时间戳并?连续,但是如果它具 有?够?的分辨率,那也许足以提供一个操作的全序关系。这一事实应?于最后写?为准的冲突解决方法中。可以预先分配序?号区块。?如,节点A可能要求从序?号1到1000区块的所有权,?节点B可能要求序列号1001到2000区块的所有权。然后每个节点可以独立分配所属区块中的序?号,并在序列号告急时请求分配一个新的区块。

这三个选项都?单一主库的自增计数?表现要好,并且?具可扩展性。它们为每个操作?成一个唯一的,*似?增的序?号。
然而它们都有同?个问题:生成的序列号与因果?一致。
因为这些序?号?成器?能正确地捕获跨节点的操作顺序,所以会出现因果关系的问题:


每个节点每秒可以处理?同数量的操作。因此,如果一个节点产?偶数序?号?另一个产?奇数序列号,则偶数计数器可能落后于奇数计数?,反之亦然。如果你有?一奇数编号的操作和?个偶数编号的操作,你?法准确地说出哪?个操作在因果上先发生。来?物?时钟的时间戳会受到时钟偏移的影响,这可能会使其与因果不一致。因果上晚发?的操作,却被分配?一个更早的时间戳。在分配区块的情况下,某个操作可能会被赋予一个范围在1001到2000内的序?号,然?一个因果上更晚的操作可能被赋予一个范围在1到1000之间的数字。这?序列号与因果关系也是不一致的。
Lamport时间戳

尽管刚才描述的三个序?号生成器与因果不一致,但实际上有?个简单的?法来产?与因果关系一致的序?号。它被称为兰伯特时间戳。
下图说明了兰伯特时间戳的应用。每个节点都有?个唯一标识符,和一个保存自己执?操作数量的计数?。 兰伯特时间戳就是两者的简单组合:(计数器,节点ID)。两个节点有时可能具有相同的计数器值,但通过在时间戳中包含节点ID,每个时间戳都是唯一的。

兰伯特时间戳与物理时间时钟没有任何关系,但是它提供了一个全序:如果你有两个时间戳,则计数器值大者是更大的时间戳。如果计数?值相同,则节点ID越大的,时间戳越大。
迄今,这个描述与上节所述的奇偶计数?基本类似。使兰伯特时间戳因果?致的关键思想如下所示:每个节点和每个客户端跟踪迄今为止所见到的最?计数?值,并在每个请求中包含这个最?计数?值。当一个节点收到最大计数器值大于自身计数?值的请求或响应时,它立即将?己的计数器设置为这个最?值。
只要每一个操作都携带着最?计数?值,这个方案确保兰伯特时间戳的排序与因果一致,而请求的因果依赖性一定会保证后发生的请求得到更大的时间戳。


时间戳排序依然不够

虽然兰伯特时间戳定义了一个与因果一致的全序,但它还不足以解决分布式系统中的许多常?问题。
例如,考虑一个需要确保?户名能唯一标识用户帐户的系统。如果两个?户同时尝试使?相同的?户名创建帐户,则其中?个应该成功,另一个应该失败。
乍看之下,似乎操作的全序关系?以解决这?问题(?如使?用兰伯特时间戳):如果创建了两个具有相同?户名的帐户,选择时间戳较小的那个作为胜者,并让带有更大时间戳者失败。由于时间戳上有全序关系,所以这个?较总是可?的。
这种?法适?于事后确定胜利者:一旦你收集了系统中的所有用户名创建操作,就可以?较它们的时间戳。然而当某个节点需要实时处理用户创建?户名的请求时,这样的方法就?法满??。节点需要?上决定这个请求是成功还是失败。在那个时刻,节点并不知道是否存其他节点正在并发执?创建同样用户名的操作。
为?确保没有其他节点正在使?相同的?户名和较小的时间戳并发创建同名账户,你必须检查其它每个节点,看看它在做?么。如果其中一个节点由于网络问题出现故障或不可达,则整个系统可能被拖至停机。这?是我们需要的那种容错系统。
这?的问题是,只有在所有的操作都被收集之后,操作的全序才会出现。如果另?个节点已经产??一些操作,但你还?知道那些操作是?么,那就?法构造所有操作最终的全序关系:来自另一个节点的未知操作可能需要被插?到全序中的?同位置。
总之:为?实诸如?户名上的唯一约束这种东西,仅有操作的全序是不够的,你还需要知道这些操作是否发生、合适确定。如果你有?个创建用户名的操作,并且确定在全序中,没有其他节点正在执行相同用户名的创建,那么你就可以安全地宣告操作执?成功。
想知道什么时候全序关系已经确定就需要“全序关系广播”了。


全序关系广播

全序?播通常被描述为在节点间交换消息的协议。 非正式地讲,它要满足两个安全属性:


可靠交付,没有消息丢失
如果消息被传递到?个节点,它将被传递到所有节点。全序交付,消息以相同的顺序传递给每个节点。

正确的全序广播算法必须始终保证可靠性和有序性,即使节点或?络出现故障。当然在?络中断的时候,消息是传不出去的,但是算法可以不断重试,以便在网络最终修复时,消息能及时通过并送达(当然它们必须仍然按照正确的顺序传递)。


采用全序关系广播实现线性化存储

在线性?致的系统中,存在操作的全序。这是否意味着线性一致与全序?播一样?不尽然,但两者之间有者密切的联系。
全序广播是异步的:消息被保证以固定的顺序可靠地传送,但是?能保证消息何时被送达(所以一个接收者可能落后于其他接收者)。相比之下,线性?致性是就*性的保证:读取一定能看?最新的写?值。
但如果有?全序广播,你就可以在此基础上构建线性一致的存储。例如,你可以确保?户名能唯一标识用户帐户。
设想对于每?个可能的?户名,你都可以有?个带有CAS原子操作的线性一致寄存?。每个寄存器最初的值为空值。当?户想要创建一个用户名时,对该?户名的寄存?执?CAS操作,在先前寄存?值为空的条件,将其值设置为?户的账号ID。如果多个?户试图同时获取相同的?户名,则只有?个CAS操作会成功,因为其他?用户会看到非空的值(由于线性一致性)。
你可以通过将全序广播当成追加日志的?式来实现这种线性一致的CAS操作:


    在日志中追加一条消息,试探性地指明你要创建的用户名。读日志,将其广播给所有节点,并等待回复。检查是否有任何消息声称目标?户名的所有权。如果这些消息中的第一条就你?己的消息,那么你就成功了:你可以提交声称的?户名。如果所需?户名的第一条消息来?其他用户,则中止操作。

由于?志项是以相同顺序送达?所有节点,因此如果有多个并发写入,则所有节点会对最先到达者达成一致。选择冲突写?中的第一个作为胜?者,并中止后来者,以此确定所有节点对某个写入是提交还是中?达成一致。
尽管这?过程保证写入是线性一致的,但它并?保证读取也是线性一致的??如果你从与?志异步更新的存储中读取数据,结果可能是陈旧的。为?使读取也线性?致,有几个选项:


可以采用追加的方式把读请求排序、广播,然后各个节点获取该日志,当本节点收到消息时才执行真正的读操作。消息在日志中的位置已经决定了读取发生时间点。etcd的quorum读取和这个思路有相似之处。如果?志允许以线性?致的?式获取最新?志消息的位置,则可以查询该位置,等待直到该位置前的所有消息都传达到你,然后执?行读取。 这是Zookeeper sync() 操作背后的思想。你可以从同步?新的副本中进?读取,因此可以确保结果是最新的。
采用线性化存储实现全序关系广播

上一节介绍?如何从全序广播构建一个线性一致的CAS操作。我们也可以把它反过来,假设我们有线性一致的存储,接下来会展示如何在此基础上构建全序广播。
最简单的方法是假设你有一个线性?致的寄存器来存储一个整数,并且有一个原?子CAS(或自增)操作。
该算法很简单:每个要通过全序?播发送的消息?先对线性一致寄存?执??增并返回操作。然后将从寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点(重新发送任何丢失的消息),而接收方将按序?号连续发送息。
请注意,与兰伯特时间戳?同,通过自增线性?致性寄存?获得的数字形式上是一个没有间隙的序?。 因此,如果一个节点已经发送?消息4并且接收到序列号为6的传入消息,则它知道它在传递消息6之前必须等待消息5。兰伯特时间戳则与之不同??事实上,这是全序?播和时间戳排序间的关键区别。
实现一个带有原?性?增并返回操作的线性?致寄存器有多困难?像往常一样,如果事情从来不出差错,那很容易:你可以简单地把它保存在单个节点内的变量中。问题在于处理当该节点的?络连接中断时的情况,并在该节点失效时能恢复这个值。一般来说,如果你对线性?致性的序列号生成?进?过?够深入的思考,你不可避免地会得出一个共识算法。
这并?巧合:可以证明,线性一致的CAS(或?增)寄存?与全序?播都等价于共识问题。也就是说,如果你能解决其中的一个问题,你可以把它转化成为其他问题的解决方案。


分布式事务与共识

共识是分布式计算中最重要也是最基本的问题之一。从表面上看似乎很简单:非正式地讲,?标只是让几个节点达成一致。你也许会认为这不会太难。不幸的是,许多出故障的系统都是因为错误地轻信这个问题很容?解决。
有很多重要的场景都需要集群节点达成某种一致,例如:


领导选举
在单主复制的数据库中,所有节点需要就哪个节点是领导者达成一致。如果一些节点由于网络故障?无法与其他节点通信,则可能会对领导权的归属引起争议。在这种情况下,共识对于避免错误的故障切换非常重要。错误的故障切换会导致两个节点都认为?己是领导者。如果有两个领导者,它们都会接受写入,它们的数据会发生分歧,从而导致不一致和数据丢失。原子提交
在支持跨多节点或跨多分区事务的数据库中,?个事务可能在某些节点上失败,但在其他节点上成功。 如果我们想要维护事务的原?性,我们必须让所有节点对事务的结果达成一致:要么全部中?/回滚,要么它们全部提交。
原子提交与两阶段提交
从单节点到分布式的原子提交

对于在单个数据库节点执?的事务,原子性通常由存储引擎实现。当客户端请求数据库节点提交事务时,数据库将使事务的写入持久化(通常在预写式?志中),然后将提交记录追加到磁盘中的?志?。如果数据库在这个过程中间崩溃,当节点*羰保挛窕岽尤罩局谢指矗喝绻峤患锹荚诒览V俺晒Φ匦?磁盘,则认为事务被提交;否则来自该事务的任何写?都被回滚。
因此,在单个节点上,事务的提交主要取决于数据持久化落盘的顺序:首先是数据,然后是提交记录。事务提交或终?的关键决定时刻是磁盘完成写入提交记录的时刻:在此之前,仍有可能中?,但在此之后,事务已经提交(即使数据库崩溃)。因此,是单一的设备使得提交具有原子性。
但是,如果一个事务中涉及多个节点呢?在这些情况下,仅向所有节点发送提交请求并独立提交每个节点的事务是?够的。这样很容易发?违反原子性的情况:提交在某些节点上成功,而在其他节点上失败。
如果某些节点提交?事务,但其他节点却放弃了这些事务,那么这些节点就会彼此不一致。而且一旦在某个节点上提交了一个事务,如果事后发现它在其它节点上被中??,它是无法撤回的。出于这个原因,一旦确定事务中的所有其他节点也将提交,节点就必须进?提交。
事务提交必须是不可撤销的??事务提交之后,你不能改变主意,并追溯性地中?事务。这个规则的原因是,一旦数据被提交,其结果就对其他事务可见,因此其他客户端可能会开始依赖这些数据。这个原则构成?读-提交隔离等级的基础。如果?个事务在提交后被允许中止,所有那些读取了已提交却?被追溯声明不存在数据的事务也必须回滚。提交事务的结果有可能通过事后执?另一个补偿事务来取消,但从数据库的?度来看,这是?个独立的事务,因此任何关于跨事务正确性的保证都是应用?己的问题。


两阶段提交

两阶段提交(two-phase commit,2PC)是一种用于实现跨多个节点的原?事务提交的算法,即确保所有节点提交或所有节点中止。 它是分布式数据库中的经典算法。
下图说明?2PC的基本流程。2PC中的提交/中止过程分为两个阶段(因此?得名),而?是单节点事务中的单个提交请求。

2PC使?一个通常不会出现在单节点事务中的新组件:协调者(也称为事务管理器)。协调者通常在请求事务的相同应?进程中以共享库的形式实现,但也可以是单独的进程或服务。
正常情况下,2PC事务以应用在多个数据库节点上读写数据开始。我们称这些数据库节点为参与者。当应?准备提交时,协调者开始阶段1:它发送一个准备请求到每个节点,询问它们是否能够提交。然后协调者会跟踪参与者的响应:


如果所有参与者都回答“是”,表示它们已经准备好提交,那么协调者在阶段 2 发出提交请求,然后提交真正发?。如果任意?个参与者回复?“否”,则协调者在阶段2中向所有节点发送中?请求。
系统的承诺

为了?解它的工作原?,我们必须?详细地分解这个过程:


    当应用想要启动一个分布式事务时,它向协调者请求一个事务ID。此事务ID是全局唯一的。应?在每个参与者上启动单节点事务,并在单节点事务上捎带上这个全局事务ID。所有的读写都是在这些单节点事务中各?完成的。如果在这个阶段出现任何问题(?如,节点崩溃或请求超时),则协调者或任何参与者都可以中止。当应?准备提交时,协调者向所有参与者发送?个准备请求,并打上全局事务ID的标记。如果任意一个请求失败或超时,则协调者向所有参与者发送针对该事务ID的中?请求。参与者收到准备请求时,需要确保在任意情况下都的确可以提交事务。这包括将所有事务数据写?磁盘(出现故障,电源故障,或硬盘空间不足都?能是稍后拒绝提交的理由)以及检查是否存在任何冲突或违反约束。通过向协调者回答“是”,节点承诺,只要请求,这个事务?定可以不出差错地提交。换?话说,参与者放弃了?中?事务的权?,但没有实际提交。当协调者收到所有准备请求的答复时,会就提交或中止事务作出明确的决定(只有在所有参与者投赞成票的情况下才会提交)。协调者必须把这个决定写到磁盘上的事务?志中,如果它随后就崩溃,恢复后也能知道?己所做的决定。这被称为提交点。?旦协调者的决定落盘,提交或放弃请求会发送给所有参与者。如果这个请求失败或超时,协调者必须永远保持重试,直到成功为止。没有回头路:如果已经做出决定,不管需要多少次重试它都必须被执?。如果参与者在此期间崩溃,事务将在其恢复后提交??由于参与者投了赞成,因此恢复后它不能拒绝提交。
    因此,该协议包含两个关键的“?归?”点:当参与者投票“是”时,它承诺它稍后肯定能够提交。?旦协调者做出决定,这?决定是不?可撤销的。这些承诺保证?2PC的原?性。 (单节点原子提交将这两个事件合二为一,写入事务日志即提交)。

协调者发生故障

我们已经讨论?在2PC期间,如果参与者之一或?络发生故障时会发??么情况:如果任何一个准备请求失败或者超时,协调者就会中止事务。如果任何提交或中?止请求失败,协调者将?条件重试。但是如果协调者崩溃,会发??么情况就?太清楚?。
如果协调者在发送准备请求之前失败,参与者可以安全地中?事务。但是,一旦参与者收到了准备请求并投?“是”,就?能再单?面放弃??必须等待协调者回答事务是否已经提交或中?。如果此时协调者崩溃或网络出现故障,参与者?么也做不??只能等待。
情况如下图所示。在这个特定的例子中,协调者实际上决定提交,数据库2收到提交请求。但是,协调者在将提交请求发送到数据库1之前发?崩溃,因此数据库1 ?知道是否提交或中?。即使超时在这?也没有帮助:如果数据库1在超时后单?方?中止,它将最终与执?提交的数据库2?一致。同样,单?面提交也是?安全的,因为另?个参与者可能已经中??。

没有协调者的消息,参与者?法知道是提交还是放弃。原则上参与者可以相互沟通,找出每个参与者是如何投票的,并达成?致,但这?是2PC协议的?部分。
可以完成2PC的唯?方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交或中?请求之前,将其提交或中止决定写?磁盘上的事务?志:协调者恢复后,通过读取其事务日志来确定所有存疑事务的状态。任何在协调者日志中没有提交记录的事务都会中止。因此,2PC的提交点归结为协调者上的常规单节点原?子提交。


三阶段提交

两阶段提交被称为阻塞原子提交协议,因为存在2PC可能卡住并等待协调者恢复的情况。 理论上,可以使一个原子提交协议变为非阻塞的,以?在节点失败时?会卡住。但是 让这个协议能在实践中工作并没有那么简单。
作为2PC的替代?案,已经提出了一种称为三阶段提交(3PC)的算法。然而,3PC假定?络延迟有界,节点响应时间有限;在?多数具有无限网络延迟和进程暂停的实际系统中,它并不能保证原子性。
通常,非阻塞原?提交需要一个完美的故障检测器??即?个可靠的机制来判断?个节点是否已经崩溃。在具有?限延迟的?络中,超时并不是一种可靠的故障检 测机制,因为即使没有节点崩溃,请求也可能由于网络问题?超时。出于这个原因,2PC仍然被使?,尽管?家都清楚可能存在协调者故障的问题。


实践中的分布式事务

分布式事务的某些实现会带来严重的性能损失???如据报告称,MySQL中的分布式事务?单节点事务慢10倍以上,所以当?们建议?要使?用它们时就不足为奇了。两阶段提交所固有的性能成本, 大部分是由于崩溃恢复所需的额外强制刷盘以及额外的?络往返。
但我们不应该直接忽视分布式事务,而应当更加



友情链接: