4、 复制（强一致性）

复制是分布式系统中非常关键的一个点。下面将会从leader election、failure detection、mutual exclusion、consensus及global snapshots这些大家关心的问题展开介绍。区别并行数据库的一种方式是更具复制集的特征。

复制是一个集体通信的问题。当网络发生分区或者节点同时崩溃时，怎样保证系统的容错性、持久性和非发散性？

复制的方式有很多种，这里并不对每种算法进行详细的介绍，知识进行一个方法的汇总讨论

首先，到底什么是复制集呢？我们认为，当我们拥有原始的数据库时，客户通过一定的请求操作会改变数据库的状态

image.png

这个时候的处理和通信模式罗分为下面几个阶段：

• （Request）客户向服务发送一个请求
• （Sync）复制中的同步部分发生
• （Responses）向客户返回答复
• （Async）复制中的异步部分发生

在这些阶段中，通信模式是怎样的呢？

同步复制

同步复制：悲观复制，接受到客户端的请求之后，各节点先同步并返回到此节点之后，再响应客户端

image.png

可以观察到，同步复制必须要当结果被所有的服务节点认可后才会返回一个值给客户

从性能的角度来看，这意味着系统最快的反应时间取决于最慢的一个服务节点。这样的系统会对网络延迟非常敏感。

与此同时，系统将不能忍受任一个服务节点发生数据丢失的情况。一旦有一个服务节点发生丢失，系统将不允许对数据进行写操作。同时修改操作也不会被允许，只会允许进行读操作

这样能提供一个非常长的持久性保证：客户能够确保所有的服务节点都接收到了请求，并且对请求做出响应。只有当所有节点上的副本都丢失了，更新的数据才会丢失

异步复制

异步复制：积极复制、惰性复制，接受到客户端的请求之后，先响应客户端，再进行各节点先同步并且返回到此节点

image.png

在接下来的阶段，复制的异步部分发生。主节点利用通信模式对其它服务节点进行交流，接着其它节点对复制集进行更新。具体实施过程依赖于所选择的算法

那么抽象而言，异步复制就是一个1-N的写方法：立刻响应客户端，再接着进行各节点的更新同步

从性能的角度来看，这样的系统通常更快，因为客户端不需要等到所有的节点同步完成后才得到响应。同时这样的系统对于网络延迟的容忍性更高。

这样的操作只能提供一个弱的，某种程度上的持久性保证。如果没有任何故障发生，数据最终在N台机器上的复制集都会保持一致。但一旦数据只在一台服务器上，这个服务器发生数据丢失的话，数据将会永久丢失（持久性：对数据所做的更改能够永久保存下来）

在异步复制中，系统只需要得到一个节点的响应就能保证它的可用性（理论上是这样，但是在现实中，实践中负载通常会很高，单位时间内承受的工作量大）。像这样的惰性复制不会保证持久性和一致性：你能够对数据进行写操作，但是一旦错误发生，不一定保证你能读到你所写的东西

积极复制不能保证系统中所有的节点都能保持在同样的状态。如果你在多个机器进行写操作，并且又不要求这些节点同步做出确定，那么很有可能造成数据不一致的结果：从不同位置上读取数据可能返回的是不同的值（尤其是节点发生故障后恢复之后），并且不能进行强制全局限制（需要各个节点进行通信）

主要的复制方法

刚刚讨论了什么是同步复制和异步复制，现在来介绍相关的主要的复制算法

两种复制方法：

• single copy systems：阻止数据不一致的复制方法
• multi-master systems：有数据不一致风险的复制方法

单拷贝系统复制方法表现的形式像单个系统一样。当局部发生故障时，系统保证只有一个系统单副本处于活跃状态。进一步说，就是系统保证复制集永远处于一致的状态。

服务进程统一统一某个值后才达成一致性，一致性定义具体如下：

• Agreement：所有正确进程必须做出相同的决议
• Integrity：每个正确的进程最多承认一个值，一旦一个进程决定了某一个值，那么这个值肯定是被其它进程提出的
• Termination：所有正确的进程最终都会同意某个值
• Validity：如果所有正确的进程提出相同的值V，那么所有正确的节点进程达成一致，承认值V

leader election、failure detection、mutual exclusion、consensus及global snapshots这些都会涉及到一致性问题。保证单拷贝一致性的复制系统需要解决这些问题

单拷贝一致性复制算法包括：
（这些算法的容错性都各自不同。根据执行过程中的信息交互数量对这些算法进行了一个分类）

• 1n messages（异步 主/备）
• 2n messages（同步 主/备）
• 4n messages（2阶段提交，多-Paxos）
• 6n messages（3阶段提交，进行leader选举的Paxos）

Ryan Barret对这些算法进行了一个不同层面的比较：

image.png

上图中从一致性、延迟性、吞吐量、数据丢失、失败等特征通过对同步和异步复制过程来对这些算法进行了一个比较。当你处于等待状态时，系统性能不高但是有高保证。

在这个图中，算法保证低一致性（最终一致性）都集中在一种类型（gossip）上。这一节不讨论低一致性。（The "transactions" row really refers more to global predicate evaluation, which is not supported in systems with weak consistency (though local predicate evaluation can be supported谓词运算：True or False+运算操作）

弱一致性通用的算法很少，一般都是根据需求选择。当系统不再强制要求单拷贝一致性时，它会更加灵活，表现得更加像分布式系统。

例如：

• 客户端为中心的一致性模型当发生数据不一致的时候，会尝试提供更易于理解的一致性保证
• CRDTs（一致复制集数据类型）：一种拥有结合性、交换性、幂等性的操作数据类型
• 整合分析（如在Bloom语言中）使用关于计算的单调性的信息来最大限度地利用无序。
• PBS（概率有界过时？？？）使用仿真和从真实世界系统收集的信息来刻画部分仲裁系统的预期行为。

后面会进行更深入的讨论。第四节主要关注单拷贝一致性的复制算法

主备复制

主备复制（主从复制、日志传输复制）是最常用的复制算法，也是最基本的复制算法。所有的更新都在主节点上进行，然后通过网络传送日志操作到其他节点副本中。这里有两种类型：

• 异步主从复制：只需一条信息（更新）
• 同步主从复制：需要两条信息（更新+确定收到）

主从复制例子：MySQL（异步）、MongoDB（有一些额外的故障备援方案）。所有的操作都在主服务器上进行，连载操作的日志信息然后异步更新到其它的备份节点中

像之前讨论的异步复制中，任何异步复制的算法都只能保证弱持久性。在MySQL复制中它的表现形式为复制滞后：异步复制的节点备份通常在主节点操作之后，一旦主机发生故障，数据更新日志可能发生丢失

主从复制的同步类型能够保证写操作在返回消息给客户端之前，每个节点上都会存储写信息，同时带来的副作用是需要等待复制的时间。但是尽管这种同步类型的主从复制系统提供的是弱保证，也没有什么影响。下面这些失败的场景案例：

• 主节点收到写操作，并且将这个命令发送给从节点
• 从节点收到并且对这个写操作做出命令正确应答的回应（ACKs）
• 主节点在发送ACK（命令正确应答）给客户端之前发生故障

这个时候客户端会猜测这次提交失败了，但是其实从节点已经正确提交了；如果备份节点提交了，但是主节点没有提交，即备份节点比主节点超前了，这样是错误的。这种矛盾需要进行协调（if the backup is promoted to primary, it will be incorrect.这里是说备份节点比主节点先提交写操作吗？为什么不能先提交，最终都向用户确认不就行了？）

之前提到过，系统都会有自己的失效备援操作，但是当主节点在这种场景下发生故障，系统是没发进行复原的

主从复制中还有一个重要的关键点：日志传输。日志传输使得主从复制只能保证尽可能的正确，如果节点在不适宜的时间失败，可能会导致更新失败或数据丢失

为了防止主从复制的不足，需要多加一轮消息传送认证，因此需要两个阶段提交协议（2PC）

两阶段提交（2PC）

两阶段提交（2PC）协议是关系数据库中最经典的一种协议。例如在MySQL集群中，就利用2PC协议来进行同步复制。下图中阐述了该复制过程中信息流的变化：

image.png

（4条消息传输）
在第一个表决阶段（voting），协调者向所有的参与者发送更新消息。每一个参与者处理更新操作并表决是否提交或是终止，当表决结果是提交时，这些参与者实际上会将更新放在一个暂时区域（写操作日志头）中，这些更新始终都是暂时的，直到第二个阶段完成

在第二个决策阶段（decision），协调者决定最后的结果，并且告知所有的参与者。如果所有的参与者第一阶段的表决都是提交，那么更新操作才会进行持久化。

在提交被认为是永久的之前，第二个阶段是非常有用的，因为它允许系统在节点失败时回滚更新。相反，在主/备份（“1PC”）中，没有回滚步骤，若发生在某些节点上失败而在其他节点上成功的情况，副本可能会出现分歧。

2PC容易造成拥塞，因为一旦一个节点失败，无论是协调者或是参与者，都会导致进程拥堵，直到节点修复。修复过程一般需要依靠第二个阶段中其它节点被告知系统状态。2PC是假设各个节点中的数据处于一个稳定的存储状态中，数据永远不会丢失并且不会发生节点崩溃。但是数据就算存储稳定，仍然会发生丢失如果发生崩溃的现象

节点故障期间恢复过程非常复杂，因此我不想详细介绍。主要任务是确保对磁盘的写入是持久的（例如，刷新到磁盘而不是缓存），并确保做出正确的恢复决策（例如，得到回合的结果，然后在本地重做或撤消更新）

正如我们在介绍CAP的章节中了解到的，2PC是一个CA算法，它没有分区容忍。2PC的故障模型中不包括网络分区；从节点故障恢复的指定方法是等待网络分区恢复。如果一个协调员失败了，就没有安全的方法来生成一个新的协调员；相反，需要人工干预。2PC还相当容易延迟，因为它是一种N对N的写方法，在最慢的节点确认之前，写操作无法继续。

2PC在性能和容错之间取得了相当好的平衡，这就是它在关系数据库中流行的原因。（因为失败了有回滚吗？？？）但是，较新的系统通常使用允许分区的一致性算法，因为这样的算法可以自动恢复由于临时网络分区造成的故障，以及能够对增加的节点间延迟时间进行更好的处理

接着来看分区容忍共识算法

分区容忍一致性算法

在保证单拷贝一致性中，考虑分区容忍一致性算法是我们将要讨论的内容。还有一类容错算法：允许任意（拜占庭式）错误的算法；这些算法来处理恶意操作导致节点失败的情况。这种算法很少在商业系统中使用，因为它们运行起来更昂贵，实现起来也更复杂——因此我将把它们排除在外。

涉及到分区容忍一致性算法时，最著名的算法是Paxos算法。然而，众所周知，它很难实现和解释，所以我将重点关注Raft，这是一种最近（2013年初）的算法，旨在更易于教学和实现。让我们首先看一下网络分区和允许分区的共识算法的一般特性。

什么是网络分区？

网络分区是指到一个或多个节点之间的网络链接失败。节点本身继续保持活动状态，甚至可以从网络分区的客户端接收请求。正如我们之前在讨论CAP定理中讨论到的，当网络分区发生后，并不是所有系统都能很好地处理它们。

网络分区很棘手，因为在网络分区期间，无法区分远程节点是发生了故障还是无法访问。如果一个网络分区出现但没有节点失败，那么系统将被划分为两个同时处于活动状态的分区。下面的两个图说明了网络分区看起来如何类似于节点故障。

下图展示了由两个节点组成的系统。网络分区VS存在故障：

image.png

一个强制实现单一拷贝一致性的系统必须有某种方法来打破对称性：否则，它将分裂成两个独立的系统，这两个系统可以彼此分离，并且不能再保持单一拷贝的假象。

对于强制执行单一拷贝一致性的系统，网络分区容忍要求在网络分区期间，只有一个系统分区保持活跃状态，因为在网络分区不能保证数据不发生分歧（CAP定理）

主要决策

分区容忍一致性算法需要多数的投票。不同于2PC算法需要所有的节点都达到一致，这里只需要大多数节点能够同意更新并且容许少部分节点宕机、慢或者由于网络分区而无法接触，这样系统仍然能够继续运行

分区容忍一致性算法使用的是奇数节点（类似于3，5，7）。如果使用2个节点的话，那么就难以对多数投票中的多数进行定义。举例说明：如果节点数量是3个，那么系统能够允许一个节点失败；如果节点数是5个，系统能够允许2个节点失败

当发生网络分区时，各个区的表现是不一致的。一个区可能包含大多数节点。小部分区会停止程序运行操作来阻止网络分区带来的数据分歧，但多数区仍然保持活跃状态。这能保证系统中只有一个单副本是活跃的

因为系统能够允许存在不一致，使得多数节点仍然是可用的：如果有变动和失败发生，节点可能投票不一致。但由于只可能有一个多数决策存在，暂时的分歧最多可以阻止协议继续进行（放弃活跃性），但不能违反单一副本一致性标准（安全属性）

角色

构造一个系统，系统中所有的节点要么含有相同的目标，要么有明确的分工和扮演的角色

复制的一致性算法通常会对每个节点分配不同的角色。一个系统中有一个固定的领导节点或者主服务能够使这个系统更加高效，所有的更新操作都要经过这个主服务。不是领导的节点只需要将它们的请求附送给领导节点

注意，明确的角色不代表系统中所有的节点一直扮演一个类型的角色。如果系统从节点失败中恢复过来，那么节点的角色可能会被从新分配，这个时候会存在一个领导节点选举的阶段。节点扮演它们的角色，到节点发生失败或者网络发生分区的时候，角色将又重新定义。

无论是Paxos算法还是Raft算法，它们都有明确的节点分工。具体而言，它们都有一个领导节点leader node（在Paxos中被称为proposer），负责正常系统运行操作中的协调作用。在正常运行中，剩下的节点是跟随节点follows（Paxos中称为acceptors或者voters）

训练周期

无论是Paxos还是Raft算法中，正常运行的每一个阶段都被称为一个训练周期（Raft中被称为‘term’）。在每一个周期中，只有一个节点被标记为领导节点

image.png

成功选举后，在这个周期中领导节点不变，直到下一次选举发生。如图所示，可能会存在选举失败的情况，这个时候会导致这个周期很快结束

周期纪元表现形式想逻辑锁一样，它允许其它节点识别出一个过期节点何时开始通信-分区或不运行的节点相比于正常的节点，周期会落后，能被识别出来并且它们的需求就直接被忽略

领导节点变化

在正常运行操作中，分区容忍一致性算法是很简单的。正如我们之前所说，如果我们不关心容错性，我们可以直接使用2PC算法。大部分情况下，算法复杂的原因就是因为我们需要保证一旦做出了一个一致性决策，它不能被丢失，并且有协议能够处理由于网络或节点崩溃带来的领导节点变化的情况

首先，刚开始的时候所有节点都是followers跟随者，然后其中一个节点被选举为leader领导者。在一个正常运行阶段，这个领导节点一直有心跳，允许其它跟随节点检测到它是否失败或者是被分区了

当一个节点检测到领导节点变得不响应时（或者，在最初的情况下，没有领导者存在），它会切换到一个中间状态（在raft中称为“候选人”），在这个状态中，它将周期纪元值增加一个，启动一个领导者选举，并竞争成为新的领导者

节点在投票过程中必须要获得多数投票才能成为一个领导节点。分配选票的最简单的一种方法是按先到先得的原则进行；这样，最终将选出一位领导节点。在选举过程中之间添加随机的等待时间将减少同时尝试当选的节点数（？？？）

一个周期中的编号提案

在每一个周期纪元中，领导节点会依次提出一个值，用来供以表决。在每个周期中，每个提案都有一个唯一的严格递增的数字编号。追随者（投票者/接受者）接受他们收到的针对特定提案编号的第一个提案

正常运行

在正常运行中，所有的提案会经过领导节点。当一个客户端提交一个提案（例如：一个更新操作），这个领导节点会联系仲裁中的所有的节点。如果没有竞争提案（基于追随者的响应），领导节点会提出一个值。如果大多数追随者接受这个值，那么这个值就被认为是被接受的

由于另一个节点也可能试图充当领导者，因此我们需要确保一旦接受了一个建议，它的值就永远不会改变。否则，一个已经被接受的提议可能会被竞争领导的节点回复。Lamport描述如下：

• P2: 如果一个提议的值一旦被确定为v，任何更高编号的提议也会选择这个值

确保追随者和提议者都不能改变已被大多数人接受的值。这里“值永远不能更改”是指协议的单个执行（或运行/实例/决策）的值。一个典型的复制算法将运行该算法的多个执行，但大多数关于该算法的讨论集中在一次运行上。我们希望防止更改或覆盖决策历史记录。

为了强制执行此属性，提案人必须首先向追随者询问他们（编号最高）接受的提案和值。如果提案人发现提案已经存在，那么它必须简单地完成协议的执行，而不是自己提出提案。Lamport描述如下：

• P2b. 如果一个提议的值一旦被确定为v，任何提议人发布的任何更高编号的提议都具有值v

更具体地说：

• P2c. 对于任何v和n，如果一个值为v编号为n的提案被[领导节点]发布，那么存在一个由大多数接受者[追随者]组成的集合S，其中，没有接受者接受编号比n小的提案，v是S中所有编号小于n的提案中编号最大的提案的值

这是paxos算法的核心，也是从中派生出来的算法的核心。在协议的第二阶段之前，不会对建议的值进行选择。提案人有时必须简单地重新传输先前做出的决定，以确保安全（例如P2c中的条款b），直到他们知道自己可以自由地强加自己的提案值（例如条款a）

如果存在多个以前的建议，则建议使用编号最高的建议值。只有在完全没有竞争性提案的情况下，提案人才能试图强加自己的值

为了确保在提案人向每个接受人询问其最新值时不会出现竞争性提案，提案人要求跟随者不要接受提案编号低于当前提案编号的提案

把这些部分放在一起，使用Paxos算法做出决定需要两轮沟通：

image.png

准备阶段允许提案人了解任何竞争或以前的提案。第二阶段是提出新值或先前接受的值。在某些情况下，例如，如果两个提议者同时处于活动状态（决斗）；如果消息丢失；或者如果大多数节点都失败，则多数人不会接受任何提议。但这是可以接受的，因为建议的值的决策规则收敛到一个值（上一次尝试中建议数最高的值）。

事实上，根据FLP不可能的结果，这是我们所能做的最好的：解决共识问题的算法必须在消息传递边界的保证不成立时放弃安全性或活跃性。Paxos放弃了活跃性：它可能不得不无限期地推迟决策，直到某个时间点没有竞争的领导者，并且大多数节点都接受了一个提议。这比违反安全保证更可取。

当然，实现这个算法要比听起来困难得多。有许多小问题，即使是在专家的手中，加起来也相当可观的代码量。这些问题包括：

• 实际优化：
  -- 通过领导权租赁（而不是心跳）避免重复的领导选举
  -- 避免在领导节点身份不变的稳定状态下重复建议消息
• 确保追随者和提议者不会丢失稳定存储中的项目，并且存储在稳定存储中的结果不会被损坏（例如磁盘损坏）。
• 允许集群成员以安全的方式进行更改（例如，基本Paxos依赖于一个事实：大多数成员总是在一个节点中相交，如果成员可以任意更改，那么这个节点就不起作用）
• 在崩溃、磁盘丢失或配置新节点后以安全有效的方式使新副本更新的过程
• 快照和垃圾收集程序：在一段合理的时间后，为确保安全所需的数据（例如，平衡存储要求和容错要求）

谷歌的Paxos制作了实况文件，详细介绍了其中的一些挑战

分区容忍一致性算法：Paxos、Raft、ZAB

这一节想让您了解了一个允许分区的共识算法是如何工作的。鼓励大家阅读下一阅读部分中的文章，以了解不同算法的具体情况。

Paxos-是在编写强一致性的容错分区复制系统时最重要的算法之一。它被用于谷歌的许多系统，包括Bigtable/MegaStore使用的丰满版锁管理器、谷歌文件系统以及Spanner

Paxos以希腊的帕克斯岛命名，最初由莱斯利·兰波特于1998年在一份名为“兼职议会”的论文中提出。它通常被认为是很难实现的，具有相当多分布式系统专业知识的公司的一系列论文对其具体实施的实际细节进行了进一步的解释（请参阅进一步阅读）

我们使用一轮共识决策来描述Paxos算法，但是实际的工作执行通常希望高效地运行多轮共识。这导致了核心协议上的许多扩展的开发，任何对构建基于Paxos的系统感兴趣的人仍然需要消化这些扩展。此外，还有一些额外的实际挑战，例如如何促进集群成员资格的改变。

ZAB-在Apache ZooKeeper中使用了ZooKeeper原子广播协议。ZooKeeper是为分布式系统提供协调原语的系统，许多以Hadoop为中心的分布式系统（如HBase、Storm、Kafka）都使用它进行协调。ZooKeeper基本上是开源社区的丰满版本。从技术上讲，原子广播是一个不同于纯一致共识的问题，但它仍然属于保证强一致性的分区容忍算法范畴。

Raft-Raft是最近（2013年）对该算法系列的一个补充。它被设计成比Paxos更容易教学，同时提供相同的保证。特别是算法的不同部分之间的分离更加清晰，本文还描述了一种集群成员关系变化的机制。它最近在受ZooKeeper启发的etcd中被采用。

本章中强一致性的复制方法

在本章中，我们介绍强制实现强一致性的复制方法。从同步工作和异步工作之间的对比开始，我们了解能够容忍日益复杂的故障的算法。以下是每种算法的一些关键特性：

主/备算法

• 单，静态主机
• 复制的日志，从服务器不参与执行操作
• 复制延迟没有限制
• 不允许分区
• 手动/故障转移，不容错，“热备份”

2PC

• 一致表决：同意或放弃
• 静态主机
• 2PC在提交过程中无法承受协调器和节点的同时失败。
• 不允许分区，尾延迟敏感

Paxos

• 多数投票机制
• 动态主机
• 作为协议的一部分，对N/2-1同时故障具有鲁棒性
• 对尾延迟不太敏感