分布式算法之MIT 6.824系列总结

一、简介

1.1 序言

作者就职业某一线互联网公司的研发部门，在研发过程中经常用到各种中间件，比如消息、缓存、数据库、批/流计算等系统。在研发的使用过程中，我对于这些中间件的使用体感就是：“像是一个运行在单机上，同时拥有高性能，高可用，且几乎不可能宕机的系统”。但是身为研发，其实很清楚这背后肯定不是类似于传统的单机服务，运行在一台物理服务器上，因为一台机器不可能做到性能无限扩展，也无法抵御断电、断网、火灾、地震、甚至数据中心彻底毁坏等场景。这些中间件系统背后实际上一个服务器集群在对外提供服务，他们的目标便如此：在存在网络分区的分布式的场景下，通过合理的设计对外屏蔽复杂的分布式场景，提供性能可以随着服务器数量变化而线性变化，具备故障转移，故障自动恢复，对外提供功能却又像是运行在单核单CPU机器上，满足线性一致性的系统。

1.2 分布式系统的驱动力与挑战

在设计一个系统时或者面对一个问题时，如果你可以在一台计算机上解决，而不需要分布式系统，那你就应该用一台计算机解决问题。有很多的工作都可以在一台计算机上完成，并且通常比分布式系统简单很多。所以，在选择使用分布式系统解决问题前，你应该要充分尝试别的思路，因为分布式系统会让问题解决变得复杂。

人们使用大量的相互协作的计算机的目的（驱动力）是：

本篇将针对前两点(性能和容错)对不同的分布式算法进行主要讨论。

所有的这些分布式系统的问题（挑战）在于：

1.3 可扩展性

通常来说，构建分布式系统的目的是为了获取可扩展的加速，或者实现单机难以到达的存储或者计算水平。所以，这里的可扩展性指的是，如果我用一台计算机解决了一些问题，当我买了第二台计算机，我只需要一半的时间就可以解决这些问题，或者说同样的时间内可以解决两倍数量的问题。两台计算机构成的系统如果有两倍性能或者吞吐能力便是指这里所说的扩展性。即：系统的计算、吞吐等性能随着计算机数量线性变化。

1.4 可用性(容错)

由于我们的系统是运行在网络分区的分布式场景下，假设集群中有100台机器，这100台机器通过网络进行连接，那么完全有可能出现机房断电、某人不小心踢掉了网线、网线老化故障，网络交换机故障等各种问题，导致这100台机器中某些机器出现不可用。因为错误总会发生，我们也无法避免错误发生，所以必须要在设计时就考虑，系统能够屏蔽错误，或者说能够在出错时继续运行。即：系统经过精心的设计，即便在发生特定错误的场景下，系统仍然能够正常运行，仍然可以像没有出现错误一样，为你提供完整且正确的服务。

除了可用性，容错还有一个特征称为可恢复性。如果系统出现了无法自动修复的问题时，系统可以停止工作，不再提供服务，之后有人来修复，并且在修复之后系统仍然可以正常运行，就像没有出现过问题一样。这是一个比可用性更弱的需求，因为在出现故障到故障组件被修复期间，系统将会完全停止工作。但是修复之后，系统又可以完全正确的重新运行，所以可恢复性是一个重要的需求。简单理解就是：当系统故障后，故障之前系统的数据不会丢失，再系统修复重启完成后又能继续正确的运行(理解相当于系统暂停了)

为了实现容错的可用性和可恢复性，有两个方案：

1.5 一致性

一致性分为强一致性与弱一致性。强一致性通俗来讲就是：你每次Get的值都是上次最近一次Put的值，强一致性可以保证每次Get获取的值都是最新的值。而弱一致性并不会做同样的保证，弱一致性可能提供Get的值可能并不是最新的，也可能是历史的某个旧值，这个旧值甚至可能是很久前写入。你可能会问，有了强一致性，为什么我还需要弱一致性？事实上，在单机环境下强一致性容易实现(利用锁等方式)，因为单机不存在网络分区，不需要进行网络通信。而在分布式环境中，各个组件需要做大量的通信，才能实现强一致性。如果你有多个副本，那么不管get还是put都需要询问每一个副本，然后从所有副本中取出最新的值，但是在容错场景下，多个副本在物理上很可能并不在一个数据中心，网络请求可能会跨数据中心，这将会带来系统吞吐性能的直线下降，并且由原来的一个网络IO，变为多副本的多次网络IO，极大的增加了网络带宽压力。

1.6 分布式存储系统设计的难点

首先我们构建分布式系统的出发点一般是为了可扩展性，因为单机的CPU、内存、磁盘、网络、并行计算等性能总是有限的，而分布式系统可以通过购买成百上千台廉价的机器，以实现算力、存储能力等性能同等数量倍数的提升。所以这里引出：1. 性能(可扩展性)是分布式系统的主要目标。而当我们拥有上千台机器后，那么这些机器中随机出现故障的概率就会大大增加，如果机器数量够多，甚至每小时或者每分钟都会有机器出现各种各样的故障，我们不能因为某台机器出现问题导致上千台的集群不可用，所以我们设计的系统需要实现容错，而实现容错的方式一般是采用复制(副本机制)，即当节点故障后，采用其复制的副本代替故障阶段继续提供服务即可。所以这里引出：2. 分布式系统需要支持容错能力，容错常见的方式为多副本机制。 有了多副本之后，副本之间的数据同步显得尤为重要，因为稍不小心，在同一个时序下可能会出现副本数据不一致的场景，严格意义上来说它们不再互为副本，而你获取的数据取决于你从哪个副本上获取的，因为不同的副本可能有不同的数据，这里又引起了数据一致性问题。所以这里引出：3. 多副本机制会造成数据一致性问题。 为了避免一致性问题，我们不得不在机器之间做大量的网络交互来处理时序问题以及状态同步，这样势必带来性能的降低，所以这里引出：4. 保证数据一致性需要大量的网络交互，这样势必会降低性能，好的一致性的代价就是低性能。 这与我们构建分布式系统的第一点目标是相违背。

理论上我们可以构建性能很高的系统，但是不可避免的，都会陷入到这里的循环来：为了性能构建然后分布式系统，由于分布式环境下错误是常见的，所以需要支持容错机制，为了实现容错便采用多副本机制，多副本机制又会引起数据一致性问题，为了解决数据一致性又需要大量的网络交互，大量的网络交互势必降低系统性能。 现实中，如果你想要好的一致性，必然性能会受损。如果你不想性能受损，那就要接受数据不一致的行为。但是现实的大多数场景中，人们都不愿意为了一致性牺牲性能。这也是弱一致性存在的主要意义。

对于上述背景，在某些Case中，有些有很好的解决方案，有些甚至到目前为止也没有那么好的解决方案。接下来作者将介绍几种分布式算法，统观各分布式算法，其本质都是在上述的循环内，围绕可扩展性、可用性、一致性上进行不同取舍并做了一些取巧的设计，最后得到了不同的系统设计结果。

二、GFS(论文:GFS)

2.1 GFS大致结构

GFS在系统结构上分为 Master 节点，以及Chunk 节点，其中Master以及Chunk服务均有各自的多个副本, 其中Master主节点对外提供服务，Master副本用于容错，需要注意的是，当Master主节点故障时，GFS并不能实现故障自动恢复，即并不能自动切换到Master副本上，而是需要人手工去处理故障然后进行恢复，其中原因读者可以深入研究, 本文不做讨论，姑且认为这个系统在设计上就没有打算支持那么好的容错(一致性上也是如此)。Chunk多副本同理，其中Chunk的主节点简称为Chunk Primary。

GFS会将文件按照指定大小进行分割(默认64MB),分割为多个Chunk，然后存储在Chunk服务器上及其副本上，底层的存储方式为Linux文件系统方式进行存储。而Master节点则保存了文件被分割成了哪几个Chunk，以及这些Chunk 所在的服务器信息。可以简单理解Chunk服务器就是存储文件的磁盘，而Master则是文件索引。保存了文件存储在哪几个磁盘。

2.2 GFS目标

有了以上目标，我的第一感觉是，GFS是一个超大型的文件系统，不支持异地容灾，专注于大数据量的顺序读取而非事务处理，另外GFS认为存储系统具有弱一致性也是可以的，因为选择了弱一致性，所以GFS提供了巨大的吞吐量，但这里也会存在一致性问题，下文将提到。

2.3 GFS文件读取过程

2.4 GFS文件写入过程

这里为了阐述原理，对于文件写入过程，只阐述文件数据Append过程(尾部追加新的Chunk)，不考虑数据修改，关于修改这里提供一个思路(作者猜测的)：Master内部维护了一份Chunk顺序的链表，修改时执行Chunk文件覆盖，修改Chunk顺序链表，方法有很多，这里仅提供一种思路

在读取阶段，为了阐述原理，特意跳过一个点，在Master上不仅存有文件名与Chunk列表的表单信息，还维护了每一个Chunk的版本号。为什么需要维护版本？因为在分布式环境下，Chunk服务器随时可能故障，故障恢复后数据可能会更新，为了保证一致性，便引入了版本号的方式。实际上在读取阶段中， Master从所有的Chunk及其副本中过滤掉了与Master维护的版本号不同的Chunk副本。然后将版本号相同的Chunk列表返回给客户端，客户端可以根据情况对多个文件进行并行读取。

GFS的文件修改过程大致为：

可扩展性：

由于GFS的多副本机制，客户端可以获取多个Chunk副本，实现并行读取数据，所以理论上可以实现吞吐量随着机器数量增加的线性提升。

容错：

由于Master维护了文件与Chunk列表表单，并且维护了每个Chunk的版本号，并且这些信息均会持久化在磁盘中，如果出现故障，可以自动识别故障Chunk，从而进行故障转移。这里有一个疑问，从目前已有资料来看，理论上Master如果故障了，其Master的副本可以接替原Master的工作继续工作，但是从现实现状中的结论是：目前Master并不支持故障的自动恢复，需要人为手工介入进行修复。也就是Master的副本只是用来进行备用，但是并不能自动完成故障恢复和迁移。笔者怀疑是因为Master需要保证强一致性，而当时提出GFS时，Master的强一致性方案并没有很好的解决；还有一种可能，GFS并不需要保证那么高的可用性。

一致性：

重点讨论一下GFS的一致性，下图为写入过程中对多个Chunk进行写入可能发生的情况，这里认为Chunk 1为主副本

上述5个阶段按照以下时序进行

在上面的时序中

• 如果在阶段3结束后，紧接着有新的客户端Client 5 发起读取请求，由于阶段2数据B在Chunk 2上写入失败，Client 5读取的数据旧完全取决于读取的Chunk副本为哪一个。如果读取的Chunk 1/2 读取到的数据则为A/B/C，如果读取的Chunk 3则只能读取到A/C；这时候就出现了数据一致性的行为。
• 如果在阶段4结束后，Client 5发起了读取请求，对于Chunk 1/2来说，读取的文件顺序为A/B/C/B，先读取到的是B后才是C，但是如果是Chunk 3则先读取到的C后才是B。所以在这种场景下，需要客户端能容忍数据的重复，以及乱序，需要客户端去指定文件顺序(客户端在存储的时候便给数据添加用于排序的数据)，并做好去重处理。
• 在阶段5之后，这个场景可能会更加糟糕。因为写入数据D的客户端下线，对于Chunk 2来说，数据D永远不会再被写入。如果Client 读取到了Chunk 2则无法读取到数据D。

GFS这样设计的理由是足够的简单，但是同时也给应用程序暴露了一些奇怪的数据。这里希望为应用程序提供一个相对简单的写入接口，但应用程序需要容忍读取数据的乱序。如果应用程序不能容忍乱序，应用程序要么可以通过在文件中写入序列号，这样读取的时候能自己识别顺序，要么如果应用程序对顺序真的非常敏感那么对于特定的文件不要并发写入。例如，对于电影文件，你不会想要将数据弄乱，当你将电影写入文件时，你可以只用一个客户端连续顺序而不是并发的将数据追加到文件中。

有人会问，如何将这里的设计转变成强一致的系统，从而与我们前面介绍的单服务器模型更接近，也不会产生一些给人“惊喜”的结果。目前能确定的是，如果为了实现强一致性，各个副本需要加大网络通信，每次都需要检查自己的状态等。

虽然GFS设计得比较简单，但GFS在它生涯的前5-10年在Google的出色表现，总的来说，它取得了巨大的成功，许多Google的应用都使用了它，包括很多Google的基础架构，例如BigTable和MapReduce是构建在GFS之上，所以GFS在Google内部广泛被应用。它最严重的局限可能在于，它只有一个Master节点，会带来以下问题：

三、Raft(论文:Raft)

3.1 某基于Raft的KV数据库应用大致架构

Raft起初是为了应对脑裂问题，脑裂是分布式系统都需要面临的一个问题，至于脑裂是什么，有兴趣的同学可以自行查阅了解。

首先对基于Raft的分布式应用，机器会分为Leader、Follower角色。Leader就是整个服务的主节点，用户接受客户端请求，Follower为Leader的副本应用，用于非强一致性的读请求，以及Leader故障时的容错。Raft会以库（Library）的形式存在于服务中。对于一个基于Raft的多副本服务，每个服务的将会由两部分组成：用于处理业务逻辑的代码，应用程序代码和Raft库。应用程序代码接收RPC或者其他客户端请求；不同节点的Raft库之间相互合作，来维护多副本之间的操作同步。

从软件的角度来看一个Raft节点，可以认为在该节点的上层，是应用程序代码。为了阐述原理，假设这部分应用程序代码就是一个Key-Value数据库。应用程序通常都有状态，Raft层会帮助应用程序将其状态拷贝到其他副本节点。对于一个Key-Value数据库而言，对应的状态就是Key-Value表单。应用程序往下，就是Raft层。所以，Key-Value数据库需要对Raft层进行函数调用，来传递自己的状态和Raft反馈的信息。接下来看看Raft如何通过精巧的设计，在实现容错的情况下，又能保证一致性，还能有较好的性能。

3.2 Raft的读取过程

3.3 Raft的写入过程

Raft算法，支持容错自动恢复，且保证数据一致性，但在扩展性，随着机器数量增加，写入性能理论上会降低。接下来主要分析一下其算法详细流程。

先看一下Raft的容错自动恢复，在Leader正常的情况下，不会出现任何问题，只有在Leader故障时才会出现问题。下图的八个阶段为Raft在运行过程中的各机器的日志序列(日志列从左至右分别为index=1/2/3/4)可能出现的情况。假设整个集群存在5台机器，每次至少过半则需要3 台机器参与操作。

在理解前，首先约定对于Leader选举存在以下规则或约束：

这里简述一下上述8个阶段，这5个Raft服务各自经历了什么：

阶段1: 假设现在S1当选为Leader，S1的任期号为1，S1收到了客户端请求保存记录10，S1收到请求后将日志保存在index=1的日志槽中，并且将该条日志同步在其他4台机器上，并且其他4台机器全部同步成功，此时5台机器都有任期为1，数据10的日志数据位于第一个日志槽位上

阶段2: S1收到新的请求，保存记录11，由于index=1已经存储了上一条日子，于是S1将日志保存在index=2的日志槽中，并且S1将该日志同步给其他所有的副本，由于网络原因，仅仅只有S2、S3保存成功，由于S1、S2、S3已经凑够了过半机器，所以这个保存请求也是成功的。但S4、S5在index=2的日志槽位上便没有这条日志(Log Data = 11,任期号=1,index=2)

阶段3: S1发生短暂的网络故障下线，由于S1的短暂下线，触发了一次新的Leader选举，但此时S1网络又迅速恢复上线，根据选举规则，只有S1、S2、S3有可能成为新的Leader，这里假设S1赢得选举，再次成为新的Leader，但是任期号需要更新为2。当选为新Leader后，S1收到请求保存日志记录12，于是S1将日志(Log Data=12，任期号=2,index=3)存储在日志槽中

阶段4: S1将日志(Log Data=12,任期号=2,index=3)存储完毕，在将该日志同步给其他副本前，网络故障再次发生，导致该日志同步给其他副本失败，该日志仅存在于S1中， 其他副本均没有；S1发生再次发生短暂的网络故障下线，由于S1的短暂下线，触发了一次新的Leader选举，但此时S1网络又迅速恢复上线，根据选举规则，仍然只有S1、S2、S3有可能成为新的Leader假设这次S1再次当选Leader，任期号更新为3，此时S1收到请求保存日志记录13，于是S1将日志(Log Data=13，任期号=3，index=4)保存在日志槽中。保存完毕后，S1发生严重的网络故障导致下线，导致该日志并没有同步至其他副本。所以该日志仅存在于S1上。

阶段5: 由于S1Leader下线，整个集群重新触发Leader选举，根据选择规则，只有S1、S2、S3有可能成为新的Leader，但是S1由于网络故障并不会发起投票，这里假设S2赢得了选举成为了新的Leader，此时任期号更新为4。S2接管成为Leader后，收到请求保存日志记录14，于是S2将日志(Log Data=14,任期号=4,index=3)保存在日志槽中

这里有一个小细节，为什么S2知道下一任任期号是4，我的回答是，S1赢得选举必然是获得了过半服务器的投票，因为上一次S1的选举S2投了票，S1告诉了上一个任期号，S2会将其持久化在本地中，各个副本除了基本的日志会进行存储，还会存储用于投票自己已知的最新任期号。这里也可能将任期号更新为2，因为可能S1在最后两次从新当选Leader可能都是S4、S5的投票，而S2、S3并未投票，导致S2本地并没有感知到最新的任期号，仅参与了第一次S1投票。这里假设S2参与了投票。

阶段6: 这时候S1重新修复上线，由于S2是新的Leader，S1此时成为副本，在S2将日志(Log Data=14,任期号=4,index=3)保存成功后，便发送日志同步给其他副本，同步信息除了上一条日志(Log Data=14，任期=4，index=3)外，还有日志槽中的上一条日志(Log Data=11，任期=1，index=2)夹带在同一个日志消息体中进行发送。这时S1、S3收到消息后，判断最新一个日志是消息中的上一条日志，并且Log Data,任期号，index完全匹配，所以S1、S3同意本次更新。将日志(Log Data=14，任期=4，index=3)存储在日志槽中。对于S4、S5由于index=2没有对应日志，会返回同步失败，表示拒绝本次日志更新。

阶段7: 当S4、S5拒绝后，这时S2会再次回溯到上上条日志，同时夹带3条日志(即多一条 Log Data=10,任期号=1,index=1)信息发送出来。S4、S5发现最新一条日志与发送的日志信息最后一条相同，则同步本次更新，且会直接插入两条日志数据。这时所有机器在index1/2/3/4的位置上数据相同了

阶段8: S2-Leader收到新的请求保存数据15，和之前的流程一样，这时候同步给所有的副本申请保存数据15的日志，正常都会保存成功。但其实收到1/2副本保存成功时便返回了结果

在7/8阶段，S1在index=3/4上的数据均被擦除了，你可能有疑问，这里的擦除是安全的吗？这里就要回到为什么Raft规定，集群服务器数量必须是奇数台，每次Leader执行更新时，需要至少过半服务器数量，即：1/2 * N + 1数量的服务器都更新才提交更新，因为S1上的两次更新，在S2-S5上并没有出现，即没有过半， 那么必定能判断Raft并没有对应用程序返回操作完毕的响应，应用程序也没理由相信Raft完成了操作，所以这里的擦除是因为能断定Raft Leader必定没有对应用程序进行回应的断定下进行的安全擦除。

扩展性：

在数据读取方面，理论上随着机器数量增加，客户端能读取的客户端也越多，其读取吞吐能力是随着机器数量线性增加的

在数据写入方面，由于每次更新要求必须完成过半服务器写入完毕，Leader才会认为写入完毕，所以随着计算机数量的增加，理论上Leader与其他Follower的网络交互便越多，需要等待写入完毕的数量也越多，则等待的时间则可能更长，导致写入能力下降。

容错：

根据写入过程，我们可以看到，任何一次更新之后，整个集群中一定有 1/2 * N个副本机器和Leader的状态一致，当Leader出现故障下线后，则可以根据选择规则，就能选举出新的Leader，作为新的Leader对外提供服务即可。

一致性：

对于读/写请求，因为仍然只有Leader节点对外提供服务，即单点处理，所以不会存在多副本同时提供服务导致数据不一致的情况，即便是在Leader出现故障后，根据选举规则，当选Leader的Follower也可以将所有副本的数据进行正确的恢复，从而保证一致性不会被破坏。

3.4 思考

3.4.1 Raft算法为什么要求服务器的的数量必须是奇数？

首先回答这个问题，就要回到Raft被提出来的背景，Raft主要目的是为了解决脑裂。脑裂的表现就是，集群无法确定一个准确的Leader，也无法判断被选举出来的Leader是否合法，那么为了解决这个问题，Raft要求服务器集群的数量必须是奇数个，每个Leader的选举都必须获得至少过半数的投票才能成为合法的Leader，有了这个限制后，那么在Leader的投票选举过程中， 就最多只有1台机器有可能拥有过半的投票成为Leader。如果是偶数，同样要求过半，则可能刚好两个选举者均获得一般的票数都可以成为Leader，导致脑裂问题。你可能会说：“我可以要求至少需要3/4表决同意才能成为Leader，这样是机器的数量偶数也只会有1台机器成为Leader”。这个想法是对的，为了防止脑裂，其核心思想就是：通过限制投票策略，让同一时间能得到投票达到Leader要求的票数只可能有1台即可。

3.4.2 在分布式场景下，怎样才算是数据持久化完成？

这个问题可能某些读者会觉得有点奇怪，这算是笔者自己的一个反思，对分布式与常用的单机场景下，持久化的区别和真正的意义。在普通的单机情况下，如果我们为了防止数据丢失，可能使用MySQL这种单点的数据库，将数据存储在MySQL就算是存储完毕了，如果服务器宕机了，重新连接到MySQL即可恢复并再次提供服务。如果MySQL宕机了，因为MySQL的数据通过BinLog的形式存储在磁盘上，所以MySQL重启后重新解析这些存储在磁盘上的BinLog即可恢复数据，然后对外再次提供服务。

那么在分布式场景下，要达到的目的也是相同的，即便是系统发生故障了，整个系统也能根据持久化的数据进行正确地恢复，或者发生局部错误时，仍然需要提供正确的服务，对外表现像是一台没有发生任何异常的单机服务。Raft是如何达到这个目的呢，首先Raft要求对于对于一个更新请求，需要至少过半服务器将更新请求进行响应， 并将相关Log持久化到本地磁盘中才算整个请求的修改持久化完毕。至于为什么是至少过半，其实是因为投票过程需要，每次更新都会记录上最新Leader的任期号，因为需要保证过半服务器能拥有正确的Leader信息，这样才能进行正确的投票选出正确的Leader。

四、Zookeeper(论文:Zookeeper)

4.1 ZK的大致架构

4.2 ZK的写入过程

4.3 ZK的读取过程

相对于写入过程，读取过程简单很多。这里我们假设客户端在这次读取Key 1请求之前，对其进行了一次更新操作，这之后整个ZK都没有更新操作，也就是说这个客户端发起了最后一次更新操作，这次更新操作对应的日志理论上应该是日志列表里最后的一条日志，客户端也拿到了最新的日志ID，且存储在了本地的已知最新Log ID字段值中。

4.4 采用Log ID来控制读取过程(读取的值不会太旧的原因)

假设发生以上两个场景，按照以下流程进行运行

在步骤4的时候，假设Client 1也发起了读取Key 1请求，请求为 Get Key 1,Log ID=100，由于副本本地最新的Log ID 满足大于等于请求中的Log ID，所以这时候副本会直接返回给Client 1，Key 1=1的结果。所以不同的客户端结果可能是不一致的，取决于客户端的自身状态。对于Client 1来说，返回Key 1=1也是合理的，因为在Client 1的认知里，并不知道有除了自己的更新外还有别的更新。而对于Client 2就不行，因为Client 2发起了更新操作，Key 1=1对于Client 2来说已经是过去，只能接受Key 1 = 2结果。

如果在两个Client 发起读取Key 1之前，得到了所有的更新，Client 1获取Key 1的值就是2。所以从全局一致性来看，Client 1读取并不一定是最新的值，同理Client 2也是(因为可能还有Client 3做了Key 1=3呢)。

4.5 ZK的多操作原子更新

ZK还支持原子操作，即：某客户端需要对多条数据进行同时更新操作时，如果有其他客户端同时需要读取这些数据，能保证其他客户端读取的这些数据要么都没更新，要么都更新了。即更新操作的原子化，不会因为读写的时序问题，导致写未完全完成数据更新前，客户端技能读取部分更新的值，又能读取没更新的值。

用上图步骤来解释ZK支持的原子更新特征

针对6.3中的问题，ZK实际上是按照以下方式进行处理的，让ZK并不会给出6.c中可能的响应

上面的过程其实漏掉了一个细节，副本本地存在一个对于数据表单的Watch表单，记录了数据被哪些Client正在读取但还没读取完；在副本收到Client 1读取Key1/Key2原子读取请求后，副本会在Key1 的Watch表单中记录上Client 1，表明Client 1正在读取Key 1但是本次为原子读取，整个读取操作还没完毕，待整个读取请求处理完毕后，这个Client 1在Watch表单中才会删除。

所以6.c实际情况是，Client 1在刚刚读取完Key 1=1后，在准备读取Key2之前，Client 2修改数据的日志到达副本，并且要对Key1/Key2执行更新前，副本会去检查这个Watch表单，是否有Key1/Key2的Watch Client，如果有，则副本会通知表单中的Client，监听值已经发生变化，Client需要放弃本次请求，并重头开始整个读取请求。这样副本就做到了原子更新过程中，读取操作要么全部读取未更新的，要么读取全部更新完毕后的值。

扩展性：

ZK在写上面仍然是单点的，不支持扩展(结合数据Sharding，即多ZK集群，是不是也算是一种水平扩展了？手动狗头....)，但是在读上支持水平扩展，有多少副本就能支持多大的读取吞吐能力。

容错：

ZK仍然能采用多副本的方式进行容错。但是Master故障是否能自动迁移，这个笔者还未研究过，如果支持自动迁移，我理解底层ZAB也应该时采取类似于Raft的选主策略和数据更新策略。

一致性：

ZK在写上是强一致的，因为Master单点且串行执行请求。在读上，并不是强一致的，但是能保证客户端至少都能读取到自己的更新，甚至更加新的数据，从Master全局一致看这个值可能是旧值，但是却比客户端新。

4.6 思考

4.6.1 ZK是线性一致(强一致)系统吗？

ZK在写请求上是强致的，因为Master将所有请求按照FIFO的方式进行串行处理(参考4.1内容)，在读请求上并不是强一致的，只能保证一定能读取到自己更新的数据，全局上看自己更新的不一定是最新的数据(参考4.4内容)。

4.6.2 为什么在连续多个值读取的时候，在整个读取操作未结束之前，如果Watch到了之前的某个任意读取过的值发生了修改，Client就需要放弃整个读取操作，然后进行重发整个读取请求？

参考4.5内容，在原子的读取操作中，如果已部分读取的某个数据(A)更新了，那么其他已读取过的数据(B)，或者即将读取的数据(C)很可能与这个刚更新的数据(A)也一同经历了一次原子更新操作，就有可能出现这种情况：读取过的数据(A)是原子更细前的值，而其他已经读取的数据(B)或者即将读取的数据(C)与这个数据(A)可能一起进行了一次原子更新，导致其他读取的数据(B)或者即将读取的数据(C)是原子更新后的值。打破了原子更新的规定：要么全读取老的，要么全读取新的。不能一部分是读取的老的，一部分是读取的新的。

五、CRAQ(论文:CRAQ)

CRAQ(Chain Replication with Apportioned Queries)是对于一个叫链式复制（Chain Replication）的旧方案的改进，Chain Replication在现实世界的系统经常被使用，CRAQ是对它的改进。CRAQ采用的策略与Zookeeper非常相似，它通过将读请求分发到任意副本去执行，来提升读请求的吞吐量，所以副本的数量与读请求性能成正比。不同的是，在任意副本上执行读请求的情况下，还可以保证线性一致性(强一致性)。这与Zookeeper不太一样，Zookeeper为了能够从任意副本执行读请求，不得不牺牲数据的实时性，因此也就不是线性一致的。CRAQ却可以从任意副本执行读请求，同时也保留线性一致性，这一点是很难得。

5.1 链式复制（Chain Replication）

链式复制方案比较简单，其采用了与Raft不一样的拓扑结构，具有以下特点：

5.2 链式复制的容错

5.3 CR与Raft的对比

Chain Replication与Raft进行对比，有以下差别：

5.4 CRAQ

CRAQ对CR进行以下改进

对于更新操作，值会存在多个版本，除Tail外，更新操作不会直接覆盖值，而是新增一个具有新版本号的新值(论文中这个版本号称为Dirty，相当于一个值会存在多版本共存了)，只有当Tail接收并处理了这个Dirty版本号的更新操作时，才能将版本号更新为Clean。理论上除Tail外，所有节点对一个值同一时刻存在一个Clean版本，多个或者0个Dirty版本，只要更新请求没有收到Tail的回复都是Dirty的，当Dirty的收到Tail回复，其版本号就会变成Clean的，原来的Clean就会被删除。这个其实很好理解：因为在这种链式结构，只要Tail执行了才算是更新请求得到了Commit，在Tail没更新前，所有的更新都是可能失败的，即Dirty。当Tail也执行了Dirty的更新后，说明更新得到了Commit，这时候这个值就是安全的，即Clean。

对于读取操作，不同于CR只能从Tail读取数据，客户端可以从所有的节点进行读取数据读取了，在进行数据读取的时候，肯定只能返回Clean版本的数据。问题在于如何确定Clean版本数据。当Client向某个副本发送读取时会存在以下情况

通用以上优化，CRAQ也达到了ZK一样的效果，在读上支持了扩展性，并且CRAQ支持从任意副本执行读请求，同时也保留线性一致性。但是还是存在CR所存在的问题，并且由于加长了链路处理流程，对写操作上降低了性能以及稳定性。

六、云原生多副本数据库-Aurora(论文:Aurora)

6.1 背景

6.1.1 EC2

在详细讨论Aurora之前，这里简单说一下Aurora被提出的背景和原因，最早的时候，Amazon提供的云产品是EC2(Elastic Cloud 2，即弹性云)，它可以帮助用户在Amazon的机房里和Amazon的硬件上创建类似网站的应用。Amazon有装满了服务器的数据中心，并且会在每一个服务器上都运行VMM（Virtual Machine Monitor，简单理解就是虚拟机软件，可以将单台物理机的CPU、内存、磁盘、网卡物理资源进行抽象，在这层上可以同时运行多个操作系统，就像真实且直接运行在物理资源上操作系统一样，即虚拟机，从虚拟机视角上看，这些虚拟机有自己独占的物理资源，VMM对单台机器的物理资源进行隔离、底层共享同一套物理资源等，对外体现就像是一台物理机可以分隔成多台机器互不影响地同时运行）。Amazon会向它的用户出租虚拟机(就是这里的EC2)，而它的用户通常会租用多个虚拟机用来运行Web服务、数据库和任何其他需要运行的服务。所以，在一个物理服务器上，有一个VMM，还有一些EC2实例，这些实例都出租给不同的云客户。每个EC2实例都会运行一个标准的操作系统，比如说Linux，在操作系统之上，运行的是应用程序，例如Web服务、数据库。这种方式相对来说成本较低，也比较容易配置，所以是一个成功的服务模式。如下图所示。EC2对于无状态的Web服务器来说是完美的。客户端通过自己的Web浏览器连接到一些运行了Web服务的EC2实例上。如果突然新增了大量客户，你可以立刻向Amazon租用更多的EC2实例，并在上面启动Web服务。这样你就可以很简单的对你的Web服务进行扩容。

另一类需求主要运行在EC2实例的服务是数据库。通常来说一个网站包含了一些无状态的Web服务，任何时候这些Web服务需要一些持久化存储的数据时，它们会与一个后端数据库交互。所以，现在的场景是，在Amazon基础设施之外有一些客户端浏览器（Client1，Client2）。之后是一些EC2实例，上面运行了Web服务，这里你可以根据网站的规模想起多少实例就起多少。这些EC2实例在Amazon基础设施内。之后，还有一个EC2实例运行了数据库。Web服务所在的EC2实例会与数据库所在的EC2实例交互，完成数据库中记录的读写。不幸的是，对于数据库来说，EC2就不像对于Web服务那样完美了，最直接的原因就是存储。对于运行了数据库的EC2实例，获取存储的最简单方法就是使用EC2实例所在服务器的本地硬盘。如果服务器宕机了，那么它本地硬盘也会无法访问。当Web服务所在的服务器宕机了，是完全没有问题的，因为Web服务本身没有状态，你只需要在一个新的EC2实例上启动一个新的Web服务就行。但是如果数据库所在的服务器宕机了，并且数据存储在服务器的本地硬盘中，那么就会有大问题，因为数据丢失了。

6.1.2 EBS

为了向用户提供EC2实例所需的硬盘，并且硬盘数据不会随着服务器故障而丢失，就出现了一个与Aurora相关的服务，并且同时也是容错的且支持持久化存储的服务，这个服务就是EBS。EBS全称是Elastic Block Store。从EC2实例来看，EBS就是一个硬盘，你可以像一个普通的硬盘一样去格式化它，就像一个类似于ext3格式的文件系统或者任何其他你喜欢的Linux文件系统。但是在实现上，EBS底层是一对互为副本的存储服务器。随着EBS的推出，你可以租用一个EBS volume。一个EBS volume看起来就像是一个普通的硬盘一样，但却是由一对互为副本EBS服务器实现，每个EBS服务器本地有一个硬盘。所以，现在你运行了一个数据库，相应的EC2实例将一个EBS volume挂载成自己的硬盘。当数据库执行写磁盘操作时，数据会通过网络送到EBS服务器。这两个EBS服务器会使用Chain Replication（5.1）进行复制。所以写请求首先会写到第一个EBS服务器，之后写到第二个EBS服务器，然后从第二个EBS服务器，EC2实例可以得到回复。当读数据的时候，因为这是一个Chain Replication，EC2实例会从第二个EBS服务器读取数据。

所以现在，运行在EC2实例上的数据库有了可用性。因为现在有了一个存储系统可以在服务器宕机之后，仍然能持有数据。如果数据库所在的服务器挂了，你可以启动另一个EC2实例，并为其挂载同一个EBS volume，再启动数据库。新的数据库可以看到所有前一个数据库留下来的数据，就像你把硬盘从一个机器拔下来，再插入到另一个机器一样。所以EBS非常适合需要长期保存数据的场景，比如说数据库。

尽管EBS是一次很大的进步，但是它仍然有自己的问题。它有一些细节不是那么的完美：

6.1.3 Amazon RDS（Mirrored MySQL）

基于EBS的通用型存储方案及其在MySQL基础上，结合Amazon自己的基础设施，Amazon为其云用户开发了改进版的数据库，叫做RDS（Relational Database Service）。在RDS的架构中，每一次写操作，例如数据库追加日志或者写磁盘的page，数据除了发送给AZ1的两个EBS副本之外，还需要通过网络发送到位于AZ2的副数据库。副数据库接下来会将数据再发送给AZ2的两个独立的EBS副本。之后，AZ2的副数据库会将写入成功的回复返回给AZ1的主数据库，主数据库看到这个回复之后，才会认为写操作完成了。

RDS这种架构提供了更好的容错性。因为现在在一个其他的AZ中，有了数据库的一份完整的实时的拷贝。这个拷贝可以看到所有最新的写请求。即使AZ1发生火灾都烧掉了，你可以在AZ2的一个新的实例中继续运行数据库，而不丢失任何数据。

6.2 Aurora

6.2.1 Aurora大致结构

在替代EBS的位置，有6个数据的副本，位于3个AZ，每个AZ有2个副本。所以现在有了超级容错性，并且每个写请求都需要以某种方式发送给这6个副本。现在有了更多的副本，为什么Aurora不是更慢了，之前Mirrored MySQL中才有4个副本。答案是，这里通过网络传递的数据只有Log条目，这才是Aurora成功的关键，每一条Log条目只有几十个字节那么多，也就是存一下旧的数值，新的数值，所以Log条目非常小。然而，当一个数据库要写本地磁盘时，它更新的是data page，这里的数据是巨大的。所以，对于每一次事务，需要通过网络发送多个8k字节的page数据。而Aurora只是向更多的副本发送了少量的Log条目。因为Log条目的大小比8K字节小得多，所以在网络性能上这里就胜出了。这是Aurora的第一个特点，只发送Log条目。

6.2.2 Aurora的容错

根据上文可以看出Aurora设计了3个AZ(数据中心)，每个AZ有2个副本，即总共6个副本，理论上Aurora具有超级容错性，Aurora这么设计的容错目标是：

为了实现上述目标，Aurora使用了Quorum思想，Quorum系统背后的思想是通过复制构建容错的存储系统，并确保即使有一些副本故障了，读请求还是能看到最近的写请求的数据。通常来说，Quorum系统就是简单的读写系统，支持Put/Get操作。它们通常不直接支持更多更高级的操作。你有一个对象，你可以读这个对象，也可以通过写请求覆盖这个对象的数值。

简述一下Quorum系统：假设有N个副本。为了能够执行写请求，必须要确保写操作被W个副本确认，W小于N。所以你需要将写请求发送到这W个副本。如果要执行读请求，那么至少需要从R个副本得到所读取的信息。这里的W对应的数字称为Write Quorum，R对应的数字称为Read Quorum。这是一个典型的Quorum配置。这里的关键点在于，W、R、N之间的关联。Quorum系统要求，任意你要发送写请求的W个服务器，必须与任意接收读请求的R个服务器有重叠。这意味着，R加上W必须大于N（ 至少满足R + W >= N + 1 ），这样任意W个服务器至少与任意R个服务器有一个重合。

按照下图，假如N=3，W=2，R=2时，每次读取的数据一定会有一台是最新写入的数据，根本版本号即可获取到最新的值，下图中写操作写S1/S3，读操作读取了S3，则读取到了S3这个最新值。

这里还有一个关键的点，客户端读请求可能会得到R个不同的结果，现在的问题是，客户端如何知道从R个服务器得到的R个结果中，哪一个是正确的呢？通过不同结果出现的次数来投票（Vote）在这是不起作用的，因为我们只能确保Read Quorum必须至少与Write Quorum有一个服务器是重合的，这意味着客户端向R个服务器发送读请求，可能只有一个服务器返回了正确的结果。对于一个有6个副本的系统，可能Read Quorum是4，那么你可能得到了4个回复，但是只有一个与之前写请求重合的服务器能将正确的结果返回，所以这里不能使用投票。在Quorum系统中使用的是版本号（Version）。所以，每一次执行写请求，你需要将新的数值与一个增加的版本号绑定。之后，客户端发送读请求，从Read Quorum得到了一些回复，客户端可以直接使用其中的最高版本号的数值。

为了描述的Aurora的容错目标，也就是在一个AZ完全下线时仍然能写，在一个AZ加一个其他AZ的服务器下线时仍然能读，Aurora的Quorum系统中，N=6，W=4，R=3。W等于4意味着，当一个AZ彻底下线时，剩下2个AZ中的4个服务器仍然能完成写请求。R等于3意味着，当一个AZ和一个其他AZ的服务器下线时，剩下的3个服务器仍然可以完成读请求。当3个服务器下线了，系统仍然支持读请求，仍然可以返回当前的状态，但是却不能支持写请求。所以，当3个服务器挂了，现在的Quorum系统有足够的服务器支持读请求，并据此重建更多的副本，但是在新的副本创建出来替代旧的副本之前，系统不能支持写请求。同时，如我之前解释的，Quorum系统可以剔除暂时的慢副本。

6.2.2 数据分片

Aurora将自己的数据分布在6个副本上，每一个副本都是一个计算机，上面挂了1-2块磁盘。但是如果只是这样的话，我们不能拥有一个数据大小大于单个机器磁盘空间的数据库。因为虽然我们有6台机器，但是并没有为我们提供6倍的存储空间，每个机器存储的都是相同的数据，只是互为副本。如果磁盘使用的是SSD，则可以将数TB的数据存放于单台机器上，但是不能将数百TB的数据存放于单台机器上。为了能支持超过10TB数据的大型数据库。Amazon的做法是将数据库的数据，分割存储到多组存储服务器上，每一组都是6个副本，分割出来的每一份数据是10GB，简单理解就对数据做Sharding。所以，如果一个数据库需要20GB的数据，那么这个数据库会使用2个PG（Protection Group），其中一半的10GB数据在一个PG中，包含了6个存储服务器作为副本，另一半的10GB数据存储在另一个PG中，这个PG可能包含了不同的6个存储服务器作为副本。

故障恢复优化：

如果其中一个存储服务器挂了，我们期望尽可能快的用一个新的副本替代它。因为如果4个副本挂了，我们将不再拥有Read Quorum，我们也因此不能创建一个新的副本。所以我们想要在一个副本挂了以后，尽可能快的生成一个新的副本。表面上看，每个存储服务器存放了某个数据库的某个某个Protection Group对应的10GB数据，但实际上每个存储服务器可能有1-2块几TB的磁盘，上面存储了属于数百个Aurora实例的10GB数据块。所以在存储服务器上，可能总共会有10TB的数据，当它故障时，它带走的不仅是一个数据库的10GB数据，同时也带走了其他数百个数据库的10GB数据。所以生成的新副本，不是仅仅要恢复一个数据库的10GB数据，而是要恢复存储在原来服务器上的整个10TB的数据。我们来做一个算术，如果网卡是10Gb/S，通过网络传输10TB的数据需要8000秒。这个时间太长了，我们不想只是坐在那里等着传输。所以我们不想要有这样一种重建副本的策略：找到另一台存储服务器，通过网络拷贝上面所有的内容到新的副本中。我们需要的是一种快的多的策略。

Aurora采用一种并行恢复的方式，当一个服务器故障时，只需要找到这个故障服务器上所有数据块的其他副本，然后这些正常的副本再去寻找新的物理机，并同时进行拷贝，简单理解：100份故障副本同时进行自身的拷贝，且拷贝到不同的机器上，最后将新的数据块加入到PG注册表中。

扩展性

Aurora由于引入了数据分片的策略，在存储能力上理论上根据数据的Sharding可以做到随着机器数量增加而线性增加，在数据写入上，由于是采用Quorum，Write Quorum的增加理论上会减少写入性能，增加容错性；在数据读取上，由于需要满足 Read Quorum数量的读取，所以和写一样，机器数量越多则理论上等待的时间就越久。所以这里可以看出来，在Quorum下扩展性与容错是冲突的目标，Quorum的目标就是为了容错，为了实现Quorum，Aurora不得不选择牺牲性能。综合：存储能力随着机器数量线性增长，读写能力随着机器数量缓慢下降

容错

由于Aurora采用副本机制，并且按照Quorum系统设计，提供了3个AZ，如果主数据库的AZ发生了崩溃，可能直接切换到其他可用AZ上，容错也得到了保障

一致性

Aurora在写上，必须达成Write Quorum才算完毕，读必须满足Read Quorum且取了最大版本号的数据，所以一致性也得到了保证

七、缓存一致性-Frangipani(论文:Frangipani)

7.1 大致结构

从整体架构上来说，Frangipani就是一个网络文件系统（NFS，Network File System）。它的目标是与已有的应用程序一起工作，比如说一个运行在工作站上的普通UNIX程序。从一个全局视图来看，它包含了大量的客户端（Client1，Client2）。每一个客户端运行了一个Frangipani服务，在该服务商运行了一些需要应用程序，比如说一个普通的文本编辑（VI）或者说一个编译程序（CC）。当这些普通的应用程序执行文件系统调用时，在系统内核中，有一个Frangipani模块，它实现了文件系统。在所有的工作站中，都有类似的结构。文件系统的数据结构，例如文件内容、inode、目录、目录的文件列表、inode和块的空闲状态，所有这些数据都存在一个叫做Petal的共享虚拟磁盘服务中。Petal运行在一些不同的服务器上，有可能是机房里面的一些服务器，但是不会是人们桌子上的工作站。Petal会复制数据，所以你可以认为Petal服务器成对的出现，这里为了简化阐述原理就只画了一个Petal，这样就算一个故障了，我们还是能取回我们的数据。当Frangipani需要读写文件时，它会向正确的Petal服务器发送RPC，并说，我需要这个块，请读取这个块，并将数据返回给我。在大部分时候，Petal表现的就像是一个磁盘，你可以把它看做是共享的磁盘，所有的Frangipani都会与之交互。细节上，Frangipani内部有一个Petal的数据缓存，Petal有一个数据表单，用以存储数据，并且Petal还存在一个锁资源表单(估计认为这个锁资源在Petal上)，用来记录操作数据对应的锁正在被哪个Client所持有。

介绍 Frangipani之前，先说一下缓存一致性协议：

7.2 Frangipani工作流程

如上图，根据上述的缓存一致性协议，对两个两单的操作过程进行分析，现在有一个表单Key1原始值为1，Client 1与Client 2对Key1分别进行+100操作，最后Key1的结果就是201，Frangipani协议工作的过程大致可以用九个流程进行阐述：

八、分布式事务之两阶段提交相关阅读:OnlineBook)

8.1 大致结构

两阶段提交(2PC)不仅被分布式数据库所使用，同时也被各种看起来不像是传统数据库的分布式系统所使用。通常情况下，我们需要执行的任务会以某种方式分包在多个服务器上，每个服务器需要完成任务的不同部分。我们将会假设，有一个计算机会用来管理事务，它被称为事务协调者（Transaction Coordinator）。事务协调者有很多种方法用来管理事务，我们这里就假设它是一个实际运行事务的计算机。在一个计算机上，事务协调者以某种形式运行事务的代码，例如Put/Get/Add，它向持有了不同数据的其他计算机发送消息，其他计算机再执行事务的不同部分。这些持有数据并参与事务实际执行的服务器被称为参与者（Participants）。

所以，在2PC的配置中，我们有一个计算机作为事务协调者（Transaction Coordinator），还有多个持有数据的实际事务参与者(Participants)

8.2 2PC的流程

关于2PC，相关的介绍已经很多，作者在这里主要详细讨论一下2PC的执行流程，以及这些执行过程中可能出现的异常情况和如何处理，这里假定事务参与者C1拥有数据X=10，事务参与者C2拥有数据Y=20，事务参与者C3拥有数据Z=30，现在执行“转账”操作，对X减2，Y加1，Z加1。

首先我们对结果进行预判，由于事务的原子性，对这两个数据进行同时读取时，只有可能存在两种结果：1. 在事务开始前进行了读取，这时候读取的数据 X=10，Y=20，Z=30；2. 在事务过程中以及事务完毕后进行了读取，事务过程中读取会被阻塞知道事务完毕所以和事务完毕后结果一致，X=8，Y=21，Z=31;除了这两种结果，其他任何结果都是非法结果。从下图看一下2PC的详细流程

上述步骤中可能出现的异常情况有很多，大部分故障都可以通过在回复ACK消息，或者在发送Commit消息前，将状态持久化到本地磁盘后，后续故障及其再进行重启或者其他恢复措施并重试来解决。这里笔者只介绍一种比较致命的故障。

这边讨论一种情况：假设C2收到了Prepare消息，并回复了准备就绪ACK。但是这个时候C2没有收到Commit消息，它接下来怎么也等不到Commit消息。或许网络出现问题了，或许TC的网络连接中断了，或者TC断电了，不管什么原因，TC等了很长时间都没有收到Commit消息。这段时间里，B一直持有事务涉及到数据的锁，这意味着，其他事务可能也在等待这些锁的释放。所以，这里我们应该尽早的Abort事务，并释放锁。所以这里的问题是，如果B收到了Prepare消息，并回复了Yes，在等待了10秒钟或者10分钟之后还没有收到Commit消息，它能单方面的决定Abort事务吗？

很不幸的是，这里的答案不行。

原因：在回复Yes给Prepare消息之后，并在收到Commit消息之前这个时间区间内，参与者会等待Commit消息。如果等待Commit消息超时了，参与者不允许Abort事务，它必须无限的等待Commit消息，这里通常称为Block。这里的原因是，因为B对Prepare消息回复了Yes，这意味着事务协调者可能收到了来自于所有参与者的Yes，并且可能已经向部分参与者发送Commit消息。这意味着C1可能已经看到了Commit消息，Commit事务，持久化存储事务的结果并释放锁。所以在上述场景里，C2不能单方面的决定Abort事务，它必须无限等待事务协调者的Commit消息。如果TC故障了，最终会有人来修复它，它在恢复过程中会读取Log，并重发Commit消息。

就像不能单方面的决定Abort事务一样，这里C2也不能单方面的决定Commit事务。因为C1可能对Prepare消息回复了No，但是B没有收到相应的Abort消息。所以，在上面的区间中，B既不能Commit，也不能Abort事务。

这里的Block行为是两阶段提交里非常重要的一个特性，并且它不是一个好的属性。因为它意味着，在特定的故障中，会很容易的陷入到一个需要等待很长时间的场景中，在等待过程中，你会一直持有锁，并阻塞其他的事务。所以，人们总是尝试在两阶段提交中，将这个区间尽可能快的完成，这样可能造成Block的时间窗口也会尽可能的小。所以人们尽量会确保协议中这部分尽可能轻量化，甚至对于一些变种的协议，对于一些特定的场景都不用等待。

这就是基本的协议。为什么这里的两阶段提交协议能构建一个要么全Commit，要么全Abort的系统？其中一个原因是，决策的TC是在一个单一的实例，也就是事务协调者完成的。参与者不能决定Commit还是不Commit事务，参与者之间不会交互来达成一致并完成事务的Commit，相反的只有TC可以做决定。TC是一个单一的实例，它会通知其他的部分这是我的决定，请执行它。但是，使用一个单一实例的TC的缺点是，在某个时间点你需要Block并等待TC告诉你决策是什么。

思考：当发生上述故障时，原子性还会得到保证吗？

上述故障发生时，由于C2一直不能收到Commit消息，导致C2一直持有对于Y的锁，且需要一直等待结果，不能提交或者放弃事务。但是C1/C3却已经收到了Commit消息，并且对事务进行了提交。这时候看数据：X=8，Y=20，Z=31；看上去并不符合原子性。其实是符合原子性的。在分布式场景下，因为对于C2而言，对于Y的锁一直没有释放，对于C2的任何读写操作都会被阻塞，对外也不会返回Y=20的数据。对于C1/C3而言现在是可以对外返回的，因为此时C2已经发生了故障，且必须人为手工处理，人为手工处理就必须让C2收到响应的Commit消息，让C2得到正确的执行。或者完全手工恢复C1/C2/C3全部数据。但是仅从原子性上看，C2在恢复后在系统上必须按照Commit的逻辑进行执行并释放对Y得锁。

参考引用