不可靠的网络

网络分区故障，指网络的一部分由于网络故障而与其他部分断开，其实可以直接称为网络故障。作者推荐，可以通过故意触发网络问题，来测试系统的反应。

在分布式系统中，需要设置响应的超时时间，从而判断节点是否失效。如果时间设置得太长，则需要等待更长的时间。如果时间设置得太短，可能节点只是负载过高而响应缓慢，此时判断节点失效并将负载转移到其他节点会进一步增加系统负载，从而可能导致失效扩散（还可能会导致其他异常）。比较好的做法是，持续测量响应时间及其变化，然后根据测量结果自动调整超时时间。

从广义上讲，网络延迟的波动可以视为资源动态分配的结果。传统的电话网络（非 VoIP）使用电路交换技术，为每个通话分配一条固定带宽的通信链路，网络的延迟是确定的；而互联网使用分组交换技术，所有用户共享网络带宽，用户之间的数据存在排队的情况，该方法可以增加带宽的利用率，但是理论上的延迟是无限大的。

不可靠的时钟

网络上的每台机器都有独立的时钟硬件设备，通常是石英晶体振荡器，用于维护机器的本地时间，该时间可能与其他机器上的时间不同。通常使用网络时间协议（Network Time Protocol，NTP）来同步机器之间的时间，该协议根据一组专门的时间服务器来调整本地时间（调整石英的振动频率），时间服务器则从精确度更高的时间源（例如 GPS 接收器）获取高精度时间。

墙上时钟和单调时钟

现代计算机内部至少有两种时钟：墙上时钟和单调时钟。

墙上时钟

墙上时钟根据某个日期返回当前的日期与时间，例如 Linux 的 clock_gettime(CLOCK_REALTIME) 和 Java 的 System.currentTimeMillis() 会返回自 1970 年 1月 1 日（UTC）以来的秒数和毫秒数，不含润秒。有些系统则使用其他日期作为参考点。

墙上时钟需要使用 NTP 进行同步，但是存在很多问题。特别是，如果本地时钟远远快于 NTP 服务器，则同步之后会发生时间倒退的现象，以及墙上时钟经常忽略润秒，导致其不太适合用于测量时间间隔。

单调时钟

单调时钟不需要和 NTP 服务器时钟进行同步，适合测量时间间隔。例如 Linux 的 clock_gettime(CLOCK_MONOTONIC) 和 Java 中的 System.nanoTime() 返回的都是单调时钟。单调时钟的单个值没有任何意义，它可能是电脑启动后经过的纳秒数或者其他含义，不同节点上的单调时钟没有相同的基准，不能相互比较。

时钟同步和准确性

硬件时钟和 NTP 服务器可能会出现各种问题，例如：计算机中的石英钟存在漂移现象（运行速度会加快或减慢，取决于机器的温度）；如果本地时钟和 NTP 服务器时钟相差太大，应用程序可能会看到时间倒退或跳跃的现象；同步的准确性受限于网络延迟，以及 NTP 服务器是否正常工作；各种其他情况，包括下面提到的润秒。

润秒（Leap second）就是对协调世界时（Coordinated Universal Time，UTC）增加或减少 1 秒，以使协调世界时和世界时（UT，通常指 UT1）之间的差异不超过 0.9 秒。2022 年 11 月，国际计量大会决定在 2035 年之前取消润秒。润秒曾经使许多大型系统崩溃，根本原因是许多系统没有正确适配润秒，软件存在 BUG 从而引发各种问题。可以看下 The Inside Story of the Extra Second That Crashed the Web 这篇文章，讲述了现实中发生过的问题。Google 处理润秒方式是，在一天内逐步调整时间，而不是在一天结束时直接改变 1 秒。PS：一个显示各个时钟目前时间的网站。

如果投入大量资源，可以达到非常高的时钟精度，例如交易系统的时钟就要求很小的时钟误差。高精度的时钟可以使用 GPS 接收器，精确时间协议（PTP）并辅以细致的部署和监测来实现。

依赖同步的时钟

如果应用需要精确同步的时钟，最好仔细监控所有节点上的时钟偏差。如果某个节点的时钟漂移超出上限，则将其视为失效节点并从集群中移除。这样监控的目的是确保在造成重大影响（例如隐式的数据丢失）之前尽早发现并处理问题。

时间戳和事件顺序

在无主复制的检测并发写中提到过，最后写入者获胜（LWW）冲突解决策略由于时钟偏差，可能会覆盖非并发写入。

在上述例子中，时钟同步机制稳定工作，节点 1 和节点 3 之间的时钟偏差小于 3ms，但是时间戳却不能正确排序事件，从而导致客户端 B 的增量操作被覆盖。解决方案就是之前提到过的，使用版本向量技术跟踪因果关系。PS：因果关系其实就是非并发写操作的前后关系，版本向量不仅可以跟踪因果关系，还可以判断写操作是否并发。

时钟的置信区间

或许墙上时钟会返回微秒甚至纳秒级别的信息，但是这种精度的测量值其实并不可信，因为存在石英漂移和网络延迟等不确定性因素。所以，我们不应该将时钟读数视为一个精确的时间点，而应该视为带有置信区间的时间范围。例如，系统可能有 95% 的置信度认为目前时间介于 10.3~10.5 秒之间。

可以根据具体的时间源来推算出时钟误差的上限。如果节点上直接装有 GPS 接收器或原子（铯）时钟，那它的误差范围通常可查询制造商的手册。如果节点是从服务器获取时间，则不确定性取决于上次同步以来的石英漂移范围，加上 NTP 服务器的不确定性，再加上节点和服务器之间的往返时间。

但是，大多数系统并不提供这种误差查询接口，通常只会返回某个确定的时间，而没有任何误差信息。Google Spanner 中的 TrueTime API 提供误差查询，它会返回时间的上下界。

全局快照的同步时钟

该节主要是讲如何在分布式场景下，生成全局单调递增的事务 ID，有点不明白这个标题是什么意思。如果是单节点数据库，使用一个计数器就可以实现正确的事务 ID。但是，如果是多节点数据库，则更加复杂并且开销更大。

Twitter 使用雪花（Snowflake）算法来生成近似单调递增的唯一 ID。如果节点之间的墙上时钟完全同步，则也可以将其作为事务 ID，但是实际上是不可能的。Google Spanner 使用 TrueTime API 返回的时钟置信区间作为事务 ID，如果两个置信区间没有重叠，则可以知道两个事务的先后顺序。

进程暂停

在使用主从复制的数据库中，只有主节点可以接受写入，如果主节点失效则需要将某个从节点提升为主节点。判断节点是否失效可以使用租约来实现：如果某个节点持有租约，那么它就是主节点；如果租约过期，则该节点失效。我们可以使用单调时钟来判断租约是否过期，但是可能由于垃圾收集、上下文切换或磁盘 I/O 等原因导致进程暂停，从而使得暂停之前判断租约没有过期，暂停之后发送请求时租约已经过期。

上图是 HBase 曾经遇到的问题，不正确的分布式锁实现，导致未持有锁的客户端修改数据。解决方案是，锁服务为每个锁维护一个单调递增的 fencing 令牌（实际上就是版本号），在锁服务授予客户端租约和客户端向存储服务发送写请求时会包含该令牌，存储服务也会维护数据最后一次修改对应的令牌。如果存储服务收到的写请求包含旧令牌，则会拒绝该请求。如果使用 ZooKeeper 作为锁服务，则事务标识 zxid 或节点版本 cversion 可以充当 fencing 令牌。

分区/分片（动词）就是将数据拆分为多个子集，一个子集被称为一个分区^[1]（名词）。使用数据分区的目的是提高可扩展性，不同分区可以存储在不同节点上，查询负载也随之分散到多个节点。在面对海量数据集或者非常高的查询压力，使用数据复制还不够，这时就需要使用数据分区。当分区和复制结合使用时（假设为主从复制），每个分区都会有自己的主节点和从节点，这种情况下单个节点也会存储多个分区的数据（作为某个分区的主节点和其他分区的从节点）。

分区方式

最好的情况是将数据和查询负载均匀分布到所有节点。如果分区不均匀，就会出现负载的倾斜，这会导致分区的效率下降。极端情况下，所有负载都集中在单个节点上，其他节点都处于空闲状态，此时这个节点被称为系统的热点。避免热点的最简单的方法是将记录随机分配给所有节点，但是由于不知道数据的分布情况，在查询时需要访问所有节点。下面将会介绍对键值数据和二级索引进行分区的方式。

这节的内容看得有点懵。按我的理解，键（key）也被称为关键字（keyword），它是一列或多列属性的集合，可以是唯一的或者不唯一的。但是按照书中的描述以及我在网上看到的定义来说，在“键值数据”这样的词中，似乎要求键必须是唯一的。书中在介绍完键值数据之后，又紧接着介绍二级索引，然后说二级索引在分区时的复杂性在于索引键的不唯一。但是书中接下来的讨论让我感觉，二级索引在分区时的复杂性在于如何创建二级索引，即是创建本地索引还是全局索引。

键值数据

基于区间的分区

解释：可以为每个分区分配一个关键字区间，区间可以由管理员手动选择，或者由数据库自动选择。

优点：分区内的数据可以按照关键字排序存储，从而支持区间查询。

缺点：如果查询集中访问某个范围内的数据，则会导致热点问题，解决方案是使用额外的内容作为关键字的第一列。

基于哈希的分区

解释：可以为每个分区分配一个哈希值区间，关键字根据哈希值进行分区，用于分区的哈希函数不需要很强的加密性。

分析：可以将关键字均匀的分配到多个分区，但是不能很好地支持关键字上的区间查询（查询时需要将请求发送给所有分区）。如果使用的是联合关键字，则可以只将关键字的第一列用于哈希分区，然后将其他列用作联合索引来对分区内的数据排序，从而可以在关键字的其他列上实现区间查询。

问答：为什么要将哈希值拆分为区间，而不直接使用取模操作？因为如果添加/删除节点，取模会导致大量的数据迁移。

负载倾斜与热点

虽然哈希分区可以减轻热点，但是无法完全避免。极端情况下，所有读/写操作都是针对一个关键字，则最终所有请求都会被路由到同一个分区。例如，发生热点事件时，会产生大量对相同关键字的读/写操作，此时哈希分区起不到作用。大多数系统至今仍无法自动消除这种高度倾斜的负载，而只能通过应用层来减轻倾斜程度。例如，如果某个关键字被认为是热点，则可以通过在关键字的开头或结尾添加随机数（有点像密码学中的盐值），从而将请求路由到不同分区。但是，此时读操作必须将多个分区中的数据合并，开销较大。

二级索引

基于文档的分区

解释：每个分区独自创建和维护二级索引，创建的是本地索引，而非全局索引。

缺点：如果要使用索引查询满足某个条件的数据，则需要将查询请求发送给所有分区，然后合并返回的结果。

基于词条的分区

解释：对所有数据创建全局索引，然后对索引进行分区，可以使用区间或哈希分区。

优点：进行单关键字查询时，只需要读取单个分区，因为相同的索引键都会被分配到相同的节点。

缺点：即使更新的是单个节点上的数据，可能也需要更新多个节点上的索引。如果选择同步更新，那么需要分布式事务的支持，写请求会被阻塞；如果选择异步更新，就意味着更新的滞后。

分区再平衡

在某些情况下，可能需要为数据库添加/删除节点，我们希望在添加/删除节点的过程中平衡所有节点的负载，这个迁移负载的过程被称为再平衡或者动态平衡。

再平衡的策略

固定数量的分区

解释：创建远超实际节点数的固定数量的分区，然后为每个节点分配多个分区。如果添加节点，则从每个现有节点中移动几个分区到新节点；如果删除节点，则将其中的分区均匀分配给剩余节点。也可以将硬件配置考虑进来，为性能更强的节点分配更多的分区。

分析：如果数据的规模不确定，就很难确定合适的分区数量。每个分区包含的数据量的上限是固定的，实际大小应该和集群中的数据总量成正比。如果分区数量太大，则每个分区包含的数据量太小，徒增管理开销；如果分区数量太小，则每个分区包含的数据量太大，再平衡和故障恢复的开销就更大（不是很懂为什么）。

动态分区

解释：为每个分区设置阈值，如果分区中的数据量太大或太小，就会进行分裂或合并（类似 B+ 树）。每个节点可以包含多个分区，当某个分区分裂时，可以将其中一半的数据转移到其他节点，以平衡负载。

分析：优点是分区的数量可以通过分裂和合并自动适配数据总量。对于空的数据库来说，需要进行预分裂，从而避免开始时只存在一个分区，导致负载不均衡的情况。

按节点比例分区

解释：为每个节点分配固定数量的分区。如果添加节点，则随机选择固定数量的现有分区进行分裂。

分析：随机选择可能会带来不公平的分裂，但是当每个节点包含的分区数量较大时，可以减少不公平的概率。

疑问：为什么书上说随机选择分区边界的前提是使用哈希分区，以及为什么说该方法符合一致性哈希。

请求路由

我们已经知道如何将数据分区，以及如何平衡节点上的分区，现在还有一个问题是，如何将请求路由到对应分区所在的节点。如果发生分区再平衡，分区和节点的对应关系还会随之变化，我们需要能够跟踪这些变化。有如下三种处理策略：

• 客户端将请求发送给任意节点，如果当前节点没有对应的分区，则将请求转发给其他节点，直到找到对应节点。
• 客户端将请求发送给路由层（负载均衡器），路由层负责将请求转发给对应节点。
• 客户端跟踪分区和节点之间的关系，直接将请求发送给对应节点。

不管使用哪种方法，核心问题是：作出路由决策的组件（节点、路由器、客户端）如何跟踪分区和节点的对应关系。有的分布式系统依靠独立的协调服务（例如 ZooKeeper）跟踪对应关系，有的使用 gossip 协议在节点之间同步对应关系，等等。

PS：数据分区这章看得有点痛苦，感觉书上的表述很乱，包括多个同义词混用，以及前后表述不一致。一些部分也讲得很模糊，没有一个实际的例子，单是看某句话感觉会有歧义，不知道实际上想表达的是什么。先这样吧，总感觉笔记上有很多问题。

---

1. 这里讨论的数据分区和网络分区问题（一种节点间的网络故障）中的分区是不同的概念。 ↩︎

复制指在多个节点上存储相同的数据，以降低访问延迟（数据分布在多个地理位置），提高容错性和吞吐量。如果复制的数据一成不变，那么只需要简单地将数据复制到每个节点。然而复制的挑战在于如何处理不断变化的数据（如何保证数据的一致性），下面讨论三种流行的应对复制数据变化的方法：主从复制、多主复制和无主复制。

主从复制

工作原理

主从复制也被称为单主复制，客户端必须将写请求发送给主节点，主节点首先将更改应用到本地，然后再将更改发送给所有从节点。客户端可以将读请求发送给主节点或者从节点。

同步和异步复制

• 同步复制
  • 优点：如果主节点发生故障，则可以在从节点访问到最新数据。
  • 缺点：如果从节点发生故障，则主节点会被阻塞直到从节点复制完成。
• 异步复制
  • 优点：主节点不会被阻塞，系统的吞吐量更大。
  • 缺点：如果主节点发生不可恢复的故障，则所有未被复制到从节点的更改都会丢失。

实践中，通常只将一个从节点设置为同步模式，其他从节点设置为异步模式。如果主节点发生故障，则可以在同步的从节点访问到最新数据；如果同步的从节点发生故障，则可以将另一个异步的从节点升级为同步模式。这种配置方式被称为半同步。

配置新的从节点

当需要提高系统的容错性或者替换失效的从节点时，就需要增加新的从节点。此时如何保证新的从节点和主节点的数据一致？简单地将数据从主节点复制到从节点是不行的，因为数据在不断变化，这样可能会丢失更改。或者可以对数据库加写锁，但是这会违反高可用的设计目标。

实际上，可以在不中断数据库服务的情况下完成新的从节点的配置。步骤如下：对主节点的数据创建一个一致性快照，将此快照复制到从节点，然后从节点向主节点请求快照之后的更改日志（根据快照中的 LSN 确定），获得日志之后重做日志的更改（这个步骤称为追赶）。

处理节点失效

从节点失效：追赶式恢复

如果从节点发生故障，然后顺利重启，或者主从节点之间的网络发生中断，则从节点可以通过向主节点请求故障期间的日志，并且将日志应用到本地来追赶主节点，从而恢复正常状态。

主节点失效：节点切换

如果主节点发生故障，选择某个从节点将其升级为主节点，同时更新客户端的主节点的信息。切换可以手动进行，也可以自动进行。

自动切换的步骤如下：

1. 确认主节点失效（心跳检测）。
2. 选举新的主节点（共识算法）。
3. 重新配置系统使新主节点生效（修改客户端配置以及原主节点上线之后降级为从节点）。

切换过程存在的问题：

• 如果使用了异步复制，并且新的主节点并未和原主节点同步，则原主节点上线之后可能会尝试将未完成复制的更改发送到新的主节点，从而产生冲突。常见的解决方案是将未完成复制的更改丢弃，这会违背持久化的承诺。
• 如果有外部系统依赖于数据库的内容，丢弃数据的方案会产生很严重的问题（可能会导致数据泄露）。
• 在某些故障下，会发生两个节点同时都认为自己是主节点的情况（称为脑裂），这可能会导致数据丢失或者破坏。
• 如何设置合适的超时时间来检测主节点失效。

复制日志的实现

原书中描述的是基于语句的复制，基于预写日志的复制，基于行的逻辑日志的复制等。下面将预写日志改为物理日志，将语句和行归为逻辑日志。之所以这样，是因为根据我所看过的一些资料（包括 CMU-15445）都将语句归为逻辑日志，而基于行的复制根据书上的说法，它和存储引擎解耦，同时书上也称其为基于行的逻辑日志的复制，所以我将两者都归为逻辑日志。而把预写日志改为物理日志，是因为书上说预写日志描述的是数据的字节级更改，按照这个说法，明显是预写日志的物理日志模式（CMU-15445 中描述了预写日志的三个日志模式：物理日志，逻辑日志，混合日志）。

基于物理日志的复制

解释：主节点将物理日志发送给从节点。

缺点：由于物理日志描述的是数据的字节级更改，这种复制方案和存储引擎紧密耦合，此时主从节点必须使用相同版本的存储引擎。所以在进行数据库升级时，只能首先将主从节点停机，再进行升级。如果复制方案允许从节点的版本比主节点更高，则可以首先将从节点升级，然后将从节点作为新的主节点，从而实现不停机升级。

基于逻辑日志的复制

解释：分为基于语句的复制和基于行的复制，主节点将逻辑日志（和物理存储引擎解耦的日志格式）发送给从节点。

缺点：如果使用基于语句的复制，则某些语句可能在不同节点产生不同的执行结果。例如：语句使用非确定性函数（NOW，RAND），语句依赖于数据库现有数据，有副作用的语句（触发器、存储过程、用户定义的函数）。

优点：主从节点可以运行不同版本的存储引擎，甚至是不同的存储引擎。对于外部应用程序，逻辑日志格式也更容易解析。

基于触发器的复制

解释：之前的复制都是由 DBMS 实现的，但在某些情况下可能需要更高的灵活性，这时需要将复制交给应用程序实现。一种方法是让应用程序读取数据库日志从而获取数据更改，另一种方法是使用触发器和存储过程，当发生数据更改时自动执行存储过程，将数据更改记录到单独的表中，应用程序通过访问该表来获取数据更改。

分析：此复制方式开销更高，也更容易出错或者暴露一些限制，但是具有更高的灵活性。

复制滞后问题

如果使用异步复制，则会出现主节点和从节点的数据不一致的情况，这种不一致只是暂时的状态。如果停止写数据库，则从节点最终会追赶上主节点，这被称为最终一致性。虽然主从节点最终会保持一致，但是暂时的不一致会引发各种问题，下面将讨论相关问题和解决方案。

写后读

问题：用户写入数据之后立即读取这些数据，如果读请求被发送给滞后的从节点，则用户看不到刚才写入的数据。

解决：此时，我们需要保证写后读一致性（也称为读写一致性），该一致性要求用户能够立即看到自己最近写入的数据，但是不保证其他用户能够立即看到这些数据。系统可以通过跟踪用户最近写入的时间戳，来保证将读请求发送给包含对应数据的节点。

单调读

问题：用户执行两次相同的查询，对应的读请求分别被路由两个不同的从节点，并且第二次查询访问的从节点比第一次查询访问的从节点更滞后。这会导致用户首先看到新数据，然后看到旧数据，就好像数据被回滚一样。

解决：此时，我们需要保证单调读一致性，该一致性要求用户进行多次读取时，不会先读到新数据再读到旧数据，即读取的数据对应的时间戳是单调递增的。系统可以总是将同一用户的读请求路由到同一个节点来保证单调读。

前缀读

问题：存在因果关系的数据被划分到不同的分区，用户在读取数据时可能会先看到果后看到因。

解决：此时，我们需要保证前缀读一致性，该一致性要求按照写入数据的顺序读取数据。对于未分区的单主数据库而言，数据总是按照因果关系的顺序写入数据库^[1]，在读取数据时也总是按照因果关系的顺序读取，因此不会发生该异常。但是，如果数据被划分到不同分区，不同分区独立运行，无法保证分区之间的从节点按照因果关系的顺序写入数据^[2]，此时将会发生异常。简单的想法是在复制日志中记录时间戳，但是由于存在时钟偏差问题，该方法不可行。一种解决方案是将具有因果关系的写入都交给一个分区完成，但是这样做的效率很低。另一种解决方案是使用版本向量技术跟踪因果关系，这将在无主复制的检测并发写中进行讨论。PS：这部分是按照我的理解描述的，可能存在错误。

多主复制

工作原理

系统中包含多个主节点，每个主节点都可以接收写请求，并且需要将更改发送给其他主节点和自己的从节点。

使用场景

多数据中心：为了容忍数据中心级别的故障或者使数据库更接近用户，可以把数据库的副本存储在多个数据中心。如果使用主从复制，主节点只能存在于某个数据中心，所有写请求都必须经过该数据中心。如果使用多主复制，则可以为每个数据中心设置一个主节点，在数据中心内部使用主从复制，主节点之间通常使用异步复制进行同步。

多主复制相比主从复制在多数据中心场景下的优势：写入延迟更低，对网络性能的依赖更低，能够容忍数据中心失效。缺点是，如果使用异步复制，多个主节点同时更改相同的数据时会产生写冲突。

处理写冲突

冲突检测

如果使用异步复制，那么多个主节点可以同时更改相同的数据，并且只能在稍后的复制过程中检测到冲突。

如果使用同步复制，每次只能进行一个写请求，无法发挥多个主节点的优势，那还不如直接使用主从复制。

冲突避免

可以在应用层保证对相同数据的写请求路由到相同的数据中心，但是在某些时候需要改变事先指定的数据中心，例如在数据中心故障或者用户移动到其他位置导致离某个数据中心更近时，写请求将会被路由到其他数据中心。

冲突解决

可能的解决方式如下：

• 为每个写请求分配唯一的 ID（时间戳、随机数、UUID、哈希值），然后按照某种规则选择特定的写请求。
• 为每个节点分配唯一的 ID，然后按照某种规则确定优先级。
• 将多个写入的值合并。
• 保存冲突信息，然后在应用层解决冲突。

在应用层解决冲突是最合理的方式，可以在写入时调用用户定义的冲突处理程序解决，还可以保留多个写入值，然后在读取时调用程序或者通知用户解决。还有一些自动解决冲突的方法，包括使用无冲突的复制数据类型（CRDT）、可合并的持久数据结构、操作转换算法。

拓扑结构

复制的拓扑结构描述了写日志从一个节点传播到其他节点的通信路径，包括全部至全部型拓扑（完全图）、环形拓扑、星形拓扑等。在环形和星形拓扑中，写日志需要经过多个节点才能传播到所有节点，为了避免循环复制（自己的写日志被传播给自己，然后又进行一轮传播），在复制日志中都会记录已传播节点的标识符。

星形和环形拓扑的问题是单点故障会影响写日志的传播，这可以通过在故障时重新配置拓扑结构解决。而全部至全部型拓扑的问题是在传播时写日志的因果顺序无法保证（参考复制滞后问题中的前缀读）。

无主复制

工作原理

客户端并行地将写请求发送给多个节点，如果得到多数节点的确认，则认为写入成功。读取时也是并行地从多个节点上读取数据，此时可能得到多个不同的值（由于复制滞后），系统会使用某种机制确定新值以及更新旧值。

读修复和反熵

当节点失效之后重新上线，可以使用以下两种机制进行追赶。

读修复

解释：客户端并行读取多个节点，获取的数据中包含版本号，以判断数据的新旧，同时会更新包含旧数据的节点。

分析：该方法适合读密集的场景，不然包含旧数据的节点得不到更新。

反熵

解释：使用后台进程检测节点之间数据的差异，然后将新数据复制到包含旧数据的节点。

分析：和基于主节点的复制不同，此过程不保证按照特定的顺序复制数据，并且会引入明显的滞后。

读写仲裁（quorum）

如果有 \(n\) 个节点参与仲裁，写入时需要得到 \(w\) 个节点的确认，读取时至少查询 \(r\) 个节点，则只要 \(w+r>n\)，读取的节点中就一定会包含最新值。满足该条件的读/写操作被称为仲裁读/写（或者法定票数读/写），可以将 \(w\) 和 \(r\) 看作是确认读/写操作是否有效的最低票数。

通常会将 \(n\) 设置为奇数，将 \(w\) 和 \(r\) 设置为 \(\frac{n+1}{2}\)。当然也可以根据实际情况做调整，例如对于读多写少的负载，设置 \(w=n\) 和 \(r=1\) 比较合适，这样读取速度很快，但是只要有一个节点失效就会导致仲裁写失败。

通常读/写请求总是并行发送给所有节点，参数 \(w\) 和 \(r\) 只是决定要等待的节点数。如果可用的节点数小于 \(w\) 或 \(r\)，则读/写操作就会返回错误。

也可以将 \(w\) 和 \(r\) 设置为较小的值，使得 \(w+r\leq n\)，不满足仲裁条件。此时可能读取到的值都是旧值，但是可用获得更低的延迟和更高的可用性。即使在 \(w+r>n\) 的情况下，也可能存在只读取到旧值的边界条件。

如果需要更高的容错性，可用使用宽松的读写仲裁：写入和读取仍需要 \(w\) 和 \(r\) 个节点确认，但是可以利用 \(n\) 个节点之外的其它节点（参与仲裁的节点数量为 \(n\)，集群中的节点数量大于 \(n\)）。例如，当 \(n\) 个节点中的多数节点失效时，客户端会向额外的节点发送读/写请求，当失效节点重新上线时，将额外节点中的新值复制到这些滞后的节点。

检测并发写

和多主复制类似，无主复制同样存在写冲突。在多主复制的处理写冲突中介绍过，可以为每个写请求分配一个时间戳，然后选择保留时间戳最大的写请求，这被称为最后写入者获胜（last write wins，LWW）。LWW 可以实现最终一致性，代价是牺牲数据的持久性，因为小于最大时间戳的并发写入都会被覆盖，由于时钟偏差，该算法甚至可能覆盖非并发写入。是否使用该算法依据实际场景而定，例如在缓存系统中覆盖是可以接受的，则可以使用该算法。

我们可以使用版本向量技术来判断两个写操作是否并发。如果一个写操作发生在另一个写操作之前（依赖关系/因果关系），则后面的写操作可以覆盖前面的写操作。如果是并发的，就需要处理写冲突问题。算法的工作流程见书上，本质上就是通过在写之前读，来获取数据的当前值以及版本向量（该数据在所有节点上的版本号的集合），之后的写操作只会覆盖服务器中低版本的数据，从而并发写（高版本）的数据得到保留。PS：书上只是简单提了一下，还有很多细节没说。

---

1. 首先因被写入数据库，然后因被读取，从而产生果，之后果才被写入数据库。 ↩︎

2. 参考注 1，分区之间的主节点总是按照因果关系的顺序写入数据，但是分区之间的从节点就无法保证写入顺序。 ↩︎