Distributed Systems Engineering

导论

人们使用分布式系统的驱动力是：

更高的计算性能。大量的计算机意味着大量的并行运算，大量CPU、大量内存、以及大量磁盘在并行的运行。
提供容错（tolerate faults）
一些问题天然在空间上是分布的。例如银行转账，我们假设银行A在纽约有一台服务器，银行B在伦敦有一台服务器，这就需要一种两者之间协调的方法。所以，有一些天然的原因导致系统是物理分布的。
达成一些安全的目标。比如有一些代码并不被信任，但是你又需要和它进行交互，这些代码不会立即表现的恶意或者出现bug。你不会想要信任这些代码，所以你或许想要将代码分散在多处运行，这样你的代码在另一台计算机运行，我的代码在我的计算机上运行，我们通过一些特定的网络协议通信。所以，我们可能会担心安全问题，我们把系统分成多个的计算机，这样可以限制出错域。

分布式系统的抽象和实现工具

需要使用的工具：

RPC（Remote Procedure Call）。RPC的目标就是掩盖我们正在不可靠网络上通信的事实。
线程。这是一种编程技术，使得我们可以利用多核心计算机。对于本课程而言，更重要的是，线程提供了一种结构化的并发操作方式，这样，从程序员角度来说可以简化并发操作。
锁。因为我们会经常用到线程，我们需要在实现的层面上，花费一定的时间来考虑并发控制，比如锁。

几个重要话题：

可扩展性（Scalability）：这是一个很强大的特性。如果你构建了一个系统，并且只要增加计算机的数量，系统就能相应提高性能或者吞吐量，这将会是一个巨大的成果，因为计算机只需要花钱就可以买到。如果不增加计算机，就需要花钱雇程序员来重构这些系统，进而使这些系统有更高的性能，更高的运行效率，或者应用一个更好的算法之类的。
可用性（Availability）：大型分布式系统一定要具有一定的容错能力。大型分布式系统中有一个大问题，那就是一些很罕见的问题会被放大。例如在我们的1000台计算机的集群中，总是有故障，要么是机器故障，要么是运行出错，要么是运行缓慢，要么是执行错误的任务。一个更常见的问题是网络，在一个有1000台计算机的网络中，会有大量的网络电缆和网络交换机，所以总是会有人踩着网线导致网线从接口掉出，或者交换机风扇故障导致交换机过热而不工作。在一个大规模分布式系统中，各个地方总是有一些小问题出现。所以大规模系统会将一些几乎不可能并且你不需要考虑的问题，变成一个持续不断的问题。
一致性（Consistency）：对于一致性有很多不同的定义。有一些非常直观，比如说get请求可以得到最近一次完成的put请求写入的值。这种一般也被称为强一致（Strong Consistency）。但是，事实上，构建一个弱一致的系统也是非常有用的。弱一致是指，不保证get请求可以得到最近一次完成的put请求写入的值。尽管有很多细节的工作要处理，强一致可以保证get得到的是put写入的最新的数据；而很多的弱一致系统不会做出类似的保证。所以在一个弱一致系统中，某人通过put请求写入了一个数据，但是你通过get看到的可能仍然是一个旧数据，而这个旧数据可能是很久之前写入的。人们对于弱一致感兴趣的原因是，虽然强一致可以确保get获取的是最新的数据，但是实现这一点的代价非常高。几乎可以确定的是，分布式系统的各个组件需要做大量的通信，才能实现强一致性。

GFS

GFS论文阐述

GFS论文发表在2003年的SOSP会议上，这是一个有关系统的顶级学术会议。通常来说，这种会议的论文标准是需要有大量的创新研究，但是GFS的论文不属于这一类标准。论文中的一些思想在当时都不是特别新颖，比如分布式，分片，容错这些在当时已经知道如何实现了。这篇论文的特点是，它描述了一个真正运行在成百上千台计算机上的系统，这个规模远远超过了学术界建立的系统。并且由于GFS被用于工业界，它反映了现实世界的经验，例如对于一个系统来说，怎样才能正常工作，怎样才能节省成本，这些内容也极其有价值。同时，论文也提出了一个当时非常异类的观点：存储系统具有弱一致性也是可以的。当时，学术界的观念认为，存储系统就应该有良好的行为，如果构建了一个会返回错误数据的系统，就像前面介绍的糟糕的多副本系统一样，那还有什么意义？为什么不直接构建一个能返回正确数据的系统？GFS并不保证返回正确的数据，借助于这一点，GFS的目标是提供更好的性能。

最后，这篇论文还有一个有意思的事情。在一些学术论文中，你或许可以看到一些容错的，多副本，自动修复的多个Master节点共同分担工作，但是GFS却宣称使用单个Master节点并能够很好的工作。

分布式存储系统（背景）

作为背景介绍，首先阐述一下分布式系统

人们设计大型分布式系统或大型存储系统出发点通常是，他们想获取巨大的性能加成，进而利用数百台计算机的资源来同时完成大量工作。因此，性能问题就成为了最初的诉求。之后，很自然的想法就是将数据分割放到大量的服务器上，这样就可以并行的从多台服务器读取数据。我们将这种方式称之为分片（Sharding）。

当我们在数百台计算机上运行我们的程序时，不可避免地会遇到的错误，而我们肯定需要一个自动的容错系统，而不是人工介入。这样就非常自然的引出了容错这个话题

实现容错最有用的一种方法是使用复制，只需要维护2-3个副本，当其中一个故障时，我们就可以使用另外一个，所以当我们需要容错时，就需要复制。

当我们有了复制，那自然就有两份数据副本，当我们访问这两份数据时，不可避免地会遇到一致性地问题。

为了达成一致性，我们总是需要做许多额外的工作，让我们的计算机进行网络交互，但这样的交互通常是消耗性能的，所以如果你想要一致性，那么代价就是性能。所以在现实生活中，如果你想要好的一致性，那么你就要付出相应的代价，而如果你想要性能，那么你就要忍受一些不确定行为。

GFS的设计目标和特征

GFS的设计目标

全局有效：Google的目标是构建一个大型的，快速的文件系统。并且这个文件系统是全局有效的，这样各种不同的应用程序都可以从中读取数据。一种构建大型存储系统的方法是针对某个特定的应用程序构建特定的裁剪的存储系统。但是如果另一个应用程序也想要一个大型存储系统，那么又需要重新构建一个存储系统。如果有一个全局通用的存储系统，那就意味着如果我存储了大量从互联网抓取的数据，你也可以通过申请权限来查看这些数据，因为我们都使用了同一个存储系统。
分割存储（分片）：为了获得大容量和高速的特性，每个包含了数据的文件会被GFS自动的分割并存放在多个服务器之上，这样读写操作自然就会变得很快。因为可以从多个服务器上同时读取同一个文件，进而获得更高的聚合吞吐量。将文件分割存储还可以在存储系统中保存比单个磁盘还要大的文件。
容错：因为我们现在在数百台服务器之上构建存储系统，我们希望有自动的故障修复。我们不希望每次服务器出了故障，派人到机房去修复服务器或者迁移数据。我们希望系统能自动修复自己。

GFS非设计目标的特征：

GFS只设计了一个数据中心，理论上应该将数据副本之间隔得远一些。
GFS只被设计用来内部使用，而不是直接面向用户。
GFS在各个方面对大型的顺序文件读写做了定制。在存储系统中有一个完全不同的领域，这个领域只对小份数据进行优化。例如一个银行账户系统就需要一个能够读写100字节的数据库，因为100字节就可以表示人们的银行账户。但是GFS是为TB级别的文件而生。并且GFS只会顺序处理，不支持随机访问。它的关注点主要在于吞吐量上。

GFS 内部设计

GFS Master 节点

GFS中Master是Active-Standby模式，所以只有一个Master节点在工作。Master节点保存了文件名和存储位置的对应关系。除此之外，还有大量的Chunk服务器，可能会有数百个，每一个Chunk服务器上都有1-2块磁盘。这是GFS的设计中做的比较好的地方，文件信息和文件内容这两种数据完全的隔绝开，这样两个问题可以使用独立的设计来解决。Master节点知道每一个文件对应的所有的Chunk的ID，这些Chunk每个是64MB大小，它们共同构成了一个文件。如果我有一个1GB的文件，那么Master节点就知道文件的第一个Chunk存储在哪，第二个Chunk存储在哪

GFS的一致性策略

更进一步，我们看一下GFS的一致性以及GFS是如何处理故障。为了了解这些，我们需要知道Master节点内保存的数据内容，这里我们关心的主要是两个表单：

第一个是文件名到Chunk ID或者Chunk Handle数组的对应。这个表单告诉你，文件对应了哪些Chunk。但是只有Chunk ID是做不了太多事情的，所以有了第二个表单。
第二个表单记录了Chunk ID到Chunk数据的对应关系。这里的数据又包括了：
- 每个Chunk存储在哪些服务器上，所以这部分是Chunk服务器的列表
- 每个Chunk当前的版本号，所以Master节点必须记住每个Chunk对应的版本号。
- 所有对于Chunk的写操作都必须在主Chunk（Primary Chunk）上顺序处理，主Chunk是Chunk的多个副本之一。所以，Master节点必须记住哪个Chunk服务器持有主Chunk。
- 并且，主Chunk只能在特定的租约时间内担任主Chunk，所以，Master节点要记住主Chunk的租约过期时间。

GFS的容错处理

刚刚以上数据都存储在内存中，如果Master故障了，这些数据就都丢失了。为了能让Master重启而不丢失数据，Master节点会同时将数据存储在磁盘上。所以Master节点读数据只会从内存读，但是写数据的时候，至少有一部分数据会接入到磁盘中。更具体来说，Master会在磁盘上存储log，每次有数据变更时，Master会在磁盘的log中追加一条记录，并生成CheckPoint（类似于备份点）。

有些数据需要存在磁盘上，而有些不用。它们分别是：

Chunk Handle的数组（第一个表单）要保存在磁盘上。我给它标记成NV（non-volatile, 非易失），这个标记表示对应的数据会写入到磁盘上。
Chunk服务器列表不用保存到磁盘上。因为Master节点重启之后可以与所有的Chunk服务器通信，并查询每个Chunk服务器存储了哪些Chunk，所以我认为它不用写入磁盘。所以这里标记成V（volatile），
版本号要不要写入磁盘取决于GFS是如何工作的，我认为它需要写入磁盘。我们之后在讨论系统是如何工作的时候再详细讨论这个问题。这里先标记成NV。
主Chunk的ID，几乎可以确定不用写入磁盘，因为Master节点重启之后会忘记谁是主Chunk，它只需要等待60秒租约到期，那么它知道对于这个Chunk来说没有主Chunk，这个时候，Master节点可以安全指定一个新的主Chunk。所以这里标记成V。
类似的，租约过期时间也不用写入磁盘，所以这里标记成V。

如果文件扩展到达了一个新的64MB，需要新增一个Chunk或者由于指定了新的主Chunk而导致版本号更新了，Master节点需要向磁盘中的Log追加一条记录。而这种向磁盘追加的操作速度是有限的，所以我们应该尽可能少的写入磁盘。GFS没有采用数据库，而是采用维护log的原因是因为追加log是非常高效的，通常是一次性的写入多个log，这些数据是向同一个地址追加，这样只需要等待磁盘的磁碟旋转一次。而不是向b树那样，每一份数据都需要随即找一个位置写入。

当master节点重启，并重建自己的状态时，不是从log’的最开始进行读取，而是从最新的checkpoint，这可能要花费几秒甚至一分钟。这样Master节点重启时，会从log中的最近一个checkpoint开始恢复，再逐条执行从Checkpoint开始的log，最后恢复自己的状态。

GFS处理读请求

对于读请求来说，意味着应用程序或者GFS客户端有一个文件名和它想从文件的某个位置读取的偏移量（offset），应用程序会将这些信息发送给Master节点。Master节点会从自己的file表单中查询文件名，得到Chunk ID的数组。因为每个Chunk是64MB，所以偏移量除以64MB就可以从数组中得到对应的Chunk ID。之后Master再从Chunk表单中找到存有Chunk的服务器列表，并将列表返回给客户端。

所以，

第一步是客户端（或者应用程序）将文件名和偏移量发送给Master。
第二步，Master节点将Chunk Handle（也就是ID，记为H）和服务器列表发送给客户端。

现在客户端可以从这些Chunk服务器中挑选一个来读取数据。GFS论文说，客户端会选择一个网络上最近的服务器（Google的数据中心中，IP地址是连续的，所以可以从IP地址的差异判断网络位置的远近），并将读请求发送到那个服务器。因为客户端每次可能只读取1MB或者64KB数据，所以，客户端可能会连续多次读取同一个Chunk的不同位置。所以，客户端会缓存Chunk和服务器的对应关系，这样，当再次读取相同Chunk数据时，就不用一次次的去向Master请求相同的信息。

接下来，客户端会与选出的Chunk服务器通信，将Chunk Handle和偏移量发送给那个Chunk服务器。Chunk服务器会在本地的硬盘上，将每个Chunk存储成独立的Linux文件，并通过普通的Linux文件系统管理。并且可以推测，Chunk文件会按照Handle（也就是ID）命名。所以，Chunk服务器需要做的就是根据文件名找到对应的Chunk文件，之后从文件中读取对应的数据段，并将数据返回给客户端。

GFS写文件

对于写文件，客户端会向Master节点发送请求说：我想向这个文件名对应的文件追加数据，请告诉我文件中最后一个Chunk的位置。多个客户端同时在写文件的时候，因为客户端本身不知道其他客户端写了多少。因此就不知道偏移量是多少，也就不清楚向哪个chunk追加数据。

对于读文件来说，可以从任何最新的Chunk副本读取数据，但是对于写文件来说，必须要通过Chunk的主副本（Primary Chunk）来写入。对于某个特定的Chunk来说，在某一个时间点，Master不一定指定了Chunk的主副本。所以，写文件的时候，需要考虑Chunk的主副本不存在的情况。

当发现主副本不存在时，master节点会找出所有存在Chunk最新副本的Chunk服务器，然后需要告诉客户端向哪个Chunk服务器去做追加操作。

每个Chunk可能同时有多个副本，最新的副本是指，副本中保存的版本号与Master中记录的Chunk的版本号一致。Chunk副本中的版本号是由Master节点下发的，所以Master节点知道，对于一个特定的Chunk，哪个版本号是最新的。

每个Chunk可能同时有多个副本，最新的副本是指，副本中保存的版本号与Master中记录的Chunk的版本号一致。Chunk副本中的版本号是由Master节点下发的，所以Master节点知道，对于一个特定的Chunk，哪个版本号是最新的。这就是为什么Chunk的版本号在Master节点上需要保存在磁盘这种非易失的存储中的原因**(为了让master总是知道最新的版本号，即使master重启之后)**

Master节点会向Primary和Secondary副本对应的服务器发送消息并告诉它们，谁是Primary，谁是Secondary，Chunk的新版本是什么。Primary和Secondary服务器都会将版本号存储在本地的磁盘中。这样，当它们因为电源故障或者其他原因重启时，它们可以向Master报告本地保存的Chunk的实际版本号。

现在我们有了一个Primary，它可以接收来自客户端的写请求，并将写请求应用在多个Chunk服务器中。之所以要管理Chunk的版本号，是因为这样Master可以将实际更新Chunk的能力转移给Primary服务器。并且在将版本号更新到Primary和Secondary服务器之后，如果Master节点故障重启，还是可以在相同的Primary和Secondary服务器上继续更新Chunk。

现在，Master节点通知Primary和Secondary服务器，你们可以修改这个Chunk。它还给Primary一个租约，这个租约告诉Primary说，在接下来的60秒中，你将是Primary，60秒之后你必须停止成为Primary。这种机制可以确保我们不会同时有两个Primary

对于每个客户端的追加数据请求（也就是写请求），Primary会查看当前文件结尾的Chunk，并确保Chunk中有足够的剩余空间，然后将客户端要追加的数据写入Chunk的末尾。并且，Primary会通知所有的Secondary服务器也将客户端要追加的数据写入在它们自己存储的Chunk末尾。这样，包括Primary在内的所有副本，都会收到通知将数据追加在Chunk的末尾。

GFS论文说，如果客户端从Primary得到写入失败，那么客户端应该重新发起整个追加过程。客户端首先会重新与Master交互，找到文件末尾的Chunk；之后，客户端需要重新发起对于Primary和Secondary的数据追加操作。

为什么当发现primary无法连接时不立即指定一个新的primary？

为了防止脑裂。对于上面的问题，master会选择什么也不做，并等待租约到期之后，master会重新选择一个新的primary。所谓脑裂，它是指同时有两个Primary处理写请求，这两个Primary不知道彼此的存在，会分别处理不同的写请求，最终会导致有两个不同的数据拷贝。它通常是由网络分区引起的。比如说，Master无法与Primary通信，但是Primary又可以与客户端通信，这就是一种网络分区问题。网络故障是这类分布式存储系统中最难处理的问题之一。

GFS的一致性策略

GFS系统追加数据时的情况是，它追求的是弱一致性，GFS被设计成多个副本可以不一致，它要求应用程序能够容忍读取乱序的数据，如果应用程序不能容忍乱序，那要么放弃并发写入，要么在写入时加上序列号。

VMware FT

状态转移和复制状态机

在VMware FT论文的开始，介绍了两种复制的方法，一种是状态转移（State Transfer），另一种是复制状态机（Replicated State Machine）。这两种我们都会介绍，但是在这门课程中，我们主要还是介绍后者。

如果我们有一个服务器的两个副本，我们需要让它们保持同步，在实际上互为副本，这样一旦Primary出现故障，因为Backup有所有的信息，就可以接管服务。状态转移背后的思想是，Primary将自己完整状态，比如说内存中的内容，拷贝并发送给Backup。Backup会保存收到的最近一次状态，所以Backup会有所有的数据。当Primary故障了，Backup就可以从它所保存的最新状态开始运行。所以，状态转移就是发送Primary的状态。虽然VMware FT没有采用这种复制的方法，但是假设采用了的话，那么转移的状态就是Primary内存里面的内容。这种情况下，每过一会，Primary就会对自身的内存做一大份拷贝，并通过网络将其发送到Backup。为了提升效率，你可以想到每次同步只发送上次同步之后变更了的内存。

复制状态机基于这个事实：我们想复制的大部分的服务或者计算机软件都有一些确定的内部操作，不确定的部分是外部的输入。通常情况下，如果一台计算机没有外部影响，它只是一个接一个的执行指令，每条指令执行的是计算机中内存和寄存器上确定的函数，只有当外部事件干预时，才会发生一些预期外的事。例如，某个随机时间收到了一个网络数据包，导致服务器做一些不同的事情。所以，复制状态机不会在不同的副本之间发送状态，相应的，它只会从Primary将这些外部事件，例如外部的输入，发送给Backup。通常来说，如果有两台计算机，如果它们从相同的状态开始，并且它们以相同的顺序，在相同的时间，看到了相同的输入，那么它们会一直互为副本，并且一直保持一致。

我们喜欢复制状态机的原因是，我们认为状态转移的代价太高了。但是对于复制状态机来说，其中的两个副本仍然需要有完整的状态，我们只是有一种成本更低的方式来保持它们的同步。如果我们要创建一个新的副本，我们别无选择，只能使用状态转移，因为新的副本需要有完整状态的拷贝。所以创建一个新的副本，代价会很高。

状态转移传输的是可能是内存，而复制状态机会将来自客户端的操作或者其他外部事件，从Primary传输到Backup。

人们倾向于使用复制状态机的原因是，通常来说，外部操作或者事件比服务的状态要小。

多核CPU的VMware方案

VMware FT论文讨论的都是复制状态机，并且只涉及了单核CPU，目前还不确定论文中的方案如何扩展到多核处理器的机器中。在多核的机器中，两个核交互处理指令的行为是不确定的，所以就算Primary和Backup执行相同的指令，在多核的机器中，它们也不一定产生相同的结果。VMware在之后推出了一个新的可能完全不同的复制系统，并且可以在多核上工作。这个新系统从我看来使用了状态转移，而不是复制状态机。因为面对多核和并行计算，状态转移更加健壮。如果你使用了一台机器，并且将其内存发送过来了，那么那个内存镜像就是机器的状态，并且不受并行计算的影响，但是复制状态机确实会受并行计算的影响。但是另一方面，我认为这种新的多核方案代价会更高一些。

VMware FT的独特之处在于，它从机器级别实现复制，因此它不关心你在机器上运行什么样的软件，它就是复制底层的寄存器和内存。你可以在VMware FT管理的机器上运行任何软件，只要你的软件可以运行在VMware FT支持的微处理器上。这里说的软件可以是任何软件。所以，它的缺点是，它没有那么的高效，优点是，你可以将任何现有的软件，甚至你不需要有这些软件的源代码，你也不需要理解这些软件是如何运行的，在某些限制条件下，你就可以将这些软件运行在VMware FT的这套复制方案上。VMware FT就是那个可以让任何软件都具备容错性的魔法棒。

VMware FT 工作原理

这里有一个术语，VMware FT论文中将Primary到Backup之间同步的数据流的通道称之为Log Channel。虽然都运行在一个网络上，但是这些从Primary发往Backup的事件被称为Log Channel上的Log Event/Entry。

当Primary因为故障停止运行时，FT（Fault-Tolerance）就开始工作了。从Backup的角度来说，它将不再收到来自于Log Channel上的Log条目。实际中，Backup每秒可以收到很多条Log，其中一个来源就是来自于Primary的定时器中断。每个Primary的定时器中断都会生成一条Log条目并发送给Backup，这些定时器中断每秒大概会有100次。所以，如果Primary虚机还在运行，Backup必然可以期望从Log Channel收到很多消息。如果Primary虚机停止运行了，那么Backup的VMM就会说：天，我都有1秒没有从Log Channel收到任何消息了，Primary一定是挂了或者出什么问题了。当Backup不再从Primary收到消息，VMware FT论文的描述是，Backup虚机会上线（Go Alive）。这意味着，Backup不会再等待来自于Primary的Log Channel的事件，Backup的VMM会让Backup自由执行，而不是受来自于Primary的事件驱动。Backup的VMM会在网络中做一些处理（猜测是发GARP），让后续的客户端请求发往Backup虚机，而不是Primary虚机。同时，Backup的VMM不再会丢弃Backup虚机的输出。当然，它现在已经不再是Backup，而是Primary。所以现在，左边的虚机直接接收输入，直接产生输出。到此为止，Backup虚机接管了服务。

类似的一个场景，虽然没那么有趣，但是也需要能正确工作。如果Backup虚机停止运行，Primary也需要用一个类似的流程来抛弃Backup，停止向它发送事件，并且表现的就像是一个单点的服务，而不是一个多副本服务一样。所以，只要有一个因为故障停止运行，并且不再产生网络流量时，Primary和Backup中的另一个都可以上线继续工作。

非确定性事件

非确定性事件可以分成几类。

客户端输入。假设有一个来自于客户端的输入，这个输入随时可能会送达，所以它是不可预期的。客户端请求何时送达，会有什么样的内容，并不取决于服务当前的状态。我们讨论的系统专注于通过网络来进行交互，所以这里的系统输入的唯一格式就是网络数据包。所以当我们说输入的时候，我们实际上是指接收到了一个网络数据包。而一个网络数据包对于我们来说有两部分，一个是数据包中的数据，另一个是提示数据包送达了的中断。当网络数据包送达时，通常网卡的DMA（Direct Memory Access）会将网络数据包的内容拷贝到内存，之后触发一个中断。操作系统会在处理指令的过程中消费这个中断。对于Primary和Backup来说，这里的步骤必须看起来是一样的，否则它们在执行指令的时候就会出现不一致。所以，这里的问题是，中断在什么时候，具体在指令流中的哪个位置触发？对于Primary和Backup，最好要在相同的时间，相同的位置触发，否则执行过程就是不一样的，进而会导致它们的状态产生偏差。所以，我们不仅关心网络数据包的内容，还关心中断的时间。

另外，如其他同学指出的，有一些指令在不同的计算机上的行为是不一样的，这一类指令称为怪异指令，比如说：随机数生成器。获取当前时间的指令。获取计算机的唯一ID
另外一个常见的非确定事件，在VMware FT论文中没有讨论，就是多CPU的并发。我们现在讨论的都是一个单进程系统，没有多CPU多核这种事情。之所以多核会导致非确定性事件，是因为当服务运行在多CPU上时，指令在不同的CPU上会交织在一起运行，进而产生的指令顺序是不可预期的。所以如果我们在Backup上运行相同的代码，并且代码并行运行在多核CPU上，硬件会使得指令以不同（于Primary）的方式交织在一起，而这会引起不同的运行结果。假设两个核同时向同一份数据请求锁，在Primary上，核1得到了锁；在Backup上，由于细微的时间差别核2得到了锁，那么执行结果极有可能完全不一样，这里其实说的就是（在两个副本上）不同的线程获得了锁。所以，多核是一个巨大的非确定性事件来源，VMware FT论文完全没有讨论它，并且它也不适用与我们这节课的讨论。

所有的事件都需要通过Log Channel，从Primary同步到Backup。有关日志条目的格式在论文中没有怎么描述，但是我（Robert教授）猜日志条目中有三样东西：

事件发生时的指令序号。因为如果要同步中断或者客户端输入数据，最好是Primary和Backup在相同的指令位置看到数据，所以我们需要知道指令序号。这里的指令号是自机器启动以来指令的相对序号，而不是指令在内存中的地址。比如说，我们正在执行第40亿零79条指令。所以日志条目需要有指令序号。对于中断和输入来说，指令序号就是指令或者中断在Primary中执行的位置。对于怪异的指令（Weird instructions），比如说获取当前的时间来说，这个序号就是获取时间这条指令执行的序号。这样，Backup虚机就知道在哪个指令位置让相应的事件发生。
日志条目的类型，可能是普通的网络数据输入，也可能是怪异指令。
最后是数据。如果是一个网络数据包，那么数据就是网络数据包的内容。如果是一个怪异指令，数据将会是这些怪异指令在Primary上执行的结果。这样Backup虚机就可以伪造指令，并提供与Primary相同的结果。

输出控制

你需要考虑，如果在一个不恰当的时间，出现了故障会怎样？在这门课程中，你需要始终考虑，故障的最坏场景是什么，故障会导致什么结果？在这个例子中，假设Primary确实生成了回复给客户端，但是之后立马崩溃了。更糟糕的是，现在网络不可靠，Primary发送给Backup的Log条目在Primary崩溃时也丢包了。那么现在的状态是，客户端收到了回复说现在的数据是11，但是Backup虚机因为没有看到客户端请求，所以它保存的数据还是10。

现在，因为察觉到Primary崩溃了，Backup接管服务。这时，客户端再次发送一个自增的请求，这个请求发送到了原来的Backup虚机，它会将自身的数值从10增加到11，并产生第二个数据是11的回复给客户端。

如果客户端比较前后两次的回复，会发现一个明显不可能的场景（两次自增的结果都是11）。

因为VMware FT的优势就是在不修改软件，甚至软件都不需要知道复制的存在的前提下，就能支持容错，所以我们也不能修改客户端让它知道因为容错导致的副本切换触发了一些奇怪的事情。在VMware FT场景里，我们没有修改客户端这个选项，因为整个系统只有在不修改服务软件的前提下才有意义。所以，前面的例子是个大问题，我们不能让它实际发生。有人还记得论文里面是如何防止它发生的吗？

论文里的解决方法就是控制输出（Output Rule）。直到Backup虚机确认收到了相应的Log条目，Primary虚机不允许生成任何输出。让我们回到Primary崩溃前，并且计数器的内容还是10，Primary上的正确的流程是这样的：

客户端输入到达Primary。
Primary的VMM将输入的拷贝发送给Backup虚机的VMM。所以有关输入的Log条目在Primary虚机生成输出之前，就发往了Backup。之后，这条Log条目通过网络发往Backup，但是过程中有可能丢失。
Primary的VMM将输入发送给Primary虚机，Primary虚机生成了输出。现在Primary虚机的里的数据已经变成了11，生成的输出也包含了11。但是VMM不会无条件转发这个输出给客户端。
Primary的VMM会等到之前的Log条目都被Backup虚机确认收到了才将输出转发给客户端。所以，包含了客户端输入的Log条目，会从Primary的VMM送到Backup的VMM，Backup的VMM不用等到Backup虚机实际执行这个输入，就会发送一个表明收到了这条Log的ACK报文给Primary的VMM。当Primary的VMM收到了这个ACK，才会将Primary虚机生成的输出转发到网络中。

所以，这里的核心思想是，确保在客户端看到对于请求的响应时，Backup虚机一定也看到了对应的请求，或者说至少在Backup的VMM中缓存了这个请求。这样，我们就不会陷入到这个奇怪的场景：客户端已经收到了回复，但是因为有故障发生和副本切换，新接手的副本完全不知道客户端之前收到了对应的回复。

如果在上面的步骤2中，Log条目通过网络发送给Backup虚机时丢失了，然后Primary虚机崩溃了。因为Log条目丢失了，所以Backup节点也不会发送ACK消息。所以，如果Log条目的丢失与Primary的崩溃同一时间发生，那么Primary必然在VMM将回复转发到网络之前就崩溃了，所以客户端也就不会收到任何回复，所以客户端就不会观察到任何异常。这就是输出控制（Output rule）。