在分布式系统中，数据复制（Data Replication）是核心设计策略之一，其核心目的是通过冗余存储相同数据副本来提升系统的可靠性、可用性、性能及容错能力：

• 高可用性（High Availability）：如果只有一个节点提供服务，单节点故障会导致服务不可用。通过将数据复制到多个节点，即使一个节点宕机，其他节点仍可继续提供服务。
• 容错与灾难恢复（Fault Tolerance and Disaster Recovery）：硬件故障、网络分区或数据中心灾难可能导致数据永久丢失。采用多副本存储（如跨机房/跨地域复制）确保数据可恢复。
• 降低延迟（Reduced Latency）：用户与数据中心的物理距离导致访问延迟（如访问跨国服务），将数据复制到地理分布的不同节点，使用户可访问最近的副本。
• 提升读性能（Read Performance Optimization）：单一节点可能成为读请求的瓶颈，通过多副本分散读负载以提升读性能。

按照复制时是否有主节点的介入，分为主从复制和无主节点复制，其中主从复制意味着系统中有一个中心节点，负责协调写入数据复制到其它副本，与之对应的，无主节点复制就是去中心化的架构。

尽管数据复制带来诸多优势，但由于数据复制延迟等原因，需要面对多个副本间数据的一致性问题。数据复制的引入，在带来可扩展性和可靠性的同时，也引发了如何保证多个副本数据语义一致性的挑战。我们将深入讨论不同一致性模型的特点和实现，不同的一致性模型的实现难度不同，不同的业务场景采用不同的一致性模型，可以看到在很多时候，采用较弱的一致性模型也能满足业务的需求。

在很多时候，单台机器不足以容纳系统的所有数据，在这种情况下，需要按照某种规则将数据划分到不同的机器中存储，这是分区一章将要讨论的内容。在本章中，我们假设单台机器的容量可以容纳系统的所有数据。

主从复制 #

为了保证系统的高可用性，需要将系统的数据保存到多个节点上，每一个保存了完整数据的节点称为副本（replica）。在主从复制模式中，系统中的副本地位不一致，分为以下两类：

• 主节点：客户端的写请求首先发往主节点，主节点收到客户端的写入数据请求之后，保存到本地存储中。
• 从节点：主节点将客户端写入的数据保存在本地之后，将数据同步到从节点，主、从节点上的数据将保持严格的写入顺序。

在不同的系统中，对主节点有不同的称呼，例如primary、master、leader等，对从节点也有不同的称呼，例如secondary、replica、slave、follower等。

如图[fig:replication/rep-primary-1]是一个简易的主从复制模式的分布式系统。在主从复制模式下，向系统写入的数据，必须首先经过主节点，再复制到从节点。与写操作不同的是，某些系统允许通过从节点读取数据，这种情况下可能读到旧的过期数据，这要看系统需要满足怎样的一致性要求，我们将在”一致性模型“小节中深入讨论这个话题。

图: 客户端1的写入请求首先发到主节点A，再由主节点同步到其它从节点。如果此时有另外的客户端2从从节点读取数据，那么可能读到旧的过期数据

数据复制模式 #

在图[fig:replication/rep-primary-1]中，我们刻意忽略了一个问题：当客户端写入数据时，何时应答客户端写入成功？是只要求在主节点上写入数据成功就能应答客户端，还是要等待数据复制到从节点成功之后才能应答？根据不同的应答时机，将复制方式分为：同步复制（Synchronous Replication）、异步复制（Asynchronous Replication）和半同步复制（Semi-synchronous Replication）。

同步复制

如图[fig:replication/rep-primary-sync.png]，在同步复制中，主节点只有在将数据同步到所有从节点并且得到所有从节点的确认之后，才向客户端返回写操作成功的响应。这种复制方式的优缺点是：

• 优点：数据一致性高，没有数据丢失的问题。
• 缺点：系统的应答时间，由响应最慢的那个从节点决定。系统中如果有一个节点宕机或者网络延迟较高，就会影响写入的成功和延迟，系统的可用性随着从节点数量的增加而降低。

图: 在同步复制中，主节点只有在收到所有从节点的复制成功应答之后，才响应客户端的写入成功。在这种方式下，系统的应答时间，由响应最慢的那个从节点决定。

异步复制

如图[fig:replication/rep-primary-async.png]，与同步复制完全不同的是，在异步复制中，主节点只要在本地持久化写入的数据，就可以响应客户端写入成功，不需要等待数据成功复制到从节点。这种复制方式的优缺点是：

• 优点：写操作延迟低，客户端响应快。主节点不受从节点故障或网络问题影响，系统可用性高。
• 缺点：数据一致性弱，主从节点间可能存在短暂不一致。如果在数据成功复制到从节点之前，主节点发生故障，未同步的数据将丢失。

图: 在异步复制中，主节点在数据保存到本地之后就应答客户端写入成功，在此之后才开始复制数据到从节点。如果主节点在主节点应答客户端之后、数据成功复制到从节点之前发生故障，那么应答客户端已经成功写入的数据，可能会丢失。

半同步复制

从上面可以看到，同步复制和异步复制都有各自的问题，业界更常使用的是两者折中之后的方案：半同步复制（Semi-synchronous Replication）[@Semi-Synchronous]，如图[fig:replication/rep-primary-semi-async.png]所示。在这种方案中，主节点并不会在数据保存到本地之后就马上应答客户端写入成功，也不会等待所有从节点都复制成功从响应客户端，而是在两者之间取一个折中：主节点等待足够多的从节点应答写入成功。

在这种折中方案下，因为系统只需要等待部分从节点应答成功，不受最慢的从节点影响，因此不会像在同步复制中那样，延迟最慢的从节点直接决定系统的响应时间；另外数据也复制到了部分从节点上，这样不会像在异步复制中那样，由于主节点的故障导致数据完全丢失。

至于何谓足够多的从节点，不同一致性要求的系统有不同的需求，我们将在[subsection:quorum]继续讨论这个话题。

图: 在半同步复制中，主节点只需要等待部分从节点应答复制成功，就可以响应客户端写入数据成功。在图中，假设此时系统要求只要复制到一个从节点就能应答写入成功，因此主节点A在收到从节点B的成功复制应答，就响应客户端写入成功，不必等待从节点C的复制应答。

下表对比总结三种复制模式的工作原理和优缺点。

模式	工作原理	优点	缺点
同步复制	主节点必须等待所有从节点都确认收到数据并写入成功后，才响应客户端。	数据一致性最强，能保证数据已安全存储在多个副本上。	延迟非常高，写入性能最差。任何一个从节点宕机都会导致整个系统无法写入（可用性低）。
异步复制	主节点完成本地写入后立即响应客户端，之后再异步地将数据复制给从节点。	延迟极低，写入性能最佳。	数据丢失风险高。如果主节点在日志发送前宕机，已确认的写操作会永久丢失，造成数据不一致。
半同步复制	折中方案。主节点只需等待足够多的从节点确认收到数据后，即可响应客户端。	在性能和数据安全之间取得了很好的平衡。	仍比异步复制的延迟高，且如果唯一确认的从节点宕机，会退化为同步模式。

对比总结三种复制模式的工作原理和优缺点

法定人数 #

当我们采用半同步模式复制数据时，需要回答一个问题：数据需要复制到多少个副本，才可以应答客户端复制成功？在分布式系统中，*法定人数（Quorum）*指的是：为了让一个操作（读或写）被系统承认是成功的，必须参与并投赞成票的最小节点数量，通常而言，以超过系统半数节点数量做为法定人数。Quorum机制就是用来约束数据复制行为的规则，它决定了复制的一致性级别。

虽然在分布式系统中，法定人数通常选择是集群半数以上的节点数量，也就是常说的大多数（majority），但是Quorum不一定非得是majority。法定人数机制的核心是满足读、写法定人数集合有重合，但是这个机制并不限于多数法定机制，还存在其它的法定人数机制[@Read-Write Quorum]。简单起见，在本书的后续描述中，将不区分“法定人数”和“大多数”。

在复制数据时，主节点向从节点写入等待确认的节点数，就是主从复制中的“Write Quorum”。以下采用N表示系统的节点总数，W表示写法定人数数量，要求W > N/2，即写操作在超过半数以上的节点上确认成功。

之所以有超过半数的限制，是因为分布式系统需要在某些情况下对数据达成集群内唯一的共识。除了复制数据以外，法定人数还用于选举主节点。选举时需要保证不会同时出现两个主节点，在系统节点对参与选举的主节点进行投票时，强制要求只有超过半数得票的节点才能赢得选举，这样就能保证不会同时出现两个主节点（因为不可能出现同时有两个节点都得到超过半数的投票）。

前面提到的不同数据复制模式，可以看做采用了不同的法定人数设置：

• 同步复制：W=N，即写操作需要所有节点都确认才可以应答。
• 异步复制：W=1，即写操作只需要复制到主节点完成就可以应答。
• 半同步复制：W > N / 2，即写操作需要复制到半数以上节点完成才可以应答。

Quorum机制主要用于在分布式系统中对数据达成唯一的共识，例如复制数据、选举主节点等，因此不仅被用于主从复制模式，还可以被用于无主复制模式，我们将在[sec:dynamo-quorum]看到在无主复制中的应用，将在[subsec:raft-leader]看到如何运用于集群主节点选举。

客户端发送请求 #

在主从复制中，客户端的写入请求只能由主节点处理，所以客户端如何感知主节点成了一个问题，一般而言有以下几种机制（为了描述方便起见，以下描述中都假设系统当前采用同步复制的模式）。

如果接收到写请求的是从节点，从节点可以将请求*转发（forward）*给主节点，主节点处理请求之后再应答这个接收到客户端请求的从节点，从节点应答客户端写入成功，如图[fig:replication/rep-primary-2]是一个典型的转发写入请求到主节点的流程图：

• 从节点A收到客户端的写请求。
• 由于从节点当前不是系统的主节点，它将该请求转发到主节点B。
• 主节点B收到写请求之后，采用同步复制的模式将数据辅助到两个从节点A和C。
• 在完成同步复制后，主节点B应答从节点A写入数据完成。
• 从节点A应答客户端写入数据完成。

注意在这里，还要考虑会出现这种情况：可能从节点得到的主节点信息也是落后的，即转发请求的目标节点当前已经不再是主节点了，那么这个旧的“主节点”可以继续转发给自己认为的主节点，这个过程一直到真正的主节点收到写入请求为止。通常而言，系统中的所有节点，需要一个机制能够感知到当前系统主节点的切换，例如在K8S架构中，系统运行的元数据保存在etcd中，关心集群变化情况的服务，通过etcd的watch (https://etcd.io/docs/v3.5/tutorials/how-to-watch-keys/)API接口监听变化。

图: 客户端的写入请求首先发到节点A，由于节点A并不是当前的主节点，需要转发请求到主节点B，主节点B完成数据的复制之后应答接收客户端写入请求的节点A，节点A应答客户端写入成功

另一种方式与前一种类似，如图[fig:replication/rep-primary-22]所示，在这种方式下从节点在收到客户端的写请求后，并不转发请求给主节点，取而代之的是返回当前主节点的地址给客户端，客户端使用返回的地址再次尝试发送请求：

• 从节点A收到客户端的写请求。
• 由于从节点当前不是系统的主节点，它将当前主节点B地址给客户端。
• 客户端重新向主节点B发起写请求。
• 主节点B在收到客户端写请求之后，复制数据到从节点A和C。
• 完成数据复制后，主节点B应答客户端写入成功。

图: 客户端的写入请求首先发到节点A，由于节点A并不是当前的主节点，节点A返回当前主节点地址（节点B）给客户端，客户端再次向当前主节点B发起写请求，主节点B收到请求之后，向从节点复制数据，完成数据复制后应答客户端写入成功

最后一种方式，客户端通过定期拉取或者订阅集群信息的方式，自己维护系统的节点信息，从而根据这些信息知道应该往哪个节点发送写请求。

以上几种机制中，第一种是最简单的，因为客户端对主节点的信息完全没有感知，并不需要额外的工作。缺点在于，如果客户端经常发送写请求给从节点，那么整个过程中就多了一次从节点转发给主节点的延迟。在另外两种方式中，客户端都要做一些额外的工作。一般而言，使用这类请求方式的服务都会以SDK的方式提供给客户端，里面封装了如何重试、维护集群信息等细节，但是这也意味着可能不能简单使用一些通用的客户端（如HTTP协议）来访问服务。

值得一提的是，写请求必须经过主节点，而读请求可以被任意节点处理，但是如果读请求发送到从节点，可能读取的并不是最新的数据，如图[fig:replication/rep-primary-3]所示，在quorum机制[[sec:dynamo-quorum]]下，认为已经写入成功，但是读请求的客户端却读到了旧的值。这取决于服务对外提供了怎样的一致性保证，这将在后面的一致性模型中讨论。

图: 如果按照quorum机制，数据已经写入3节点中的2节点即可认为写入成功，但是读数据的客户端读到了旧的数据

复制数据 #

前面我们讨论了数据复制的模式，本小节我们讨论在复制数据时的数据内容。回忆一下在[sec:snapshot]中我们讨论过，维护一个系统的数据分为以下三类：

• 状态（status）：一个系统中所有数据的值，状态会随着事件发生改变；
• 事件（event）：能够改变系统状态的操作。在一个服务中，所有写请求（写入、更新、删除等），都可以称为事件；
• 快照（snapshot）：快照是一种特殊的状态，快照是静止的状态，一旦确定了快照的时间，也就确定了快照的内容。

在以上三类数据中，哪类数据才是副本之间复制数据时采用的数据内容？答案通常取决于副本的数据和当前系统最新数据的差距。

在这三类数据中，状态数据和快照数据属于系统的全量、静态数据，数据量比较大，而事件数据则是增量的、动态数据。所以，根据副本处于不同的阶段，会同步不同类型的数据。

一般而言，新增的节点没有任何数据，此时要追赶系统当前的进度是比较困难的，因为在加入节点的时候，客户端还在不断写入数据。另外，如果新加入的节点不能马上追赶上系统的进度，还有可能影响系统的可用性。

• 主节点上生成一份当前最新的快照数据，将这份快照数据同步到新增的从节点上；
• 在快照数据同步完成之后，主节点继续将在生成快照数据之后的新增数据日志发送给从节点；
• 完成前面两步之后，继续将此后客户段写入的数据同步给从节点，一直到新增的从节点追赶上最新的主节点数据进度为止。

如果副本上的数据，距离当前系统的最新数据很接近，可以直接通过同步增量事件数据的方式更新副本上的数据。

如图[fig:replication/rep-primary-5]所示同步副本数据的大体流程。如果在同步了快照数据之后，发现和当前系统的最新数据又有较大的差距，就需要再次进行快照数据的同步，直到较为接近的时候才转为同步事件数据。

图: 同步副本数据的流程。如果在同步了快照数据之后，发现和当前系统的最新数据又有较大的差距，就需要再次进行快照数据的同步，直到较为接近的时候才转为同步事件数据。

以上回答了复制数据时采用快照数据还是事件数据。在复制事件数据时，由于事件数据是动态变更系统状态的数据，还需要考虑另一个因素：确定性（Deterministic）。在[sec:snapshot]中提到，分布式系统中，保持同样的事件在不同的副本之间有相同的执行顺序是至关重要的，相同的事件执行顺序才能保证系统的确定性。但是，系统的确定性要求，却不止事件的执行顺序要求。严格来说，一个系统的确定性要求它对事件的处理不依赖于时间（isn’t timing dependent）[@I Heart Logs]，换言之：要求同一个事件在任何时间执行，都能得到相同的结果。

图: 分布式系统的确定性要满足的两个条件：不同副本的事件序列以同样的顺序排列；每个事件的执行结果不依赖于时间。

如图[fig:replication/rep-primary-4]所示，虽然以相同的顺序执行同样的事件序列，但是由于其中的z=random()操作，在不同时间执行会得到不同的结果，导致了系统的不确定性。

图: 同样顺序的事件序列中的某个操作，由于其中有涉及随机数计算的事件，因此每次执行会得到不同的结果，导致了系统的不确定性。

总结下来，系统的确定性，既要求事件按照同样的顺序来执行，也要求每个事件的执行结果不依赖于时间。

按照这个标准，我们来看事件中的数据内容。对于一般的KV类型的存储（例如Redis、Memcache）而言相对简单，事件的内容就是对具体的键进行修改的操作。但是对于关系型数据库产品，则要特别注意。

在基于语句的复制（Statement-based replication），关系型数据库将把每个涉及到数据库变更的SQL语句（例如Insert、Update或者Delete语句）发送到副本上执行。它的优点是不需要记录每一行的变更数据，减少了数据量，性能较高。但它的问题在于存在不确定性，如果SQL语句中包括非确定性语句，例如获取随机数、调用NOW()函数获取当前的数据、UUID()生成随机的UUID值等操作，就会导致不同副本出现不一致的数据。

除此以外，还有基于行的复制（row-based replication），它不记录执行的SQL语句，仅需要记录某一行数据被修改成了什么数据。它的缺点在于数据量较大，例如一条update语句，如果修改了多条记录，那么每一行记录的修改都被被记录下来。

Mysql既支持基于语句的复制方式，也支持基于行的复制，同时还支持两者的混合模式。对于一般无副作用的语句，采用基于语句的复制方式，否则就采用基于行的复制。

节点失效 #

在分布式系统中，节点失效是常见的情况，导致节点失效可能有节点本身的原因，例如物理上的磁盘、内存爆满，或者代码逻辑上的问题导致异常退出，又或者由于外部网络等原因导致节点无法被访问。

无论哪种原因，当节点失效时，在系统层面表现出来的，就是发往节点的请求失败，或者不再收到节点发来的消息。

在单机系统中，操作系统可以准确判断一个进程是否结束。但在分布式系统中，在异步网络中准确区分“节点宕机”和“网络延迟”在理论上是不可能的。因此，在工程实践中，不做“绝对准确”的检测，而是做“基于超时猜测”的检测，并在准确性（Accuracy）和及时性（Completeness）之间做权衡。下面我们来详细解释检测节点失效的相关机制。

*心跳（Heartbeat）*是最常用、最直观的故障检测方法。通常有两种模式：

• *主动推送（push）*模式：被检测节点每隔固定时间向检测者发送心跳消息，如果检测者在连续几个心跳周期都没有收到被检测者的心跳消息，则判断被检测节点失效。这种模式被大部分分布式系统采用。
• *被动拉取（pull）*模式：与主动推送模式相反，被动拉取模式中由检测节点主动发起心跳消息，要求被检测节点应答，这种模式通常只适用于节点数量较少的场景。

然而，心跳机制里有不少可以待讨论的地方。例如，设置心跳超时时间为多长，几次没有收到心跳消息就认为节点失效？有可能出现这样一种情况：网络突然发生了抖动，或者节点在运行时阻塞在一些耗时的操作里（磁盘IO、GC等），导致了发送心跳消息被延迟，从而被错误地判定为失效。而在判断节点失效之后，节点又恢复了运行，无疑将对系统的可用性造成困扰。

心跳机制有一个致命问题：“双向认知不一致”。检测者由于网络等问题认为被检测者宕机，开始选举新的主节点进行故障转移（选新主）。但被检测者实际上还活着，并认为自己还是主节点，继续写入数据。这就导致了脑裂（Split-brain）。如图[fig:replication/rep-brain-split]所示，由于网络原因，节点A无法发消息到节点B，导致节点B认为节点A下线，选出了自己做为新的主节点，另一方面节点A认为自己仍然还在以主节点继续工作，这样系统中就同时出现了两个主节点。

图: 分布式系统中的脑裂问题。由于网络原因，节点A无法发消息到节点B，导致节点B认为节点A下线，选出了自己做为新的主节点，另一方面节点A认为自己仍然还在以主节点继续工作，这样系统中就同时出现了两个主节点。

分布式系统中采用*租约（Lease）*机制来解决这类问题。所谓“租约”，就是检测节点向被检测节点发放的一个带有时间期限的许可证。被检测节点必须承诺在租约到期之前，向检测节点发送消息进行续约，否则在租约到期之后，检测节点将认为被检测节点已经下线。区别于心跳机制，要求两个节点互相发送消息，租约机制只要求被检测节点主动续约，这避免了检测节点的消息由于网络等原因到达不了被检测节点而产生的脑裂问题。我们将在[ss:raft-liveness]中看到，Raft协议中采用租约来解决节点的活性检测和脑裂问题。

以上无论是心跳还是租约机制，解决的都是单个节点对另一个节点的活性判断，但是一个分布式系统是由一组节点组成的，在复制数据时，需要在多节点中复制同样的数据，否则可能从不同的节点读到不同的数据。判断节点下线也是类似的：不应该由单一节点检测失败，就判断某个节点下线，“判断节点下线”和“复制数据”一样，需要在超半数节点上达成一致才可以。仍然以[fig:replication/rep-brain-split]图为例，节点B由于收不到节点A的消息，判定节点A下线，而节点C和节点A的通信是正常的，此时节点B和节点C对节点A的判断没有达成一致，这样就不会判定节点A下线重新选举新节点了。分布式系统的新任主节点选举，也是类似的流程：只有当超过半数节点都投票给了新节点，才能认为成功当选。我们将在[subsec:raft-leader]中讨论Raft的选举机制，Redis中采用主观下线和客观下线的机制，来判断节点下线，同样也需要超过半数的节点达成一致才行 (https://redis.io/docs/latest/operate/oss\_and\_stack/management/sentinel/)。

除了检测节点失效的机制以外，在节点失效以后，主、从节点还有不同的处理策略。

从节点失效

主节点探测到从节点失效后，后续将不再将客户端的写入请求转发到从节点上。当从节点从故障中恢复，追赶当前系统进度的步骤，与前面新增从节点的步骤类似，只不过在恢复时不再从头开始同步数据。

主节点失效

相比较而言，在主从复制中，主节点失效的情况要更复杂一些，这是因为前面提到的，主、从节点的地位并不相同，主节点要负责接收所有客户端的写请求。所以当主节点失效时，需要重新选出一个新的主节点，这个过程称为切换（failover）。

• 新的主节点，一般由选举产生。新选出来的主节点，最好可以与原主节点之间的数据差异最小，这样可以丢失尽量少的数据。
• 如果系统中的节点，由于网络分区的原因，位于两个不同的网络分区中，则可能会出现“脑裂现象”。在这种情况中，位于两个网络分区的节点，可能都会认为自己是当前系统中的主节点，从而处理客户端的写入请求，而一旦系统恢复成一个网络分区时，这些在不同主节点上写入的数据将无法进行合并。脑裂现象，导致了在一个只允许同时存在一个主节点的系统中有多个主节点，属于系统安全性问题[[sec:property]]，是需要避免的。

需要特别强调的是，在本小节中我们提到采用心跳和租约机制来检测节点失效，但是对于主节点失效的情况，仅有这些还不能完全避免脑裂问题。如图[fig:replication/rep-fence]，采用租约机制来判断主节点的活性。节点1是集群的主节点，收到客户端写入x=2的请求后，此时租约没有过期仍然有效，但是由于在节点1上发生了Full GC，导致节点1的主节点任期超时。在这个期间，节点3被选为新的主节点，在这之后收到来自客户端写入x=3的请求并且写入成功。当节点1从GC中恢复回来，误认为自己仍然还是主节点，用过期的写入数据x=2覆盖了新的值。这本质上就是一个“脑裂”问题。

图: 主节点1由于GC导致租约到期，此时新任主节点变成了节点3，成功写入x=3的数据，当节点1从GC中恢复后，误认为自己仍然还是主节点，用已经过期的数据x=2覆盖了最新的值。

为了解决这个问题：系统需要一个机制，判断当前哪个节点才是最新的主节点。一个直观的想法是：引入单调递增的版本号，给每个主节点做为标记，这就能区分谁才是当前更新的主节点，这种方式称为栅栏令牌（Fencing Token），每次选举成功的新任主节点，都对应获得一个单调递增的token。

根据这一思路，改造前面的问题，如图[fig:replication/rep-fence-1]所示。节点2收到token=2的数据x=2时，由于前面已经写入了token=3的x=3的数据，因此当前新任主节点的token是3，于是拒绝写入token=2的过期数据。

图: 节点2收到token=2的数据x=2时，由于前面已经写入了token=3的x=3的数据，因此当前新任主节点的token是3，于是拒绝写入token=2的过期数据。

我们在后面将在[sec:property]中看到关于安全性和活性的定义，根据这两个属性的定义，回看租约和令牌，它们分别解决不同的问题：

• 租约的作用：是为了系统的活性。它保证了如果主节点真的死机了，系统不会永久卡死，过一段时间能选出新 主节点继续工作。
• 令牌的作用：是为了系统的安全性。它保证了在“脑裂”或“假死”的情况下，系统只能有一个合法的写入者，防止旧主节点破坏数据。

租约和令牌必须配合工作，才能达到保证系统安全性和活性的作用。

这里的令牌号，需要满足单调递增特性，本质上这是一个满足“全序性”[[sec:total order]]要求的符号。我们将在共识算法章节介绍Raft的实现时看到，在选举主节点时，Raft的任期号（Term）也是一种令牌号。

一致性模型 #

数据复制在带来可扩展性和可靠性的同时，也引入了一个核心挑战：如何在多个副本间维护数据语义的一致性。这正是我们需要系统学习“一致性模型”的原因。

理想情况下，应该只有一种一致性模型：数据更新后，所有的观察者立即可以看到更新后的数据。如果能有这样的保证，那么一个分布式系统就实现了分布式透明性（distribution transparency）：对于访问该分布式系统的用户而言，无论访问系统中的哪个副本，都能读到一样的数据，这个分布式系统看起来就像是只有一个系统，而不是由多个副本组成的系统。在20世纪70年代，许多分布式系统设计时，都将保证透明性放在系统的可用性之前[@Bruce Lindsay]。

然而，到了20世纪90年代，随着大型互联网的兴起，这些做法重新受到审视，人们开始认为可用性才是系统中最重要的属性。在 2000年分布式计算原理的主题演讲中，Eric Brewer教授综合阐述了分布式系统设计中不同的权衡取舍原则，并在此基础上提出了CAP定理[[section:cap]]。该定理指出，在分布式系统中，以下的三个属性：数据一致性、系统可用性和网络分区容忍度，在任何给定时间只能实现两个。

在大规模的分布式系统中，以上三个属性中的网络分区是系统必须面对的问题，根据CAP定理，在必须考虑网络分区的情况下，就必须在数据的一致性和可用性之间做出抉择，因此一致性和可用性无法同时实现。这意味着在系统设计时有两种不同的选择：把一致性做为系统设计时的优先级，就要接受系统在某些时刻不可用；另一方面，如果降低系统的一致性要求，将使系统在网络分区发生时继续保持高可用。

无论以上的哪种选择，都要求开发人员了解系统需要满足的一致性条件。在CAP定理中提到的数据一致性，指的是线性一致性，这是最强的一致性要求。但是我们将看到，现实的场景中，有其它可选择的，但是强度更弱一些的一致性，也能满足系统的要求。现实上存在着不同的一致性类型，我们称之为“一致性模型（consistency models）”。本节中将介绍最常见的一致性模型，在此之前我们通过一个问题的讨论来了解什么是一致性模型。

这是本书中第一次讨论“一致性”问题，在后续的章节里，还会陆续看到和一致性相关话题的讨论：

• CAP定理中的C指的是“Consistency”，是下面即将讨论到的线性一致性。
• ACID中的C虽然也是指的“Consistency”，但这是更偏数据库应用层面的概念。
• 很多人会把*“共识算法”称为“一致性算法”*，其实这是不准确的，我们将在第[chapter:consensus]章节中展开讨论。

什么是一致性模型 #

在前面讲解事件先后顺序时，我们曾经提出了一个问题，如图[fig:consistency-model-1]所示：

图: 用户E和用户F看到了违反先后关系的事件排序

设想在图中，这些节点都是社交媒体上的账号，用户C、D、E关注了用户A和用户B，节点的事件就是这些用户在社交媒体上的发言，这些被关注者的发言，最终会合并到关注者的时间线上，形成一个合理的排序。

为了解答观察者上看到被关注者的事件如何合理排序问题，首先来看在用户A和用户B的四个事件中，按照Happen Before关系[[sec:happen-before]]，满足：

• a、c、d是同一个用户A上顺序发生的事件，因此有 $a < c$和$c < d$。
• 先有用户B的发送事件b，才有用户A的接收事件c，因此事件b和c有因果关系，即有$b < c$。
• 最后，根据事件之间的Happen Before关系满足传递性，有：
• $b < c \ and \ c < d \Rightarrow b < d$。
• $a < c \ and \ c < d \Rightarrow a < d$。

$$ \begin{aligned} & a < c \ \text{，同一用户A上的顺序发生事件} & c < d \ \text{，同一用户A上的顺序发生事件} & b < c \ \text{，满足因果关系的事件} & b < d \ \text{，满足传递性的事件} & a < d \ \text{，满足传递性的事件} \end{aligned} $$

从观察者的角度，对以上四个事件进行排序，一共有$4!(=4 \times 3 \times 2 \times 1)$种可能，但是无论如何排序，都不能违反以上的五个Happen Before关系。

根据以上的结论，就能知道几个观察者的事件排序是否正确了。用户E上看到的事件排序是不正确的，因为在图中，事件c先于事件d发生，而在用户E的事件排序中将事件d至于事件c之后，同理用户F上看到的事件排序也违反了先后顺序。而用户C和用户D上的事件排序，区别仅在于两个并发事件a和事件b如何排序，在某些情况下都是合理的排序。

从这个例子可以看出，在分布式系统中，如何针对多个节点的事件有一个合理的排序，是一个重要的问题。这些事件的排序，除了要合理（例如不能明确违反Happen Before关系）之外，还与系统实现的难度息息相关。

其次，分布式系统给应用开发者带来了例如容错性、可扩展性等便利，实现这些便利的策略就是复制和分片。我们希望同一份数据在不同的节点之间总是能够保持一致，但是复制给系统带来的一个挑战就是一致性问题，系统在复制数据到多个节点时，总会存在时间延迟，这样就会存在数据不一致的风险。

要求一个分布式系统在任意时刻都保证多数据副本上的数据总是一致的，要付出极大的代价。幸运的是，也并不要求所有时刻系统的所有节点数据都保持一致，只要系统能够保证在客户端去读取数据的时刻一致就可以了。

维基百科中对一致性模型（consistency model） (https://en.wikipedia.org/wiki/Consistency\_model)的定义如下：

In computer science, a consistency model specifies a contract between the programmer and a system, wherein the system guarantees that if the programmer follows the rules for operations on memory, memory will be consistent and the results of reading, writing, or updating memory will be predictable. （在计算机科学中，一致性模型规定了程序员与系统之间的契约，其中系统保证，如果程序员遵循内存操作规则，内存将保持一致，读取、写入或更新内存的结果将是可预测的。）

在进行系统设计时，知道所运行的分布式系统提供怎样的一致性保证，对应用开发者而言尤其重要。不同强度的一致性保证，带来的实现难度和并发性不尽相同，应用程序根据应用场景来决定要求的数据一致性强度，例如：

• 某些社交媒体的消息排序，只需要保证因果一致性即可；
• 对某些至关重要不允许出错的数据（例如银行存款、系统中的主节点等），则要求线性一致性。

以下以朋友圈这个产品的设计为例，解释在系统设计时要考虑的一致性模型问题。

图: 以朋友圈为例来理解一致性模型问题

不妨把朋友圈这个产品看成一个大型的的分布式系统：

• 这个分布式系统，对外提供了写入（发朋友圈）和读取（ 读朋友圈）的功能。
• 朋友圈这个分布式系统，有两种客户端：发朋友圈的客户端负责写入数据，读朋友圈的客户端负责读取数据，当然很多时候同一个客户端既能读也能写。
• 存储这些朋友圈数据的，不止一台机器，这些机器在一起构成了这个大型的分布式系统。不同的用户，发朋友圈的时候，也不一定都写入相同的一台机器。反之也是，在读朋友圈时也不一定会到同一台机器上读取数据。

接下来的问题是：那些看朋友圈的人，是否能看到全局一致的数据？即所有人看到的朋友圈都是同一个顺序排列的？

有很多时候，即便是在看同一个朋友圈下的评论回复，不同的人看到也不尽然都是同一个顺序的，所以以上的答案是否定的。那么就引入了下一个问题：如果不同的人看到的朋友圈（包括评论）顺序各有不同，这些顺序又该遵守怎样的规则才是合理的？

回答怎样的顺序规则才是合理的，这就是一致性模型要解答的问题。

以朋友圈这个系统来说，一条朋友圈下面有多个人发表评论，可以认为这是一个二维的数据：

• 进程（也就是发表评论的人）是一个维度。
• 时间又是另一个维度，即这些评论出现的先后顺序。

但是在阅读这些评论的读者看来，需要将这一份二维的数据，去除掉不同进程这个维度，压平到只有本进程时间线这一个单一维度上面来。

图: 单用户视角下的事件排列

在图[fig:consistency-model/wechat-2]中，在读进程用户C​的视角看来，两个写进程的事件，需要压平到本进程的时间线上进行排列，可以看到这些事件在压平之后有多种排列的可能性。

将多个写进程的事件进行排列，放到单进程的时间线上，这是一个排列组合问题，如果所有的写进程事件加起来一共有n个，那么这些事件的所有排列组合就是n!。如果当前系统有事件a、b、c，不同的排列一共有这些：{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}。

一致性模型就是要回答：在所有的这些可能存在的事件排列组合中，按照要求的一致性严格程度，哪些是可以接受的，哪些不可能出现的。

带着这些问题，在本节中，我们依次介绍以下几种常见的一致性模型：

• 顺序一致性；
• 线性一致性；
• 因果一致性；
• 最终一致性。

虽然在这里，将最终一致性和其他几类一致性模型放在一起，但是我们后面将会看到，最终一致性和这几类一致性模型不属于同一个概念。

一致性模型图例 #

在开始展开一致性模型的介绍之前，有必要首先交待一下一致性模型图例中的各种元素。

除了不同节点上可能存在并发的事件以外，事件在执行时还可能出现时间重叠的情况。 在过去的图示中，我们把事件在时间轴上使用一个点来表示，这造成了一个幻觉：事件的执行都是瞬间完成的。实际上，因为涉及到内存的读写、CPU的计算、磁盘IO读写等因素，每个事件的执行都不是瞬间完成的。当把事件的执行时间考虑在内时，多个事件在执行时就可能发生重叠。

为了明确起见，本章中的图示，将不再把事件看做图上时间轴的一个点，而是有两个边界：

• 事件的发起时间（invocation time）；
• 事件的完成时间（completion time）。

表现在图示中，事件使用一个矩形来表示，矩形左边界就是事件的发起时间，右边界则是事件的完成时间，矩形的宽度就是事件的执行时长，如图[fig:consistency-model-3]所示。

图: 使用矩形表示事件的完整执行流程

在图中，有以下几类操作：

• $w(x,a)$：表示向变量x写入数据a；
• $r(x) \Rightarrow a$：表示读变量x的结果为a。

同时，如果事件的矩形有重叠，表示两个事件的执行时间有重叠，认为在时间上是并发事件；反之，如果没有重叠，表示事件在执行时间上没有重叠。

顺序一致性 #

首先介绍顺序一致性（Sequential Consistency），最早由Lamport在论文[@sequential-consistency]中提出：

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.（任何执行的结果都与所有处理器的操作按某种顺序执行的情况相同，每个单独的处理器的操作按其程序指定的顺序出现在这个序列中。）

以上关于顺序一致性的定义可以总结为：所有操作看起来按单一全局顺序执行，且每个参与者的局部操作顺序得到保留。它要求满足以下几个条件：

• 事件不能发生回退。
• 同一个节点内的事件，在重排后依然保持同样的顺序。
• 满足以上两点的事件重排顺序，在所有的节点中都一样，即重排后的事件顺序在系统的所有节点中保持一致。

以下对这三个条件逐个做出解释。

首先看事件不能发生回退，这一点要求：如果一个新值被写入或者读取，所有后续的事件不能看到比它更旧的数据。我们来看一个例子。

图: 事件回退的例子，情况1中后续的读事件读到了更旧的值，事件发生了回退；情况2和3中，后续的读事件没有读到更旧的值，没有发生事件回退。

在图[fig:consistency-model-4]的三个场景中，节点A同样进行了3次写操作，按照顺序依次向变量x写入数据1、2、3，而节点B进行了2次读操作，不能发生回退指的是节点B在读取时，在一次读操作中不能读到比前面读操作更旧的值，例如如果读到了x的值为2，那么后面的读操作就不能读到x的值为1，因为根据节点A的写操作顺序，写操作x=1在x=2之前。

• 情况1中，节点B在第一次读取了x=2之后，第二次读取到x=1，这是相较于x=2更旧的值，在这里事件发生了回退；
• 情况2中，第二次读取x=1，并不比第一次x=1更旧，这是可以接受的；
• 同样的，情况3中，第二次读取到x=3，也比第一次读取的x=1更新，也没有违反事件不能回退的规则。

再来看违反同一节点上事件顺序的例子，如图[fig:consistency-model-1]中，节点A上的事件发生的顺序为a、c、d，但是在节点E处进行事件重排时，将事件d放在了事件c前面，这就违反了这两个事件在节点A上的顺序。

最后，可能有多个满足前两个条件的事件排序（例如图[fig:consistency-model-1]中C和D都是符合条件的排序），但是只要选定了其中一个，其它节点上也必须是这个排序，重排后的顺序要求在所有节点都一致。

我们试着来直观理解一下顺序一致性的这些要求。在理想情况下，分布式系统应该*“表现得像一个副本一样”*。这里面其实暗含了两个要求：

• 系统只有一种顺序，否则“一个副本”就无从谈起；
• 除了系统中只有一种顺序以外，顺序还需要是合理的，所以才要求需要满足节点中的事件顺序，以及事件不能发生回退现象。

需要说明一下，虽然顺序一致性的几个条件中，没有明确提到事件的排序需要满足因果关系，其实这一点是暗含在事件不能回退这一条件中的，即如果看到事件的结果，后续的事件就不能再看到事件的因。如图[fig:consistency-model-1]中，节点B上的事件b是发送事件，节点A上的事件c是对应的接收事件，重排后的顺序必须保证把事件b放在事件c之前，否则也是不满足事件不能回退这一条件的。

有了以上对顺序一致性基本的了解，我们多看几个例子：

• 如图[fig:consistency-model-sequential-1]所示，节点C和节点D的顺序都是合理的且保持一致，依次读到了节点A上的两次写操作结果，并没有发生事件回退；此外，对于x=2和x=3的两个并发写操作，两个节点也保持了相同的读顺序（先读到x=2再读到x=3），因此符合顺序一致性；

  

图: 顺序一致性例子1

• 如图[fig:consistency-model-sequential-2]所示，与图[fig:consistency-model-sequential-1]相比，节点C和节点D的顺序变成了$(r(x) \Rightarrow 3,r(x) \Rightarrow 1,r(x) \Rightarrow 2)$，这看上去有一点反直觉，毕竟在图中节点A上的$w(x,1)$操作先于节点B上的$w(x,3)$操作完成，但是节点C和节点D上读到的数据却不是这个顺序。但是仔细一想，这个排序也并没有违反顺序一致性的要求，因为这个读顺序既保持了节点上的事件顺序，也全局一致；

  

图: 顺序一致性例子2

• 如图[fig:consistency-model-sequential-3]所示，节点C和节点D的顺序不一致，因此不是顺序一致性。

  

图: 没有保证全局一致，违反顺序一致性条件

上面这些例子中，最反直觉和难以理解的是图[fig:consistency-model-sequential-2]，但是这个例子却揭示了顺序一致性的一个特性：顺序一致性对事件发生的实时性并没有要求。这就会出现某些在全局时钟下排序的事件，在顺序一致性下却顺序颠倒了，如图中的$w(x,1)$先于$w(x,3)$完成，但是顺序一致性可以先读出x=3的值。

如果系统设计需要对数据的一致性保证有实时性的要求，那么应该选择以下要介绍的线性一致性。

在很多场景里，系统只要求保证顺序，对实时性要求并不高，这类场景就适合选用顺序一致性来实现。例如：

• 一个账号在社交平台发布了两条推文，在不同关注者账号上同步推文可能有延迟，有的关注者账号只看到了第一条推文，有的账号可能已经两条推文都看到了，但是只要保证看到的推文不是乱序的，按照发布者账号发布的顺序显示在时间线即可；
• 一些实时性要求不高的游戏（例如棋牌类游戏），玩家的操作需要按照顺序同步到客户端，避免状态不一致；

线性一致性 #

接着来看线性一致性（Linearizability）[@Linearizability]，有时也被称为原子一致性（atomic consistency）[@atomic-consistency]、强一致性（strong consistency），它是目前常见的一致性实现中最强的一致性模型。

线性一致性在顺序一致性的基础上，增加了一个条件：

不同节点上的事件，如果不是并发事件（在时间轴上不是重叠的矩形），那么执行的先后顺序，也必须在重排之后保持一致。

即，如果两个事件a和b的时间满足$t(a) < t(b)$，要求事件b必须看到事件a的操作结果。

顺序一致性的顺序要求满足程序顺序，而线性一致性的顺序要求满足实时性，实时性要求是强于程序顺序的。例如，同一个节点上顺序执行的事件，事件的时间肯定也有先后；有因果关系的事件，其事件时间也有先后。

这一点是线性一致性对比顺序一致性更强的数据实时性要求。有了实时性的保证之后，提供线性一致性的系统就能够提供只有一个副本的假象。

由于线性一致性比顺序一致性多一个条件，因此满足线性一致性的系统，自然就满足顺序一致性；反之则不然。

来看一个满足顺序一致性，却不满足线性一致性的例子：

图: 满足顺序一致性，却不满足线性一致性

在图[fig:consistency-model-5]中，节点C依次读出来1、3、2三个值，要满足这个顺序，图中的事件排序只能是：$(w(x,1),r(x) \Rightarrow 1, w(x,3), r(x) \Rightarrow 3, w(x,2), r(x) \Rightarrow 2)$。

可以看到，这个排序是满足顺序一致性要求的：

• 节点A和节点B上都发生了多个事件，重排后的事件排序都保持了这两个节点上的事件顺序；
• 也没有发生事件回退，三次读操作都没有读到更旧的值。

然而，这个排序却不满足线性一致性要求：节点B的$w(x,3)$事件发生在节点C的事件$r(x) \Rightarrow 1$之前且并不重叠，但是排序中却将$r(x) \Rightarrow 1$放在了事件$w(x,3)$之前。

来看一个满足线性一致性的例子，如图[fig:consistency-model-linearizability-1]所示，节点C的事件顺序为$(r(x) \Rightarrow 1, r(x) \Rightarrow 3, r(x) \Rightarrow 2)$，为了讲述方便起见，这些事件下面分别标注了事件名称：

• 这个顺序满足节点A上的事件排序：先读到了数据1，再读到数据2；
• 事件C1发生在事件A2之后，与事件A3和B1重叠，所以事件C1读到这三个写事件中的任意一个值，都是合理的，但是事件C1如果读到A1事件的结果x=0，就违反了线性一致性；
• 同理，事件C2与事件B1和事件A3重叠，它读到1、3或者2都是合理的；
• 事件C3发生在最后一个写事件A3之后，所以C3必须读到A3写入的x=3。

图: 满足线性一致性的例子

顺序一致性和线性一致性，都试图提供“一个副本”的假象，但是顺序一致性的副本没有实时性要求，对于某些对数据有实时性要求的场景，只能使用线性一致性，如图[fig:consistency-model-6]所示，我们将在第[chapter:consensus]章中看到分布式共识算法如何实现线性一致性：

• 两个客户端首先请求两个节点，查询当前的剩余票数，都返回1；
• 客户端A向节点1发起购票请求，节点1上将剩余票数减一，这一操作也复制到了节点2上；
• 在复制请求到达节点2之前，客户端B也发起了购票请求，由于此时节点2剩余票数是1，因此购票成功，车票发生了超售现象。

图: 对数据实时性要求高的购票场景

\

[fig:consistency-model-6]图中的这类场景，即使系统满足线性一致性，由于这客户端B两次读写操作读写事件操作之间有延迟，因此对这类先读取再根据读取的值进行修改的操作，更好的办法是使用*CAS（compare and swap）*操作：只有在满足读取时的某些条件时，才进行修改。

因果一致性 #

顺序一致性、线性一致性都属于强一致性，这两种一致性都要求系统中的所有副本只能有一种顺序，这个要求在实现时的代价很高。很多场景里，并不需要这么强的一致性要求。因果一致性就是一种相对较弱的一致性保证，在这种一致性模型中，只要求有因果关系的事件保持顺序即可。

如图[fig:consistency-model-7]所示，A向另外两个人提出问题（消息m1）“今天去哪儿玩”，B回复（消息m2）“去看电影”，如果这两个消息在用户C看来是m2先于m1到达，就违反了因果序。

图: 违反因果一致性的场景

可以使用前面介绍过的向量时钟[vector-clock]来保证因果序，如图[fig:consistency-model-causal-1]所示：

• A发出消息m1时，将带上本地的向量时钟为[1,0,0]；
• B收到消息m1，发出消息m2时，将带上本地的向量时钟为[1,1,0]；
• C先收到消息m2后，发现其向量时钟为[1,1,0]，将推迟交付该消息，直到收到消息m1之后才交付。

图: 使用向量时钟保证因果序

这种使用向量时钟实现的因果序，一大问题就是向量时钟的大小和节点数量相关，很多时候会造成同步的数据量多，另外还有一个弊端是：在某些场景里，无法知道参与通信的节点有多少，也就无法判断向量时钟的数组大小。以图[fig:consistency-model-7]中的场景为例，在这三个用户对话的过程中，还可能会加入新的用户来，这样一开始定义的只有三个向量的数组就不够用了。

针对这些情况，可以对这类只需要保证因果序的场景这样定制逻辑时钟（逻辑时钟的定义见[logic-clock]）：

• 每个用户维护一个递增的数字ID，每次对外发出消息时递增；
• 对外发出消息时，需要带上本节点的ID以及消息ID，如果消息是针对另一个消息的回复，需要带上父消息的消息ID。

有了消息ID之后，消息投递流程修改为：

• 如果消息没有父消息ID，说明不是针对另一个消息的回复，可以直接交付消息；
• 否则，只有在父消息已经交付的情况下，才能交付消息。

这里的一个问题是：如何判断父消息已经被交付呢？以下提供一种思路：

• 每个节点内，维护一个以节点ID为键的最大数字ID，保存目前看到的来自另一个节点的最大ID；
• 当收到的父消息ID不为空时，从父消息ID中取出节点ID和消息ID：
• 如果当前存在该节点的最大数字ID，取当前保存的最大数字ID，如果大于该消息的ID，认为已经交付了，否则就是没有交付，父消息还没有被交付的消息，需要暂存在消息队列中等待交付；
• 否则，之前没有保存过该节点的最大数字ID，这种情况肯定是没有交付过父消息。
• 当收到消息时，如果不存在父消息ID，从消息中取出节点ID和消息ID，更新节点ID对应的最大数字ID；到消息队列中根据节点ID和消息ID，判断是否有消息等待该消息完成交付，如果有就从消息队列中删除消息完成交付。

按照以上的思路，我们重新实现一下前面的问题，如图[fig:consistency-model-causal-2]所示，图中的id表示消息id，p-id表示父消息id，不存在父消息id的时候p-id为None，消息id由(节点id,消息id)二元组构成：

• A发出消息m1时，带上的id信息是(id:(A,1),p-id:None)，表示从节点A发出的消息，消息ID是1，而不存在对应的父消息，即不是另一条消息的评论；
• B回复消息m2时，带上的id信息是(id:(B,1),p-id:(A,1))，表示从节点B发出的消息，消息ID是1，同时该消息的父消息ID是(A,1)，也就是针对用户A的消息ID为1的消息的评论；
• C收到消息m2时，取出父消息ID信息，判断父消息还没有完成交付，于是暂存在消息队列中；
• C收到消息m1时，取出消息ID信息，因为这条消息没有父消息ID，可以直接完成交付，交付完毕之后，查看消息队列中还有一条等待交付的子消息，从消息队列中删除消息m2，完成对消息m2的交付。

图: 使用父消息ID保证因果序

以上使用向量时钟以及父消息ID来实现因果一致性的方式，都只是其中一种实现思路，本质上只要采用的逻辑时钟能满足时钟条件（见[Clock-Condition]）就能实现因果一致，开发者根据不同的业务场景设计出满足时钟条件的逻辑时钟来实现因果一致性。

只需要满足因果一致性的系统，还有一个特点：在满足因果序的前提下，可以允许消息乱序，而且不要求消息在所有节点上全局一致。如图[fig:consistency-model-causal-3]中，节点B在发出消息m2之后，又发出了消息m3。虽然节点C先收到了消息m2，但是由于消息m2要等待m1先完成交付，而消息m3没有父消息可以直接交付，节点C上的消息交付顺序是(m3,m1,m2)；而节点D上的消息交付顺序是(m1,m2,m3)。

可以看到，消息在这里允许乱序，例如在节点C上，消息m3在同一节点发出的消息m2之前交付；同时，节点C和节点D的消息顺序也不一致，不要求所有节点有全局一致的消息顺序。

图: 每个节点上的消息顺序，只要满足m1在m2之前就能保证消息的因果序，在这个前提下允许消息乱序和非全局一致

因果一致性的这一特点，无疑给实现带来了很大的便利，很多一致性要求不高的场景，都可以采用因果一致性。

我们重新审视在本节开头用于介绍一致性模型时提出的朋友圈评论系统的设计。对于这个系统而言，只需要保持因果一致性即可。在图[fig:consistency-model/casual-model.png]左边列出了几种朋友圈评论的人可能看到的评论顺序排列，其中上面的两种虽然不尽相同，但都是符合因果一致性要求的，因为：

• 依然保持了同一个用户A发出的三条评论的顺序。
• 依然保持了用户之间的相互评论（即有因果关系的评论）的顺序。

但是下面两个排列的顺序就不符合要求了，其中一个违反了因果关系，把回复他人的评论放在了评论前面；另一个是违反了同一个用户A发出的三条评论的顺序。

图: 朋友圈的评论，只需要满足因果一致性即可

最终一致性 #

最后来讨论最终一致性（Eventual Consistency），它最早在由Douglas B. Terry在[@Eventually Consistent first]中提出， 后经由Werner Vogels普及[@Eventually Consistent1,Eventually Consistent2]。虽然最终一致性经常和前面几种一致性模型放在一起讨论，但是严格来说却不是一个范畴的概念。要理解这一点，首先要了解以下两个概念：安全性和活性 (https://en.wikipedia.org/wiki/Safety\_and\_liveness\_properties)。

安全性和活性 #

安全性和活性的定义最早出自论文[@Defining Liveness]：

• 安全性（safety property）：表示违反规则的事情永远不会发生（Nothing bad will never happen）；
• 活性（liveness property）：表示好事最终会发生（Something good eventually happen）。

安全性用于定义一个系统绝对不能违反的属性，例如：“数据永不会丢失”、“银行余额永不能为负数”、“系统中不能在同一时间出现超过一个Leader节点”等，都在描述系统需要满足的安全性质。对应地，活性定义了某些最终会被保证的属性，这些属性可能在系统运行的某些时刻没有被满足，但是不会被永久违反，终有满足这些属性的时刻。例如，“请求最终会被处理”、“过期的数据最终会被清理”、“多个数据副本最终会有一致的数据”，都在描述系统需要满足的活性。

这里还需要强调的是：

• 安全性中描述的性质，属于系统绝对不能违反的性质（所谓的“bad thing”），而且是在系统运行的过程中任意一个时刻都不能违反（所谓的“never happen”）。
• 活性中描述的性质，属于系统中的“好事”（所谓的“good thing”），但是并不要求系统任意时刻都能满足，只要在事件不再发生变更的某一时刻满足就可以了（所谓的“eventually happen”）。

最终一致性 #

最终一致性的核心承诺是：如果不再有新的更新操作，所有副本最终会收敛到相同的状态。

最终一致性的这个描述完全符合活性的特征：

• 不禁止中间状态的不一致：允许暂时的“坏事”，例如读到脏数据；
• 保证最终会达成一致：“好事”终会发生；
• 无法通过单次观察来判断是否违反：不像安全性那样，要求系统运行的任意时刻都不能违反安全性。

将最终一致性与前面介绍的强一致性模型作对比：

• 强一致性：强一致性要求每次读取都必须是最新的值，违反这一条件即出错，所以这是安全性要求。
• 因果一致性：因果一致性要求互为因果关系的事件，在任意时刻的系统事件排列中都要得到满足，这同样是一个安全性要求。
• 最终一致性：只要求未来某个时刻会一致，不约束中间过程，因此这是活性要求。

由此可见，最终一致性和前面讨论的另外几种一致性模型有本质的区别，它们讨论的不是一个范畴的问题。它的核心属性是收敛性（convergence），表示系统中的所有副本最终都会收敛到同样的值。

最终一致性的活性要求，给系统设计带来了以下的优点和挑战：

• 由于不再要求系统在任意时刻都满足某些安全性要求，因此在系统发生分区、网络延迟等问题时，允许出现系统中副本数据不一致的情况，这无疑给系统设计者更大的弹性。例如，开发者可以采用异步数据复制的方式在多副本中同步数据；在发生网络分区问题时，选择降低系统的一致性要求，优先保证系统的可用性。
• 与此同时，对系统使用者而言，也要针对会出现不一致数据的可能，做好数据*补偿（compensation）*措施，这就把处理不一致数据的复杂度交给了使用者。

典型的最终一致性的应用场景有：

• DNS系统：当一个域名更新其IP地址时，全球的DNS服务器不会立即同步，但经过一段时间（通常几分钟到几小时），所有服务器都会反映最新的IP地址。
• 社交媒体的发言：用户在社交媒体上发布动态之后，该用户的部分关注者不会马上刷到这条动态，但过了一段时间之后，也会看到最新的内容。

图[fig:consistency-model/consistency-model-8.png]总结了本节讲解的几种一致性模型，在图中严格区分了安全性保证的几种模型和活性保证的最终一致性模型，因此全局有序、实时性和因果性这几个安全性保证没有在最终一致性中列出，最终一致性允许中间状态出现不一致的情况。

图: 一致性模型的对比总结。

CAP定理 #

至此，我们已经详细探讨了从最严格的线性一致性，到灵活的最终一致性等一系列一致性模型。大家可以看到，一致性模型就像一把标尺，精确地度量了分布式系统对数据“新鲜度”的承诺。一个自然而然的问题浮现在我们脑海中：既然线性一致性（强一致性）如此符合直觉、能极大简化应用层逻辑，为什么我们不总是选择它呢？为什么像DynamoDB、Cassandra这样的系统反而选择了看似“不靠谱”的最终一致性？

想象一下，为了维护线性一致性，集群中的每个节点都必须像一个纪律严明的军队，任何数据的写入都必须得到“司令部”（或者说，大多数节点）的确认，才能生效。这个过程在网络风平浪静时运转良好。

但如果发生了网络故障——比如两个数据中心之间的海底光缆被鲨鱼咬断了——我们的“军队”被分割成了两个无法通信的孤岛。这时，一个驻扎在孤岛上的“士兵”（节点）收到了一个新的写入命令，它该怎么办？

• 如果它为了保证一致性，坚持要联系上“司令部”，那么在网络恢复之前，它只能拒绝服务，系统就不可用了。
• 如果它为了保证可用性，擅自接受了这个命令，那么它的数据就和另一半“军队”产生了分歧，一致性就被打破了。

从上面的例子可以看到，在“网络分区”这个残酷的现实面前，系统被迫面临一个两难的抉择。这个根本性的、无法回避的权衡，就是由分布式领域最重要的基石之一——CAP 定理所揭示的。

接下来，就让我们深入理解CAP定理，这个支配着所有分布式系统设计的“铁三角”法则。它将完美地解答我们刚才的疑问：为什么不同的系统，会选择走上不同的一致性道路。

CAP定理 (https://en.wikipedia.org/wiki/CAP\_theorem)是由加州大学伯克利分校的Eric Brewer教授于2000年7月提出的一个猜想[@CAP]，2年后由Seth Gilbert和Nancy Lynch从理论上证明了CAP猜想 [@CAP-Proof]，正式成为分布式系统领域的重要定理。

CAP定理指出，对于一个分布式计算系统，不可能同时满足以下三项保证：

• C（一致性，Consistency）
• A（可用性，Availability）
• P（分区容错性，Partition tolerance）

由于这个原因，在系统设计时，必须在这三个保证之间做出选择。要真正理解这个定理，我们必须精确地定义这三个保证的具体含义。

一致性

CAP定理中的一致性是线性一致性[[txt:Linearizability]]，即更新操作成功后，所有节点的数据完全一致，这是一个很强的约束条件，而后面提到BASE定理中的一致性则是最终一致性[[txt:EventualConsistency]]，这是两个定理的最大区别。

线性一致性要求一旦某个写操作成功返回，所有后续的读请求（无论发往哪个节点）都必须能看到这个新数据。系统对外表现得就像一个单机系统，所有操作都在排队依次执行。例如，在社交媒体上改了用户名，点击“保存”后，立即刷新页面，看到的必须是新用户名。如果看到的是旧的，就不满足强一致性。

可用性

可用性要求对于任何发送到非故障节点的请求，系统总能在有限的时间内返回一个非错误的响应。只要集群中还有节点活着，就必须能响应请求，不能拒绝服务，也不能无限期地等待。注意，可用性只保证“有响应”，但不保证响应的数据是最新的。

例如，访问一个电商网站，即使后台有几个服务器宕机了，网站依然能打开，用户依然能浏览商品。可能商品库存不是最新的，但网站是“可用的”。

分区容错性

分区容错性是理解CAP定理的关键和前提，它要求系统即使在节点之间的网络连接出现问题（消息丢失或延迟），导致集群分裂成多个无法相互通信的“网络分区”的情况下，依然能够持续运行。

在分布式系统中，网络是不可靠的。服务器之间的网线可能被拔掉，交换机可能故障。分区容错性意味着我们必须设计一个能够在这种现实情况下依然能工作的系统。只要选择构建分布式系统，就必须假设网络会出问题。不能选择“不要分区容错性”。因此，在现代分布式系统设计中，分区容错性是一个事实，而不是一个选项。

既然分区容错性是系统必须满足的，那么当网络分区真的发生时，系统就面临一个残酷的抉择：选择可用性，还是一致性？

以一个经典的银行转账例子来推演这个过程：

• 一个用户的银行账户数据，为了高可用，同时存储在两个数据中心的节点N1和N2 上。
• 初始余额是1000元。
• 现在，N1和N2之间的网络连接断开了（“网络分区” 发生了），它们无法相互通信。

此时，一个更新请求（取款 100 元）到达了节点 N1。N1 该怎么办？此时有两种选择：

选择一：保证一致性 (C)，牺牲可用性 (A) -> CP 系统

为了保证强一致性，N1必须将这次取款操作同步给N2。但是现在网络断了，N1联系不上N2。如果N1单方面把余额改成 900，那么N1和N2的数据就不一致了，这违反了一致性。为了保证一致性，N1选择了牺牲可用性，拒绝这次取款请求，或者返回一个错误，但对于向N1发起请求的用户来说，系统是不可用的。

这是一个典型的CP系统：宁愿不工作，也绝不返回一个可能错误的数据。

选择二：保证可用性 (A)，牺牲一致性 (C) -> AP 系统

为了优先保证可用性，N1必须响应用户的请求。虽然N1联系不上N2，但是不能让用户取不了钱。此时的做法是接受这次取款请求，将本地的余额从1000改为900。同时，它会把这次操作记录下来，等网络恢复后，再想办法同步给N2。此时系统对用户是可用的。但是，在网络恢复之前，N1的余额是900，而 N2 的余额还是1000，系统处于不一致状态。

这就是一个典型的AP系统：会尽力服务，但用户看到的数据可能不是最新的，稍后会把数据同步好。这种稍后同步的模式，满足的是最终一致性。

以上是关于CAP定理的介绍。考虑到实际应用中，系统都是运行在异步网络上的，异步网络的特点就是网络通信的延时没有上限。所以网络分区这个划分过于非黑即白，更多的时候，系统面对的情况是消息延迟突然发生抖动，例如：节点繁忙导致没有及时应答、系统的网络突然抖动等等。除此以外，权衡是连续的光谱，而非二进制开关，现实系统不是纯粹的CP或AP。很多系统允许你在不同程度上调整一致性级别，例如提供“会话一致性”、“读你所写一致性”等多种折衷模型。

Eric Brewer教授也意识到在最早描述的CAP理论中，没有考虑到延迟的影响，在2012年发表的《CAP Twelve Years Later: How the “Rules” Have Changed》[@CAP-12]中，补充了对延迟的描述：

In its classic interpretation, the CAP theorem ignores latency, although in practice, latency and partitions are deeply related. Operationally, the essence of CAP takes place during a timeout, a period when the program must make a fundamental decision-the partition decision:

• cancel the operation and thus decrease availability.
• proceed with the operation and thus risk inconsistency.

2010年，由耶鲁大学Daniel J. Abadi提出的PACELC[@PACELC-2010]可以看做是在延迟方面对CAP定理的补充：

• 如果发生网络分区，那么系统应该像CAP定理一样，在一致性和可用性之间做出选择；
• 否则，系统设计应该在延迟和一致性之间做出选择。

图: PACELC补充了CAP定理中关于延迟处理的部分

CAP定理的不足和启示

最初的CAP定理存在不少的问题，例如：

• CAP定理没有考虑网络延迟的影响。如果要保持系统的一致性，是需要时间成本在系统的节点之间同步数据的。
• CAP定理中认为三个特性只能三选二，也带有一定的误导性。如果在系统不存在分区的情况下，就没有理由在一致性和可用性之间做出选择。其次，这个表述过于非黑即白，忽视了系统的运行情况是一个光谱，例如可用性指标就是一个动态变化的百分比，一致性也有各种强度的一致性级别，延迟在不同的应用场景里也有不同的时间范围。在这些光谱范围内，开发者可以根据业务的场景来定制所需要的特性参数。

除了前面提到的PACELC[@PACELC-2010]在延迟方面对CAP定理做了扩展，Martin Kleppmann也在[@critique-of-CAP]中谈到了CAP定理的一些不足。

尽管如此，CAP定理的提出目的是为了引导系统设计者在设计时思考一个系统是优先保证一致性，还是应该优先保证可用性：

• AP（放弃一致性）：这意味着当发生网络分区时，允许系统的节点之间的数据不一致；
• CP（放弃可用性）：这意味着当发生网络分区时，系统的节点之间为了保持一致性，同步信息的时间延长，导致影响了系统的可用性。

如图[fig:tx-cap-1]所示，用户向电商平台发起购买请求时，电商平台网关与银行系统位于不同的网络分区。当电商平台向银行系统发起的扣款请求超时时，不能向客户应答购买成功。也就是说，在这个业务场景里，应该优先保证一致性，而不是可用性。宁愿向客户返回请求超时，也不能在未扣款成功之前应答。

图: 电商购物应该优先保证一致性，在扣款不成功的情况下，不应向客户端返回购买成功

如图[fig:tx-cap-2]所示，快递员上门揽件时，在网络环境不好的情况下，与后端的物流平台无法连通，可以认为形成了两个网络分区。在这种情况下，优先保证可用性，揽件的数据可以暂存在设备端，认为揽件成功，在网络恢复时再将数据同步到物流服务。

图: 快递员的设备与物流平台网络形成两个分区，优先保证快递员揽件

以上是在形成网络分区的情况下需要在一致性和可用性之间做出选择的例子，当不存在网络分区情况时，就需要在服务的延迟和一致性之间做出选择。如图[fig:tx-cap-2]所示，用户A在社交平台上发出一则新的消息，该消息需要同步到三个不同的节点上。用户B在社交平台上关注了用户A，但是他的请求发到节点3的时候，用户A的消息还没有同步到这个节点。在这种场景下，允许节点向客户端返回旧的数据，以优先保证服务的可用性。

图: 用户B在社交媒体上关注了用户A，允许该用户读到的不是最新的数据

客户端一致性模型 #

在前面已经介绍了几种最常见的一致性模型，当系统只能满足最终一致性时，客户端可能会读取到过期的旧数据。尽管如此，客户端仍然需要在只提供最终一致性的系统中，满足一些特定的一致性要求来保证客户端的业务。这些由客户端提供的一致性保证，被称为*“客户端一致性模型（client-centric consistency model）”*。本节将介绍常见的几种客户端一致性模型，它们出自论文[@Baseball]，作者以棒球比赛为例来说明这几种客户端一致性模型的使用场景，在本小节最后也会以这个例子来做为总结。

前缀一致性 #

*前缀一致性（Consistent Prefix） *确保客户端读取到的数据是系统中所有写入操作的一个有序、连续的子集（前缀）。换句话说，客户端看到的数据反映了某个时间点之前的所有写操作，且这些操作按照写入顺序呈现，没有乱序或部分更新的情况。读取操作看到的写入顺序是某个逻辑上一致的前缀，即数据版本按照一定顺序演进，不会出现因果错乱，例如“先看到结果，后看到原因”。

如图[fig:consistency-model/Consistent-Prefix.png]，考虑这样的场景，在一个三人的群聊中，用户A提问：“今天去哪里玩”，用户B回答：“去露营”，那么在群里的第三个人用户C看来，即使消息的接收可能会有延迟，以上两个消息应该保证是按照顺序到来的，这就是前缀一致性所要保证的。

图: 用户C看到了两条乱序的消息，违反了前缀一致性

前缀一致性的关键特性是：

• 有序性：读取到的数据反映了写入操作的实际顺序。例如，如果写操作按顺序为 {W1, W2, W3}，如图[fig:consistency-model/Consistent-Prefix-1.png]给出了几种合法和不合法的前缀，在前缀一致性模型下：
• 客户端可能只读到{W1}，或者读到{W1,W2}，以上两种情况都是符合前缀一致性要求的。
• 但是不会读到{W3}（跳过了在W3之前发生的W1和W2），或者{W1,W3}（跳过了W2），因为这两种情况都不是{W1, W2, W3}集合的合法前缀。
• 前缀性：读取结果是写入历史的一个前缀，而不是随机或不完整的片段。仍然以上面的例子为例，{W1}和{W1,W2}是{W1, W2, W3}的前缀，但{W3}和{W1,W3}则不是。
• 无部分写入：不会返回仅部分完成的写操作结果，确保数据完整性。
• 弱一致性：前缀一致性比强一致性要求低，可能不会反映最新的写入，但保证看到的是一致的“历史”片段。

图: 针对集合{W1, W2, W3}

前缀一致性主要用于以下场景：

• 读取多个数据对象时，确保它们来自同一逻辑时间点的状态（避免看到部分更新的不一致组合）；
• 写入操作是渐进式更新（而非完全覆盖）时，保证读取到的中间状态是逻辑上连贯的。客户端能够读取到有序的写入历史：读取到的数据版本必须构成一个完整的、逻辑连续的“历史片段”，不会跳过中间的写入。例如阅读某个人在社交媒体上发布的动态时，可能不能读到最近刚刚发布的动态，但是会看到满足发布顺序的动态。
• 在事件驱动的架构中，一致性前缀确保消费者读取的事件流是按顺序提交的，例如消息队列系统。
• 在主从多副本中进行数据复制时，从节点可能落后于主节点，但一致性前缀保证从节点返回的数据是主节点写入的一个完整前缀。

举几个例子：

• 读取多个相关数据对象时，如果多个数据（如订单和支付记录）之间存在依赖关系，前缀一致性确保不会读到互相矛盾的组合。例如在电商支付场景中，看到支付记录时，但没有看到对应的订单记录。
• 读取增量更新的数据时，如果写入是逐步更新而不是覆盖式写入，前缀一致性确保能够按序读到这些增量变更记录。例如一个银行账户有两笔余额的变更，从最初的余额为0，先变成余额为100，再变成余额为200，那么前缀一致性应该保证能够按序读到这两次变更记录。

单调读 #

如图[fig:consistency-model/Monotonic-Read.png]中，用户A的评论要同步到两个从节点，用户B的两次读操作分别落在了两个不同的从节点上，导致第一次读到了数据，但是第二次却没有读到，看起来就像时间发生了“倒流”。

单调读（Monotonic Reads）保证客户端在同一会话期间的读取操作时不会出现时间倒流。在这种模型下，客户端可能读取到旧数据，但是能够保证客户端在同一个会话期间，读到的数据随着时间推进会越来越新，绝对不会出现数据回退的情况。例如，同一个客户端如果先后发起两次针对同一个对象的读操作，那么单调读模型保证第二次读操作返回的值要么与第一次相同，要么是一个更新写入的值。也正因为这个特性，单调读也被称为“会话保证”（session guarantee）”。

图: 用户B的先后两次读操作，在第一次读到数据之后，第二次却读不到数据

可以看到，单调读的两个关键特性是：

• 防止“时间倒流”：不会在多次的请求中，看到数据发生回退现象。
• 不保证全局最新：单调读可能会读到滞后的数据，但仍保持单调递增。

需要注意单调读和上面的前缀一致性的区别。仍然以{W1, W2, W3}事件集合为例，在单调读中允许读到{W2, W3}这样的事件集合，因为在读到事件W2之后读出了W3，事件并没有发生回退，但是在前缀一致性中不允许出现{W2, W3}，因为这不是{W1, W2, W3}事件集合的合法前缀。

常见的实现单调读的方案有：

• 客户端会话绑定（Session Stickiness）：同一个客户端，始终从同一个副本读取数据。例如，可以通过会话ID路由请求（如Nginx的ip_hash），或者在数据库代理层记录下来客户端最近的读取位置等。
• 客户端记录下来已读取的最新版本号，后续请求要求服务端大于该版本的数据。

读自己所写 #

如图[fig:consistency-model/Read-Your-Write.png]所示，用户A在社交媒体上更新个人资料，数据在复制到主节点成功后就返回资料更新成功，然后再同步到两个从节点。如果在数据尚未同步到从节点之前，用户A试图读取新的个人资料，该请求被路由到了还未完成数据同步的从节点上处理，就会读到旧数据，这会导致用户误认为更新的数据丢失了。

图: 用户A在社交媒体上更新个人资料成功之后，再次读取时读到了旧的个人资料

*“读自己所写”（Read my writes）*确保客户端的所有写入操作，其效果对该客户端后续的读取均可见。换言之：

• 如果客户端对某个数据对象写入一个新值，随后立即读取该对象，则读取操作会返回该客户端最后一次写入的值。
• 如果客户端没有写入操作，则行为降级为最终一致性，可能读到旧值。

读己所写的典型应用场景有：

• 社交网络：用户发布动态后，自己的页面必须能立即查看到刚刚发出的内容，避免出现“发帖成功但刷不出来”的情况。
• 电子商务：订单列表必须立即显示新订单，以防止用户重复购买商品。

读己所写模型，能够确保用户操作后能立即看到自己的更改。如果系统设计不考虑这一点，可能导致 “我改了资料，怎么还是显示老的？” 这类问题，影响用户体验。

常见的实现读自己所写的方案有：

• 客户端在写入数据成功后，记录下来当前的时间戳，在请求读数据时带上最近一次写入数据的时间戳，服务端保证返回不小于该时间戳的数据。
• 根据某些客户端写请求时的参数，保证客户端的请求始终路由到已同步该写入的副本。

棒球比赛的例子 #

为了解释这几类客户端一致性模型在实际业务中的应用，论文[@Baseball]中以棒球比赛为例来说明几类需要读取当前比分的人所面对的数据一致性问题。假设比赛的分数存储到一个键值存储中，客队和主队的分数写入不同的存储键值。

以下给出一个简化的棒球比赛流程，这里做一些简单的说明：

• 比赛双方为主队（home）和客队（visitors），初始得分为0；
• 比赛供分为9轮，每一轮客队和主队依次分别做为击球方和防守方，其中击球方用球棒击球后跑垒，依次踩过一垒、二垒、三垒并回到本垒得1分，而防守方通过投球、接球、传杀等方式阻止对方得分，并争取让3名击球员出局后攻守交换。

根据以上的棒球比赛流程，更新比分的代码流程如图[code:replication-baseball]所示。

Write (“visitors”, 0);
Write (“home”, 0);

for inning = 1 .. 9
	outs = 0;
	while outs < 3
		visiting player bats;
		for each run scored
			score = Read (“visitors”);
			Write (“visitors”, score + 1);

	outs = 0;
	while outs < 3
		home player bats;
		for each run scored
			score = Read (“home”);
			Write (“home”, score + 1);
end game;

简化的棒球比赛流程 {#code:replication-baseball}

表4-1是模拟的是一场棒球比赛进行到第七轮时各轮次的分数和总分，此时比赛进行到第7轮，客队完成本轮的比赛，而主队还没有开始，总比分为2-5。

\	1	2	3	4	5	6	7	8	9	\text{总分}
\text{客队}	0	0	1	0	1	0	0	\	\	2
\text{主队}	1	0	1	1	0	2	\	\	\	5

一场棒球比赛各轮次的分数

根据表4-1显示的比分顺序，更新比赛比分的流程顺序如图[code:replication-baseball-1]所示。

	Write("home", 1);
	Write("visitors", 1);
	Write("home", 2);
	Write("home", 3);
	Write("visitors", 2);
	Write("home", 2);
	Write("home", 3);

更新示例棒球比赛比分的流程 {#code:replication-baseball-1}

当比赛进行到第7轮总比分为2比5时，按照不同的一致性模型，将可能读到以下的分数（表4-2）：

• 强一致性：只能读到当前最新的比分2-5。
• 最终一致性模型：可能读到任意的分数，其中包括某一轮的比分不是按序出现的情况。例如在最终一致性的表中，可能读到0-3这样的分数，我们从表4-1可以看到，比赛按照顺序进行，绝不可能出现0-3这样的比分，读到这样的分数，只能说明在某一次读取两队分数时，读到的客队得分旧于读到的主队得分，这种情况在最终一致性模型中是可能出现的。最终一致性模型中，比分最终定格在2-5，也就是说即使中间读取的数据不一致，随着时间推进最终能读到正确的一致性数据。
• 前缀一致性：在前缀一致性中，读到的分数满足图[code:replication-baseball-1]中客队主队“交替变化”的顺序，也就是在任意一轮，首先更新的是客队的分数，因为是客队先成为攻击方，然后再更新主队的分数。例如在读到0-1的比分之后，先读到的分数是1-1，因为在第三轮客队先得1分，然后才是1-2，主队在第三轮也得1分。
• 单调读：在单调读中，不管读主队还是客队的分数，都没有出现数据回滚的情况。因此在表格中，当读到了1-3之后，就不会再读出在这之前的分数，只会读出在这个比分之后的分数。
• 读自己所写：如果是写入者，必须满足强一致性，因此只能读到2-5的比分；否则，对于非写入者，读到的数据和最终一致性模型可能读到的比分集合一样。

\text{强一致性}	2-5
\text{最终一致性}	0-0, 0-1, 0-2, 0-3, 0-4, 0-5, 1-0, 1-1, 1-2, 1-3, 1-4, 1-5, 2-0, 2-1, 2-2, 2-3, 2-4, 2-5
\text{前缀一致性}	0-0, 0-1, 1-1, 1-2, 1-3, 2-3, 2-4, 2-5
\text{单调读}	在读到1-3之后: 1-3, 1-4, 1-5, 2-3, 2-4, 2-5
\text{读自己所写}	对于写入者：2-5；对于其它任何非写入者：读到的数据和最终一致性读到的比分集合一样

各种一致性模型读到的比分

了解了这一场模拟棒球比赛各阶段比分以及各种一致性模型下可能读到的分数以后，我们来看看针对这样一场实时更新比分的比赛，各类不同类型的读者都要求满足怎样的一致性。虽然可以使用强一致性来满足所有读者的需求，但是我们将看到，在棒球比赛的例子中，通过分析不同类型读者所需要满足的一致性要求，可以通过弱于强一致性的读数据保证，在满足需求的同时获得性能优势。在这个例子中，棒球比赛比分的读者分为：官方记分员、裁判、电台记者、体育记者、统计员、数据观察者。

官方记分员（Official scorekeeper）

官方记分员负责更新比赛分数，将双方的比分实时更新到键值存储中，图[code:replication-official-scorekeeper]演示了官方记分员更新客队得分时的工作流程（主队得分时的操作逻辑类似）。记分员必须在原有比分的基础上加一，因此每次更新新的分数之前，都必须能够读到最新的比分，否则可能导致错误记录了分数。例如，如果主队之前已经得了5分，那么在得到第6分时，如果此时采用最终一致性来读取分数，将可能返回0到5之间的任何分数。

可见，记分员需要的是强一致性的数据，但是在棒球比赛的场景中，由于记分员是唯一变更比分的主体，因此只需要满足“读自己所写”保证即可，这也将达到强一致读数据的效果。可见，通过对特定场景的分析，可以使用较弱的一致性达成业务的目标。

这个微秒的区别，很大程度了提升了官方记分员的读性能。如果采用强一致读，系统将不得不假设在官方记分员更新比分的同时，还有另外的客户端也在更新数据，如果是这样的话，系统需要访问大多数服务器来确保刚刚读出的数据是最新的数据。而采用读我所写一致性时，系统只需要记住先前在哪些服务器执行过写操作，从这些服务器上就能读到自己先前写入的数据。

score = Read (“visitors”);
Write (“visitors”, score + 1);

官方记分员更新客队得分时的工作流程 {#code:replication-official-scorekeeper}

裁判员（Umpire）

棒球比赛在第九轮的上半部分之后，也就是客队已经击球、主队即将击球之前，会进行判断是否可以提前终止比赛。由于这是最后一轮，所以如果主队已经在得分上领先，那么不用进行剩下的比赛，可以直接判定主队赢球。根据这个规则，裁判员在比赛的大部分时候并不关心比赛的比分，直到来到第九轮的上半部分之后，将根据图[code:replication-umpire]中的算法来判断是否可以提前终止比赛。与记分员不同，裁判员从不记录分数，只是读取官方记分员写的数值。因此，为了接收最新的信息，裁判员必须采用强一致性方式来读取数据。

if first half of 9th inning complete then
	vScore = Read (“visitors”);
	hScore = Read (“home”);
	if vScore < hScore
		end game;

裁判的工作流程 {#code:replication-umpire}

电台记者（Radio reporter）

广播电台会定期公布正在进行的比赛的实时比分，也许很多读者已经不听广播电台了，那么也可以理解各种体育类应用会在比赛进行的时候实时更新比赛的比分，这类读者的工作流程如图[code:replication-reporter]所示。

在比赛进行中播报的实时比分，可能不是完全最新的比分。例如，在比分发现变化之后，广播电台报道最新比分的同时，比分又发生了新的变化，那么刚刚播报的比分就不是当前最新的结果了。因此，当读到的数据不能满足强一致性时，哪种形式的最终一致性，才是这类比分播报员能够接受的？

首先，记者绝对不允许读到不存在的分数。从表4-1可以看到，比赛中绝不可能出现0-3这样的比分，读到这样的分数，只能说明在某一次读取两队分数时，读到的客队得分是第二轮及之前的分数，而同时却读到了主队在第4轮的分数。如果读到这样的分数，对收看比分播报的观众而言是不能接受的。

因此，记者要求他的所有读取操作都在一个包含计分员所执行写入的一致性前缀快照上执行。这样记者就能读取到某个特定时间点存在的比分，而无需强制获取当前最新比分。

但是，仅仅满足读取时的前缀一致性还是不够的。例如，不能出现某个时刻读到的比分是2-5，在这之后又读到了比分为1-3的情况，因为比赛的比分满足单调递增，所以如果报道中先后出现2-5和1-3这样矛盾的比分是不可接受的。这类错误可能发生在记者先从主服务器读到了比分2-5，下一次读取时再从一个还未更新最新数据的从服务器中读到了旧的比分1-3。

因此，记者的数据读取，除了要满足前缀一致性以外，还需要保证单调读。

do {
	vScore = Read (“visitors”);
	hScore = Read (“home”);
	report vScore and hScore;
}

电台记者的工作流程 {#code:replication-reporter}

统计员（Statistician）

球队统计员负责跟踪赛季中的每场比赛球队以及队员的统计数据，如图[code:replication-statistician]所示，统计员在比赛结束之后，读取主队的分数更新到整个赛季的统计中。当比赛结束时，必须执行强一致读到本场比赛的最终分数。同样的，当读取本赛季的累计分数时，也需要执行强一致性读，否则如果读到了过期数据，更新赛季总分数会出现遗漏的情况。不过，考虑到球队统计员是唯一执行向数据库写入赛季统计总分的主体，也可以采用读自己所写的保证来更新赛季总分。

Wait for end of game;
score = Read (“home”);
stat = Read (“season-runs”);
Write (“season-runs”, stat + score);

统计员的工作流程 {#code:replication-statistician}

数据观察者（Stat watcher）

其他定期查看球队赛季统计数据的人员通常能接受最终一致性。在[code:replication-stat-watcher]中假设这些统计数据每天仅更新一次，略有过时的数据完全可以接受。

do {
	stat = Read (“season-runs”);
	discuss stats with friends;
	sleep (1 day);
}

数据观察者的工作流程 {#code:replication-stat-watcher}

表4-3总结了各类参与者所要满足的一致性模型。在这里可以看到，利用特定的场景知识，可以在不牺牲一致性的前提下利用弱一致性读取达到不同业务所要求的效果。

\text{官方记分员}	读自己所写
\text{裁判}	强一致性
\text{电台记者}	前缀一致性以及单调读
\text{统计员}	强一致性，读自己所写
\text{数据观察者}	最终一致性

各类参与者所要满足的一致性模型

无主节点复制 #

前面介绍的主从复制模式中，系统存在一个主节点，这是一种*中心化（Centralized）*的架构：所有写操作都必须经过唯一的“主节点”（Leader），再由主节点复制给“从节点”（Follower）。

主从复制模式最大的问题是：主节点本身是一个单点。如果主节点宕机，整个系统就失去了写入能力，必须花费时间进行故障转移（Failover），选举出新的主节点。在这个选举窗口期，系统是不可用的。

为了追求极致的高可用性和低延迟，特别是写入操作的可用性，工程师们设计出了另一种范式——无主节点复制。其核心哲学是：系统中的所有节点都是平等的，任何节点都可以直接接收写请求。

*无主节点复制（leaderless replication）是分布式系统中的另一种复制策略，在Amazon 2007年的论文《Dynamo: Amazon’s Highly Available Key-value Store》[@dynamo]发表之后进入人们的视野，实际上在更早之前的[@Gifford1979]中就已经提出这样的复制策略了。对比主节点复制的中心化架构，无主节点的架构设计，也被称为“去中心化（Decentralized）”*的架构，它的思想深刻影响了后面出现的比特币的架构设计。在比特币的架构中，任何一个比特币钱包都是这个分布式系统的节点，都可以接收处理用户的请求。

与传统的主从复制不同的是，无主节点复制的核心特征是：

• 无中心节点：所有副本的地位平等，没有主节点负责协调写入请求，也就不存在主从复制中主节点出现故障时的主备切换问题。
• 客户端直连：客户端需要同时向多个副本发送读写请求，因此如何客户端请求的到达顺序成为一个棘手的问题。
• 最终一致性：无主节点复制提供不了前面一致性模型中的一致性保证，只能通过冲突解决机制（如Quorum、版本向量等）实现多个副本数据的最终一致性。

无主节点复制的优势是，由于没有了中心节点，所有副本的地位相同，可以比中心化架构更容易容忍节点的故障。在主节点复制架构中，主节点成为了系统中的单点，一旦主节点出现故障，整个系统无法正常工作，需要将其它节点切换为中心节点才能继续服务。而在无主节点架构中，只要能够满足写入数量的节点可用，系统就仍然是可用的，无主复制中采用的数据冗余机制是quorum机制。

由于没有了中心节点负责协调数据的写入顺序，多副本上的冲突就更多了。客户端在不同的副本上可能读取到不同的数据，客户端需要解决读取数据不一致的问题。同时，由于多个副本的数据也不完全同步，也需要机制能够保证副本之间数据的最终一致性。

本节将结合Dynamo的论文，讲解无主节点复制的难点和解决方案。

概述 #

亚马逊是全球最大的电商网站之一，最开始采用关系型数据库来存储业务数据，随着业务的扩大，在业务中发现对存储服务的使用有以下的特点[@dynamo,dynamo2]：

• 关系型数据库的复杂关系查询功能，在业务中使用的场景并不多，大约70%的操作属于键值类型的查询，即仅使用主键返回一行数据，没有关系型数据库中复杂的多表查询（Join）。大约20%的操作会返回一组航，但是仍然只针对单表进行操作。
• 路由抖动、组件失败、网络分区是经常要面对的情况，但是对于电商业务而言，要尽量确保绝大多数场景下客户的修改请求成功，即需要满足*“永远可写（always writeable）”*。例如，用户修改购物车里的商品是电商业务中常见的操作，如果出现修改失败的情况会影响用户体验。

以购物车为例，用户将商品加入购物车这个操作，绝对不能失败。如果因为数据库分区、节点宕机等问题导致用户无法添加商品，用户很可能就流失了。相比之下，短暂地显示一个稍微过时（比如缺少刚刚加入的商品）的购物车，其损失要小得多。这些业务上的观察让亚马逊的工程师重新思考适合他们业务的存储服务设计。在传统的关系型数据库中：

• 关系型数据库的复制功能很受限，而且通常是靠牺牲可用性来换一致性，这不符合上面提到的大型电商网站经常要面对各种失败的情况。
• 电商服务大多数只用主键去检索，并不需要关系型数据提供的复杂查询和管理功能。这些额外的功能需要昂贵的硬件和专门的技能，而实际上服务根本用不到，最终的结果就是使用关系型数据库非常不经济。

这个业务需求催生了Dynamo的核心设计哲学：牺牲强一致性 (Strong Consistency)，换取极致的高可用性 (High Availability)。 这是理解Dynamo所有技术的出发点。

基于这些考虑，亚马逊设计Dynamo系统替换了关系型数据库，它仅提供put(key,context,object)和get(key)两个根据主键查询数据的接口，这里的参数context存储数据的元信息（metadata），例如数据的多个版本，我们将在后面看到这些信息如何用来解决数据冲突。

该系统对使用者有以下几点假设：

• ACID：如果要满足ACID特性[[sec:ACID]小节]，将牺牲系统的可用性。Dynamo系统并不提供ACID特性，取而代之，提供的是最终一致性，同时也不提供任何隔离保证。
• 效率：亚马逊的服务，把系统可用性、延迟放在系统设计时最高的考量位置。

总体而言，Dynamo有以下特点：

• 去中心化（Decentralised）：集群中的每个节点承担相同的职责并提供相同的功能。该系统完全是点对点的，不存在领导者或追随者节点的概念。
• 高可用（Highly Available）：Dynamo 将数据分布在各个节点上，并管理多个副本。每个节点都可以通过将请求转发到存储数据的节点来处理数据的读写操作。
• 最终一致性（Eventually Consistent）：为了提供始终可用且始终可写的数据存储，因此它牺牲了数据的一致性以换取可用性。在特定时间点，对于给定的数据项，不同副本节点对某个键的值可能存在分歧，但更新最终会到达所有副本。
• 容错性（Fault Tolerant）：数据分散存储，并在多个节点间进行复制以提供冗余。只有当所有副本都不可用时，数据子集才会变得不可用。DynamoDB 可以配置为将数据复制到位于不同地理位置数据中心的节点，这意味着即使整个数据中心发生故障，集群也能保持可用。
• 可扩展性（Scalable）：通过向集群中添加或移除机器，可以线性地增加或减少读写吞吐量。Dynamo 能够无缝地处理数据重新分配以适应此类变化，扩展集群无需停机，且运维开销极低。数据重新分配还能减少单个节点必须存储的数据量。

读写Quorum机制 #

无主复制中没有“主节点”来统一发布命令，系统如何保证数据最终是一致呢？答案是借鉴了现实世界中的“投票”机制，即 在[[subsection:quorum]]中提到的Quorum (法定人数)，我们来看如何运用这个机制在无主复制模式中保证数据的最终一致性。

在Quorum机制里，有几个三个关键变量：

• N：总副本数 (Total number of replicas)：一份数据被复制了 N 份，存储在 N 个不同的节点上。
• W：写法定人数 (Write quorum)：一次写操作，必须在 W 个副本上成功写入，才被认为是“写入成功”。
• R：读法定人数 (Read quorum)：一次读操作，必须从 R 个副本上成功读取数据，才被认为是“读取成功”。

在无主节点复制时，由于不存在主节点，所以需要同时向系统中的多个副本发起写操作，这是读、写操作要分别收到多少节点的响应，才能认为请求被成功处理，这依赖于Quorum机制中的参数配置。

我们从最简单的3节点组成的系统开始我们的讨论。在这样一个分布式系统中，假设客户端只向一个节点写入数据成功就认为写入成功，而读请求同样也是只向一个节点读取数据就认为读取到了最新的数据，由于系统由3节点组成，所以这个机制可能读到的是旧数据。如图[fig:rep-quorum]所示，客户端在t1时刻向A、B、C三个节点写入数据，其中发向节点B的写请求因为某些原因丢失，而客户端在节点A的写请求应答之后，就认为写入成功，再向节点B发送读请求时，读到的却是t0时刻的旧值。

图: 只成功写入一个节点就认为写入成功，只从一个节点读取数据，可能返回旧数据

从上面的例子中可以看出，3节点组成的系统中，写入1个节点成功就认为成功时，只从1个节点读取数据，可能读到旧的数据。原因在于：在这个数据配置下，写入成功的节点，可能和读取时的节点并不重合。只有保证读和写的节点集合有重合，才能保证读取的数据中至少有一个节点存储了最新的数据。在这个3节点的例子中，以下的读写节点数量配置都是可以满足重合条件的：

• 写入2节点成功才认为写入成功（W=2），读取时从1个节点读取（R=1）；
• 或者，写入1节点成功就认为写入成功（W=1），但是读取时需要从2个节点读取（R=2），如图[fig:rep-quorum-2]所示。

图: 只成功写入一个节点就认为写入成功，但是需要从2个节点读取数据，才能读到最新的值

把3节点系统的情况加以推广，如果系统中有N个节点，响应写请求的副本集合被称为写入法定人数（write quorum），该集合元素数量为w，响应读取请求的集合构成读取法定人数（read quorum），该集合元素数量为r。*quorum（法定人数）*机制，要求写入法定数与读取法定数必须存在非空交集，即满足W + R > N，根据鸽巢原理就能保证读写操作至少有一个重叠节点，这样读取的数据中一定能读取到最新的值。

分布式系统中，常用的*多数法定数（majority quorum）*定义为超过半数节点的子集，例如：

• 图[fig:rep-quorum]由A、B、C组成的3节点系统中，有4个多数法定数：{A,B}、{A,C}、{B,C}和{A,B,C}。
• 推广开来，如果系统的节点数量为奇数，任何超过$\lfloor \frac{n+1}{2} \rfloor$节点组成的集合就构成多数，例如3选2、5选3；如果系统的节点数量为奇数，任何超过$\lceil \frac{n+1}{2} \rceil$节点组成的集合就构成多数，例如4选3，6选4。

图: 读、写法定人数集合有交集，才能读到最新的值

Dynamo采用了类似Quorum的仲裁系统的一致性协议，允许使用方根据自己业务场景来灵活配置W和R参数，W和R的设置决定了系统的一致性级别：

• 强一致性：R、W和节点数量N需要满足关系$R + W > N$，即R和W中必须至少有一个值超过N/2，这样能保证R和W操作的副本集合一定有交集。
• 最终一致性：当$R+W \leq N$时，系统只保证最终一致性。

参考在[sec:replication-mode]中对数据复制模式的讨论，Quorum读写仲裁算法可以归为半同步复制模式，但是由于这个算法可以配置不同的R和W参数，不同的配置下可以变为不同的复制模式：

• R=1,W=N：此时系统在读操作时是全异步模式，而写操作则变成了全同步模式。
• R=N,W=1：此时系统在读操作时是全同步模式，而写操作则变成了全异步模式。
• R=N,W=N：此时系统在读、写操作时都是全同步模式。

数据冲突问题 #

Quorum机制解决了同一个读写数据操作的一致性问题，但是没有解决并发修改数据时可能出现的顺序不一致问题。无主复制架构中，由于没有主节点来协调写请求，任何一个节点都可以处理写请求，因此请求之间缺乏顺序的保证，可能出现同时并发对同一个数据的写操作，这些请求到达不同的节点上不一致，导致“写-写冲突”，不同的副本上可能存储着不同的“最新值”。

如图[fig:rep-leaderless-1.png]的无主复制架构中，同时有两个客户端修改同一份数据，客户端1到节点B的写请求，落后于客户端2到节点B的写请求，而到另外两个节点A和C的写请求，则是客户端1的请求先到。如果不加以处理，几个节点上将出现冲突的数据。

图: 无主节点架构中，不同客户端同时并发修改同一份数据。

解决并发写冲突最简单的策略是最后写入者获胜（Last-Write-Wins, 简称LWW），这种策略为每次写入附加一个精确到微秒或纳秒的时间戳，冲突发生时，时间戳最新的数据获胜。但是这种策略严重依赖所有节点的时钟同步，我们在[section:physical-time]中已经介绍过节点之间物理时钟同步的难点，如果时钟不准，可能导致新数据被旧数据覆盖。

我们来看Dynamo如何解决并发写冲突问题。为了解决数据冲突问题，需要回答两个选择：*何时（when）解决冲突，以及谁（who）*来解决冲突。

在传统的关系型数据中，在收到数据的写请求时来解决冲突，这样可以保证读的复杂度很低，因为客户端读出来的数据都是没有冲突的数据。但是在这样的系统里，任何时候如果不能访问大部分的副本，写请求就会被拒绝。Dynamo的设计与此相反，它的目标是要实现一个*“永远可写（always writable）”*，如果在发生网络分区或故障时就拒绝客户端的写入请求，将造成很差的用户体验。这个需求使Dynamo将解决数据冲突的复杂度放到了读操作，以保证写请求永远不会被拒绝。

回答了何时解决冲突的问题，再来看谁来解决数据冲突：是数据库还是应用方。如果由数据库来解决冲突，通常只有有限的手段，例如采用前面提到的LWW机制来解决冲突。另一方面，应用方才真正理解数据描述的是什么，它可以自主选择对用户体验最好的冲突解决方式。以购物车应用为例，该类应用可以实现一个可以“合并”多个不同版本冲突数据的方案。在很多情况下，一些应用开发者也许并不想自己实现一套冲突解决机制，在这种情况下，解决冲突的问题就下放给数据库，退化为选择一些简单的策略，例如采用最后写入胜出。

Dynamo选择的是由应用在读数据时来解决冲突，当系统无法自动解决冲突时，它会将所有冲突的版本（例如，两个不同内容的购物车）都返回给客户端应用，由应用层的业务逻辑来决定如何“合并”这些版本，然后将合并后的新版本再写回系统。回到前面购物车读到旧数据的例子，在亚马逊的应用中，为了保证可用性，类似的数据不一致是可以容忍的。如果接下来用户又接着从读出的旧购物车数据中进行修改，那么相当于出现两个分支的购物车数据，系统中将保留下来每次的修改为一个*不可变（immutable）*的版本数据，如果多个版本之间能够进行数据合并将进行合并，否则将向客户端返回所有版本的数据，由应用来解决数据的冲突。

Dynamo采用向量时钟[content:vector-clock]来保存多版本的数据，如果多版本的数据之间能够根据向量时钟的算法判断出有先后顺序，那么可以进行数据合并，否则就向应用返回所有不能合并的多版本数据。

如图[fig:rep-dynamo-2.png]所示，采用向量时钟表示同一份数据的不同版本，格式为“[(节点,计数器)]”，对象经历了以下几次修改：

• 客户端的第一次写入数据请求由节点x处理，由于是初次写入数据，系统创建了对象D1，其中的向量时钟为[(x,1)]。
• 客户端更新数据，请求再次发送给了节点x处理，因此得到了数据对象D2，它的向量时钟为[(x,2)]，根据向量时钟的原理，对象D2是对象D1的后代，因此可以直接覆盖对象D1。
• 接下来的两次不同客户端的数据修改，不再由节点x处理，而是分别发送到了节点y和z上，由于这两次修改分别是这两个节点上的第一次数据修改，因此得到了两个对象D3和D4，两者分别在向量时钟中新增本节点的版本号。
• 接下来再次有客户端进行数据修改，从节点y和节点z上读到了两个不同版本的对象D3和D4，两者的改动都没有反映在对方的改动之中，因此不能进行数据合并，两个版本都要保留，最后向节点x写入了数据D5。

在以上的流程中，首先会根据版本之间的因果关系进行覆盖合并（例如D2版本数据可以覆盖D1），不能进行合并的数据（例如D3和D4版本）将同时保留下来，一同返回给客户端，由客户端的应用层逻辑来决定如何使用这些多版本数据。

图: 通过向量时钟进行数据合并解决冲突。

集群成员管理 #

在Dynamo中没有“主节点”或其它中心化协调服务，因此，集群必须自己解决一个基本问题：一个节点如何知道所有其他节点的存在、状态，以及谁负责哪些数据？Gossip协议就是Dynamo用来解决这个问题的技术手段，它通过节点间随机传播成员状态信息，实现了去中心化的集群管理架构，有效解决了节点增删、故障检测和状态同步等关键问题。这种机制使得Dynamo能够在没有中心协调节点的情况下，保持集群成员的一致性视图，同时具备高可用性和弹性扩展能力。这种协议避免了传统的中心化协调机制，降低了系统的复杂性和单点故障风险。

Gossip协议是一种基于概率传播的分布式通信机制，其核心思想模拟了流行病在人群中的传播方式，它的主要工作原理是：

首先，Dynamo通过*种子节点(Seed Nodes)*来解决新节点加入集群的问题。种子节点是预先配置的固定节点，所有新加入的节点首先连接到种子节点，获取当前集群成员信息。种子节点的存在确保了新节点能够顺利加入集群，避免了逻辑隔离的问题。即使部分种子节点失效，只要至少有一个种子节点存活，新节点仍然可以加入集群，这大大提高了系统的容错能力。

其次，Dynamo采用向量时钟来记录成员状态的版本信息。每个节点维护一个向量时钟，其中每个元素对应一个节点的计数器，表示该节点状态变更的次数。当节点交换成员信息时，它们也会交换各自的向量时钟。通过向量时钟的比较，节点可以确定哪个成员信息是最新版本，并据此更新本地状态，这有效解决了成员信息同步中的版本冲突问题。

如图[fig:rep-dynamo-6.png]是集群节点通过Gossip协议感知集群中其它节点的过程，随着这个过程持续进行，最终集群中的所有节点都能感知到其它所有节点的运行情况。

图: 节点之间通过Gossip感知集群中的其它节点。

Gossip协议在Dynamo中带来了显著的优势，同时也存在一些局限性。对Dynamo这样的大规模分布式系统而言，Gossip协议的去中心化特性使其成为管理集群成员的理想选择。

它的主要优点是：

• 高可用性与容错性：Gossip协议去中心化的架构避免了单点故障问题，即使部分节点失效，集群仍能正常运行。节点间随机选择通信伙伴，使得网络中的信息能够通过多种路径传播，增强了系统的容错能力。
• 低通信开销：与传统的洪泛(flooding)机制相比，Gossip协议通过随机选择通信伙伴，大大减少了网络中的冗余消息。Dynamo的Gossip协议每秒仅需一次随机节点通信，平衡了实时性与网络开销，适合大规模集群环境。
• 弹性扩展能力：Gossip协议的传播速度与网络规模呈对数关系，即使在数千节点的集群中也能保持高效。Dynamo通过Gossip协议实现了无中心节点的集群扩展，节点可以随时加入或离开集群而不影响整体服务。
• 快速收敛特性：Gossip协议的指数级传播特性使得信息能够快速扩散到整个集群。在Dynamo中，即使节点频繁变更，集群也能在较短时间内达成成员状态的一致性视图，保证了系统的稳定运行。

然而，Gossip协议也存在一些局限性：

• 最终一致性：Gossip协议无法保证强一致性，只能保证最终一致性。在Dynamo中，节点可能需要一段时间才能获取最新的成员状态，这可能导致短暂的不一致现象。
• 潜在的网络风暴：虽然Gossip协议通过随机选择通信伙伴减少了网络开销，但在大规模集群中，节点频繁变更仍可能引发短暂的通信高峰。Dynamo通过控制Gossip传播频率和采用谣言传播模式，有效缓解了这一问题。
• 状态同步的复杂性：Gossip协议需要处理节点间的版本冲突和状态不一致问题。Dynamo通过向量时钟和"已见集合"机制，解决了成员状态同步中的版本冲突问题，但这也增加了协议的复杂性。

自Dynamo发布以来，Gossip协议在分布式系统领域得到了广泛应用和改进。现代分布式系统如Cassandra、Riak和Akka Cluster等，都采用了类似Dynamo的Gossip协议进行集群成员管理。

数据修复 #

由于无主节点架构，并不强制要求写请求在所有节点处理之后才响应，因此可能出现在某些节点没有复制成功的情况下就已经应答给客户端。此时，需要一个数据修复的流程。

在Dynamo架构中，节点之间会定期地、随机地选择伙伴，相互“对账”，如果发现节点有缺失的数据，需要将这部分数据同步到失效节点上，这个修复节点间数据差异的过程，被称为*“反熵（anti entropy）”*。如果采用节点间对比所有键值的方式，在数据量非常大的情况下效率极低。为了快速检测副本之间的不一致性，以及最小化恢复的数据量，Dynamo采用了Merkle tree[@Merkle] (https://en.wikipedia.org/wiki/Merkle\_tree)数据结构，它本质上是一颗二叉树，树上的每个节点存储哈希值：

• 如果是叶子节点：哈希值就是键对应的值的哈希值。
• 如果是非叶子节点（即内部节点）：哈希值就是其子节点的哈希值再次进行哈希计算之后的值。

如图[fig:rep-dynamo-5.png]是一棵Merkle trees的示例，在图中，h表示所使用的哈希函数，H表示哈希函数计算出来的哈希值，H根据不同的节点类型有两种下标的表示：

• 对于叶子节点，H只有一个下标，例如$H_1=h(V_1)$计算的是叶子节点1的值$V_1$的哈希值。
• 对于非叶子节点，H有两个下标表示它的子节点的数据范围，例如$H_{12}=h(H_1 + H_2)$表示计算的是子节点$H_1$与$H_2$的哈希值之和的哈希值。

图: Merkle tree示例。

我们可以看到，由于Merkle tree是一棵二叉树，节点的哈希值是自底向上计算的，可以按照如下流程对比两棵Merkle tree上叶子节点的值是否相同：

• 如果两棵树的根节点哈希值相同，说明两棵树的叶子节点必然相同；
• 否则，从根节点开始往下沿着哈希值不同的节点进行遍历，找到所有值不同的叶子节点。这个过程和二叉树的查找算法一样，时间复杂度是$O(log_2(n))$。如果采用的是线性的数据结构（例如链表）来查找数据冲突，就需要$O(n)$的时间复杂度。

Dynamo中的每个节点为每段虚拟节点所覆盖的键范围维护一棵单独的Merkle tree树，当需要恢复数据时，按照上面的流程马上就可以定位到数据不一致的叶子节点进行数据同步。

亚马逊的这篇论文发表于2007年，是NoSQL和最终一致性领域的奠基之作。虽然在此之前已经有不少NoSQL (https://en.wikipedia.org/wiki/NoSQL)类型的数据库，但是这篇脱胎于世界最大电商网站生产实践的论文无疑让业界开始思考两个问题：是否需要提供SQL查询功能，尤其是复杂的跨多表JOIN查询在很多场景下并不会用到；另外，在互联网用户爆发式增长之后，系统的可用性成为了更高的考虑因素，为了保证系统的可用性，就需要牺牲强一致性，在这个过程中，又应该如何解决数据的冲突。

本章小结 #

本章系统性地探讨了分布式系统中最为核心的策略之一——数据复制（Data Replication）。我们从复制的基本目标出发，阐述了其在高可用性、容错能力、降低延迟以及提升读性能等方面的重要意义。然而，复制的引入也带来了分布式系统中最棘手的挑战：如何在不可靠的网络和节点故障中，维护多副本数据的一致性。

首先，我们详细剖析了主从复制架构，分析了同步、异步及半同步复制在性能与数据安全性之间的权衡。针对主从架构中节点失效与脑裂（Split-brain）的问题，我们探讨了心跳检测、租约（Lease）机制以及栅栏令牌（Fencing Token）在保障系统活性与安全性中的关键作用。

随后，本章的重点转向了一致性模型的理论体系。我们从观察者的视角出发，由强至弱依次界定了线性一致性、顺序一致性、因果一致性及最终一致性。通过引入“安全性”与“活性”的概念，明确了强一致性属于对系统状态的严格约束，而最终一致性则是对系统收敛能力的承诺。同时，结合CAP定理及其演进版本PACELC，从理论高度指出了在网络分区与延迟约束下，一致性与可用性之间不可调和的矛盾，为系统架构的选型提供了理论依据。

针对最终一致性系统可能带来的用户体验挑战，本章补充介绍了客户端一致性模型（如写后读、单调读、前缀一致性等）。通过棒球比赛的生动案例，展示了如何根据不同的业务角色需求，在不追求强一致性的前提下，利用会话级的一致性保证来满足业务逻辑的正确性。

最后，我们转向了去中心化的无主节点复制架构，并以Amazon Dynamo为经典案例进行了剖析。通过对读写Quorum（W+R>N）、向量时钟处理并发冲突、Gossip协议进行集群成员管理以及Merkle Tree进行反熵数据修复等关键技术的讲解，展示了如何构建一个永远可写、高可用且可线性扩展的分布式存储系统。

综上所述，分布式系统的复制设计没有绝对的“银弹”。无论是选择主从架构还是无主架构，亦或是选择强一致性还是最终一致性，本质上都是在数据一致性、系统可用性与访问延迟之间进行的博弈与权衡。理解这些模型背后的原理与适用场景，是构建可靠分布式系统的基石。