一、简介

1.1 序言

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

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

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

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

  1. 人们需要获得更高的计算性能。可以这么理解这一点，大量的计算机意味着大量的并行运算，大量CPU、大量内存、以及大量磁盘在并行的运行。而单台机器并不能做到无限添加CPU，内存等物理资源。
  2. 另一个人们构建分布式系统的原因是，我们需要能够支持容错（tolerate faults）的系统，比如两台计算机运行完全相同的任务，其中一台发生故障，可以切换到另一台，如果是单机服务，发生断电，系统故障时，那么整个系统服务便不可用，直到有人手动来处理问题并重启服务。在金融，电力，通信等某些重要场景中，每一秒钟的系统瘫痪便会造成几百万，甚至千万级的损失。所以在某些重要场景中，采用分布式系统的目标便是为了实现容错，在某些相当重要的场景，甚至会为了容错牺牲部分性能。
  3. 第三个原因是，一些问题天然在空间上是分布的。例如银行转账，我们假设银行A在纽约有一台服务器，银行B在伦敦有一台服务器，这就需要一种两者之间协调的方法。所以，有一些天然的原因导致系统是物理分布的。
  4. 最后一个原因是，人们构建分布式系统来达成一些安全的目标。比如有一些代码并不被信任，但是你又需要和它进行交互，这些代码不会立即表现的恶意或者出现bug。你不会想要信任这些代码，所以你或许想要将代码分散在多处运行，这样你的代码在另一台计算机运行，我的代码在我的计算机上运行，我们通过一些特定的网络协议通信。所以，我们可能会担心安全问题，我们把系统分成多个的计算机，这样可以限制出错域。

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

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

  1. 因为系统中存在很多部分，这些部分又在并发执行，你会遇到并发编程和各种复杂交互所带来的问题，以及时序、同步、异步等问题。这让分布式系统变得很难。
  2. 另一个导致分布式系统很难的原因是，分布式系统有多个组成部分，再加上计算机网络，你会会遇到一些意想不到的故障。如果你只有一台计算机，那么它通常要么是工作，要么是故障或者没电，总的来说，要么是在工作，要么是没有工作。而由多台计算机组成的分布式系统，可能会有一部分组件在工作，而另一部分组件停止运行，或者这些计算机都在正常运行，但是网络中断了或者不稳定。所以，局部错误也是分布式系统很难的原因。
  3. 最后一个导致分布式系统很难的原因是，人们设计分布式系统的根本原因通常是为了获得更高的性能，比如说一千台计算机达到的性能。但是实际上一千台机器到底有多少性能是一个棘手的问题，这里有很多难点。所以通常需要倍加小心地设计才能让系统实际达到你期望的性能。

1.3 可扩展性

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

1.4 可用性(容错)

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

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

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

  1. 采用非易失存储，比如磁盘，磁盘将数据进行永久的物理存储。但使用磁盘会引起性能问题
  2. 采用复制，比如多副本机制，如果一个副本挂了，采用另一个副本提供服务。但多副本会引起数据一致性问题。

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目标

  1. 构建一个大型的，快速的文件系统
  2. 并且这个文件系统是全局有效的，这样各种不同的应用程序都可以从中读取并共享数据。
  3. 只在一个数据中心运行
  4. 为TB级别的文件而生，只进行顺序处理，不支持随机访问。关注于巨大的吞吐量上，单次操作都涉及到MB级别的数据。
  5. 支持对文件进行分割存储，这样读取时，可以多部分同时读取，已提升吞吐量

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

2.3 GFS文件读取过程

  1. Client需要访问指定文件的指定位置的内容时，向GFS Master发送读取请求，请求包含文件名+访问的数据偏移Offset
  2. Master阶段根据文件名，根据内部的文件-ChunkID 表单，获取到这个文件所有的Chunk ID列表，以及Chunk服务器信息，再根据偏移的Offset计算出请求数据所在Chunk位置,这里假设是位于Chunk 2
  3. Master将计算得到的ChunkID以及所在Chunk服务器信息，比如IP信息等返回给Client(这里可能存在数据跨越Chunk的情况，这里不做讨论，感兴趣的可以再研究)
  4. Client获取到待访问数据的ChunkID及其所在服务器信息后，将这些信息缓存在本地的Chunk列表中，因为Client可能后续会多次读取同一个Chunk信息，存在本地缓存中这可以减少从Master的交互
  5. Client 与 Chunk2 建立通信，传输给Chunk 2所在服务器所需文件的chunk ID与偏移量，Chunk服务器返回相应数据

2.4 GFS文件写入过程

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

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

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

  1. Client查询Master节点，申请追加数据，并申请向哪一个Chunk 服务器执行追加，并且获取新追加数据的Chunk ID
  2. Master扫描出最后一个Chunk ID的文件所在位置，查询出该Chunk ID的所有最新副本(版本号与Master保存的版本相同的副本)，准备在其文件后追加文件。
  3. Master首先下发消息到最新的Chunk中，告诉其最新的版本号，当所有的Chunk都更新后，Master将进行追加的Chunk服务器信息及其所有的副本发送给Client
  4. Client与主Chunk，及其副本建立通信执行追加操作。


可扩展性：

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

容错：

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

一致性：

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

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

  1. Client 1发出写入数据A请求，这时候对于Chunk都写入成功了
  2. Client 2然后发出写入数据B请求，但是由于网络问题，导致Chunk3未写入成功，给Client 2返回了写入失败
  3. Client 3发出写入数据C请求，由于Client 3知道主Chunk写完后的偏移量，那么数据C正常地写入了多个Chunk对应的Offset位置中
  4. Client 2 由于第一次写入B失败，发起重试写入B，于是在C后插入了B
  5. Client 4 发起写入D，但是Chunk 2写入失败了，在发起重试前，客户端下线了，对于Chunk 2来说，数据D永远丢失

在上面的时序中

  • 如果在阶段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节点，会带来以下问题：

  1. Master节点必须为每个文件，每个Chunk维护表单，随着GFS的应用越来越多，这意味着涉及的文件也越来越多，最终Master会耗尽内存来存储文件表单。你可以增加内存，但是单台计算机的内存也是有上限的。所以，这是人们遇到的最早的问题。
  2. 除此之外，单个Master节点要承载数千个客户端的请求，而Master节点的CPU每秒只能处理数百个请求，尤其Master还需要将部分数据写入磁盘，很快，客户端数量超过了单个Master的能力。
  3. 另一个问题是，应用程序发现很难处理GFS奇怪的语义（本节最开始介绍的GFS的副本数据的同步，或者可以说不同步）。
  4. 最后一个问题是，在GFS论文中，Master节点的故障切换不是自动的。GFS需要人工干预来处理已经永久故障的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的读取过程

  1. 对于一致性要求高的读请求，走Leader节点读取即可，Raft的读取过程比较简单，没有什么特殊性，Leader直接对外提供数据读取能力即可

3.3 Raft的写入过程

  1. Client 向 Leader服务发起K/V更新请求
  2. Leader 应用层服务收到请求后，调用Raft层接口，用于持久化本次更新需要持久化的日志，此时客户端的请求阻塞，等待Raft层接口返回成功为止
  3. Raft查看下一个日志能插入的索引位置，然后向指定的索引位置，插入Log信息，该Log信息包含Leader的任期号，以及本次需要持久化的日志真实数据
  4. 本地插入日志之后，Raft Leader向所有的Raft Follower发送Log日志，让所有的Raft 也插入该日志
  5. 注意：这里同步给副本的Log日志与Leader插入本地的日志格式上并不一样，该日志除了包含本次的Log Data和任期号，及存储的Index，还会携带该Log的上一个index的同样的信息，关于这个细节在论文以及Robbert教授的讲解中并没有特意强调。但是能从论文的一些细节中大致得出该结论，目的是为了解决Log的时序同步和完整性问题
  6. Raft Follower在收到Leader的Log日志后，首先会比对上一条LogData与本地对应的Log index的做对比，如果Log Data与Leader任期号相同，则执行此次更新，如果不同则返回拒绝给Leader节点，Leader节点则继续回溯上上条日志，依此类推，知道匹配到Leader任期号与日志数据为止，然后执行日志中的更新操作
  7. Raft Follower更新完毕后，返回日志插入完成给Raft Leader节点
  8. 当Raft Leader节点收到超过一半Follower节点更新完毕的回复后，Raft Leader节点将会提交该请求的持久化日志，并发送提交消息给各副本
  9. 返回操作成功给应用层服务，应用层更新内存值

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

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

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

  1. 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号
  2. 或者，候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号，且候选人的Log记录长度大于等于本地Log记录的长度

这里简述一下上述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的大致架构

  1. 与Raft比较类似，ZK也是的多副本架构，即一个主节点，并采用多个副本节点来实现容错
  2. 在数据管理上，ZK内部是通过ZNode的方式来管理数据，这里为了简化理解，我们仍然认为ZNode存储的表单数据
  3. 与Raft不同的是，ZK是一个具体的应用，底层是通过ZAB组件来实现分布式协调，在层级上，Raft与ZAB类似，属于底层Lib组件，其上层可以架设任何业务应用，而ZK则是完整的分布式应用
  4. 对于请求处理上，ZK SDK里的Client和ZK Server的均有一个FIFO请求队列池；在Client中按照FIFO的方式对请求队列中的请求向ZK Server发送；而在ZK Server中则会将收到的请求也放在本地的请求队列池中，然后按照FIFO的方式对请求进行串行处理
  5. Raft的读写都是走的主节点，其副本只是为了容错存在，不参与任何读写请求，这样就能保证数据的一致性，但是摒弃了扩展性；而ZK则是写请求走主节点，读请求走的副本节点，这就意味着在数据读取上是满足扩展性性的，更多的副本就支持更强大的数据读取能力；但是读取副本也意味着ZK在读请求上并不能保证线性一致性
  6. 虽然ZK在读请求上并不能保证一致性，但是ZK在数据读取上做了特殊的处理，能保证虽然读取的数据虽然有可能是旧的，但又不是“太旧”；还支持原子化对多个数据的更新，即原子化更新，并且保证读取是操作不会读取原子更新的中间状态(即保证: 不会读取到原子更新的过程值，类似于事务特征)，而实现方式就是通过图中的数据的Watch表单，以及Client本地存取的已知最新Log ID进行实现，下文会针对原子更新实现方式进行详细阐述

4.2 ZK的写入过程

  1. 正如前文所说，Client发起写入请求时，只会向Master发起，而Master收到后，会将请求放在请求队列池中，然后按照FIFO的方式对请求队列池中的请求进行处理
  2. Master在收到更新请求后，首先对该请求生成对应的日志，该日志具备一个自增属性的ID，该ID值由ZK在生成日志时进行生成，在本地存取日志后，再将该日志发送给其他副本。
  3. 在日志存储完毕后，首先会对指定数据的Key进行加锁，然后对数据执行更新，更新完毕后，再释放锁(在ZK中的加锁，实际上是删除Key所在的ZNode的就绪文件，更新操作会删除这个就绪文件，更新完毕后再重建其就绪文件，只有就绪文件存在才能对这个ZNode执行读写操作，否则就必须等待就绪文件重新生成，删除就绪文件相当于对指定ZNode的数据进行加锁，重建指定ZNode的就绪文件相当于释放指定ZNode的数据的锁，关于ZK中的就绪文件是什么，有兴趣的同学自行查阅)
  4. 其他副本收到这个数据更新的日志后，首先对日志内容进行解析，这里有一个细节点，副本首先会查看本地的数据Watch表单看本次日志更新的数据是否存在Watch的Client，如果存在则对这些Client发送通知，告知这些Client这个值发生了改变
  5. 在通知发送之后然后再将这条日志插入到本地的日志列表中，然后执行与Master一样的操作，对Key的ZNode的就绪文件进行删除，然后按照日志进行更新，再重建这个就绪文件
  6. Master返回给Client本次更新请求操作成功，返回给Client的消息中会带有步骤2生成的日志的ID字段值，相当于告知客户端本次更新对应的操作序列号

4.3 ZK的读取过程

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

客户端对key 1进行更新操作，更新成功，得到最新的Log ID

客户端发起Key 1读取请求，该请求还会携带Client刚刚获取到的最新的Log ID

假设副本1对其进行了响应，副本1首先会将客户端记录在Key 1的数据Watch表单中

对付副本1来说，这里存在两种情况

  1. 副本1比对请求中的Log ID与本地最新日志的ID值，如果副本1本地最新日志的ID大于等于本次请求中的Log ID值，证明客户端想要读取的值相对于客户端的上一次更新来说已经被其他客户端也更新了很多次了，即副本中存的值比客户端想要的要新，这种情况下，副本1会直接返回Key 1的值，并且会携带上最新的Log ID，客户端也会同步更新本地的Log ID
  2. 还有可能，副本1本地最新日志的ID小于本次请求中的Log ID值，即副本1并没有获取到最新的更新日志，副本本地Key 1的值对于客户度来说是一个旧值，这时候副本1知道这个值相较于本地来说一定更新过，只是同步日志还没被同步到本地，所以本地的这个值不能返回给客户端，副本1会在超时之前一直等待直到相应的更新日志被同步到本地后，且日志中的ID大于等于请求中的Log ID时，才将更新后的值返回给客户端。

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

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

  1. Client 1发起Key 1更新，发送 Set Key 1 = 1请求，更新完毕后，得到最新的Log ID=100，并且记录在本地中
  2. Key = 1,Log ID = 100的日志同步到副本中，副本也完成相应的数据更新和日志存储
  3. 这时Client 2发起Key 1更新，发送Set key 1= 2请求，更细完毕后，得到最新的Log ID = 101，记录在本地中
  4. Client 2再次发起Key 1读取请求，发送Get Key 1，并携带刚刚获取到的最新Log ID=101的请求给副本
  5. 这时候假设副本还没有收到Master发送的Set Key 1 = 2的请求的同步日志，所以这时副本中Key 1的值仍然是1
  6. 副本接收到Client 2的请求，发现请求Key 1的Log ID=101，比本地的最新日志要大，说明Key 1已经被更新过，只是日志还没同步到本地，这时候副本会等到同步日志到达本地后，将日志更新到数据上之后，再将结果返回给Client 2

在步骤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支持的原子更新特征

Client 1发起更新操作，本次更新包含两个更新操作，即：Set Key1=1、Set Key2=2

Master响应该请求后，操作完成，返回了本次操作的最新Log ID=100给Client 1，Client 1将Log ID=100也存储在本地

Master将本次操作的日志同步给了副本，副本收到了日志后，也完成了相应的更新操作，设置Key1=1、Key2=2

然后Client 1发起读取请求，本次读取请求包含两个数据同时读取，即：Get Key1、Get Key2，Log ID = 100；

与此同时，Client 2发起了一次更新请求，本次请求包含两个更新操作，即：Set Key1=3、Set Key2=4；Master更新完毕后，设置Key1=3、Key2=4，并且发送同步日志给副本

对于Client 1的读取请求，这里根据Client 2日志执行的到达情况，可能会有不同的响应。先看看Client 1能够接受的合法响应有哪些，由于 Key 1/Key2的更新是原子更新，那么就意味着Key1/Key2要么同时都不更新，然后返回给Client 1，即返回：Key1=1，Key2=2；要么都更新成功再返回给Clieng 1，即返回：Key1=3，kye2=4；不能允许出现其他情况

  1. 假如Client 2发起的更新请求这时候还没有到达副本，这时候副本比对Log ID，刚好等于Client 1请求中的数值，直接返回Key1=1，Key2=2给Client 1。再给Client 1响应完成后，副本才收到Client 2的更新日志。这种情况Client 1收到的是Key1=1，Key2=2合法的输出，所以这种情况是没问题的，满足ZK协议中的弱一致性，也满足原子原子更新
  2. 假如日志在Client 1的读取请求之前到达副本，并且完成了Key1/Key2的更新操作，这时候副本中Key 1=3，Key 2=4，日志也完全存储完毕，副本状态与Master的状态完全一致。这时候副本响应给Client 1的结果为 Key 1 = 3，Key 2 = 4。这种结果也是符合ZK协议中的弱一致性，而且拿到的是最新的数据，也满足了原子更新
  3. 假如Client 1在刚刚读取完Key 1=1后，在准备读取Key2之前，Client 2修改数据的日志到达副本，由于需要修改Key1/Key2，副本则对Key1/Key2进行加锁，Client 1读取Key2暂时被阻塞，等待Key2的锁释放，待副本将日志的内容解析并应用后，Key1/Key2的值得到更新，并且释放了Key1/Key2的锁，Client 1的读取请求得以继续进行，这时候再读取Key2，Key2=4。那么Client 1理论上会得到的回复是：Key1=1，Key2=4。这并不在两个合法结果中的任何一个。这显然是不对的。

针对6.c中的问题，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不一样的拓扑结构，具有以下特点：

  1. 在Chain Replication(CR)中，有一些服务器按照链排列。第一个服务器称为HEAD，最后一个被称为TAIL
  2. 当客户端想要发送一个写请求，写请求总是发送给HEAD，读请求总是发给Tail
  3. 当HEAD收到了写请求，根据写请求更新本地数据，之后会再将写请求通过链向下一个服务器传递
  4. 下一个服务器执行完写请求之后，再将写请求向下一个服务器传递，以此类推，所有的服务器都可以看到写请求
  5. 当写请求到达TAIL时，TAIL将回复发送给客户端，表明写请求已经完成了。这是处理写请求的过程
  6. 对于读请求，如果一个客户端想要读数据，它将读请求发往TAIL，TAIL直接根据自己的当前状态来回复读请求。读请求处理的非常的简单

5.2 链式复制的容错

如果HEAD出现故障，作为最接近的服务器，下一个节点可以接手成为新的HEAD，并不需要做任何其他的操作。对于还在处理中的请求，可以分为两种情况：

  1. 对于任何已经发送到了第二个节点的写请求，不会因为HEAD故障而停止转发，它会持续转发直到commit。
  2. 如果写请求发送到HEAD，在HEAD转发这个写请求之前HEAD就故障了，那么这个写请求必然没有commit，也必然没有人知道这个写请求，我们也必然没有向发送这个写请求的客户端确认这个请求，因为写请求必然没能送到TAIL。所以，对于只送到了HEAD，并且在HEAD将其转发前HEAD就故障了的写请求，我们不必做任何事情。或许客户端会重发这个写请求，但是这并不是我们需要担心的问题。

如果TAIL出现故障，处理流程也非常相似，TAIL的前一个节点可以接手成为新的TAIL。所有TAIL知道的信息，TAIL的前一个节点必然都知道，因为TAIL的所有信息都是其前一个节点告知的。

中间节点出现故障会稍微复杂一点，但是基本上来说，需要做的就是将故障节点从链中移除。或许有一些写请求被故障节点接收了，但是还没有被故障节点之后的节点接收，所以，当我们将其从链中移除时，故障节点的前一个节点或许需要重发最近的一些写请求给它的新后继节点。这是恢复中间节点流程的简单版本

5.3 CR与Raft的对比

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

  1. 从性能上看，对于Raft，如果我们有一个Leader和一些Follower。Leader需要直接将数据发送给所有的Follower。所以，当客户端发送了一个写请求给Leader，Leader需要自己将这个请求发送给所有的Follower。然而在Chain Replication中，HEAD只需要将写请求发送到一个其他节点。数据在网络中发送的代价较高，所以Raft Leader的负担会比Chain Replication中HEAD的负担更高。当客户端请求变多时，Raft Leader会到达一个瓶颈，而不能在单位时间内处理更多的请求。而同等条件以下，Chain Replication的HEAD可以在单位时间处理更多的请求，瓶颈会来的更晚一些。
  2. 另一个与Raft相比的差别是，Raft中读请求同样也需要在Raft Leader中处理，所以Raft Leader可以看到所有的请求。而在Chain Replication中，每一个节点都可以看到写请求，但是只有TAIL可以看到读请求。所以负载在一定程度上，在HEAD和TAIL之间分担了，而不是集中在单个Leader节点。
  3. 前面分析的故障恢复，Chain Replication也比Raft更加简单。这也是使用Chain Replication的一个主要动力。
  4. 在链式复制中，如果有一个节点非常慢，则会导致整个系统变慢，所有节点都需要等待该节点完成写入才能继续往下执行。而Raft不用等待
  5. 链式复制无法抵御网络分区，即无法抵御脑裂问题，当Head与后续节点无法通信时，Head会认为后续节点故障而自己作为即作为Head又作为Tail节点，而原本的第二个节点则会认为是Head发生了故障，自己接管Head的能力，这时候整个系统就存在两个Head节点，这是不能接受的。所以链式复制是一个有用的方案，但是它不是一个完整的复制方案。它在很多场景都有使用，但是会以一种特殊的方式来使用。总是会有一个外部的权威（External Authority）来决定谁是活的，谁挂了，并确保所有参与者都认可由哪些节点组成一条链，这样在链的组成上就不会有分歧。这个外部的权威通常称为Configuration Manager。
  6. Configuration Manager通常会基于Raft或者Paxos。在CRAQ的场景下，它会基于Zookeeper。而Zookeeper本身又是基于类似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向某个副本发送读取时会存在以下情况

假如副本中没有Dirty版本的数据，说明这时没有更新请求，Tail更不能更新，本地的Clean版本的数据可以直接进行返回

假如本地的副本中有Dirty版本的数据，说明已经有了更新操作，但是该副本并不知道Tail是否也执行这个更新操作，这里也存在两种情况

  1. Tail 可能还未收到这个更新请求，这时请求Tail这个值的版本号肯定就是Clean版本，所以需要返回Clean版本
  2. Tail可能已经执行了这个更新请求，但是回传的消息还没到到该副本，导致该副本伤的Dirty版本未得到更新，但是全局来看，此时数据的Dirty版本才是Clean版，只是消息没到到副本未更新而已，所以这时应该返回Dirty版本的值。

通用以上优化，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是一次很大的进步，但是它仍然有自己的问题。它有一些细节不是那么的完美：

  1. 如果你在EBS上运行一个数据库，那么最终会有大量的数据通过网络来传递(传输的物理磁盘的页数据，每次传输在8KB以上)。所以，如果在EBS上运行了一个数据库，会产生大量的网络流量。除了网络的限制之外，还有CPU和存储空间的限制。在Aurora论文中，花费了大量的精力来降低数据库产生的网络负载，同时看起来相对来说不太关心CPU和存储空间的消耗。所以也可以理解成他们认为网络负载更加重要。
  2. 另一个问题是，EBS的容错性不是很好。出于性能的考虑，Amazon总是将EBS volume的两个副本存放在同一个数据中心。所以，如果一个副本故障了，那没问题，因为可以切换到另一个副本，但是如果整个数据中心挂了，那就没辙了。很明显，大部分客户还是希望在数据中心故障之后，数据还是能保留的。数据中心故障有很多原因，或许网络连接断了，或许数据中心着火了，或许整个建筑断电了。用户总是希望至少有选择的权利，在一整个数据中心挂了的时候，可以选择花更多的钱，来保留住数据。 但是Amazon描述的却是，EC2实例和两个EBS副本都运行在一个AZ（Availability Zone）。Amazon通常在一个城市范围内有多个独立的数据中心。大概2-3个相近的数据中心，通过冗余的高速网络连接在一起，我们之后会看一下为什么这是重要的。但是对于EBS来说，为了降低使用Chain Replication的代价，Amazon 将EBS的两个副本放在一个AZ中。

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这么设计的容错目标是：

  1. 首先是对于写操作，当只有一个AZ彻底挂了之后，写操作不受影响。
  2. 其次是对于读操作，当一个AZ和一个其他AZ的服务器挂了之后，读操作不受影响。这里的原因是，AZ的下线时间可能很长，比如说数据中心被水淹了。人们可能需要几天甚至几周的时间来修复洪水造成的故障，在AZ下线的这段时间，我们只能依赖其他AZ的服务器。如果其他AZ中的一个服务器挂了，我们不想让整个系统都瘫痪。所以当一个AZ彻底下线了之后，对于读操作，Aurora还能容忍一个额外服务器的故障，并且仍然可以返回正确的数据。至于为什么会定这样的目标，我们必须理所当然的认为Amazon知道他们自己的业务，并且认为这是实现容错的最佳目标。
  3. Aurora期望能够容忍暂时的慢副本。如果你向EBS读写数据，你并不能得到稳定的性能，有时可能会有一些卡顿，或许网络中一部分已经过载了，或许某些服务器在执行软件升级，任何类似的原因会导致暂时的慢副本。所以Aurora期望能够在出现短暂的慢副本时，仍然能够继续执行操作。
  4. 最后一个需求是，如果一个副本挂了，在另一个副本挂之前，是争分夺秒的。统计数据或许没有你期望的那么好，因为通常来说服务器故障不是独立的。事实上，一个服务器挂了，通常意味着有很大的可能另一个服务器也会挂，因为它们有相同的硬件，或许从同一个公司购买，来自于同一个生产线。如果其中一个有缺陷，非常有可能会在另一个服务器中也会有相同的缺陷。所以，当出现一个故障时，人们总是非常紧张，因为第二个故障可能很快就会发生。对于Aurora的Quorum系统，有点类似于Raft，你只能从局部故障中恢复。所以这里需要快速生成新的副本（Fast Re-replication）。也就是说如果一个服务器看起来永久故障了，我们期望能够尽可能快的根据剩下的副本，生成一个新的副本。

为了实现上述目标，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之前，先说一下缓存一致性协议：

  1. 客户端不允许持有缓存的数据，除非同时也持有了与数据相关的锁。所以基本上来说，不允许在没有锁保护的前提下缓存数据。从操作意义上来说，这意味着对于一个客户端来说，在它使用一个数据之前，它首先要从锁服务器获取数据的锁。只有当客户端持有锁了，客户端才会从Petal读取数据，并将数据放在缓存中，并且释放锁之后本地的缓存需要清空。所以这里的顺序是，获得锁，之后再从Petal读取数据。所以，直到获取了锁，工作站是不能缓存数据的，要想缓存数据，工作站必须先持有锁，之后，才能从Petal读取数据。
  2. 如果你在释放锁之前，修改了锁保护的数据，那你必须将修改了的数据写回到Petal，只有在Petal确认收到了数据，你才可以释放锁，也就是将锁归还给锁服务器。所以这里的顺序是，先向Petal存储系统写数据，之后再释放锁。

7.2 Frangipani工作流程

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

根据Frangipani的协议，Client首先申请操作Key1的锁资源，由于目前Key1的锁现在是空闲的，所以Client1占据Key1的锁成功，并且Client1在本地记录上对于Key1拥有锁

Client1拿到了Key1的锁之后，向Petal发送Get(Key1)请求，获取到值后，Client1将Key1=1缓存至本地的数据表单

Client1对本地Key1=1的缓存执行+100的计算，将本地Key1的缓存更新为101

注意，这次Client1更新完毕后并没有释放Client1的锁，而是将锁的状态在本地标记为空闲状态，但是Client1仍然持有对于Key1的锁，只是不进行更新操作而已，你可能会问这样的话其他Client需要获取这个Key的操作权限时岂不是需要通知Client1将锁释放，如果操作完就释放岂不是更方便。操作完仍然不放弃Key1的原因有两个：

  1. 如果每次更新完都要释放锁，那如果Client1如果下一次还需要更新的话，则又要与Petal走一遍获取Key1锁的过程，这个过程是网络IO及其影响性能，因为在真实世界，大部分操作都是相关的，或者相近的，可以简单理解为这是一种贪心法的取舍，因为Client 1操作了Key1，大概率在接下来的时序中，Client1还会继续操作Key1。即大部分对于Key1进行操作的客户端都是聚合的，非离散的。如果说这个系统面向的业务，对于一个Key的操作大部分是离散的而非聚合的，那么个人认为，操作完后立即释放锁才是更好的选择。这个策略在现在目前的多核CPU，多级缓存是类似的思想。
  2. 根据协议，如果要释放锁，在释放锁之前，需要将本地的修改同步到Petal中，这个操作是损耗性能的。所以Frangipani的作者选择不释放锁，只要在其他客户端需要这个数据的时候，才将数据同步给Petal并释放锁，这样可以将Client1对于Key1的多次操作通过一次网络IO进行发送

Client2准备执行更新Key1，需要先获取Key1的锁，Client2向Petal发送申请Key1的锁资源申请，通过锁资源表单，目前Key1的锁被Client1占有，于是Petal发送解锁通知给Client1

Client1收到解锁通知后，首先会看自己本地对于Key1的锁是否是空闲状态，如果是则先将本地Key1的最新数据发送给Petal进行更新，然后对Petal上Key1的值执行更新，然后清除本地的对于Key1的锁资源记录，最后后Client1释放Key1的锁。如果Client1记录本地的锁仍然是繁忙状态(仍然正在操作Key1)，则会直接拒绝Petal的解锁请求，那么Client2就无法获取Key1的锁，也无法对Key1进行操作

Client1释放Key1的锁之后，Client2获取Key1的锁并在锁服务上注册，Client2再在本地的锁资源表单中记录拥有Key1的锁资源

Client2从Petal获取Key1的值，此时Key1的值为101

Client2对Key1执行计算+100，将本地Key1的缓存更新为201，和Client1当时测策略一样，Key1=201这时仅存在于Client2的本地数据缓存上

为了防止对于Key1的请求长时间没有，Frangipani要求Client需要定时与Petal进行更新，防止Client2故障后下线，Client2的更新就永远丢失了，但是仍然可能存在Client2是突然故障的，导致上一次同步于本次故障之间的修改丢失

八、分布式事务之两阶段提交相关阅读: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的详细流程

  1. 首先客户端发起转账请求，向TC发起事务操作请求
  2. TC根据请求首先创建事务Log，该事务Log携带可以进行唯一标识的ID(TID)，后续的消息也都会携带上这个TID，然后将这个转账事务解析成Prepare消息，这里Prepare消息分成三部分，对于C1就是X=X-2，对于C2就是Y=Y+1，对于C3就是Z=Z+1，然后将Prepare消息发送给对应的参与者
  3. 参与者Prepare消息后，首先将该消息持久化到本地，然后执行是否可以进行操作的检查，并对所有需要的数据进行获取锁操作，准备执行事务。对于C1就是对X加锁，对于C2就是对Y加锁，对于C3就是对Z加锁。当参与者都检查通过，并获取到响应的锁资源后，参与者对TC回复准备就绪ACK，告知TC可以提交事务；否则参与者回复给TC准备失败，发送放弃(Abort)本次事务消息给TC
  4. TC等待所有的参与者回复消息，当任何一个参与者回复了Abort消息，TC都会发送Abort消息给所有的参与者，并放弃本次事务。当所有的参与者都回复了准备就绪的ACK，TC就会发送携带了TID的Commit消息给所有的参与者告知参与者可以进行提交操作。
  5. 参与者收到TC发送的Commit消息后，就会对Prepare消息中的描述的事务操作进行提交并持久化到磁盘中，当持久化完毕后，释放本次操作占有的锁资源，并删除本次事务消息(TID)所有相关的日志。知道此时，整个事务处理完毕。

上述步骤中可能出现的异常情况有很多，大部分故障都可以通过在回复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得锁。

参考引用

  1. 6.5840 Schedule: Spring 2023
  2. MIT 6.824 GitBook translated by 肖宏辉
  3. 端到端一致性,流系统Spark/Flink/Kafka/DataFlow对比总结(压箱宝具呕血之作)
  4. GFS
  5. Raft
  6. Zookeeper
  7. Aurora
  8. Frangipani
  9. OnlineBook