本文最后更新于 2024-04-19，文章内容可能已经过时。

Mit6.824: Distributed Systems:

本文为麻省理工学院 分布式系统课程笔记。

作者：Robert Morris

官网：https://pdos.csail.mit.edu/6.824/

课程内容概述：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824

课程视频（往年）：https://www.youtube.com/watch?v=cQP8WApzIQQ

1.引入：

1.1 分布式系统的驱动力和挑战（Drivens and Challenges）:

1.1.1 选择分布式系统：

在你设计一个系统时或者面对一个你需要解决的问题时，如果你可以在一台计算机上解决，而不需要分布式系统，那你就应该用一台计算机解决问题。有很多的工作都可以在一台计算机上完成，并且通常比分布式系统简单很多。

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

  • 更高的性能。人们需要获得更高的计算性能。可以这么理解这一点，（大量的计算机意味着）大量的并行运算，大量CPU、大量内存、以及大量磁盘在并行的运行。

  • 更高的容错性。另一个人们构建分布式系统的原因是，它可以提供容错（tolerate faults）。比如两台计算机运行完全相同的任务，其中一台发生故障，可以切换到另一台。

  • 业务需求导向。第三个原因是，一些问题天然在空间上是分布的。例如银行转账，我们假设银行A在纽约有一台服务器，银行B在伦敦有一台服务器，这就需要一种两者之间协调的方法。所以，有一些天然的原因导致系统是物理分布的。

  • 更安全的环境。最后一个原因是，人们构建分布式系统来达成一些安全的目标。比如有一些代码并不被信任，但是你又需要和它进行交互，这些代码不会立即表现的恶意或者出现bug。你不会想要信任这些代码，所以你或许想要将代码分散在多处运行，这样你的代码在另一台计算机运行，我的代码在我的计算机上运行，我们通过一些特定的网络协议通信。所以，我们可能会担心安全问题，我们把系统分成多个的计算机，这样可以限制出错域。

主要原因是前两点：性能和容错。 image-20240418172029801

1.1.2 挑战：

  • 复杂性。因为系统中存在很多部分，这些部分又在并发执行，你会遇到并发编程和各种复杂交互所带来的问题，以及时间依赖的问题（比如同步，异步）。这让分布式系统变得很难。

  • 网络通信。另一个导致分布式系统很难的原因是，分布式系统有多个组成部分，再加上计算机网络，你会会遇到一些意想不到的故障。如果你只有一台计算机，那么它通常要么是工作，要么是故障或者没电，总的来说，要么是在工作，要么是没有工作。而由多台计算机组成的分布式系统，可能会有一部分组件在工作，而另一部分组件停止运行，或者这些计算机都在正常运行，但是网络中断了或者不稳定。所以，局部错误也是分布式系统很难的原因。

  • 性能。最后一个导致分布式系统很难的原因是，人们设计分布式系统的根本原因通常是为了获得更高的性能，比如说一千台计算机或者一千个磁盘臂达到的性能。但是实际上一千台机器到底有多少性能是一个棘手的问题，这里有很多难点。所以通常需要倍加小心地设计才能让系统实际达到你期望的性能。

1.2 分布式特性：

1.2.1 可扩展性（Scalability）：

可扩展或者可扩展性指的是，如果我用一台计算机解决了一些问题，当我买了第二台计算机，我只需要一半的时间就可以解决这些问题，或者说每分钟可以解决两倍数量的问题。两台计算机构成的系统如果有两倍性能或者吞吐，就是我说的可扩展性。

这是一个很强大的特性。如果你构建了一个系统，并且只要增加计算机的数量，系统就能相应提高性能或者吞吐量，这将会是一个巨大的成果，因为计算机只需要花钱就可以买到。如果不增加计算机，就需要花钱雇程序员来重构这些系统，进而使这些系统有更高的性能，更高的运行效率，或者应用一个更好的算法之类的。花钱请程序员来修补这些代码，使它们运行的更快，通常会是一个昂贵的方法。我们还是希望能够通过从十台计算机提升到一千台计算机，就能扛住一百倍的流量。

所以，当人们使用一整个机房的计算机来构建大型网站的时候，为了获取对应的性能，必须要时刻考虑可扩展性。你需要仔细设计系统，才能获得与计算机数量匹配的性能。

我们希望可以通过增加机器的方式来实现扩展，但是现实中这很难实现，需要一些架构设计来将这个可扩展性无限推进下去。

1.2.2 可用性（Availability）：

如果你只使用一台计算机构建你的系统，那么你的系统大概率是可靠的。

但是，在大型分布式系统中有一个大问题，那就是一些很罕见的问题会被放大。

例如在我们的1000台计算机的集群中，总是有故障，要么是机器故障，要么是运行出错，要么是运行缓慢，要么是执行错误的任务。一个更常见的问题是网络，在一个有1000台计算机的网络中，会有大量的网络电缆和网络交换机，所以总是会有人踩着网线导致网线从接口掉出，或者交换机风扇故障导致交换机过热而不工作。在一个大规模分布式系统中，各个地方总是有一些小问题出现。所以大规模系统会将一些几乎不可能并且你不需要考虑的问题，变成一个持续不断的问题。

因为错误总会发生，必须要在设计时就考虑，系统能够屏蔽错误，或者说能够在出错时继续运行。

同时，因为我们需要为第三方应用开发人员提供方便的抽象接口，我们的确也需要构建这样一种基础架构，它能够尽可能多的对应用开发人员屏蔽和掩盖错误。这样，应用开发人员就不需要处理各种各样的可能发生的错误。

对于容错，有很多不同的概念可以表述。这些表述中，有一个共同的思想就是可用性（Availability）。某些系统经过精心的设计，在特定的错误类型下，系统仍然能够正常运行，仍然可以像没有出现错误一样，为你提供完整的服务。

除了可用性之外，另一种容错特性是自我可恢复性（recoverability）。这里的意思是，如果出现了问题，服务会停止工作，不再响应请求，之后有人来修复，并且在修复之后系统仍然可以正常运行，就像没有出现过问题一样。这是一个比可用性更弱的需求，因为在出现故障到故障组件被修复期间，系统将会完全停止工作。但是修复之后，系统又可以完全正确的重新运行，所以可恢复性是一个重要的需求。

1.2.2.1 实现：

  • 一个是非易失存储（non-volatile storage，类似于硬盘）。这样当出现类似电源故障，甚至整个机房的电源都故障时，我们可以使用非易失存储，比如硬盘，闪存，SSD之类的。我们可以存放一些checkpoint或者系统状态的log在这些存储中，这样当备用电源恢复或者某人修好了电力供给，我们还是可以从硬盘中读出系统最新的状态，并从那个状态继续运行。所以，这里的一个工具是非易失存储。因为更新非易失存储是代价很高的操作，所以相应的出现了很多非易失存储的管理工具。同时构建一个高性能，容错的系统，聪明的做法是避免频繁的写入非易失存储。在过去，甚至对于今天的一个3GHZ的处理器，写入一个非易失存储意味着移动磁盘臂并等待磁碟旋转，这两个过程都非常缓慢。有了闪存会好很多，但是为了获取好的性能，仍然需要许多思考。

  • 对于容错的另一个重要工具是复制（replication），不过，管理复制的多副本系统会有些棘手。任何一个多副本系统中，都会有一个关键的问题，比如说，我们有两台服务器，它们本来应该是有着相同的系统状态，现在的关键问题在于，这两个副本总是会意外的偏离同步的状态，而不再互为副本。对于任何一种使用复制实现容错的系统，我们都面临这个问题。lab2和lab3都是通过管理多副本来实现容错的系统，你将会看到这里究竟有多复杂。

1.2.3 一致性：

一致性就是用来定义操作行为的概念。

之所以一致性是分布式系统中一个有趣的话题，是因为，从性能和容错的角度来说，我们通常会有多个副本。由于复制或者缓存，数据可能存在于多个副本当中，于是就有了多个不同版本的key-value对。

1.2.3.1 强一致与弱一致：

get请求可以得到最近一次完成的put请求写入的值。这种一般也被称为强一致（Strong Consistency）。

不保证get请求可以得到最近一次完成的put请求写入的值。这种被称为弱一致。

人们对于弱一致感兴趣的原因是，虽然强一致可以确保get获取的是最新的数据，但是实现这一点的代价非常高。几乎可以确定的是，分布式系统的各个组件需要做大量的通信，才能实现强一致性。

如果你有多个副本，那么不管get还是put都需要询问每一个副本。在之前的例子中，客户端在更新的过程中故障了，导致一个副本更新了，而另一个副本没有更新。如果我们要实现强一致，简单的方法就是同时读两个副本，如果有多个副本就读取所有的副本，并使用最近一次写入的数据。但是这样的代价很高，因为需要大量的通信才能得到一个数据。

强一致带来的昂贵的通信问题，会把你带入这样的困境：当我们使用多副本来完成容错时，我们的确需要每个副本都有独立的出错概率，这样故障才不会关联。例如，将两个副本放在一个机房的一个机架上，是一个非常糟糕的主意。如果有谁踢到了机架的电源线，那我们数据的两个副本都没了，因为它们都连在同一个机架的同一根电线上。所以，为了使副本的错误域尽可能独立，为了获得良好的容错特性，人们希望将不同的副本放置在尽可能远的位置，例如在不同的城市或者在大陆的两端。这样，如果地震摧毁了一个数据中心，另一个数据中心中的副本有很大可能还能保留。我们期望这样的效果。但是如果我们这么做了，另一个副本可能在数千英里之外，按照光速来算，也需要花费几毫秒到几十毫秒才能完成横跨洲际的数据通信，而这只是为了更新数据的另一个副本。所以，为了保持强一致的通信，代价可能会非常高。因为每次你执行put或者get请求，你都需要等待几十毫秒来与数据的两个副本通信，以确保它们都被更新了或者都被检查了以获得最新的数据。现在的处理器每秒可以执行数十亿条指令，等待几十毫秒会大大影响系统的处理速度。

所以，为了尽可能的避免通信，尤其当副本相隔的很远的时候，人们会构建弱一致系统，并允许读取出旧的数据。

1.3 MapReduce：

MapReduce是由Google设计，开发和使用的一个系统，相关的论文在2004年发表。

Google当时面临的问题是，他们需要在TB级别的数据上进行大量的计算。由于数据量非常的大，Google非常希望能将对大量数据的大量运算并行跑在几千台计算机上，这样才能快速完成计算。而对他们来说，购买计算机是梅雨问题的（不缺钱）。

如果你只雇佣熟练的分布式系统专家作为工程师，尽管可能会有些浪费，也是可以的。但是Google想雇用的是各方面有特长的人，不一定是想把所有时间都花在编写分布式软件上的工程师。所以Google需要一种框架，可以让它的工程师能够进行任意的数据分析，例如排序，网络索引器，链接分析器以及任何的运算。工程师只需要实现应用程序的核心，就能将应用程序运行在数千台计算机上，而不用考虑如何将运算工作分发到数千台计算机，如何组织这些计算机，如何移动数据，如何处理故障等等这些细节。于是就出现了MapReduce。

MapReduce的思想是，应用程序设计人员和分布式运算的使用者，只需要写简单的Map函数和Reduce函数，而不需要知道任何有关分布式的事情，MapReduce框架会处理剩下的事情。

MapReduce假设有一些输入，这些输入被分割成大量的不同的文件或者数据块。

1.3.1 Map函数：

MapReduce启动时，会查找Map函数。之后，MapReduce框架会为每个输入文件运行Map函数。

Map函数使用一个key和一个value作为参数。

Map函数不需要知道任何分布式相关的信息，不需要知道有多台计算机，不需要知道实际会通过网络来移动数据。

1.3.2 Reduce函数：

Reduce函数的入参是某个特定key的所有实例（Map输出中的key-value对中，出现了一次特定的key就可以算作一个实例）。所以Reduce函数也是使用一个key和一个value作为参数，其中value是一个数组，里面每一个元素是Map函数输出的key的一个实例的value。

1.3.1 一个例子：单词计数器：

运算的第一阶段是是Map函数。在单词计数器中，Map函数会将输入中的每个单词拆分，并输出一个key-value对，key是该单词，value是1。最后需要对所有的key-value进行计数，以获得最终的输出。

运算的第二阶段是运行Reduce函数。MapReduce框架会收集所有Map函数输出的每一个单词的统计。比如说，MapReduce框架会先收集每一个Map函数输出的key为a的key-value对。收集了之后，会将它们提交给Reduce函数。

之后会收集所有的b。这里的收集是真正意义上的收集，因为b是由不同计算机上的不同Map函数生成，所以不仅仅是数据从一台计算机移动到另一台（如果Map只在一台计算机的一个实例里，可以直接通过一个RPC将数据从Map移到Reduce）。

在单词计数器的例子中，Reduce函数只需要统计传入参数的长度，甚至都不用查看传入参数的具体内容，因为每一个传入参数代表对单词加1，而我们只需要统计个数。最后，每个Reduce都输出与其关联的单词和这个单词的数量。

  • Job。整个MapReduce计算称为Job。

  • Task。每一次MapReduce调用称为Task。

所以，对于一个完整的MapReduce Job，它由一些Map Task和一些Reduce Task组成。所以这是一个单词计数器的例子，它解释了MapReduce的基本工作方式。

2.GFS:

The Google File System.

存储是一种关键的抽象。你可以想象，在分布式系统中，可能有各种各样重要的抽象可以应用在分布式系统中，但是实际上，简单的存储接口往往非常有用且极其通用。所以，构建分布式系统大多都是关于如何设计存储系统，或是设计其它基于大型分布式存储的系统。

2.1 分布式存储的困难：

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

如果你在成百上千台服务器进行分片，你将会看见常态的故障。如果你有数千台服务器，那么总是会有一台服务器宕机，每天甚至每个小时都可能会发生错误。所以，我们需要自动化的方法而不是人工介入来修复错误。我们需要一个自动的容错系统，这就引出了容错这个话题（fault tolerance）。

实现容错最有用的一种方法是使用复制，只需要维护2-3个数据的副本，当其中一个故障了，你就可以使用另一个。所以，如果想要容错能力，就得有复制（replication）。

如果有复制，那就有了两份数据的副本。可以确定的是，如果你不小心，它们就会不一致。所以，你本来设想的是，有了两个数据副本，你可以任意使用其中一个副本来容错。但是如果你不够小心，两个数据的副本就不是完全一致，严格来说，它们就不再互为副本了。而你获取到的数据内容也将取决于你向哪个副本请求数据。这对于应用程序来说就有些麻烦了。所以，如果我们有了复制，我们就有不一致的问题（inconsistency）。

通过聪明的设计，你可以避免不一致的问题，并且让数据看起来也表现的符合预期。但是为了达到这样的效果，你总是需要额外的工作，需要不同服务器之间通过网络额外的交互，而这样的交互会降低性能。所以如果你想要一致性，你的代价就是低性能。但这明显不是我们最开始所希望的。

2.2 好的设计：

对于具备强一致或者好的一致性的系统，从应用程序或者客户端看起来就像是和一台服务器在通信。尽管我们会通过数百台计算机构建一个系统，但是对于一个理想的强一致模型，你看到的就像是只有一台服务器，一份数据，并且系统一次只做一件事情。这是一种直观的理解强一致的方式。

2.3 错误的设计：多读多写：

我们有两台服务器，每个服务器都有数据的一份完整拷贝。它们在磁盘上都存储了一个key-value表单。当然，直观上我们希望这两个表单是完全一致的，这样，一台服务器故障了，我们可以切换到另一台服务器去做读写。两个表单完全一致意味着，每一个写请求都必须在两台服务器上执行，而读请求只需要在一台服务器上执行，否则就没有容错性了。

2.4 设计：

Google的目标是构建一个大型的，快速的文件系统。并且这个文件系统是全局有效的，这样各种不同的应用程序都可以从中读取数据。一种构建大型存储系统的方法是针对某个特定的应用程序构建特定的裁剪的存储系统。

为了获得大容量和高速的特性，每个包含了数据的文件会被GFS自动的分割并存放在多个服务器之上，这样读写操作自然就会变得很快。因为可以从多个服务器上同时读取同一个文件，进而获得更高的聚合吞吐量。将文件分割存储还可以在存储系统中保存比单个磁盘还要大的文件。

第三，GFS在各个方面对大型的顺序文件读写做了定制。在存储系统中有一个完全不同的领域，这个领域只对小份数据进行优化。例如一个银行账户系统就需要一个能够读写100字节的数据库，因为100字节就可以表示人们的银行账户。但是GFS不是这样的系统，GFS是为TB级别的文件而生。并且GFS只会顺序处理，不支持随机访问。某种程度上来说，它有点像批处理的风格。GFS并没有花费过多的精力来降低延迟，它的关注点在于巨大的吞吐量上，所以单次操作都涉及到MB级别的数据。

2.4.1 Master-Chunk：

GFS中Master是Active-Standby模式，所以只有一个Master节点在工作。Master节点用来管理文件和Chunk的信息，而Chunk服务器用来存储实际的数据。这是GFS设计中比较好的一面，它将这两类数据的管理问题几乎完全隔离开了，这样这两个问题可以使用独立设计来解决。

Master节点知道每一个文件对应的所有的Chunk的ID，这些Chunk每个是64MB大小，它们共同构成了一个文件。如果我有一个1GB的文件，那么Master节点就知道文件的第一个Chunk存储在哪，第二个Chunk存储在哪，等等。当我想读取这个文件中的任意一个部分时，我需要向Master节点查询对应的Chunk在哪个服务器上，之后我可以直接从Chunk服务器读取对应的Chunk数据。

2.4.2 读文件：

对于读请求来说，意味着应用程序或者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地址的差异判断网络位置的远近），并将读请求发送到那个服务器。

接下来，客户端会与选出的Chunk服务器通信，将Chunk Handle和偏移量发送给那个Chunk服务器。Chunk服务器会在本地的硬盘上，将每个Chunk存储成独立的Linux文件，并通过普通的Linux文件系统管理。

2.4.3 写文件：

对于读文件来说，可以从任何最新的Chunk副本读取数据，但是对于写文件来说，必须要通过Chunk的主副本（Primary Chunk）来写入。

对于Master节点来说，如果发现Chunk的主副本不存在，Master会找出所有存有Chunk最新副本的Chunk服务器。如果你的一个系统已经运行了很长时间，那么有可能某一个Chunk服务器保存的Chunk副本是旧的，比如说还是昨天或者上周的。导致这个现象的原因可能是服务器因为宕机而没有收到任何的更新。所以，Master节点需要能够在Chunk的多个副本中识别出，哪些副本是新的，哪些是旧的。所以第一步是，找出新的Chunk副本。这一切都是在Master节点发生，因为，现在是客户端告诉Master节点说要追加某个文件，Master节点需要告诉客户端向哪个Chunk服务器（也就是Primary Chunk所在的服务器）去做追加操作。所以，Master节点的部分工作就是弄清楚在追加文件时，客户端应该与哪个Chunk服务器通信。

2.4.4 一致性：

当我们追加数据时，面对Chunk的三个副本，当客户端发送了一个追加数据的请求，要将数据A追加到文件末尾，所有的三个副本，包括一个Primary和两个Secondary，都成功的将数据追加到了Chunk，所以Chunk中的第一个记录是A。

假设第二个客户端加入进来，想要追加数据B，但是由于网络问题发送给某个副本的消息丢失了。所以，追加数据B的消息只被两个副本收到，一个是Primary，一个是Secondary。这两个副本都在文件中追加了数据B，所以，现在我们有两个副本有数据B，另一个没有。

之后，第三个客户端想要追加数据C，并且第三个客户端记得下图中左边第一个副本是Primary。Primary选择了偏移量，并将偏移量告诉Secondary，将数据C写在Chunk的这个位置。三个副本都将数据C写在这个位置。

对于数据B来说，客户端会收到写入失败的回复，客户端会重发写入数据B的请求。所以，第二个客户端会再次请求追加数据B，或许这次数据没有在网络中丢包，并且所有的三个副本都成功追加了数据B。现在三个副本都在线，并且都有最新的版本号。

之后，如果一个客户端读文件，读到的内容取决于读取的是Chunk的哪个副本。客户端总共可以看到三条数据，但是取决于不同的副本，读取数据的顺序是不一样的。如果读取的是第一个副本，那么客户端可以读到A、B、C，然后是一个重复的B。如果读取的是第三个副本，那么客户端可以读到A，一个空白数据，然后是C、B。所以，如果读取前两个副本，B和C的顺序是先B后C，如果读的是第三个副本，B和C的顺序是先C后B。所以，不同的读请求可能得到不同的结果。

在GFS的这种工作方式下，如果Primary返回写入成功，那么一切都还好，如果Primary返回写入失败，就不是那么好了。Primary返回写入失败会导致不同的副本有完全不同的数据。

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

有人会问，如何将这里的设计转变成强一致的系统，从而与我们前面介绍的单服务器模型更接近，也不会产生一些给人“惊喜”的结果。实际上我不知道怎么做，因为这需要完全全新的设计。目前还不清楚如何将GFS转变成强一致的设计。但是，如果你想要将GFS升级成强一致系统，我可以为你列举一些你需要考虑的事情：

  • 你可能需要让Primary来探测重复的请求，这样第二个写入数据B的请求到达时，Primary就知道，我们之前看到过这个请求，可能执行了也可能没执行成功。Primay要尝试确保B不会在文件中出现两次。所以首先需要的是探测重复的能力。

  • 对于Secondary来说，如果Primay要求Secondary执行一个操作，Secondary必须要执行而不是只返回一个错误给Primary。对于一个严格一致的系统来说，是不允许Secondary忽略Primary的请求而没有任何补偿措施的。所以我认为，Secondary需要接受请求并执行它们。如果Secondary有一些永久性故障，例如磁盘被错误的拔出了，你需要有一种机制将Secondary从系统中移除，这样Primary可以与剩下的Secondary继续工作。但是GFS没有做到这一点，或者说至少没有做对。

  • 当Primary要求Secondary追加数据时，直到Primary确信所有的Secondary都能执行数据追加之前，Secondary必须小心不要将数据暴露给读请求。所以对于写请求，你或许需要多个阶段。在第一个阶段，Primary向Secondary发请求，要求其执行某个操作，并等待Secondary回复说能否完成该操作，这时Secondary并不实际执行操作。在第二个阶段，如果所有Secondary都回复说可以执行该操作，这时Primary才会说，好的，所有Secondary执行刚刚你们回复可以执行的那个操作。这是现实世界中很多强一致系统的工作方式，这被称为两阶段提交（Two-phase commit）。

  • 另一个问题是，当Primary崩溃时，可能有一组操作由Primary发送给Secondary，Primary在确认所有的Secondary收到了请求之前就崩溃了。当一个Primary崩溃了，一个Secondary会接任成为新的Primary，但是这时，新Primary和剩下的Secondary会在最后几个操作有分歧，因为部分副本并没有收到前一个Primary崩溃前发出的请求。所以，新的Primary上任时，需要显式的与Secondary进行同步，以确保操作历史的结尾是相同的。

  • 最后，时不时的，Secondary之间可能会有差异，或者客户端从Master节点获取的是稍微过时的Secondary。系统要么需要将所有的读请求都发送给Primary，因为只有Primary知道哪些操作实际发生了，要么对于Secondary需要一个租约系统，就像Primary一样，这样就知道Secondary在哪些时间可以合法的响应客户端。

为了实现强一致，以上就是我认为的需要在系统中修复的东西，它们增加了系统的复杂度，增加了系统内部组件的交互。

3.VMware FT:

3.1 复制：

容错本身是为了提供高可用性。例如，当你想构建一个服务时，尽管计算机硬件总是有可能故障，但是我们还是希望能稳定的提供服务，甚至，即使出现了网络问题我们还是想能够提供服务。我们所使用到的工具就是复制。

3.1.1 Fail-stop：

单台计算机的fail-stop故障。Fail-stop是一种容错领域的通用术语。它是指，如果某些东西出了故障，比如说计算机，那么它会单纯的停止运行。当任何地方出现故障时，就停止运行，而不是运算出错误结果。

服务器彻底从网络上隔离的场景有点有趣，因为从外界来看，服务器和停止运行没有两样。所以，这些是我们可以通过复制处理的一些故障。复制也能处理一些硬件问题，比如，服务器的风扇坏了，进而会使CPU过热，而CPU会自我关闭，并停止运行。

3.1.2 复制不能解决的问题：

复制不能处理软件中的bug和硬件设计中的缺陷。

我们也不能期望复制可以处理硬件的漏洞，当硬件有漏洞的时候会计算出错误的结果，这时我们就无能为力了，至少基于复制这种技术，我们就无能为力了。

当然，如果你足够幸运的话，肯定也有一些硬件和软件的bug是可以被复制处理掉的。比如说，如果有一些不相关的软件运行在你的服务器上，并且它们导致了服务器崩溃，例如kernel panic或者服务器重启，虽然这些软件与你服务的副本无关，但是这种问题对于你的服务来说，也算是一种fail-stop。kernel panic之后，当前服务器上的服务副本会停止运行，备份副本会取而代之。

3.2 状态转移和复制状态机（State Transfer and Replicated State Machine）：

在VMware FT论文的开始，介绍了两种复制的方法，一种是状态转移（State Transfer），另一种是复制状态机（Replicated State Machine）。

3.2.1 状态转移：

如果我们有一个服务器的两个副本，我们需要让它们保持同步，在实际上互为副本，这样一旦Primary出现故障，因为Backup有所有的信息，就可以接管服务。

状态转移背后的思想是，Primary将自己完整状态，比如说内存中的内容，拷贝并发送给Backup。Backup会保存收到的最近一次状态，所以Backup会有所有的数据。当Primary故障了，Backup就可以从它所保存的最新状态开始运行。所以，状态转移就是发送Primary的状态。

假设采用了的话，那么转移的状态就是Primary内存里面的内容。这种情况下，每过一会，Primary就会对自身的内存做一大份拷贝，并通过网络将其发送到Backup。

为了提升效率，你可以想到每次同步只发送上次同步之后变更了的内存。

3.2.2 复制状态机：

复制状态机基于这个事实：我们想复制的大部分的服务或者计算机软件都有一些确定的内部操作，不确定的部分是外部的输入。通常情况下，如果一台计算机没有外部影响，它只是一个接一个的执行指令，每条指令执行的是计算机中内存和寄存器上确定的函数，只有当外部事件干预时，才会发生一些预期外的事。

例如，某个随机时间收到了一个网络数据包，导致服务器做一些不同的事情。所以，复制状态机不会在不同的副本之间发送状态，相应的，它只会从Primary将这些外部事件，例如外部的输入，发送给Backup。

通常来说，如果有两台计算机，如果它们从相同的状态开始，并且它们以相同的顺序，在相同的时间，看到了相同的输入，那么它们会一直互为副本，并且一直保持一致。

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

image-20240418211119252

人们倾向于使用复制状态机的原因是，通常来说，外部操作或者事件比服务的状态要小。如果是一个数据库的话，它的状态可能是整个数据库，可能到达GB这个级别，而操作只是一些客户端发起的请求，例如读key27的数据。所以操作通常来说比较小，而状态通常比较大。

所以复制状态机通常来说更吸引人一些。复制状态机的缺点是，它会更复杂一些，并且对于计算机的运行做了更多的假设。而状态转移就比较简单粗暴，我就是将我整个状态发送给你，你不需要再考虑别的东西。

如果我们要构建一个复制状态机的方案，我们有很多问题要回答，我们需要决定要在什么级别上复制状态，我们对状态的定义是什么，我们还需要担心Primary和Backup之间同步的频率。

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

3.3 Test-and-Set 服务:

一个非常常见的场景就是，Primary和Backup都在运行，但是它们之间的网络出现了问题，同时它们各自又能够与一些客户端通信。这时，它们都会以为对方挂了，自己需要上线并接管服务。所以现在，我们对于同一个服务，有两个机器是在线的。因为现在它们都不向彼此发送Log条目，它们自然就出现了分歧。它们或许会因为接收了不同的客户端请求，而变得不一样。

因为涉及到了计算机网络，那就可能出现上面的问题，而不仅仅是机器故障。如果我们同时让Primary和Backup都在线，那么我们现在就有了脑裂（Split Brain）。这篇论文解决这个问题的方法是，向一个外部的第三方权威机构求证，来决定Primary还是Backup允许上线。这里的第三方就是Test-and-Set服务。

Test-and-Set服务不运行在Primary和Backup的物理服务器上，VMware FT需要通过网络支持Test-and-Set服务。这个服务会在内存中保留一些标志位，当你向它发送一个Test-and-Set请求，它会设置标志位，并且返回旧的值。

Primary和Backup都需要获取Test-and-Set标志位，这有点像一个锁。为了能够上线，它们或许会同时发送一个Test-and-Set请求，给Test-and-Set服务。当第一个请求送达时，Test-and-Set服务会说，这个标志位之前是0，现在是1。第二个请求送达时，Test-and-Set服务会说，标志位已经是1了，你不允许成为Primary。

对于这个Test-and-Set服务，我们可以认为运行在单台服务器。当网络出现故障，并且两个副本都认为对方已经挂了时，Test-and-Set服务就是一个仲裁官，决定了两个副本中哪一个应该上线。(分布式锁)

4.Raft：

单机系统--高可用，高容错--分布式系统（建立副本）--一致性问题--一致性共识协议。

对于多副本写来说，无法解决网络分区问题，不具备自愈能力，对于主从复制来说，数据的一致性无法保证。

而raft和paxos最核心解决的问题正是通过过半投票解决网络分区问题，在多副本的高容错性上大大的提高。

但是，单纯的raft和paxos并不能具备强一致性，因为只要过半节点投票通过即可，但是却给实现强一致性提供了工程实现的可能，通过一些工程的优化可以基于raft搭建出来强一致性/线性一致性的系统。

在之前的课程中，我们介绍了几个具备容错特性（fault-tolerant）的系统。如果你有留心的话，你会发现，它们有一个共同的特点。

  • MapReduce复制了计算，但是复制这个动作，或者说整个MapReduce被一个单主节点控制。

  • GFS以主备（primary-backup）的方式复制数据。它会实际的复制文件内容。但是它也依赖一个单主节点，来确定每一份数据的主拷贝的位置。

  • VMware FT，它在一个Primary虚机和一个Backup虚机之间复制计算相关的指令。但是，当其中一个虚机出现故障时，为了能够正确的恢复。需要一个Test-and-Set服务来确认，Primary虚机和Backup虚机只有一个能接管计算任务。

这三个例子中，它们都是一个多副本系统（replication system），但是在背后，它们存在一个共性：它们需要一个单节点来决定，在多个副本中，谁是主（Primary）。

使用一个单节点的好处是，它不可能否认自己。因为只有一个节点，它的决策就是整体的决策。但是使用单节点的缺点是，它本身又是一个单点故障（Single Point of Failure）。

所以，你可以认为我们前面介绍的这些系统，它们将系统容错的关键点，转移到了这个单点上。这个单点，会在系统出现局部故障时，选择数据的主拷贝来继续工作。使用单点的原因是，我们需要避免脑裂（Split-Brain）。当出现故障时，我们之所以要极其小心的决定数据的主拷贝，是因为，如果不这么做的话，我们可能需要面临脑裂的场景。

4.1 脑裂：Split Brain

假设我们有一个网络，这个网络里面有两个服务器（S1，S2），这两个服务器都是我们Test-and-Set服务的拷贝。这个网络里面还有两个客户端（C1，C2），它们需要通过Test-and-Set服务确定主节点是谁。在这个例子中，这两个客户端本身就是VMware FT中的Primary和Backup虚拟机。

如果这是一个Test-and-Set服务，那么你知道这两个服务器中的数据记录将从0开始。任意一个客户端发送Test-and-Set指令，这个指令会将服务器中的状态设置成1。所以在这个图里面，两个服务器都应该设置成1，然后将旧的值0，返回给客户端。本质上来说，这是一种简化了的锁服务。

当一个客户端可以与其中一个服务器通信，但是不能与另一个通信时，有可能出现脑裂的问题。我们假设，客户端发送请求时，它会将请求同时发送给两个服务器。这样，我们就需要考虑，当某个服务器不响应时，客户端该怎么做？或者说，某个服务器不响应时，整个系统该如何响应？更具体点，我们假设C1可以访问S1但是不能访问S2，系统该如何响应？

  • 一种情况是，我们必然不想让C1只与S1通信。因为，如果我们只将C1的请求设置给S1，而不设置给S2，会导致S2的数据不一致。

  • 对于任何操作，客户端必须总是与两个服务器交互，而不是只与其中一个服务器交互。但是这是一个错误的想法，为什么呢？因为这里根本就没有容错。这里甚至比只使用一个服务器更糟。

  • 另一个明显的答案是，如果客户端不能同时与两个服务器交互，那它就与它能连通的那个服务器交互，同时认为另一个服务器已经关机了。为什么这也是一个错误的答案呢？因为，我们的故障场景是，另一个服务器其实还开机着。我们假设我们经历的实际问题并不是这个服务器关机了，因为如果关机了对我们来说其实更好。实际情况可能更糟糕，

4.1.2 出现原因：

实际可能是网络线路出现了故障，从而导致C1可以与S1交互，但是不能与S2交互。同时，C2可以与S2交互，但是不能与S1交互。现在我们规定，如果一个客户端连接了两个服务器，为了达到一定的容错性，客户端只与其中一个服务器交互也应该可以正常工作。但是这样就不可避免的出现了这种情况：假设这根线缆中断了，将网络分为两个部分。网络分区。

C1发送Test-and-Set请求给S1，S1将自己的状态设置为1，并返回之前的状态0给C1。

这就意味着，C1会认为自己持有锁。如果这是一个VMware FT，C1对应的虚拟机会认为自己可以成为主节点。

但是同时，S2里面的状态仍然是0。所以如果现在C2也发送了一个Test-and-Set请求，本来应该发送给两个服务器，但是现在从C2看来，S1不能访问，根据之前定义的规则，那就发送给S2吧。同样的C2也会认为自己持有了锁。如果这个Test-and-Set服务被VMware FT使用，那么这两个VMware 虚机都会认为自己成为了主虚拟机而不需要与另一个虚拟机协商，所以这是一个错误的场景。

在这种有两个拷贝副本的配置中，看起来我们只有两种选择：要么等待两个服务器响应，那么这个时候就没有容错能力；要么只等待一个服务器响应，那么就会进入错误的场景，而这种错误的场景，通常被称为脑裂。

4.1.2 解决方案：

  • 第一种是构建一个不可能出现故障的网络。实际上，不可能出现故障的网络一直在我们的身边。你们电脑中，连接了CPU和内存的线路就是不可能出现故障的网络。所以，带着合理的假设和大量的资金，同时小心的控制物理环境，比如不要将一根网线拖在地上，让谁都可能踩上去。如果网络不会出现故障，这样就排除了脑裂的可能。这里做了一些假设，但是如果有足够的资金，人们可以足够接近这个假设。当网络不出现故障时，那就意味着，如果客户端不能与一个服务器交互，那么这个服务器肯定是关机了。

  • 另一种就是人工解决问题，不要引入任何自动完成的操作。默认情况下，客户端总是要等待两个服务器响应，如果只有一个服务器响应，永远不要执行任何操作。相应的，给运维人员打电话，让运维人员去机房检查两个服务器。要么将一台服务器直接关机，要么确认一下其中一台服务器真的关机了，而另一个台还在工作。所以本质上，这里把人作为了一个决策器。而如果把人看成一台电脑的话，那么这个人他也是个单点。

4.2 过半票决（Majority Vote）：

尽管存在脑裂的可能，但是随着技术的发展，人们发现哪怕网络可能出现故障，可能出现分区，实际上是可以正确的实现能够自动完成故障切换的系统。

当网络出现故障，将网络分割成两半，网络的两边独自运行，且不能访问对方，这通常被称为网络分区。

在构建能自动恢复，同时又避免脑裂的多副本系统时，人们发现，关键点在于过半票决（Majority Vote）。

这是Raft论文中出现的，用来构建Raft的一个基本概念。过半票决系统的第一步在于，服务器的数量要是奇数，而不是偶数。例如在上图中（只有两个服务器），中间出现故障，那两边就太过对称了。这里被网络故障分隔的两边，它们看起来完全是一样的，它们运行了同样的软件，所以它们也会做相同的事情，这样不太好（会导致脑裂）。

但是，如果服务器的数量是奇数的，那么当出现一个网络分割时，两个网络分区将不再对称。假设出现了一个网络分割，那么一个分区会有两个服务器，另一个分区只会有一个服务器，这样就不再是对称的了。这是过半票决吸引人的地方。

首先你要有奇数个服务器。然后为了完成任何操作，例如Raft的Leader选举，例如提交一个Log条目，在任何时候为了完成任何操作，你必须凑够过半的服务器来批准相应的操作。这里的过半是指超过服务器总数的一半。直观来看，如果有3个服务器，那么需要2个服务器批准才能完成任何的操作。

这里背后的逻辑是，如果网络存在分区，那么必然不可能有超过一个分区拥有过半数量的服务器。例如，假设总共有三个服务器，如果一个网络分区有一个服务器，那么它不是一个过半的分区。如果一个网络分区有两个服务器，那么另一个分区必然只有一个服务器。因此另一个分区必然不能凑齐过半的服务器，也必然不能完成任何操作。

对于过半票决，可以用一个更通用的方程式来描述。在一个过半票决的系统中，如果有3台服务器，那么需要至少2台服务器来完成任意的操作。换个角度来看，这个系统可以接受1个服务器的故障，任意2个服务器都足以完成操作。如果你需要构建一个更加可靠的系统，那么你可以为系统加入更多的服务器。所以，更通用的方程是：

如果系统有 2 * F + 1 个服务器，那么系统最多可以接受F个服务器出现故障，仍然可以正常工作。

image-20240418220606292

通常这也被称为多数投票（quorum）系统，因为3个服务器中的2个，就可以完成多数投票。

前面已经提过，有关过半票决系统的一个特性就是，最多只有一个网络分区会有过半的服务器，所以我们不可能有两个分区可以同时完成操作。这里背后更微妙的点在于，如果你总是需要过半的服务器才能完成任何操作，同时你有一系列的操作需要完成，其中的每一个操作都需要过半的服务器来批准，例如选举Raft的Leader，那么每一个操作对应的过半服务器，必然至少包含一个服务器存在于上一个操作的过半服务器中。也就是说，任意两组过半服务器，至少有一个服务器是重叠的。

相比其他特性，Raft更依赖这个特性来避免脑裂。例如，当一个Raft Leader竞选成功，那么这个Leader必然凑够了过半服务器的选票，而这组过半服务器中，必然与旧Leader的过半服务器有重叠。所以，新的Leader必然知道旧Leader使用的任期号（term number），因为新Leader的过半服务器必然与旧Leader的过半服务器有重叠，而旧Leader的过半服务器中的每一个必然都知道旧Leader的任期号。类似的，任何旧Leader提交的操作，必然存在于过半的Raft服务器中，而任何新Leader的过半服务器中，必然有至少一个服务器包含了旧Leader的所有操作。这是Raft能正确运行的一个重要因素。

学生提问：可以为Raft添加服务器吗？

Rober教授：Raft的服务器是可以添加或者修改的，Raft的论文有介绍，可能在Section 6。如果是一个长期运行的系统，例如运行5年或者10年，你可能需要定期更换或者升级一些服务器，因为某些服务器可能会出现永久的故障，又或者你可能需要将服务器搬到另一个机房去。所以，肯定需要支持修改Raft服务器的集合。虽然这不是每天都发生，但是这是一个长期运行系统的重要维护工作。Raft的作者提出了方法来处理这种场景，但是比较复杂。

所以，在过半票决这种思想的支持下，大概1990年的时候，有两个系统基本同时被提出。这两个系统指出，你可以使用这种过半票决系统，从某种程度上来解决之前明显不可能避免的脑裂问题，例如，通过使用3个服务器而不是2个，同时使用过半票决策略。两个系统中的一个叫做Paxos，Raft论文对这个系统做了很多的讨论；另一个叫做ViewStamped Replication（VSR）。尽管Paxos的知名度高得多，Raft从设计上来说，与VSR更接近。VSR是由MIT发明的。这两个系统有着数十年的历史，但是他们仅仅是在15年前，也就是他们发明的15年之后，才开始走到最前线，被大量的大规模分布式系统所使用。

4.3 Raft初探：

Raft会以库（Library）的形式存在于服务中。如果你有一个基于Raft的多副本服务，那么每个服务的副本将会由两部分组成：应用程序代码和Raft库。应用程序代码接收RPC或者其他客户端请求；不同节点的Raft库之间相互合作，来维护多副本之间的操作同步。

从软件的角度来看一个Raft节点，我们可以认为在该节点的上层，是应用程序代码。例如对于Lab 3来说，这部分应用程序代码就是一个Key-Value数据库。应用程序通常都有状态，Raft层会帮助应用程序将其状态拷贝到其他副本节点。对于一个Key-Value数据库而言，对应的状态就是Key-Value Table。应用程序往下，就是Raft层。所以，Key-Value数据库需要对Raft层进行函数调用，来传递自己的状态和Raft反馈的信息。

image-20240418220855019

例如一个访问Key-Value数据库的请求。这些请求可能是Put也可能是Get。Put请求带了一个Key和一个Value，将会更新Key-Value数据库中，Key对应的Value；而Get向当前服务请求某个Key对应的Value。

一旦一个Put请求从客户端发送到了服务端，对于一个单节点的服务来说，应用程序会直接执行这个请求，更新Key-Value表，之后返回对于这个Put请求的响应。但是对于一个基于Raft的多副本服务，就要复杂一些。

假设客户端将请求发送给Raft的Leader节点，在服务端程序的内部，应用程序只会将来自客户端的请求对应的操作向下发送到Raft层，并且告知Raft层，请把这个操作提交到多副本的日志（Log）中，并在完成时通知我。

之后，Raft节点之间相互交互，直到过半的Raft节点将这个新的操作加入到它们的日志中，也就是说这个操作被过半的Raft节点复制了。

当且仅当Raft的Leader节点知道了所有（课程里说的是所有，但是这里应该是过半节点）的副本都有了这个操作的拷贝之后。Raft的Leader节点中的Raft层，会向上发送一个通知到应用程序，也就是Key-Value数据库，来说明：刚刚你提交给我的操作，我已经提交给所有（注：同上一个说明）副本，并且已经成功拷贝给它们了，现在，你可以真正的执行这个操作了。

所以，客户端发送请求给Key-Value数据库，这个请求不会立即被执行，因为这个请求还没有被拷贝。当且仅当这个请求存在于过半的副本节点中时，Raft才会通知Leader节点，只有在这个时候，Leader才会实际的执行这个请求。对于Put请求来说，就是更新Value，对于Get请求来说，就是读取Value。最终，请求返回给客户端，这就是一个普通请求的处理过程。

4.4 Raft工作流程：时序图：

从另一个角度来看Raft Log同步的一些交互，这种角度将会在这门课中出现很多次，那就是时序图。

假设我们有一个客户端，服务器1是当前Raft集群的Leader。同时，我们还有服务器2，服务器3。这张图的纵坐标是时间，越往下时间越长。

1.假设客户端将请求发送给服务器1，这里的客户端请求就是一个简单的请求，例如一个Put请求。

image-20240418221201041

2.之后，服务器1的Raft层会发送一个添加日志（AppendEntries）的RPC到其他两个副本（S2，S3）。现在服务器1会一直等待其他副本节点的响应，一直等到过半节点的响应返回。这里的过半节点包括Leader自己。所以在一个只有3个副本节点的系统中，Leader只需要等待一个其他副本节点。

image-20240418221227806

3.当Leader收到了过半服务器的正确响应，Leader会执行（来自客户端的）请求，得到结果，并将结果返回给客户端。

image-20240418221301887

4.与此同时，服务器3可能也会将它的响应返回给Leader，尽管这个响应是有用的，但是这里不需要等待这个响应。

5.现在Leader知道过半服务器已经添加了Log，可以执行客户端请求，并返回给客户端。但是服务器2还不知道这一点，服务器2只知道：我从Leader那收到了这个请求，但是我不知道这个请求是不是已经被Leader提交（committed）了，这取决于我的响应是否被Leader收到。服务器2只知道，它的响应提交给了网络，或许Leader没有收到这个响应，也就不会决定commit这个请求。所以这里还有一个阶段。一旦Leader发现请求被commit之后，它需要将这个消息通知给其他的副本。所以这里有一个额外的消息。

这条消息的具体内容依赖于整个系统的状态。至少在Raft中，没有明确的committed消息。相应的，committed消息被夹带在下一个AppendEntries消息中，由Leader下一次的AppendEntries对应的RPC发出。任何情况下，当有了committed消息时，这条消息会填在AppendEntries的RPC中。下一次Leader需要发送心跳，或者是收到了一个新的客户端请求，要将这个请求同步给其他副本时，Leader会将新的更大的commit号随着AppendEntries消息发出，当其他副本收到了这个消息，就知道之前的commit号已经被Leader提交，其他副本接下来也会执行相应的请求，更新本地的状态。

image-20240418221402163

4.5 日志（Raft Log）：

Raft系统之所以对Log关注这么多的一个原因是，Log是Leader用来对操作排序的一种手段。这对于复制状态机（详见4.2）而言至关重要，对于这些复制状态机来说，所有副本不仅要执行相同的操作，还需要用相同的顺序执行这些操作。而Log与其他很多事物，共同构成了Leader对接收到的客户端操作分配顺序的机制。

比如说，我有10个客户端同时向Leader发出请求，Leader必须对这些请求确定一个顺序，并确保所有其他的副本都遵从这个顺序。实际上，Log是一些按照数字编号的槽位（类似一个数组），槽位的数字表示了Leader选择的顺序。

Log的另一个用途是，在一个（非Leader，也就是Follower）副本收到了操作，但是还没有执行操作时。该副本需要将这个操作存放在某处，直到收到了Leader发送的新的commit号才执行。

Log的另一个用途是用在Leader节点，我（Robert教授）很喜欢这个特性。Leader需要在它的Log中记录操作，因为这些操作可能需要重传给Follower。如果一些Follower由于网络原因或者其他原因短时间离线了或者丢了一些消息，Leader需要能够向Follower重传丢失的Log消息。所以，Leader也需要一个地方来存放客户端请求的拷贝。即使对那些已经commit的请求，为了能够向丢失了相应操作的副本重传，也需要存储在Leader的Log中。

所有节点都需要保存Log还有一个原因，就是它可以帮助重启的服务器恢复状态。你可能的确需要一个故障了的服务器在修复后，能重新加入到Raft集群，要不然你就永远少了一个服务器。比如对于一个3节点的集群来说，如果一个节点故障重启之后不能自动加入，那么当前系统只剩2个节点，那将不能再承受任何故障，所以我们需要能够重新并入故障重启了的服务器。对于一个重启的服务器来说，会使用存储在磁盘中的Log。每个Raft节点都需要将Log写入到它的磁盘中，这样它故障重启之后，Log还能保留。而这个Log会被Raft节点用来从头执行其中的操作进而重建故障前的状态，并继续以这个状态运行。所以，Log也会被用来持久化存储操作，服务器可以依赖这些操作来恢复状态。

4.6 应用层接口：

假设我们的应用程序是一个key-value数据库，下面一层是Raft层。

在Raft集群中，每一个副本上，这两层之间主要有两个接口。

第一个接口是key-value层用来转发客户端请求的接口。如果客户端发送一个请求给key-value层，key-value层会将这个请求转发给Raft层，并说：请将这个请求存放在Log中的某处。这个接口实际上是个函数调用，称之为Start函数。这个函数只接收一个参数，就是客户端请求。key-value层说：我接到了这个请求，请把它存在Log中，并在committed之后告诉我。

第二个接口是，随着时间的推移，Raft层会通知key-value层：哈，你刚刚在Start函数中传给我的请求已经commit了。Raft层通知的，不一定是最近一次Start函数传入的请求。例如在任何请求commit之前，可能会再有超过100个请求通过Start函数传给Raft层。这个向上的接口以go channel中的一条消息的形式存在。Raft层会发出这个消息，key-value层要读取这个消息。所以这里有个叫做applyCh的channel，通过它你可以发送ApplyMsg消息。

image-20240418221753940

4.7 Leader选举（Leader Election）：

4.7.1 为什么需要leader：

可以不用Leader就构建一个类似的系统。实际上有可能不引入任何指定的Leader，通过一组服务器来共同认可Log的顺序，进而构建一个一致系统。实际上，Raft论文中引用的Paxos系统就没有Leader，所以这是有可能的。

有很多原因导致了Raft系统有一个Leader，其中一个最主要的是：通常情况下，如果服务器不出现故障，有一个Leader的存在，会使得整个系统更加高效。因为有了一个大家都知道的指定的Leader，对于一个请求，你可以只通过一轮消息就获得过半服务器的认可。

对于一个无Leader的系统，通常需要一轮消息来确认一个临时的Leader，之后第二轮消息才能确认请求。所以，使用一个Leader可以提升系统性能至2倍。同时，有一个Leader可以更好的理解Raft系统是如何工作的。

4.7.2 开始选举：

Raft生命周期中可能会有不同的Leader，它使用任期号（term number）来区分不同的Leader。Followers（非Leader副本节点）不需要知道Leader的ID，它们只需要知道当前的任期号。每一个任期最多有一个Leader，这是一个很关键的特性。对于每个任期来说，或许没有Leader，或许有一个Leader，但是不可能有两个Leader出现在同一个任期中。每个任期必然最多只有一个Leader。

每个Raft节点都有一个选举定时器（Election Timer），如果在这个定时器时间耗尽之前，当前节点没有收到任何当前Leader的消息，这个节点会认为Leader已经下线，并开始一次选举。所以我们这里有了这个选举定时器，当它的时间耗尽时，当前节点会开始一次选举。

开始一次选举的意思是，当前服务器会增加任期号（term number），因为它想成为一个新的Leader。

4.7.3 发起投票：

之后，当前服务器会发出请求投票（RequestVote）RPC，这个消息会发给所有的Raft节点。其实只需要发送到N-1个节点，因为Raft规定了，Leader的候选人总是会在选举时投票给自己。

并不是说如果Leader没有故障，就不会有选举。但是如果Leader的确出现了故障，那么一定会有新的选举。这个选举的前提是其他服务器还在运行，因为选举需要其他服务器的选举定时器超时了才会触发。另一方面，如果Leader没有故障，我们仍然有可能会有一次新的选举。比如，如果网络很慢，丢了几个心跳，或者其他原因，这时，尽管Leader还在健康运行，我们可能会有某个选举定时器超时了，进而开启一次新的选举。在考虑正确性的时候，我们需要记住这点。所以这意味着，如果有一场新的选举，有可能之前的Leader仍然在运行，并认为自己还是Leader。例如，当出现网络分区时，旧Leader始终在一个小的分区中运行，而较大的分区会进行新的选举，最终成功选出一个新的Leader。这一切，旧的Leader完全不知道。所以我们也需要关心，在不知道有新的选举时，旧的Leader会有什么样的行为？

假设网线故障了，旧的Leader在一个网络分区中，这个网络分区中有一些客户端和少数（未过半）的服务器。在网络的另一个分区中，有着过半的服务器，这些服务器选出了一个新的Leader。旧的Leader会怎样，或者说为什么旧的Leader不会执行错误的操作？

如果一个Leader在一个网络分区中，并且这个网络分区没有过半的服务器。那么下次客户端发送请求时，这个在少数分区的Leader，它会发出AppendEntries消息。但是因为它在少数分区，即使包括它自己，它也凑不齐过半服务器，所以它永远不会commit这个客户端请求，它永远不会执行这个请求，它也永远不会响应客户端，并告诉客户端它已经执行了这个请求。

所以，如果一个旧的Leader在一个不同的网络分区中，客户端或许会发送一个请求给这个旧的Leader，但是客户端永远也不能从这个Leader获得响应。所以没有客户端会认为这个旧的Leader执行了任何操作。另一个更奇怪的问题是，有可能Leader在向一部分Followers发完AppendEntries消息之后就故障了，所以这个Leader还没决定commit这个请求。

4.7.4 进行投票：

为了能够当选，Raft要求一个候选人从过半服务器中获得认可投票。每个Raft节点，只会在一个任期内投出一个认可选票。这意味着，在任意一个任期内，每一个节点只会对一个候选人投一次票。这样，就不可能有两个候选人同时获得过半的选票，因为每个节点只会投票一次。所以这里是过半原则导致了最多只能有一个胜出的候选人，这样我们在每个任期会有最多一个选举出的候选人。

过半原则意味着，即使一些节点已经故障了，你仍然可以赢得选举。如果少数服务器故障了或者出现了网络问题，我们仍然可以选举出Leader。如果超过一半的节点故障了，不可用了，或者在另一个网络分区，那么系统会不断地额尝试选举Leader，并永远也不能选出一个Leader，因为没有过半的服务器在运行。

4.7.5 通知选举：

如果一次选举成功了，整个集群的节点是如何知道的呢？当一个服务器赢得了一次选举，这个服务器会收到过半的认可投票，这个服务器会直接知道自己是新的Leader，因为它收到了过半的投票。但是其他的服务器并不能直接知道谁赢得了选举，其他服务器甚至都不知道是否有人赢得了选举。这时，（赢得了选举的）候选人，会通过心跳通知其他服务器。

aft规定，除非是当前任期的Leader，没人可以发出AppendEntries消息。所以假设我是一个服务器，我发现对于任期19有一次选举，过了一会我收到了一条AppendEntries消息，这个消息的任期号就是19。那么这条消息告诉我，我不知道的某个节点赢得了任期19的选举。所以，其他服务器通过接收特定任期号的AppendEntries来知道，选举成功了。

4.7.6 选举定时器（Election Timer）:

一个导致选举失败的更有趣的场景是，所有环节都在正常工作，没有故障，没有丢包，但是候选人们几乎是同时参加竞选，它们分割了选票（Split Vote）。假设我们有一个3节点的多副本系统，3个节点的选举定时器几乎同超时，进而期触发选举。

首先，每个节点都会为自己投票。之后，每个节点都会收到其他节点的RequestVote消息，因为该节点已经投票给自己了，所以它会返回反对投票。这意味着，3个节点中的每个节点都只能收到一张投票（来自于自己）。

没有一个节点获得了过半投票，所以也就没有人能被选上。接下来它们的选举定时器会重新计时，因为选举定时器只会在收到了AppendEntries消息时重置，但是由于没有Leader，所有也就没有AppendEntries消息。所有的选举定时器重新开始计时，如果我们不够幸运的话，所有的定时器又会在同一时间到期，所有节点又会投票给自己，又没有人获得了过半投票，这个状态可能会一直持续下去。

Raft不能完全避免分割选票（Split Vote），但是可以使得这个场景出现的概率大大降低。Raft通过为选举定时器随机的选择超时时间来达到这一点。我们可以这样来看这种随机的方法。假设这里有个时间线，我会在上面画上事件。在某个时间，所有的节点收到了最后一条AppendEntries消息。之后，Leader就故障了。我们这里假设Leader在发出最后一次心跳之后就故障关机了。所有的Followers在同一时间重置了它们的选举定时器，因为它们大概率在同一时间收到了这条AppendEntries消息。

image-20240418222540835

因为不同的服务器都选取了随机的超时时间，总会有一个选举定时器先超时，而另一个后超时。假设S2和S3之间的差距足够大，先超时的那个节点（也就是S2）能够在另一个节点（也就是S3）超时之前，发起一轮选举，并获得过半的选票，那么那个节点（也就是S2）就可以成为新的Leader。

4.8 可能的异常情况：

在Raft中，当Leader故障了才有可能出错。

4.8.1 日志恢复（Log Backup）：

Leader使用了一种备份机制来探测Followers的Log中，第一个与Leader的Log相同的位置。在获得位置之后，Leader会给Follower发送从这个位置开始的，剩余的全部Log。经过这个过程，所有节点的Log都可以和Leader保持一致。

因此无论之前的Leader是谁，发送了这条Log，它都没有得到过半服务器的认可。因此旧的Leader不可能commit了这条记录，也就不可能将它应用到应用程序的状态中，进而也就不可能回复给客户端说请求成功了。因为它没有存在于过半服务器中，发送这个请求的客户端没有理由认为这个请求被执行了，也不可能得到一个回复。

Leader只会在commit之后回复给客户端。客户端甚至都没有理由相信这个请求被任意服务器收到了。并且，Raft论文中的图2说明，如果客户端发送请求之后一段时间没有收到回复，它应该重新发送请求。所以我们知道，不论这个被丢弃的请求是什么，我们都没有执行它，没有把它包含在任何状态中，并且客户端之后会重新发送这个请求。

4.8.2 选举约束（Election Restriction）：

哪些节点允许成为Leader？

为了保证系统的正确性，并非任意节点都可以成为Leader。不是说第一个选举定时器超时了并触发选举的节点，就一定是Leader。Raft对于谁可以成为Leader，谁不能成为Leader是有一些限制的。

在处理别节点发来的RequestVote RPC时，需要做一些检查才能投出赞成票。这里的限制是，节点只能向满足下面条件之一的候选人投出赞成票：

  1. 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号；

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

4.8.3 快速恢复（Fast Backup）：

如果Log有冲突，Leader每次会回退一条Log条目。 这在许多场景下都没有问题。但是在某些现实的场景中，至少在Lab2的测试用例中，每次只回退一条Log条目会花费很长很长的时间。

现实的场景中，可能一个Follower关机了很长时间，错过了大量的AppendEntries消息。这时，Leader重启了。按照Raft论文中的图2，如果一个Leader重启了，它会将所有Follower的nextIndex设置为Leader本地Log记录的下一个槽位。所以，如果一个Follower关机并错过了1000条Log条目，Leader重启之后，需要每次通过一条RPC来回退一条Log条目来遍历1000条Follower错过的Log记录。这种情况在现实中并非不可能发生。

所以，为了能够更快的恢复日志，大致思想是，让Follower返回足够的信息给Leader，这样Leader可以以任期（Term）为单位来回退，而不用每次只回退一条Log条目。所以现在，在恢复Follower的Log时，如果Leader和Follower的Log不匹配，Leader只需要对每个不同的任期发送一条AppendEntries，而不用对每个不同的Log条目发送一条AppendEntries。这只是一种加速策略，当然，或许你也可以想出许多其他不同的日志恢复加速策略。

4.8.4 持久化（Persistence）:

如果一个服务器故障了，那简单直接的方法就是将它从集群中摘除。我们需要具备从集群中摘除服务器，替换一个全新的空的服务器，并让该新服务器在集群内工作的能力。实际上，这是至关重要的，因为如果一些服务器遭受了不可恢复的故障，例如磁盘故障，你绝对需要替换这台服务器。同时，如果磁盘故障了，你也不能指望能从该服务器的磁盘中获得任何有用的信息。所以我们的确需要能够用全新的空的服务器替代现有服务器的能力。你或许认为，这就足以应对任何出问题的场景了，但实际上不是的。

实际上，一个常见的故障是断电。断电的时候，整个集群都同时停止运行，这种场景下，我们不能通过从Dell买一些新的服务器来替换现有服务器进而解决问题。这种场景下，如果我们希望我们的服务是容错的， 我们需要能够得到之前状态的拷贝，这样我们才能保持程序继续运行。因此，至少为了处理同时断电的场景，我们不得不让服务器能够将它们的状态存储在某处，这样当供电恢复了之后，还能再次获取这个状态。这里的状态是指，为了让服务器在断电或者整个集群断电后，能够继续运行所必不可少的内容。这是理解持久化存储的一种方式。

在Raft中，有且仅有三个数据是需要持久化存储的。它们分别是Log、currentTerm、votedFor。

Log是所有的Log条目。当某个服务器刚刚重启，在它加入到Raft集群之前，它必须要检查并确保这些数据有效的存储在它的磁盘上。服务器必须要有某种方式来发现，自己的确有一些持久化存储的状态，而不是一些无意义的数据。Log需要被持久化存储的原因是，这是唯一记录了应用程序状态的地方。

currentTerm和votedFor都是用来确保每个任期只有最多一个Leader。在一个故障的场景中，如果一个服务器收到了一个RequestVote请求，并且为服务器1投票了，之后它故障。如果它没有存储它为哪个服务器投过票，当它故障重启之后，收到了来自服务器2的同一个任期的另一个RequestVote请求，那么它还是会投票给服务器2，因为它发现自己的votedFor是空的，因此它认为自己还没投过票。现在这个服务器，在同一个任期内同时为服务器1和服务器2投了票。因为服务器1和服务器2都会为自己投票，它们都会认为自己有过半选票（3票中的2票），那它们都会成为Leader。现在同一个任期里面有了两个Leader。这就是为什么votedFor必须被持久化存储。

currentTerm的情况要更微妙一些，但是实际上还是为了实现一个任期内最多只有一个Leader.

4.8.5 日志快照（Log Snapshot）:

对于一个长期运行的系统，例如运行了几周，几个月甚至几年，如果我们按照Raft的规则，那么Log会持续增长。最后可能会有数百万条Log，从而需要大量的内存来存储。如果持久化存储在磁盘上，最终会消耗磁盘的大量空间。如果一个服务器重启了，它需要通过重新从头开始执行这数百万条Log来重建自己的状态。当故障重启之后，遍历并执行整个Log的内容可能要花费几个小时来完成。这在某种程度上来说是浪费，因为在重启之前，服务器已经有了一定的应用程序状态。

为了应对这种场景，Raft有了快照（Snapshots）的概念。快照背后的思想是，要求应用程序将其状态的拷贝作为一种特殊的Log条目存储下来。

重启的时候会发生什么呢？现在，重启的场景比之前只有Log会更加复杂一点。重启的时候，必须让Raft有方法知道磁盘中最近的快照和Log的组合，并将快照传递给应用程序。因为现在我们不能重演所有的Log（部分被删掉了），所以必须要有一种方式来初始化应用程序。所以应用程序不仅需要有能力能生成一个快照，它还需要能够吸纳一个之前创建的快照，并通过它稳定的重建自己的内存。所以，尽管Raft在管理快照，快照的内容实际上是应用程序的属性。Raft并不理解快照中有什么，只有应用程序知道，因为快照里面都是应用程序相关的信息。所以重启之后，应用程序需要能够吸纳Raft能找到的最近的一次快照。到目前为止还算简单。

4.8.6 线性一致（Linearizability）:

通常来说，线性一致等价于强一致。一个服务是线性一致的，那么它表现的就像只有一个服务器，并且服务器没有故障，这个服务器每次执行一个客户端请求，并且没什么奇怪的是事情发生。

一个系统的执行历史是一系列的客户端请求，或许这是来自多个客户端的多个请求。如果执行历史整体可以按照一个顺序排列，且排列顺序与客户端请求的实际时间相符合，那么它是线性一致的。当一个客户端发出一个请求，得到一个响应，之后另一个客户端发出了一个请求，也得到了响应，那么这两个请求之间是有顺序的，因为一个在另一个完成之后才开始。一个线性一致的执行历史中的操作是非并发的，也就是时间上不重合的客户端请求与实际执行时间匹配。并且，每一个读操作都看到的是最近一次写入的值。

5.Zookeeper:

Zookeeper是一个现实世界成功的系统，是一个很多人使用的开源服务，并且集成到了很多现实世界的软件中，所以它肯定有一些现实意义和成功。自然而然，Zookeeper的设计应该是一个合理的设计，这使得它变得吸引人。

相比Raft来说，Raft实际上就是一个库。你可以在一些更大的多副本系统中使用Raft库。但是Raft不是一个你可以直接交互的独立的服务，你必须要设计你自己的应用程序来与Raft库交互。

Zookeeper实际上运行在Zab之上，从我们的角度来看，Zab几乎与Raft是一样的。这里我只看多副本系统的性能，我并不关心Zookeeper的具体功能。

当一个客户端发送了一个请求，Zab层会将这个请求的拷贝发送给其他的副本，其他副本会将请求追加在它们的内存中的Log或者是持久化存储在磁盘上，这样它们故障重启之后可以取回这些Log。

当我们加入更多的服务器时，Leader几乎可以确定是一个瓶颈，因为Leader需要处理每一个请求，它需要将每个请求的拷贝发送给每一个其他服务器。当你添加更多的服务器时，你只是为现在的瓶颈（Leader节点）添加了更多的工作负载。

5.1 读不具备线性一致性：

如果你有一个读请求，把它发给某一个副本而不是Leader。如果我们这么做了，对于写请求没有什么帮助，是我们将大量的读请求的负担从Leader移走了。现在对于读请求来说，有了很大的提升，因为现在，添加越多的服务器，我们可以支持越多的客户端读请求，因为我们将客户端的读请求分担到了不同的副本上。

其中一个原因是，这个副本可能不在Leader所在的过半服务器中。对于Raft来说，Leader只会等待它所在的过半服务器中的其他follower对于Leader发送的AppendEntries消息的返回，之后Leader才会commit消息，并进行下一个操作。所以，如果这个副本不在过半服务器中，它或许永远也看不到写请求。又或许网络丢包了，这个副本永远没有收到这个写请求。所以，有可能Leader和过半服务器可以看见前三个请求，但是这个副本只能看见前两个请求，而错过了请求C。所以从这个副本读数据可能读到一个旧的数据。

即使这个副本看到了相应的Log条目，它可能收不到commit消息。Zookeeper的Zab与Raft非常相似，它先发出Log条目，之后，当Leader收到了过半服务器的回复，Leader会发送commit消息。然后这个副本可能没有收到这个commit消息。

最坏的情况是，我之前已经说过，这个副本可能与Leader不在一个网络分区，或者与Leader完全没有通信，作为follower，完全没有方法知道它与Leader已经失联了，并且不能收到任何消息了（心跳呢？）。

Zookeeper并不要求返回最新的写入数据。Zookeeper的方式是，放弃线性一致性。它对于这里问题的解决方法是，不提供线性一致的读。所以，因此，Zookeeper也不用为读请求提供最新的数据。它有自己有关一致性的定义，而这个定义不是线性一致的，因此允许为读请求返回旧的数据。

如果系统不提供线性一致性，那么系统是否还可用？

5.2 线性一致性的保证：Consistency Guarantees

Zookeeper的确有一些一致性的保证，用来帮助那些使用基于Zookeeper开发应用程序的人，来理解他们的应用程序，以及理解当他们运行程序时，会发生什么。

5.2.1 写请求：

Zookeeper并不是一个严格的读写系统。写请求通常也会跟着读请求。对于这种混合的读写请求，任何更改状态的操作相比其他更改状态的操作，都是线性一致的。所以，写请求是线性一致的。

任何一个客户端的请求，都会按照客户端指定的顺序来执行，论文里称之为FIFO（First In First Out）客户端序列。，如果一个特定的客户端发送了一个写请求之后是一个读请求或者任意请求，那么首先，所有的写请求会以这个客户端发送的相对顺序，加入到所有客户端的写请求中（满足保证1）。所以，如果一个客户端说，先完成这个写操作，再完成另一个写操作，之后是第三个写操作，那么在最终整体的写请求的序列中，可以看到这个客户端的写请求以相同顺序出现（虽然可能不是相邻的）。所以，对于写请求，最终会以客户端确定的顺序执行。

这里实际上是服务端需要考虑的问题，因为客户端是可以发送异步的写请求，也就是说客户端可以发送多个写请求给Zookeeper Leader节点，而不用等任何一个请求完成。Zookeeper论文并没有明确说明，但是可以假设，为了让Leader可以实际的按照客户端确定的顺序执行写请求，我设想，客户端实际上会对它的写请求打上序号，表明它先执行这个，再执行这个，第三个是这个，而Zookeeper Leader节点会遵从这个顺序。这里由于有这些异步的写请求变得非常有意思。

5.2.2 读请求：

请求不需要经过Leader，只有写请求经过Leader，读请求只会到达某个副本。

对于读请求，我们应该这么考虑FIFO客户端序列，客户端会以某种顺序读某个数据，之后读第二个数据，之后是第三个数据，对于那个副本上的Log来说，每一个读请求必然要在Log的某个特定的点执行，或者说每个读请求都可以在Log一个特定的点观察到对应的状态。

然后，后续的读请求，必须要在不早于当前读请求对应的Log点执行。也就是一个客户端发起了两个读请求，如果第一个读请求在Log中的一个位置执行，那么第二个读请求只允许在第一个读请求对应的位置或者更后的位置执行。

第二个读请求不允许看到之前的状态，第二个读请求至少要看到第一个读请求的状态。这是一个极其重要的事实，我们会用它来实现正确的Zookeeper应用程序。

5.3 同步操作：（sync）：

Zookeeper有一个弥补（非严格线性一致）的方法。

Zookeeper有一个操作类型是sync，它本质上就是一个写请求。假设我知道你最近写了一些数据，并且我想读出你写入的数据，所以现在的场景是，我想读出Zookeeper中最新的数据。这个时候，我可以发送一个sync请求，它的效果相当于一个写请求，所以它最终会出现在所有副本的Log中。

接下来，在发送读请求时，我（客户端）告诉副本，在看到我上一次sync请求之前，不要返回我的读请求。

如果这里把sync看成是一个写请求，这里实际上符合了FIFO客户端请求序列，因为读请求必须至少要看到同一个客户端前一个写请求对应的状态。所以，如果我发送了一个sync请求之后，又发送了一个读请求。Zookeeper必须要向我返回至少是我发送的sync请求对应的状态。

不管怎么样，如果我需要读最新的数据，我需要发送一个sync请求，之后再发送读请求。这个读请求可以保证看到sync对应的状态，所以可以合理的认为是最新的。但是同时也要认识到，这是一个代价很高的操作，因为我们现在将一个廉价的读操作转换成了一个耗费Leader时间的sync操作。所以，如果不是必须的，那还是不要这么做。

5.4 就绪文件（Ready file/znode）：

我们假设有另外一个分布式系统，这个分布式有一个Master节点，而Master节点在Zookeeper中维护了一个配置，这个配置对应了一些file（也就是znode）。通过这个配置，描述了有关分布式系统的一些信息，例如所有worker的IP地址，或者当前谁是Master。所以，现在Master在更新这个配置，同时，或许有大量的客户端需要读取相应的配置，并且需要发现配置的每一次变化。所以，现在的问题是，尽管配置被分割成了多个file，我们还能有原子效果的更新吗？

为什么要有原子效果的更新呢？因为只有这样，其他的客户端才能读出完整更新的配置，而不是读出更新了一半的配置。这是人们使用Zookeeper管理配置文件时的一个经典场景。

5.5 API:

Zookeeper的特点：

  • Zookeeper基于（类似于）Raft框架，所以我们可以认为它是，当然它的确是容错的，它在发生网络分区的时候，也能有正确的行为。

  • 当我们在分析各种Zookeeper的应用时，我们也需要记住Zookeeper有一些性能增强，使得读请求可以在任何副本被处理，因此，可能会返回旧数据。

  • 另一方面，Zookeeper可以确保一次只处理一个写请求，并且所有的副本都能看到一致的写请求顺序。这样，所有副本的状态才能保证是一致的（写请求会改变状态，一致的写请求顺序可以保证状态一致）。

  • 由一个客户端发出的所有读写请求会按照客户端发出的顺序执行。

  • 一个特定客户端的连续请求，后来的请求总是能看到相比较于前一个请求相同或者更晚的状态（详见8.5 FIFO客户端序列）。

Zookeeper的目标是解决什么问题，或者期望用来解决什么问题？

  • 对于我来说，使用Zookeeper的一个主要原因是，它可以是一个VMware FT所需要的Test-and-Set服务（详见4.7）的实现。Test-and-Set服务在发生主备切换时是必须存在的，但是在VMware FT论文中对它的描述却又像个谜一样，论文里没有介绍：这个服务究竟是什么，它是容错的吗，它能容忍网络分区吗？Zookeeper实际的为我们提供工具来写一个容错的，完全满足VMware FT要求的Test-and-Set服务，并且可以在网络分区时，仍然有正确的行为。这是Zookeeper的核心功能之一。

  • 使用Zookeeper还可以做很多其他有用的事情。其中一件是，人们可以用它来发布其他服务器使用的配置信息。例如，向某些Worker节点发布当前Master的IP地址。

  • 另一个Zookeeper的经典应用是选举Master。当一个旧的Master节点故障时，哪怕说出现了网络分区，我们需要让所有的节点都认可同一个新的Master节点。

  • 如果新选举的Master需要将其状态保持到最新，比如说GFS的Master需要存储对于一个特定的Chunk的Primary节点在哪，现在GFS的Master节点可以将其存储在Zookeeper中，并且知道Zookeeper不会丢失这个信息。当旧的Master崩溃了，一个新的Master被选出来替代旧的Master，这个新的Master可以直接从Zookeeper中读出旧Master的状态。

  • 其他还有，对于一个类似于MapReduce的系统，Worker节点可以通过在Zookeeper中创建小文件来注册自己。

  • 同样还是类似于MapReduce这样的系统，你可以设想Master节点通过向Zookeeper写入具体的工作，之后Worker节点从Zookeeper中一个一个的取出工作，执行，完成之后再删除工作。

Zookeeper的API某种程度上来说像是一个文件系统。它有一个层级化的目录结构，有一个根目录（root），之后每个应用程序有自己的子目录。比如说应用程序1将自己的文件保存在APP1目录下，应用程序2将自己的文件保存在APP2目录下，这些目录又可以包含文件和其他的目录。

Zookeeper被设计成要被许多可能完全不相关的服务共享使用。所以我们需要一个命名系统来区分不同服务的信息，这样这些信息才不会弄混。

所以，Zookeeper的API看起来像是一个文件系统，但是又不是一个实际的文件系统，比如说你不能mount一个文件，你不能运行ls和cat这样的命令等等。这里只是在内部，以这种路径名的形式命名各种对象。假设应用程序2下面有X，Y，Z这些文件。当你通过RPC向Zookeeper请求数据时，你可以直接指定/APP2/X。这就是一种层级化的命名方式。

  1. 第一种Regular znodes。这种znode一旦创建，就永久存在，除非你删除了它。

  2. 第二种是Ephemeral znodes。如果Zookeeper认为创建它的客户端挂了，它会删除这种类型的znodes。这种类型的znodes与客户端会话绑定在一起，所以客户端需要时不时的发送心跳给Zookeeper，告诉Zookeeper自己还活着，这样Zookeeper才不会删除客户端对应的ephemeral znodes。

  3. 最后一种类型是Sequential znodes。它的意思是，当你想要以特定的名字创建一个文件，Zookeeper实际上创建的文件名是你指定的文件名再加上一个数字。当有多个客户端同时创建Sequential文件时，Zookeeper会确保这里的数字不重合，同时也会确保这里的数字总是递增的。

Zookeeper以RPC的方式暴露以下API。

  • CREATE(PATH，DATA，FLAG)。入参分别是文件的全路径名PATH，数据DATA，和表明znode类型的FLAG。这里有意思的是，CREATE的语义是排他的。也就是说，如果我向Zookeeper请求创建一个文件，如果我得到了yes的返回，那么说明这个文件之前不存在，我是第一个创建这个文件的客户端；如果我得到了no或者一个错误的返回，那么说明这个文件之前已经存在了。所以，客户端知道文件的创建是排他的。在后面有关锁的例子中，我们会看到，如果有多个客户端同时创建同一个文件，实际成功创建文件（获得了锁）的那个客户端是可以通过CREATE的返回知道的。

  • DELETE(PATH，VERSION)。入参分别是文件的全路径名PATH，和版本号VERSION。有一件事情我之前没有提到，每一个znode都有一个表示当前版本号的version，当znode有更新时，version也会随之增加。对于delete和一些其他的update操作，你可以增加一个version参数，表明当且仅当znode的当前版本号与传入的version相同，才执行操作。当存在多个客户端同时要做相同的操作时，这里的参数version会非常有帮助（并发操作不会被覆盖）。所以，对于delete，你可以传入一个version表明，只有当znode版本匹配时才删除。

  • EXIST(PATH，WATCH)。入参分别是文件的全路径名PATH，和一个有趣的额外参数WATCH。通过指定watch，你可以监听对应文件的变化。不论文件是否存在，你都可以设置watch为true，这样Zookeeper可以确保如果文件有任何变更，例如创建，删除，修改，都会通知到客户端。此外，判断文件是否存在和watch文件的变化，在Zookeeper内是原子操作。所以，当调用exist并传入watch为true时，不可能在Zookeeper实际判断文件是否存在，和建立watch通道之间，插入任何的创建文件的操作，这对于正确性来说非常重要。

  • GETDATA(PATH，WATCH)。入参分别是文件的全路径名PATH，和WATCH标志位。这里的watch监听的是文件的内容的变化。

  • SETDATA(PATH，DATA，VERSION)。入参分别是文件的全路径名PATH，数据DATA，和版本号VERSION。如果你传入了version，那么Zookeeper当且仅当文件的版本号与传入的version一致时，才会更新文件。

  • LIST(PATH)。入参是目录的路径名，返回的是路径下的所有文件。

6.链复制（Chain Replication）:

CRAQ采用的方式与Zookeeper非常相似，它通过将读请求分发到任意副本去执行，来提升读请求的吞吐量，所以副本的数量与读请求性能成正比。

CRAQ有意思的地方在于，它在任意副本上执行读请求的前提下，还可以保证线性一致性（Linearizability）。这与Zookeeper不太一样，Zookeeper为了能够从任意副本执行读请求，不得不牺牲数据的实时性，因此也就不是线性一致的。CRAQ却可以从任意副本执行读请求，同时也保留线性一致性，这一点非常有趣。

6.1 写请求：

首先，在Chain Replication中，有一些服务器按照链排列。第一个服务器称为HEAD，最后一个被称为TAIL。

  1. 当客户端想要发送一个写请求，写请求总是发送给HEAD。

  2. HEAD根据写请求更新本地数据，我们假设现在是一个支持PUT/GET的key-value数据库。所有的服务器本地数据都从A开始。

  3. 当HEAD收到了写请求，将本地数据更新成了B，之后会再将写请求通过链向下一个服务器传递。

  4. 下一个服务器执行完写请求之后，再将写请求向下一个服务器传递，以此类推，所有的服务器都可以看到写请求。

  5. 当写请求到达TAIL时，TAIL将回复发送给客户端，表明写请求已经完成了。这是处理写请求的过程。

6.2 读请求：

对于读请求，如果一个客户端想要读数据，它将读请求发往TAIL里。

TAIL直接根据自己的当前状态来回复读请求。所以，如果当前状态是B，那么TAIL直接返回B。读请求处理的非常的简单。

Chain Replication本身是线性一致的，在没有故障时，从一致性的角度来说，整个系统就像只有TAIL一台服务器一样，TAIL可以看到所有的写请求，也可以看到所有的读请求，它一次只处理一个请求，读请求可以看到最新写入的数据。如果没有出现故障的话，一致性是这么得到保证的，非常的简单。

从一个全局角度来看，除非写请求到达了TAIL，否则一个写请求是不会commit，也不会向客户端回复确认，也不能将数据通过读请求暴露出来。而为了让写请求到达TAIL，它需要经过并被链上的每一个服务器处理。所以我们知道，一旦我们commit一个写请求，一旦向客户端回复确认，一旦将写请求的数据通过读请求暴露出来，那意味着链上的每一个服务器都知道了这个写请求。

6.3 故障恢复：

在Chain Replication中，出现故障后，你可以看到的状态是相对有限的。因为写请求的传播模式非常有规律，我们不会陷入到类似于Raft论文中图7和图8描述的那种令人毛骨悚然的复杂场景中。并且在出现故障之后，也不会出现不同的副本之间各种各样不同步的场景。

在Chain Replication中，因为写请求总是依次在链中处理，写请求要么可以达到TAIL并commit，要么只到达了链中的某一个服务器，之后这个服务器出现故障，在链中排在这个服务器后面的所有其他服务器不再能看到写请求。所以，只可能有两种情况：committed的写请求会被所有服务器看到；而如果一个写请求没有commit，那就意味着在导致系统出现故障之前，写请求已经执行到链中的某个服务器，所有在链里面这个服务器之前的服务器都看到了写请求，所有在这个服务器之后的服务器都没看到写请求。

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

  • 对于任何已经发送到了第二个节点的写请求，不会因为HEAD故障而停止转发，它会持续转发直到commit。

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

6.4 与raft的区别：

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

  • 从性能上看，对于Raft，如果我们有一个Leader和一些Follower。Leader需要直接将数据发送给所有的Follower。所以，当客户端发送了一个写请求给Leader，Leader需要自己将这个请求发送给所有的Follower。然而在Chain Replication中，HEAD只需要将写请求发送到一个其他节点。数据在网络中发送的代价较高，所以Raft Leader的负担会比Chain Replication中HEAD的负担更高。当客户端请求变多时，Raft Leader会到达一个瓶颈，而不能在单位时间内处理更多的请求。而同等条件以下，Chain Replication的HEAD可以在单位时间处理更多的请求，瓶颈会来的更晚一些。

  • 另一个与Raft相比的有趣的差别是，Raft中读请求同样也需要在Raft Leader中处理，所以Raft Leader可以看到所有的请求。而在Chain Replication中，每一个节点都可以看到写请求，但是只有TAIL可以看到读请求。所以负载在一定程度上，在HEAD和TAIL之间分担了，而不是集中在单个Leader节点。

  • 分析的故障恢复，Chain Replication也比Raft更加简单。这也是使用Chain Replication的一个主要动力。

所以，Chain Replication并不能抵御网络分区，也不能抵御脑裂。在实际场景中，这意味它不能单独使用。Chain Replication是一个有用的方案，但是它不是一个完整的复制方案。它在很多场景都有使用，但是会以一种特殊的方式来使用。总是会有一个外部的权威（External Authority）来决定谁是活的，谁挂了，并确保所有参与者都认可由哪些节点组成一条链，这样在链的组成上就不会有分歧。这个外部的权威通常称为Configuration Manager。

现在只有一个角色（Configuration Manager）在做决定，它不可能否认自己，所以可以解决脑裂的问题。

7.Aurora:

Aurora是一个高性能，高可靠的数据库。Aurora本身作为云基础设施一个组成部分而存在，同时又构建在Amazon自己的基础设施之上。

7.1 事务:

事务是指将多个操作打包成原子操作，并确保多个操作顺序执行。假设我们运行一个银行系统，我们想在不同的银行账户之间转账。你可以这样看待一个事务，首先需要定义想要原子打包的多个操作的开始；之后是操作的内容，现在我们想要从账户Y转10块钱到账户X，那么账户X需要增加10块，账户Y需要减少10块；最后表明事务结束。

我们希望数据库顺序执行这两个操作，并且不允许其他任何人看到执行的中间状态。同时，考虑到故障，如果在执行的任何时候出现故障，我们需要确保故障恢复之后，要么所有操作都已经执行完成，要么一个操作也没有执行。这是我们想要从事务中获得的效果。除此之外，数据库的用户期望数据库可以通知事务的状态，也就是事务是否真的完成并提交了。如果一个事务提交了，用户期望事务的效果是可以持久保存的，即使数据库故障重启了，数据也还能保存。

通常来说，事务是通过对涉及到的每一份数据加锁来实现。所以你可以认为，在整个事务的过程中，都对X，Y加了锁。并且只有当事务结束、提交并且持久化存储之后，锁才会被释放。所以，数据库实际上在事务的过程中，是通过对数据加锁来确保其他人不能访问。

7.2 预写日志：

预写式日志（Write-Ahead Log，简称为WAL）。预写式日志对于系统的容错性至关重要。

在服务器内部，有数据库软件，通常数据库会对最近从磁盘读取的page有缓存。

当你在执行一个事务内的各个操作时，例如执行 X=X+10 的操作时，数据库会从硬盘中读取持有X的记录，给数据加10。但是在事务提交之前，数据的修改还只在本地的缓存中，并没有写入到硬盘。我们现在还不想向硬盘写入数据，因为这样可能会暴露一个不完整的事务。

为了让数据库在故障恢复之后，还能够提供同样的数据，在允许数据库软件修改硬盘中真实的data page之前，数据库软件需要先在WAL中添加Log条目来描述事务。所以在提交事务之前，数据库需要先在WAL中写入完整的Log条目，来描述所有有关数据库的修改，并且这些Log是写入磁盘的。

在提交并写入硬盘的data page之前，数据库通常需要写入至少3条Log记录：

  1. 第一条表明，作为事务的一部分，我要修改X，它的旧数据是500，我要将它改成510。

  2. 第二条表明，我要修改Y，它的旧数据是750，我要将它改成740。

  3. 第三条记录是一个Commit日志，表明事务的结束。

如果数据库成功的将事务对应的操作和commit日志写入到磁盘中，数据库可以回复给客户端说，事务已经提交了。而这时，客户端也可以确认事务是永久可见的。

接下来有两种情况。

如果数据库没有崩溃，那么在它的cache中，X，Y对应的数值分别是510和740。最终数据库会将cache中的数值写入到磁盘对应的位置。所以数据库写磁盘是一个lazy操作，它会对更新进行累积，每一次写磁盘可能包含了很多个更新操作。这种累积更新可以提升操作的速度。

如果数据库在将cache中的数值写入到磁盘之前就崩溃了，这样磁盘中的page仍然是旧的数值。当数据库重启时，恢复软件会扫描WAL日志，发现对应事务的Log，并发现事务的commit记录，那么恢复软件会将新的数值写入到磁盘中。这被称为redo，它会重新执行事务中的写操作。

7.3 Quorum 复制机制：

假设有N个副本。为了能够执行写请求，必须要确保写操作被W个副本确认，W小于N。所以你需要将写请求发送到这W个副本。如果要执行读请求，那么至少需要从R个副本得到所读取的信息。这里的W对应的数字称为Write Quorum，R对应的数字称为Read Quorum。这是一个典型的Quorum配置。

Quorum系统要求，任意你要发送写请求的W个服务器，必须与任意接收读请求的R个服务器有重叠。这意味着，R加上W必须大于N（ 至少满足R + W = N + 1 ），这样任意W个服务器至少与任意R个服务器有一个重合。

image-20240419173555633

这是Quorum系统的要求，Read Quorum必须至少与Write Quorum有一个服务器是重合的。所以任何读请求可以从至少一个看见了之前写请求的服务器得到回复。

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

假设刚刚的例子中，S2有一个旧的数值20。每一个服务器都有一个版本号，S1和S3是版本3，因为它们看到了相同的写请求，所以它们的版本号是相同的。同时我们假设没有看到前一个写请求的S2的版本号是2。

之后客户端从S2和S3读取数据，得到了两个不同结果，它们有着不同的版本号，客户端会挑选版本号最高的结果。

如果你不能与Quorum数量的服务器通信，不管是Read Quorum还是Write Quorum，那么你只能不停的重试了。这是Quorum系统的规则，你只能不停的重试，直到服务器重新上线，或者重新联网。

相比Chain Replication，这里的优势是可以轻易的剔除暂时故障、失联或者慢的服务器。实际上，这里是这样工作的，当你执行写请求时，你会将新的数值和对应的版本号给所有N个服务器，但是只会等待W个服务器确认。类似的，对于读请求，你可以将读请求发送给所有的服务器，但是只等待R个服务器返回结果。因为你只需要等待R个服务器，这意味着在最快的R个服务器返回了之后，你就可以不用再等待慢服务器或者故障服务器超时。这里忽略慢服务器或者挂了的服务器的机制完全是隐式的。在这里，我们不用决定哪个服务器是在线或者是离线的，只要Quorum能达到，系统就能继续工作，所以我们可以非常平滑的处理慢服务或者挂了的服务。

除此之外，Quorum系统可以调整读写的性能。通过调整Read Quorum和Write Quorum，可以使得系统更好的支持读请求或者写请求。对于前面的例子，我们可以假设Write Quorum是3，每一个写请求必须被所有的3个服务器所确认。这样的话，Read Quorum可以只是1。所以，如果你想要提升读请求的性能，在一个3个服务器的Quorum系统中，你可以设置R为1，W为3，这样读请求会快得多，因为它只需要等待一个服务器的结果，但是代价是写请求执行的比较慢。如果你想要提升写请求的性能，可以设置R为3，W为1，这意味着可能只有1个服务器有最新的数值，但是因为客户端会咨询3个服务器，3个服务器其中一个肯定包含了最新的数值。

当R为1，W为3时，写请求就不再是容错的了，同样，当R为3，W为1时，读请求不再是容错的，因为对于读请求，所有的服务器都必须在线才能执行成功。所以在实际场景中，你不会想要这么配置，你或许会与Aurora一样，使用更多的服务器，将N变大，然后再权衡Read Quorum和Write 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系统可以剔除暂时的慢副本。

7.4 数据分片（Protection Group）：

为了能支持超过10TB数据的大型数据库。Amazon的做法是将数据库的数据，分割存储到多组存储服务器上，每一组都是6个副本，分割出来的每一份数据是10GB。所以，如果一个数据库需要20GB的数据，那么这个数据库会使用2个PG（Protection Group），其中一半的10GB数据在一个PG中，包含了6个存储服务器作为副本，另一半的10GB数据存储在另一个PG中，这个PG可能包含了不同的6个存储服务器作为副本。

因为Amazon运行了大量的存储服务器，这些服务器一起被所有的Aurora用户所使用。两组PG可能使用相同的6个存储服务器，但是通常来说是完全不同的两组存储服务器。随着数据库变大，我们可以有更多的Protection Group。

这里有一件有意思的事情，你可以将磁盘中的data page分割到多个独立的PG中，比如说奇数号的page存在PG1，偶数号的page存在PG2。如果可以根据data page做sharding，那是极好的。

Sharding之后，Log该如何处理就不是那么直观了。如果有多个Protection Group，该如何分割Log呢？答案是，当Aurora需要发送一个Log条目时，它会查看Log所修改的数据，并找到存储了这个数据的Protection Group，并把Log条目只发送给这个Protection Group对应的6个存储服务器。这意味着，每个Protection Group只存储了部分data page和所有与这些data page关联的Log条目。所以每个Protection Group存储了所有data page的一个子集，以及这些data page相关的Log条目。

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

Aurora实际使用的策略是，对于一个特定的存储服务器，它存储了许多Protection Group对应的10GB的数据块。对于Protection Group A，它的其他副本是5个服务器。

假设有足够多的服务器，这里的服务器大概率不会有重合，同时假设我们有足够的带宽，现在我们可以以100的并发，并行的拷贝1TB的数据，这只需要10秒左右。如果只在两个服务器之间拷贝，正常拷贝1TB数据需要1000秒左右。

如果大量的服务器挂了，可能不能正常工作，但是如果只有一个服务器挂了，Aurora可以非常快的重新生成副本。

8.Frangipani:

Frangipani，是一篇很久之前有关分布式文件系统的论文。

Frangipani就是一个网络文件系统（NFS，Network File System）。它的目标是与已有的应用程序一起工作，比如说一个运行在工作站上的普通UNIX程序。

文件系统的数据结构，例如文件内容、inode、目录、目录的文件列表、inode和块的空闲状态，所有这些数据都存在一个叫做Petal的共享虚拟磁盘服务中。Petal运行在一些不同的服务器上，有可能是机房里面的一些服务器，但是不会是人们桌子上的工作站。Petal会复制数据，所以你可以认为Petal服务器成对的出现，这样就算一个故障了，我们还是能取回我们的数据。当Frangipani需要读写文件时，它会向正确的Petal服务器发送RPC，并说，我需要这个块，请读取这个块，并将数据返回给我。在大部分时候，Petal表现的就像是一个磁盘，你可以把它看做是共享的磁盘，所有的Frangipani都会与之交互。

除了最基本的缓存之外，Frangipani还支持Write-Back缓存。所以，除了在每个工作站或者说每个Frangipani服务器上要持有缓存之外，我们还需要支持Write-Back缓存。这意味着，如果我想要修改某个数据，比如说我修改了一个文件，或者创建了一个文件，或者删除了一个文件，只要没有其他的工作站需要看到我的改动，Frangipani通过Write-Back缓存方式管理这些数据。

这意味着，最开始的时候，我的修改只会在本地的缓存中。如果我创建了一个文件，至少在最开始，有关新创建文件的信息，比如说新创建的inode和初始化的内容，home目录文件列表的更新，文件名等等，所有的这些修改最初只会在本地缓存中存在，因此类似于创建文件的操作可以非常快的完成，因为只需要修改本地的内存中对于磁盘的缓存。而这些修改要过一会才会写回到Petal。所以最开始，我们可以为文件系统做各种各样的修改，至少对于我自己的目录，我自己的文件，这些修改完全是本地的。这对于性能来说有巨大的帮助，因为写本地内存的性能比通过RPC向一个远端服务器写要快1000倍。

8.1 挑战（Challenges）：

Frangipani的挑战主要来自于两方面，一个是缓存，另一个是这种去中心化的架构带来的大量的逻辑存在于客户端之中进而引起的问题。

假设我的工作站修改了大量的内容，由于Write-Back缓存，可能会在本地的缓存中堆积了大量的修改。如果我的工作站崩溃了，但是这时这些修改只有部分同步到了Petal，还有部分仍然只存在于本地。同时，其他的工作站还在使用文件系统。那么，我的工作站在执行操作的过程中的崩溃，最好不要损坏其他人同样会使用的文件系统。这意味着，我们需要的是单个服务器的故障恢复，我希望我的工作站的崩溃不会影响其他使用同一个共享系统的工作站。哪怕说这些工作站正在查看我的目录，我的文件，它们应该看到一些合理的现象。它们可以漏掉我最后几个操作，但是它们应该看到一个一致的文件系统，而不是一个损坏了的文件系统数据。所以这里我们希望有故障恢复。一如既往的，在分布式系统中，这增加了更多的复杂度，我们可以很容易陷入到这样一个场景，一个工作站崩溃了，但是其他的工作站还在运行。

image-20240419175827020

8.2 锁服务：

对于线性一致性来说，当我查看文件系统中任何内容时，我总是能看到最新的数据。对于缓存来说，我们想要缓存带来的性能提升。某种程度上，我们想要同时拥有这两种特性的优点。

使用缓存一致性协议（Cache Coherence Protocol）来实现缓存一致性。这些协议在很多不同的场景都有使用，不只在分布式文件系统，在多核处理器每个核的缓存的同步中也有使用。

Frangipani的缓存一致性核心是由锁保证的，我们之后在原子性和故障恢复中将会再次看到锁。

除了Frangipani服务器（也就是工作站），Petal存储服务器，在Frangipani系统中还有第三类服务器，锁服务器。辑上，锁服务器是独立的服务器，但是实际上我认为它与Petal服务器运行在一起。在锁服务器里面，有一个表单，就叫做locks。我们假设每一个锁以文件名来命名，所以对于每一个文件，我们都有一个锁，而这个锁，可能会被某个工作站所持有。

我们假设锁是排他锁（Exclusive Lock），尽管实际上Frangipani中的锁更加复杂可以支持两种模式：要么允许一个写入者持有锁，要么允许多个读取者持有锁。（读写锁）

当一个Frangipani服务器决定要读取文件，比如读取目录 /、读取文件A、查看一个inode，首先，它会向一个锁服务器请求文件对应的锁，之后才会向Petal服务器请求文件或者目录的数据。收到数据之后，工作站会记住，本地有一个文件X的拷贝，对应的锁的状态，和相应的文件内容。

每一个工作站的锁至少有两种模式。工作站可以读或者写相应的文件或者目录的最新数据，可以在创建，删除，重命名文件的过程中，如果这样的话，我们认为锁在Busy状态。

在工作站完成了一些操作之后，比如创建文件，或者读取文件，它会随着相应的系统调用（例如rename，write，create，read）释放锁。只要系统调用结束了，工作站会在内部释放锁，现在工作站不再使用那个文件。但是从锁服务器的角度来看，工作站仍然持有锁。工作站内部会标明，这是锁时Idle状态，它不再使用这个锁。所以这个锁仍然被这个工作站持有，但是工作站并不再使用它。

8.3 缓存一致性：

工作站和锁服务器之间的缓存一致协议协议包含了4种不同的消息。

首先是Request消息，从工作站发给锁服务器。Request消息会说：hey锁服务器，我想获取这个锁。

如果从锁服务器的lock表单中发现锁已经被其他人持有了，那锁服务器不能立即交出锁。但是一旦锁被释放了，锁服务器会回复一个Grant消息给工作站。

如果锁服务器收到了一个加锁的请求，它查看自己的lock表单可以发现，这个锁现在正被工作站WS1所持有，锁服务器会发送一个Revoke消息给当前持有锁的工作站WS1。并说，现在别人要使用这个文件，请释放锁吧。

当一个工作站收到了一个Revoke请求，如果锁时在Idle状态，并且缓存的数据脏了，工作站会首先将修改过的缓存写回到Petal存储服务器中，因为前面的规则要求在释放锁之前，要先将数据写入Petal。所以如果锁的状态是Idle，首先需要将修改了的缓存数据发回给Petal，只有在那个时候，工作站才会再向锁服务器发送一条消息说，好吧，我现在放弃这个锁。所以，对于一个Revoke请求的响应是，工作站会向锁服务器发送一条Release消息。

如果工作站收到Revoke消息时，它还在使用锁，比如说正在删除或者重命名文件的过程中，直到工作站使用完了锁为止，或者说直到它完成了相应的文件系统操作，它都不会放弃锁。完成了操作之后，工作站中的锁的状态才会从Busy变成Idle，之后工作站才能注意到Revoke请求，在向Petal写完数据之后最终释放锁。

工作流程：

我们有了2个工作站（WS1，WS2），一个锁服务器（LS）。

  1. 如果WS1想要读取并修改文件Z。在它从Petal读取文件之前，它需要先获取对于Z的锁，所以它向锁服务器发送Request消息（下图中ACQ Z）。

  2. 如果当前没有人持有对文件Z的锁，或者锁服务器没听过对于文件Z的锁（初始化状态），锁服务器会在lock表单中增加一条记录，并返回Grant消息给工作站说，你现在持有了对于Z文件的锁。

  3. 从这个时间点开始，工作站WS1持有了对文件Z的锁，并且被授权可以从Petal读取Z的数据。所以这个时间点，WS1会从Petal读取并缓存Z的内容。之后，WS1也可以在本地缓存中修改Z的内容。

  4. 过了一会，坐在工作站WS2前面的用户也想读取文件Z。但是一开始WS2并没有对于文件Z的锁，所以它要做的第一件事情就是向锁服务器发送Request消息，请求对于文件Z的锁。

  5. 但是，锁服务器知道不能给WS2回复Grant消息，因为WS1现在还持有锁。接下来锁服务器会向WS1发送Revoke消息。

  6. 而工作站WS1在向Petal写入修改数据之前，不允许释放锁。所以它现在会将任何修改的内容写回给Petal。

  7. 写入结束之后，WS1才可以向锁服务器发送Release消息。

  8. 锁服务器必然会有一个表单记录谁在等待文件Z的锁，一旦锁的当前持有者释放了锁，锁服务器需要通知等待者。所以当锁服务器收到了这条Release消息时，锁服务器会更新自己的表单，并最终将Grant消息发送给工作站WS2。

  9. 这个时候，WS2终于可以从Petal读取文件Z。

**image-20240419180515698**

直到所有有可能私底下在缓存中修改了数据的工作站先将数据写回到Petal，其他工作站才能读取相应的文件。所以，这里的锁机制确保了读文件总是能看到最新写入文件的数据。

8.4 原子性（Atomicity）：

在完全完成操作之前，Frangipani确保其他的工作站看不到我的修改。

首先我的工作站需要获取所有我需要读写数据的锁，在完成操作之前，我的工作站不会释放任何一个锁。并且为了遵循一致性规则，将所有修改了的数据写回到Petal之后，我的工作站才会释放所有的锁。比如我将文件从一个目录移到另一个目录，这涉及到修改两个目录的内容，我不想让人看到两个目录都没有文件的状态。为了实现这样的结果，Frangipani首先会获取执行操作所需要的所有数据的锁。

之后完成所有的步骤，比如完成所有数据的更新，并将更新写入到Petal，最后释放锁。

对于锁来说，这里有一件有意思的事情，Frangipani使用锁实现了两个几乎相反的目标。对于缓存一致性，Frangipani使用锁来确保写操作的结果对于任何读操作都是立即可见的，所以对于缓存一致性，这里使用锁来确保写操作可以被看见。但是对于原子性来说，锁确保了人们在操作完成之前看不到任何写操作，因为在所有的写操作完成之前，工作站持有所有的锁。

8.5 Frangipani Log：

一个工作站持有锁，并且在一个复杂操作的过程中崩溃了。比如说一个工作站在创建文件，或者删除文件时，它首先获取了大量了锁，然后会更新大量的数据，在其向Petal回写数据的过程中，一部分数据写入到了Petal，还有一部分还没写入，这时工作站崩溃了，并且锁也没有释放（因为数据回写还没有完成）。

一种处理方法是，如果发现工作站崩溃了，就释放它所有的锁。。假设工作站在创建新文件，它已经在Petal里将文件名更新到相应的目录下，但是它还没有将描述了文件的inode写入到Petal，Petal中的inode可能还是一些垃圾数据，这个时候是不能释放崩溃工作站持有的锁（因为其他工作站读取这个文件可能读出错误的数据）。

另一种处理方法是，不释放崩溃了的工作站所持有的锁。这至少是正确的。如果工作站在向Petal写入数据的过程中崩溃了，因为它还没有写完所有的数据，也就意味着它不能释放所有的锁。

Frangipani与其他的系统一样，需要通过预写式日志（Write-Ahead Log，WAL，见10.2）实现故障可恢复的事务（Crash Recoverable Transaction）。

当一个工作站需要完成涉及到多个数据的复杂操作时，在工作站向Petal写入任何数据之前，工作站会在Petal中自己的Log列表中追加一个Log条目，这个Log条目会描述整个的需要完成的操作。只有当这个描述了完整操作的Log条目安全的存在于Petal之后，工作站才会开始向Petal发送数据。所以如果工作站可以向Petal写入哪怕是一个数据，那么描述了整个操作、整个更新的Log条目必然已经存在于Petal中。

Frangipani在实现WAL时，有一些不同的地方。

第一个是，在大部分的事务系统中，只有一个Log，系统中的所有事务都存在于这个Log中。当有故障时，如果有多个操作会影响同一份数据，我们在这一个Log里，就会保存这份数据的所有相关的操作。

工作站的Log存储在Petal，而不是本地磁盘中。几乎在所有使用了Log的系统中，Log与运行了事务的计算机紧紧关联在一起，并且几乎总是保存在本地磁盘中。但是出于优化系统设计的目的，Frangipani的工作站将自己的Log保存在作为共享存储的Petal中。每个工作站都拥有自己的半私有的Log，但是却存在Petal存储服务器中。这样的话，如果工作站崩溃了，它的Log可以被其他工作站从Petal中获取到。所以Log存在于Petal中。

8.6 故障恢复（Crash Recovery）：

当工作站需要重命名文件或者创建一个文件时，首先它会获得所有需要修改数据的锁，之后修改自身的缓存来体现改动。但是后来工作站在向Petal写入数据的过程中故障了。工作站可能在很多个位置发生故障，但是由于前面介绍过的工作流程，Frangipani总是会先将自身的Log先写入到Petal。这意味着如果发生了故障，那么发生故障时可能会有这几种场景：

  • 要么工作站正在向Petal写入Log，所以这个时候工作站必然还没有向Petal写入任何文件或者目录。

  • 要么工作站正在向Petal写入修改的文件，所以这个时候工作站必然已经写入了完整的Log。

当持有锁的工作站崩溃了之后，发生的第一件事情是锁服务器向工作站发送一个Revoke消息，但是锁服务器得不到任何响应，之后才会触发故障恢复。如果没有人需要用到崩溃工作站持有的锁，那么基本上没有人会注意到工作站崩溃了。假设一个其他的工作站需要崩溃了的工作站所持有的一个锁，锁服务器会发出Revoke消息，但是锁服务器永远也不会从崩溃了的工作站收到Release消息。Frangipani出于一些原因对锁使用了租约，当租约到期了，锁服务器会认定工作站已经崩溃了，之后它会初始化恢复过程。实际上，锁服务器会通知另一个还活着的工作站说：看，工作站1看起来崩溃了，请读取它的Log，重新执行它最近的操作并确保这些操作完成了，在你完成之后通知我。在收到这里的通知之后，锁服务器才会释放锁。这就是为什么日志存放在Petal是至关重要的，因为一个其他的工作站可能会要读取这个工作站在Petal中的日志。

9.分布式事务（Distributed Transaction）：

分布式事务主要有两部分组成。第一个是并发控制（Concurrency Control）第二个是原子提交（Atomic Commit）。

对于拥有大量数据的人来说，他们通常会将数据进行分割或者分片到许多不同的服务器上。假设你运行了一个银行，你一半用户的账户在一个服务器，另一半用户的账户在另一个服务器，这样的话可以同时满足负载分担和存储空间的要求。对于其他的场景也有类似的分片，比如说对网站上文章的投票，或许有上亿篇文章，那么可以在一个服务器上对一半的文章进行投票，在另一个服务器对另一半进行投票。

对于一些操作，可能会要求从多个服务器上修改或者读取数据。比如说我们从一个账户到另一个账户完成银行转账，这两个账户可能在不同的服务器上。因此，为了完成转账，我们必须要读取并修改两个服务器的数据。

9.1 并发控制（Concurrency Control）:

在并发控制中，主要有两种策略。

第一种主要策略是悲观并发控制（Pessimistic Concurrency Control）。

在事务使用任何数据之前，它需要获得数据的锁。如果一些其他的事务已经在使用这里的数据，锁会被它们持有，当前事务必须等待这些事务结束，之后当前事务才能获取到锁。在悲观系统中，如果有锁冲突，比如其他事务持有了锁，就会造成延时等待。所以这里需要为正确性而牺牲性能。

第二种主要策略是乐观并发控制（Optimistic Concurrency Control）。

基本思想是，你不用担心其他的事务是否正在读写你要使用的数据，你直接继续执行你的读写操作，通常来说这些执行会在一些临时区域，只有在事务最后的时候，你再检查是不是有一些其他的事务干扰了你。如果没有这样的其他事务，那么你的事务就完成了，并且你也不需要承受锁带来的性能损耗，因为操作锁的代价一般都比较高；但是如果有一些其他的事务在同一时间修改了你关心的数据，并造成了冲突，那么你必须要Abort当前事务，并重试。这就是乐观并发控制。

实际，这两种策略哪个更好取决于不同的环境。如果冲突非常频繁，你或许会想要使用悲观并发控制，因为如果冲突非常频繁的话，在乐观并发控制中你会有大量的Abort操作。如果冲突非常少，那么乐观并发控制可以更快，因为它完全避免了锁带来的性能损耗。

9.2 两阶段锁：（Two-Phase Locking）：

当事务需要使用一些数据记录时，第一个规则是在使用任何数据之前，在执行任何数据的读写之前，先获取锁。

第二个对于事务的规则是，事务必须持有任何已经获得的锁，直到事务提交或者Abort，你不允许在事务的中间过程释放锁。你必须要持有所有的锁，并不断的累积你持有的锁，直到你的事务完成了。所以，这里的规则是，持有锁直到事务结束。

就是两阶段锁的两个阶段，第一个阶段获取锁，第二个阶段是在事务结束前一直持有锁。

9.3 两阶段提交（Two-Phase Commit）：

在一个分布式环境中，数据被分割在多台机器上，如何构建数据库或存储系统以支持事务。

两阶段提交不仅被分布式数据库所使用，同时也被各种看起来不像是传统数据库的分布式系统所使用。

  1. 我们有一个计算机作为事务协调者（TC），然后还有服务器S1，S2，分别持有X，Y的记录。

  2. 事务协调者会向服务器S1发消息说，请对X加1，向服务器S2发消息说，请对Y减1。

  3. 之后会有更多消息来确认，要么两个服务器都执行了操作，要么两个服务器都没有执行操作。

事务协调者运行了整个事务，它会向A，B发送Put和Get，告诉它们读取X，Y的数值，对X加1等等。所以，在事务的最开始，TC会向参与者A发送Get请求并得到回复，之后再向参与者B发送一个Put请求并得到回复。

之后，当事务协调者到达了事务的结束并想要提交事务，这样才能：

  • 释放所有的锁，

  • 并使得事务的结果对于外部是可见的，

  • 再向客户端回复。

  1. 当A或者B收到了Prepare消息，它们就知道事务要执行但是还没执行的内容，它们会查看自身的状态并决定它们实际上能不能完成事务。A和B会检查自己的状态并说，我有能力或者我没能力完成这个事务，它们会向TC回复Yes或者No。

  2. 事务协调者会等待来自于每一个参与者的这些Yes/No投票。如果所有的参与者都回复Yes，那么事务可以提交，不会发生错误。之后事务协调者会发出一个Commit消息给每一个事务的参与者。

  3. 之后，事务参与者通常会回复ACK说，我们知道了要commit。当事务协调者发出Prepare消息时，如果所有的参与者都回复Yes，那么事务可以commit。如果任何一个参与者回复了No，表明自己不能完成这个事务，或许是因为错误，或许有不一致性，或许丢失了记录，那么事务协调者不会发送commit消息，它会发送一轮Abort消息给所有的参与者说，请撤回这个事务。

  4. 在事务Commit之后，会发生两件事情。首先，事务协调者会向客户端发送代表了事务输出的内容，表明事务结束了，事务没有被Abort并且被持久化保存起来了。另一个有意思的事情是，为了遵守前面的锁规则（两阶段锁），事务参与者会释放锁（这里不论Commit还是Abort都会释放锁）。

image-20240419211244788

9.4 故障恢复（Crash Recovery）：

9.4.1 场景1:

第一个场景是，参与者B可能在回复事务协调者的Prepare消息之前的崩溃了。

所以，B在回复Yes之前就崩溃了。从TC的角度来看，B没有回复Yes，TC也就不能Commit，因为它需要等待所有的参与者回复Yes。

如果B发现自己不可能发送Yes，比如说在发送Yes之前自己就故障了，那么B被授权可以单方面的Abort事务。因为B知道自己没有发送Yes，那么它也知道事务协调者不可能Commit事务。

9.4.2 场景2:

现在B承诺可以commit，因为它回复了Yes。接下来极有可能发生的事情是，事务协调者从所有的参与者获得了Yes的回复，并将Commit消息发送给了A，所以A实际上会执行事务分包给它的那一部分，持久化存储结果，并释放锁。这样的话，为了确保All-or-Nothing原子性，我们需要确保B在故障恢复之后，仍然能完成事务分包给它的那一部分。在B故障的时候，不知道事务是否能Commit，因为它还没有收到Commit消息。但是B还是需要做好Commit的准备。这意味着，在故障重启的时候，B不能丢失对于事务的状态记录。

在B回复Prepare之前，它必须确保记住当前事务的中间状态，记住所有要做的修改，记住事务持有的所有的锁，这些信息必须在磁盘上持久化存储。通常来说，这些信息以Log的形式在磁盘上存储。所以在B回复Yes给Prepare消息之前，它首先要将相应的Log写入磁盘，并在Log中记录所有有关提交事务必须的信息。这包括了所有由Put创建的新的数值，和锁的完整列表。之后，B才会回复Yes。

之后，如果B在发送完Yes之后崩溃了，当它重启恢复时，通过查看自己的Log，它可以发现自己正在一个事务的中间，并且对一个事务的Prepare消息回复了Yes。Log里有Commit需要做的所有的修改，和事务持有的所有的锁。之后，当B最终收到了Commit而不是Abort，通过读取Log，B就知道如何完成它在事务中的那部分工作。

9.4.3 场景3:

最后一个可能崩溃的地方是，B可能在收到Commit之后崩溃了。

B有可能在处理完Commit之后就崩溃了。但是这样的话，B就完成了修改，并将数据持久化存储在磁盘上了。这样的话，故障重启就不需要做任何事情，因为事务已经完成了。

因为没有收到ACK，事务协调者会再次发送Commit消息。当B重启之后，收到了Commit消息时，它可能已经将Log中的修改写入到自己的持久化存储中、释放了锁、并删除了有关事务的Log。所以我们需要关心，如果B收到了同一个Commit消息两次，该怎么办？这里B可以记住事务的信息，但是这会消耗内存，所以实际上B会完全忘记已经在磁盘上持久化存储的事务的信息。对于一个它不知道事务的Commit消息，B会简单的ACK这条消息。

当然事务协调者或许不能收到ACK，这时它会假设丢包了并重发Commit消息。这时，如果一个参与者收到了一个Commit消息，但是它并不知道对应的事务，因为它在之前回复ACK之后就忘记了这个事务，那么参与者会再次回复一个ACK。因为如果参与者收到了一个自己不知道的事务的Commit消息，那么必然是因为它之前已经完成对这个事务的Commit或者Abort，然后选择忘记这个事务了。

9.5 总结：

这就是两阶段提交，它实现了原子提交。两阶段提交在大量的将数据分割在多个服务器上的分片数据库或者存储系统中都有使用。

两阶段提交可以支持读写多条记录，一些更特殊的存储系统不允许你在多条记录上支持事务。对于这些不支持事务中包含多条数据的系统，你就不需要两阶段提交。但是如果你需要在事务中支持多条数据，并且你将数据分片在多台服务器之上，那么你必须支持两阶段提交。

然而，两阶段提交有着极差的名声。其中一个原因是，因为有多轮消息的存在，它非常的慢。

你只会在一个小的环境中看到两阶段提交，比如说在一个组织的一个机房里面。你不会在不同的银行之间转账看到它，你或许可以在银行内部的系统中看见两阶段提交，但是你永远也不会在物理分隔的不同组织之间看见两阶段提交，因为它可能会陷入到Block区间中。

两阶段提交的架构中，本质上是有一个Leader（事务协调者），将消息发送给Follower（事务参与者），Leader只能在收到了足够多Follower的回复之后才能继续执行。这与Raft非常像，但是，这里协议的属性与Raft又非常的不一样。这两个协议解决的是完全不同的问题。

9.5.1 与raft的区别：

使用Raft可以通过将数据复制到多个参与者得到高可用。Raft的意义在于，即使部分参与的服务器故障了或者不可达，系统仍然能工作。Raft能做到这一点是因为所有的服务器都在做相同的事情，所以我们不需要所有的服务器都参与，我们只需要过半服务器参与。

然而两阶段提交，参与者完全没有在做相同的事情，每个参与者都在做事务中的不同部分，比如A可能在对X加1，B可能在对Y减1。所以在两阶段提交中，所有的参与者都在做不同的事情。所有的参与者都必须完成自己那部分工作，这样事务才能结束，所以这里需要等待所有的参与者。

所以实际上，两阶段提交的可用性非常低，因为任何一个部分崩溃都有可能阻止整个系统的运行。Raft并不需要确保所有的参与者执行操作，它只需要过半服务器执行操作，或许少数的服务器完全没有执行操作也没关系。这里的原因是Raft系统中，所有的参与者都在做相同的事情，我们不必等待所有的参与者。这就是为什么Raft有更高的可用性。所以这是两个完全不同的协议。

然而，是有可能结合这两种协议的。两阶段提交对于故障来说是非常脆弱的，在故障时它可以有正确的结果，但是不具备可用性。所以，这里的问题是，是否可以构建一个合并的系统，同时具备Raft的高可用性，但同时又有两阶段提交的能力将事务分包给不同的参与者。这里的结构实际上是，通过Raft或者Paxos或者其他协议，来复制两阶段提交协议里的每一个组成部分。