基于最终一致性的数据同步工具的设计与实现2

对于数据同步工具 Syncer，一致性是保证其正确性的关键因素，并且对于 实现中的很多选择提供了理论依据，所以本文着重对于相关理论进行一些简单的介绍。

FLP不可能性原理

FLP 不可能性原理(FLP Impossibility) [Fischer, M. J. et al., 1985] 的名 称起源于它的三位论文作者，Fischer、Lynch 和 Paterson。这篇论文研究的 是在异步系统中，想要解决共识问题，是否可能，会受到怎样的限制的讨论 (结论同样可以适用于，存在拜占庭故障的同步系统中)。

共识问题是普遍存在于分布式系统中的基本问题:即，使得分布式系统中 的各个处理者最后都对同一个结果值达成共识。一个可以解决停机故障的共识 问题的协议需要满足“终止”、“一致同意”和“有效性” [Consensus, 2019] 这三个特性:

• 所有无错误的进程(处理过程)最终都将决定一个值;
• 所有会做决定的无错误进程决定的都将是同一个值;
• 如果所有正确的进程提出了同一个值，那么任何正确的进程都将决定同一个值。

FLP 不可能性原理论文中的研究环境模型假设如下:

• 无拜占庭故障
  拜占庭故障或称为拜占庭将军问题(The Byzantine Generals Problem) [Lamport, L. et al, 1982]，是指在分布式系统中，某些处理 者可能在面对其他处理者时，展现不一致的结果，从而影响系统整体达 成一致的问题。拜占庭故障一般比较少见，在系统被黑客攻击等情况下 可能出现。

• 消息通信是可靠的，异步的 所有消息都可以正确的最终发送到接收方，并且只发送一次。此处异步 的定义在于:对于进程的处理消息延迟，对于传递消息的延迟都没有上 限。

通过反证法，FLP 不可能性原理形成了两条主要结论:

• 在异步模型环境下并不存在任何一个完全容错的分布式共识算法。除了

  满足上述三个特性的，较“强”形式的共识算法不可能实现，论文还证 明了比它弱一些的、只需要“最终被决定的值必须被至少一个进程提出 过”的共识算法也是不可能实现的。 换句话说，在异步模型中，即使 仅仅只有一个进程可能崩溃的情况下，就已经不存在可以解决共识问题 分布式算法。这是该问题的理论上界。

• 在异步模型下存在部分正确的共识算法。这个算法的前置条件是严格多 数进程没有错误，并且没有进程会在算法的执行过程中死亡，结论是所 有未崩溃进程可以达成共识。

  FLP 不可能性原理的意义不在于阻止我们提出分布式共识的解决方案，而 在于，该解决方案需要对进程错误有恢复能力，处理者一旦崩溃以后，就不再 参与计算。而判断进程崩溃的方式是:等待一个既定的完整的处理步长来检测 某个处理者是否已失败。如果没有收到回复，那就假定它已经崩溃。

CAP定理

CAP 理论(CAP theorem) [Fox, A. et al., 1999] 是分布式系统设计中最 基础，也是最为关键的理论之一。它指出，分布式数据存储系统不可能同时满 足以下三个特性:

• 一致性(Consistency):每次读取请求要么获得最近写入的数据，要 么获得一个错误。

• 可用性(Availability):每次读取请求都能获得一个(非错误)响应， 但不保证返回的是最新写入的数据。

• 分区容忍(Partition tolerance):在任意数量的消息被节点间的网络丢 失(或延迟)的情况下，系统仍能继续正确运行。

举例来说，在发生了网络分区问题的情况下，由 CAP 定理可以推出，一致 性和可用性必须二选一。反之，如果在没有发生网络故障的情况下，即分布式 系统正常运行时，一致性和可用性是可以同时被满足的。需要注意的是，CAP 定理中的一致性与 ACID [ACID, 2019] 数据库事务中的一致性定义完全不同， 不可以混淆。

掌握 CAP 定理，尤其是能够根据需求对 C、A、P 进行取舍，对于系统 架构来说非常重要。因为对于分布式系统来说，网络分区问题在所难免，如何 在出现网络分区问题的时候，如何使得系统按照正常的行为逻辑运行，得益于 正确的设计及实现系统。针对实际的业务场景和具体需求，需要进行不同的权 衡。例如，对于大多数互联网服务来说(如 Google 的搜索服务)，因为机器 数量庞大，部署节点分散，网络故障是不可避免的(Partition tolerance)，可 用性(Availability)是必须要保证的，所以只有放弃强一致性(Consistency) 来保证服务的 AP。而对于银行等，需要确保强一致性的场景，通常会在 CA 和 CP 模型之间权衡选择。CA 模型网络故障时完全不可用，CP 模型具备部 分可用性。

CA (Consistency + Availability)，这样的系统关注一致性和可用性，它需要 非常严格的全体一致的协议，比如著名原子提交协议的“两阶段提交协议” (Two-phase commit protocol) [Gray, 1978]。CA 系统不能容忍网络错误或 节点错误，一旦类似的问题发生，整个系统就会拒绝写请求直到原有节点恢复 或新的节点参与。这是因为它并不知道其他结点是否挂掉了，还是只是网络问 题。唯一安全的做法就是把自己变成只读的。类似的软件实现有，搜索引擎 Elasticsearch [Elasticsearch and CAP, 2014]。

CP (Consistency + Partition tolerance)，这样的系统关注一致性和分区容 忍性。它关注的是系统里大多数人的一致性协议，比如:Paxos [Lamport, 1998] [Paxos, 2019] 算法(Quorum 类的算法)。这样的系统只需要保证多数过 半的结点数据一致，而少数的结点会在没有同步到最新版本的数据时变成不可 用的状态。这样能够提供“部分”的可用性。类似的软件实现有，文档数据库 MongoDB。

AP (Availability + Partition tolerance)，这样的系统关心可用性和分区容忍 性。因此，这样的系统不能达成强一致性，需要解决数据冲突，而解决数据冲 突就需要维护数据版本。类似的软件实现有，键值存储 DynamoDB。

最终一致性

最终一致性 [Vogels, 2009] 是 CAP 理论在具体工程中的发展，这种方式 舍弃了系统的强一致性而选择 AP，从而提高了软件系统的可达性和性能。最 终一致性通常被阐述为 BASE (Basically Available, Soft state, Eventual consistency) 原则，相对于强一致性，最终一致性保证如果没有对数据进行 新的更新，那么最终所有的对该数据进行的访问，都会返回最后的更新值。最 终一致性在数据复制(replication)时，最为常用，所以亦被称为乐观数据复 制。

要达到最终一致性，系统必须解决多份数据拷贝之间的冲突问题。解决过程分为两步:

• 在进程之间交换数据更新与数据版本;
• 根据一定的规则，选择合适的最终状态用于更新。

大多数冲突解决方案依赖于数据系统自身的特点，每个应用可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。其中最常见的一种方 式便是“last writer wins”，即数据更新的最后一个版本。对于“最后”的判 断，则通常使用时间戳或逻辑时钟(Logical Clock) [Mattern, 1988] [Fidge, 1988] 的方式。由于全局时间戳通常并不可准确，所以逻辑时钟更加合适。

在最终一致性的基础上，有人提出了强最终一致性。除却更新最终可见的要求之外，其还要求如果任意两个节点都收到了相同的无序的数据更新，他们最终应该处于相同的状态。

复制状态机

复制状态机(State machine replica) [Fred, 1990] 在分布式领域是一个 常用且重要的技术，通过复制服务副本，并和副本一起来协调客户端的交互， 来实现容错服务。这个方法同样提供了一个框架，来理解和设计复制管理协 议。

复制状态机顾名思义，是一个用于数据复制的状态机算法。在复制状态机中，一般使用有限状态机。算法的大概步骤如下:

1. 将状态机的初始副本放在多个不同的、独立的节点。
2. 接收客户端的请求，作为状态机的输入。
3. 决定输入的一个次序。
4. 使用相同的次序在每个节点的状态机执行操作。
5. 将状态机的输出作为客户端的返回值。
6. 定期监控多个状态机之间的状态和输出是否不同。

其中，第三步是整个算法的核心操作。由于所有正确的状态机在给定相同的输入时，将会到达相同的状态，所以输入顺序是否正确将影响到系统状态。

对于消息输入的顺序，通常有三种定义:

• 先进先出序(FIFO ordering):是一种偏序关系。如果两个消息由同 一个输入源产生，那么任意一个状态机都会以相同顺序收到这两个消 息。

• 因果序(Causal ordering):是一种偏序关系。如果一个消息产生在另 一个消息之前(Ordering of Events) [Lamport, 1978] ，则状态机都 会以这个顺序收到这两个消息。

• 全序(Total ordering):不同于前面两种顺序，这是一种消息之间的 全序关系。代表任意两个消息，在任意一个状态机都会是相同的输入顺 序。

在实际生产中，由于“全序”实现代价过高，并且对于很多消息并没有必 要确定顺序，所以大多并不采用这种方式。“因果序”相对“先进先出序”更 加严格，不同应用会根据自身要求实现。例如，在 MySQL 主从同步中，从服 务器(slave)只需要保证来自主服务器(master)消息以相同顺序到达即可。

At Least Once 与 Exactly Once 语义

事实上，有三种常见的发送语义 [Exactly Once, 2015] :

• 最多一次 At Most Once:发送方最多向接收方发送一次消息;
• 至少一次 At Least Once:发送方至少向接收方发送一次消息;
• 刚好一次 Exactly Once:发送方刚好向接收方发送一次消息;

最多一次语义在实际应用中常用于对于一致性要求不高的场景，并且宁可不发送成功，也不可以重复发送的场景，诸如，某些短信通知。至少一次语义 非常常见并实用，通常使用重试机制达到这样的效果。严格来说，刚好一次语 义在分布式系统中无法实现，这是因为刚好一次语义可以看成发送方与接收方 之间的一个共识问题:发送方与接收方之间对于发送次数达到一个共识。由 FLP 异步系统不可能性原理，我们可以知道在严格意义上，该共识问题并不可 解。

虽然刚好一次语义理论上无法实现，但是可以通过至少一次语义间接实现:如果发送方实现了至少一次语义并且可以不断重试，并且接收方的消费是幂等的，那么当最终消费成功之后，这样的实现对外即表现为刚好一次语义。

Written with StackEdit.