复制（Replication）

复制意味着在通过网络连接的多台机器上保留相同数据的副本，我们希望能复制数据，可能出于各种各样的原因：

• 高可用性：即使在一台机器（或多台机器，或整个数据中心）停机的情况下也能保持系统正常运行

• 断开连接的操作：允许应用程序在网络中断时继续工作

• 延迟：将数据放置在距离用户较近的地方，以便用户能够更快地与其交互

• 可扩展性：能够处理比单个机器更高的读取量可以通过对副本进行读取来处理

如果复制中的数据不会随时间而改变，那复制就很简单：将数据复制到每个节点一次就万事大吉。复制的困难之处在于处理复制数据的变更（change），目前三种流行的变更复制算法：单领导者（single leader），多领导者（multi leader）和无领导者（leaderless）。

• 单主复制：客户端将所有写入操作发送到单个节点（领导者），该节点将数据更改事件流发送到其他副本（追随者）。读取可以在任何副本上执行，但从追随者读取可能是陈旧的。

• 多主复制：客户端发送每个写入到几个领导节点之一，其中任何一个都可以接受写入。领导者将数据更改事件流发送给彼此以及任何跟随者节点。

• 无主复制：客户端发送每个写入到几个节点，并从多个节点并行读取，以检测和纠正具有陈旧数据的节点每种方法都有优点和缺点。单主复制是非常流行的，因为它很容易理解，不需要担心冲突解决。在出现故障节点，网络中断和延迟峰值的情况下，多领导者和无领导者复制可以更加稳健，但以更难以推理并仅提供非常弱的一致性保证为代价。

复制可以是同步的，也可以是异步的，在发生故障时对系统行为有深远的影响。尽管在系统运行平稳时异步复制速度很快，但是在复制滞后增加和服务器故障时要弄清楚会发生什么，这一点很重要。如果一个领导者失败了，并且你推动一个异步更新的追随者成为新的领导者，那么最近承诺的数据可能会丢失。我们研究了一些可能由复制滞后引起的奇怪效应，我们讨论了一些有助于决定应用程序在复制滞后时的行为的一致性模型：

• 写后读：用户应该总是看到自己提交的数据。

• 单调读：用户在一个时间点看到数据后，他们不应该在某个早期时间点看到数据。

• 一致前缀读：用户应该将数据视为具有因果意义的状态：例如，按照正确的顺序查看问题及其答复。

复制与分区

复制即在几个不同的节点上保存数据的相同副本，可能放在不同的位置。复制提供了冗余：如果一些节点不可用，剩余的节点仍然可以提供数据服务。分区 (Partition/Shard)则是将一个大型数据库拆分成较小的子集，从而不同的分区可以指派给不同的节点（node）。

复制和分区是不同的机制，但它们经常同时使用。

复制与一致性

由于采用多机器进行分布式部署的方式提供服务，必然存在着数据的复制。分布式系统的数据复制需求能够保证系统的可用性与性能：将数据复制到分布式部署的多台机器中，可以消除单点故障，防止系统由于某台(些)机器宕机导致的不可用；而通过负载均衡技术，能够让分布在不同地方的数据副本全都对外提供服务。有效提高系统性能。

在分布式系统引入复制机制后，不同的数据节点之间由于网络延时等原因很容易产生数据不一致的情况；如果你在同一时刻查看两个数据库节点，则可能在两个节点上看到不同的数据，因为写请求在不同的时间到达不同的节点。无论数据库使用何种复制方法（单主复制，多主复制或无主复制），都会出现这些不一致情况。复制机制的目的是为了保证数据的一致性。但是数据复制面临的主要难题也是如何保证多个副本之间的分布式一致性。如何能既保证分布式一致性，又保证系统的性能，是每一个分布式系统都需要重点考虑和权衡的。在实际的分布式系统中，我们常常会面临以下具体的场景：

• 比如在集中式系统中，有一些关键的配置信息，可以直接保存在服务器的内存中，但是在分布式系统中，如何保存这些配置信息，又如何保证所有机器上的配置信息都保持一致，又如何保证修改一个配置能够把这次修改同步到所有机器中，就是存在的问题。
• 在集中式系统中，进行一个同步操作要写同一个数据的时候，可以直接使用事务+锁来管理保证数据的 ACID。但是，在分布式系统中如何保证多台机器不会同时写同一条数据。

大多数复制的数据库至少提供了最终一致性，这意味着如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值。换句话说，不一致性是暂时的，最终会自行解决（假设网络中的任何故障最终都会被修复）。最终一致性的一个更好的名字可能是收敛（convergence），因为我们预计所有的复本最终会收敛到相同的值。然而，这是一个非常弱的保证，它并没有说什么什么时候副本会收敛。在收敛之前，读操作可能会返回任何东西或什么都没有。例如，如果你写入了一个值，然后立即再次读取，这并不能保证你能看到刚跟写入的值，因为读请求可能会被路由到另外的副本上。

如何保证一致性

实现分布式系统一致性，首先需要考虑的就是分布式时钟，我们需要解决不同节点之间的标准时间问题。从最初的网络时间协议（NTP）到逻辑时钟到向量时钟，较好地解决了不同节点间的顺序问题。CALM 原则的全称是 Consistency and Logical Monotonicity，主要描述的是分布式系统中单调逻辑与一致性的关系：

• 在分布式系统中，单调的逻辑都能保证最终一致性，这个过程中不需要依赖中心节点的调度。
• 任意分布式系统，如果所有的非单调逻辑都有中心节点调度，那么这个分布式系统就可以实现最终一致性。

接下来我们需要考虑合适的数据结构进行节点间的数据同步与合并，这也是一致性算法的前提，设计良好的数据结构加上精妙的算法可以高效的解决现实的问题。分布式系统的数据结构 CRDT(Conflict-Free Replicated Data Types) 即是分布式系统中被广泛采用的数据结构：

• 基于状态(state-based)：即将各个节点之间的 CRDT 数据直接进行合并，所有节点都能最终合并到同一个状态，数据合并的顺序不会影响到最终的结果。
• 基于操作(operation-based)：将每一次对数据的操作通知给其他节点。只要节点知道了对数据的所有操作（收到操作的顺序可以是任意的），就能合并到同一个状态。

最后需要来关注一下分布式系统的一些重要的协议 HATs(Highly Available Transactions)，ZAB(Zookeeper Atomic Broadcast)，这些往往是基于业界主流的一致性算法，譬如 Paxos, Raft 以及 Gossip 等。