主从复制存在一个明显的缺点：系统只有一个主节点，而所有写入都必须经由主节点。如果由于某种原因，例如与主节点之间的网络中断而导致主节点无法连 接，主从复制方案就会影响所有的写入操作。
对主从复制模型进行自然的扩展，则可以配置多个主节点，每个主节点都可以接受写操作，后面复制的流程类似：处理写的每个主节点都必须将该数据更改转发到所有其他节点。这就是多主节点（也称为主主，或主动/主动）复制。此时，每个主节点还同肘扮演其他主节点的从节点。
为了容忍整个数据中心级别故障或者更接近用户，可以把数据库的副本横跨多个数据中心。而如果使用常规的基于主从的复制模型，主节点势必只能放在其中的某一个数据中心，而所有写请求都必须经过该数据中心。
可以对比一下在多数据中心环境下，部署单主节点的主从复制方案与多主复制方案之间的差异：
- 性能：对于主从复制，每个写请求都必须经由广域网传送至主节点所在的数据中心。这会大大增加写入延迟，并基本偏离了采用多数据中心的初衷（即就近访问）。而在多主节点模型中，每个写操作都可以在本地数据中心快速响应，然后采用异步复制方式将变化同步到其他数据中心。
- 容忍数据中心失效：对于主从复制，如果主节点所在的数据中心发生故障，必须切换至另一个数据中心，将其中的一个从节点被提升为主节点。在多主节点模型中，每个数据中心则可以独立于其他数据中心继续运行，发生故障的数据中心在恢复之后更新到最新状态。
- 容忍网络问题：数据中心之间的通信通常经由广域网，它往往不如数据中心内的本地网络可靠。对于主从复制模型，由于写请求是同步操作，对数据中心之间的网络性能和稳定性等更加依赖。多主节点模型则通常采用异步复制，可以更好地容忍此类问题，例如临时网络闪断不会妨碍写请求最终成功。
尽管多主复制具有上述优势，但也存在一个很大的缺点：不同的数据中心可能会同时修改相同的数据，因而必须解决潜在的==写冲突==。
这种情况下，每个设备都有一个充当主节点的本地数据库（用来接受写请求），然后在所有设备之间采用异步方式同步这些多主节点上的副本，同步滞后可能是几小时或者数天，具体时间取决于设备何时可以再次联网。
如果是主从复制数据库，第二个写请求要么会被阻塞直到第一个写完成，要么被中止（用户必须重试）。然而在多主节点的复制模型下，这两个写请求都是成功的，并且只能在稍后的时间点上才能异步检测到冲突，那时再要求用户层来解决冲突为时已晚。
处理冲突最理想的策略是避免发生冲突，即如果应用层可以保证对特定记录的写请求总是通过同一个主节点，这样就不会发生写冲突。
例如，一个应用系统中，用户需要更新自己的数据，那么我们确保特定用户的更新请求总是路由到特定的数据中心，并在该数据中心的主节点上进行读/写。不同的用户则可能对应不同的主数据中心（例如根据用户的地理位置来选择）。从用户的角度来看，这基本等价于主从复制模型。
实现收敛的冲突解决有以下可能的方式：
- 给每个写入分配唯一的 ID，例如，一个时间戳，一个足够长的随机数，一个 UUID 或者一个基于键-值的哈希，挑选最高 ID 的写入作为胜利者，并将其他写入丢弃。如果基于时间戳，这种技术被称为==最后写入者获胜==。虽然这种方法很流行，但是很容易造成数据丢失。我们将在本章最后部分来详细解释。
- 为每个副本分配一个唯一的 ID，并制定规则，例如序号高的副本写入始终优先于序号低的副本。这种方法也可能会导致数据丢失。
- 以某种方式将这些值合并在一起。例如，按字母顺序排序，然后拼接在一起
- 利用预定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突（可能会提示用户）。
解决冲突最合适的方式可能还是依靠应用层，所以大多数多主节点复制模型都有工具来让用户编写应用代码来解决冲突。可以在写入时或在读取时执行这些代码逻辑：
- 在写入时执行。只要数据库系统在复制变更日志时检测到冲突，就会调用应用层的冲突处理程序。例如，Bucardo 支持编写一段 Perl 代码。这个处理程序通常不能在线提示用户，而只能在后台运行，这样速度更快。
- 在读取时执行。当检测到冲突时，所有冲突写入值都会暂时保存下来。下一次读取数据时，会将数据的多个版本读返回给应用层。应用层可能会提示用户或自动解决冲突，并将最后的结果返回到数据库。CouchDB 采用了这样的处理方式。
注意，冲突解决通常用于单个行或文档，而不是整个事务。因此，如果有一个原子事务包含多个不同写请求（如第 7 章），每个写请求仍然是分开考虑来解决冲突。
有些冲突是显而易见的。在图 5-7 的例子中，两个写操作同时修改同一个记录中的同一个字段，并将其设置为不同的值。 毫无疑问，这就是一个冲突。而其他类型的冲突可能会非常微妙，更难以发现。
环形和星形拓扑的问题是，如果某一个节点发生了故障，在修复之前，会影响其他节点之间复制日志的转发。可以采用重新配置拓扑结构的方法暂时排除掉故障节点。 在大多数部署中，这种重新配置必须手动完成。而对于链接更密集的拓扑（如全部到全部），消息可以沿着不同的路径传播，避免了单点故障，因而有更好的容错性。
但另一方面，全链接拓扑也存在一些自身的问题。主要是存在某些网络链路比其他链路更快的情况（例如由于不同网络拥塞），从而导致复制日志之间的覆盖，如图 5-9 所示。
这里涉及到一个因果关系问题类似于在本章前面 ”前缀一致读” 所看到的：更新操作一定是依赖于先前完成的插入，因此我们要确保所有节点上一定先接收插入日志，然后再处理更新。在每笔写日志里简单地添加时间戳还不够，主要因为无法确保时钟完全同步，因而无法在主节点 2 上正确地排序所收到日志（参见第 8 章）。
为了使得日志消息正确有序，可以使用一种称为==版本向量==（version vectors）的技术，本章稍后将讨论这种技术（参见本章后面的 “检测并发写入”）。
对于某些无主节点系统实现，客户端直接将其写请求发送到多副本，而在其他一些实现中，由一个协调者节点代表客户端进行写入，但与主节点的数据库不同，协调者并不负责写入顺序的维护。我们很快就会看到，这种设计上的差异对数据库的使用方式有着深刻的影响。
假设一个三副本数据库，其中一个副本当前不可用。在基于主节点复制模型下，如果要继续处理写操作，则需要执行切换操作。
对于无主节点配置，则不存在这样的切换操作。图 5-10 展示了所发生的情况：用户 1234 将写请求并行发送到三个副本，有两个可用副本接受写请求，而不可用的副本无法处理该写请求。如果假定三个副本中有两个成功确认写操作 ，用户 1234 收到两个确认的回复之后，即可认为写入成功。客户端完全可以忽略其中一个副本无法写入的情况。
现在设想一下，失效的节点之后重新上线，而客户端又开始从中读取内容。由于节点失效期间发生的任何写入在该节点上都尚未同步，因此读取可能会得到过期的数据。为了解决这个问题，当一个客户端从数据库中读取数据时，它不是向一个副本发送请求，而是并行地发送到多个副本。客户端可能会得到不同节点的不同响应，包括某些节点的新值和某些节点的旧值。可以采用版本号技术确定哪个值更新（参见本章后面的 “检测并发写入”）。
复制模型应确保所有数据最终复制到所有的副本，它如何赶上中间错过的那些写请求呢？
Dynamo 风格的数据存储系统经常使用以下两种机制：
-
读修复。当客户端并行读取多个副本时，可以检测到过期的返回值。例如，在图 5-10 中，用户 2345 从副本 3 获得的是版本 6，而从副本 1 和 2 得到的是版本 7。客户端可以判断副本 3 一个过期值，然后将新值写入到该副本。这种方法主要适合那些被频繁读取的场景。
-
反熵过程。此外，一些数据存储有后台进程不断查找副本之间数据的差异，将任何缺少的数据从一个副本复制到另一个副本。与基于主节点复制的复制日志不同，此反墒过程并不保证以特定的顺序复制写入，并且会引入明显的同步滞后。
我们知道，成功的写操作要求三个副本中至少两个完成，这意味着至多有一个副本可能包含旧值。因此，在读取时需要至少向两个副本发起读请求，通过版本号可以确定一定至少有一个包含新值。如果第三个副本出现停机或响应缓慢，则读取仍可以继续并返回最新值。
把上述道理推广到一般情况，==如果有 n 个副本，写入需要 w 个节点确认，读取必须至少查询 r 个节点，则只要 w + r > n，读取的节点中一定会包含最新值==。
在 Dynamo 风格的数据库中，参数 n、w 和 r 通常是可配置的。一个常见的选择是设置 n 为某奇数（通常为 3 或 5），w = r = ( n+1) /2（向上舍入）。也可以根据自己的需求灵活调整这些配置。例如，对于读多写少的负载，设置 w=n 和 r = 1 比较合适，这样读取速度更快，但是一个失效的节点就会使得数据库所有写入因无法完成 quorum 而失败。
即使在 w + r > n 的情况下，也可能存在返回旧值的边界条件。这主要取决于具体实现，可能的情况包括：
- 如果采用了 sloppy quorum（参阅本章后面的宽松的 quorum 与数据回传），写操作的 w 节点和读取的 r 节点可能完全不同，因此无法保证读写请求一定存在重叠的节点。
- ==如果两个写操作同时发生，则无法明确先后顺序==。这种情况下，唯一安全的解决方案是合并并发写入（参见本章前面的 “处理写冲突”）。如果根据时间戳（最后写入获胜）挑选胜者，则由于时钟偏差问题，某些写入可能会被错误地抛弃。
- ==如果写操作与读操作同时发生，写操作可能仅在一部分副本上完成。此时，读取时返回旧值还是新值存在不确定性。== (3)
- ==如果某些副本上已经写入成功，而其他一些副本发生写入失败（例如磁盘已满），且总的成功副本数少于 w，那些已成功的副本上不会做回滚。这意味着尽管这样的写操作被视为失败，后续的读操作仍可能返回新值。== (4)
- 如果具有新值的节点后来发生失效，但恢复数据来自某个旧值，则总的新值副本数会低于 w，这就打破了之前的判定条件。
- 即使一切工作正常，也会出现一些边界情况，如第 9 章所介绍的 “可线性化与 quorum”。
因此，虽然 quorum 设计上似乎可以保证读取最新值，但现实情况却往往更加复杂。Dynamo 风格的数据库通常是针对==最终一致性==场景而优化的。
==这里通常无法得到本章前面的 “复制滞后问题” 中所罗列的一致性保证，包括写后读、单调读、前缀一致读等，因此前面讨论种种异常同样会发生在这里。==
Tips:
上面 (3) (4) 两种情况都存在的一个问题：如何确定最高版本号是已经成功提交的数据？在本书中，处理方法是读的时候不去判断，只返回最新的数据即可。实际上如果要判断的话，需要继续读其他的副本，直到读到的最高版本号副本出现了 w 次，但这种方法已经违背了 Quorum 的初衷。
我们下面的讨论也都是基于读的时候只返回读到的最新数据。
- 写后读：TODO
- 单调读：TODO
- 前缀一致性读：TODO
从运维角度来看，监视数据库是否返回最新结果非常重要。即使应用程序可以容忍读取旧值，也需要仔细了解复制的当前运行状态。如果已经出现了明显的滞后，它就是个重要的信号提醒我们需要采取必要措施来排查原因（例如网络问题或节点超负荷）。
对于主从复制的系统，数据库通常会导出复制滞后的相关指标，可以将其集成到统一监控模块。原理大概是这样，由于主节点和从节点上写入都遵从相同的顺序，而每个节点都维护了复制日志执行的当前偏移晕。通过对比主节点和从节点当前偏移扯的差值，即可衡量该从节点落后于主节点的程度。
然而，对于无主节点复制的系统，并没有固定的写入顺序，因而监控就变得更加困难。而且，如果数据库只支持读时修复（不支持反墒），那么旧值的落后就没有一个上限。例如如果一个值很少被访问，那么所返回的旧值可能非常之古老。
quorum 并不总如期待的那样提供高容错能力。一个网络中断可以很容易切断一个客户端到多数数据库节点的链接。尽管这些集群节点是活着的，而且其他客户端也确实可以正常链接，但是对于断掉链接的客户端来讲，情况无疑等价于集群整体失效。这种情况下，很可能无法满足最低的 w 和 r 所要求的节点数，因此导致客户端无法满足 quorum 要求。
在一个大规模集群中（节点数远大于 n 个），客户可能在网络中断期间还能连接到某些数据库节点，但这些节点又不是能够满足数据仲裁的那些节点。此时，数据库设计者就面临着一个选择：
- 如果无法达到 w 或 r 所要求 quorum，将错误明确地返回给客户端？
- 或者，我们是否应该接受该写请求，只是将它们暂时写入一些可访问的节点中？注意，这些节点并不在 n 个节点集合中。
后一种方案称之为 ==Sloppy Quorums==，写入和读取仍然需要 w 和 r 个成功的响应，但包含了那些并不在先前指定的 n 个节点。
一旦网络问题得到解决，临时节点需要把接收到的写入全部发送到原始主节点上。这就是所谓的数据回传（或暗示移交，==hinted handoff==）。
可以看出，sloppy quorum 对于提高写人可用性特别有用：只要有任何 w 个节点可用，数据库就可以接受新的写入。然而这意味着，即使满足 w + r> n，也不能保证在读取某个 key 时，一定能读到最新值，因为新值可能被临时写入 n 之外的某些节点且尚未回传过来 。
Dynamo 风格的数据库允许多个客户端对相同的主键同时发起写操作，即使采用严格的 quorum 机制也可能会发生写冲突。这与多主节复制类似，此外，由于读时修复或者数据回传也会导致并发写冲突。
一个核心问题是，==由于网络延迟不稳定或者局部失效，请求在不同的节点上可能会呈现不同的顺序==。如图 5-12 所示，对于包含三个节点的数据系统，客户端 A 和B 同时向主键 X 发起写请求：
- 节点 1 收到来自客户端 A 的写请求，但由于节点失效，没有收到客户端 B 的写请求。
- 节点 2 首先收到 A 的写请求，然后是 B 的写请求。
- 与节点 2 相反，节点 3 首先收到 B 的写请求，然后是 A 的写请求。
如果节点每当收到新的写请求时就简单地覆盖原有的主键，那么这些节点将永久无法达成一致，如图 5-12 中的所示，节点 2 认为 X 的最终值是 B，而其他节点认为值是 A。
我们已经在本章前面的 “处理写冲突" 简要介绍了一些解决冲突的技巧。在总结本章之前，我们来更详细地探讨这个问题。
一种实现最终收敛的方法是，每个副本总是保存最新值，允许覆盖并丢弃旧值。那么，假定每个写请求都最终同步到所有副本，只要我们有一个明确的方法来确定哪一个写入是最新的，则副本可以最终收敛到相同的值。
==这个想法其实有些争议，关键点在于前面所提到关于如何定义 “最新”==。在图 5-12 的例子中，当客户端向数据库节点发送写请求时，一个客户端无法意识到另一个客户端，也不清楚哪一个先发生。==其实，争辩哪个先发生没有太大意义，当我们说支持写入并发，也就意味着它们的顺序是不确定的==。
==即使无法确定写请求的 “自然顺序”，我们可以强制对其排序==。例如，为每个写请求附加一个时间戳，然后选择最新即最大的时间戳，丢弃较早时间戳的写入。这个冲突解决算法被称为==最后写入者获胜==（last write wins, LWW）
LWW 可以实现最终收敛的目标，但是以牺牲数据持久性为代价。如果同一个主键有多个并发写，即使这些并发写都向客户端报告成功（因为完成了写入 w 个副本），但最后只有一个写入值会存活下来，其他的将被系统默默丢弃。此外，LWW 甚至可能会删除那些非并发写，我们将在第 8 章 ”时间戳与事件顺序” 中举例说明。
如何判断两个操作是否是并发呢？首先为了建立起一个快速的直觉判断，一些例子：
- 图 5-9 中，两个写入不是并发的：A 的插入操作发生在 B 的增量修改之前，B 的递增是基于 A 插入的行。换句话说，B 后发生，其操作建立在 A 基础之上。A和 B 属于因果依赖关系。
- 另一个例子，图 5-12 中的两个写入则是并发的：每个客户端启动写操作时，并不知道另一个客户端是否也在同一个主键上执行操作。因此，操作之间不存在因果关系。
如果 B 知道 A，或者依赖于 A，或者以某种方式在 A 基础上构建，则称操作 A 在操作 B 之前发生。这是定义何为并发的关键。事实上，我们也可以简单地说，如果两个操作都不在另一个之前发生，那么操作是并发的（或者两者都不知道对方）。
因此，对于两个操作 A 和 B，一共存在三种可能性：A 在 B 之前发生，或者 B 在 A 之前发生，或者 A 和 B 并发。我们需要的是一个算法来判定两个操作是否发。如果一个操作发生在另一个操作之前，则后面的操作可以覆盖较早的操作。如果属于并发，就需要解决潜在的冲突问题。
并发性 、时间和相对性
通常如果两个操作 “同时” 发生，则称之为并发，然而事实上，==操作是否在时间上重叠并不重要==。==由于分布式系统中复杂的时钟同步问题（第 8 章将会详细讨论），现实当中，我们很难严格确定它们是否同时发生==。
为更好地定义并发性，我们并不依赖确切的发生时间，即不管物理的时机如何，==如果两个操作并不需要意识到对方，我们即可声称它们是并发操作==。
我们来看一个确定操作并发性的算法，即两个操作究竟属于并发还是一个发生在另一个之前（依赖关系）。简单起见，我们先从只有一个副本的数据库开始，在阐明其原理之后，将其推广到有多个副本的无主节点数据库。
图 5-13 的例子是两个客户端同时向购物篮车加商品，初始时购物车为空。然后两个客户端向数据库共发出五次写入操作。
- 客户端 1 首先将牛奶加入购物车。这是第一次写入该主键的值，服务器保存成功然后分配版本 1 服务器将值与版本号一起返回给该客户端 1。
- 客户端 2 将鸡蛋加入购物车，此时它并不知道客户端l己添加了牛奶，而是认为鸡蛋是购物车中的唯一物品。服务器为此写入并分配版本 2，然后将鸡蛋和牛奶存储为两个单独的值，最好将这两个值与版本号 2 返回给客户端 2。
- 同理，客户端 1 也并不意识上述步骤 2，想要将面粉加入购物车，且以为购物车的内容应该是 [牛奶, 面粉]，将此值与版本号 1一起发送到服务器。服务器可以从版本号中知道 [牛奶, 面粉] 的新值要取代先前值 [牛奶]，但值 [鸡蛋] 则是新的并发操作。因此，服务器将版本 3 分配给 [牛奶, 面粉] 并覆盖版本 1 的 [牛奶]，同时保留版本 2 的值 [鸡蛋]，将二者同时返回给客户端 1。
- 同时，客户端 2 想要加入火腿，也不知道客户端 1 刚刚加了面粉。==其在最后一个响应中从服务器收到的两个值是 [牛奶] 和 [蛋]，现在合并这些值==，并添加火腿形成一个新的值 [鸡蛋, 牛奶, 火腿]。它将该值与前一个版本号 2一起发送到服务器。服务器检测到版本 2 会覆盖 [鸡蛋]，但与 [牛奶, 面粉] 是同时发生，所以设置为版本 4 并将所有这些值发送给客户端 2。
- 最后，客户端 1 想要加培根。它以前在版本 3 中从服务器接收 [牛奶，面粉] 和 [鸡蛋]，所以合并这些值，添加培根，并将最终值 [牛奶, 面粉, 鸡蛋, 培根] 连同版本号 3 来覆盖 [牛奶, 面粉]，但与 [鸡蛋, 牛奶, 火腿] 并发，所以服务器会保留这些并发值。
图 5-13 操作之间的数据流可以通过图 5-14 形象展示。箭头表示某个操作发生在另一个操作之前，即后面的操作 “知道” 或是 “依赖” 于前面的操作。在这个例子中，因为总有另一个操作同时进行，所以每个客户端都没有时时刻刻和服务器上的数据保持同步。但是，新版本值最终会覆盖旧值，且不会发生已写入值的丢失。
需要注意的是，服务器判断操作是否并发的依据主要依靠对比版本号，而并不需要解释新旧值本身（值可以是任何数据结构）。算法的工作流程如下：
- 服务器为每个主键维护一个版本号，每当主键新值写入时递增版本号，并将新版本号与写入的值一起保存。
- 当客户端读取主键时，服务器将返回所有（未被覆盖的）当前值以及最新的版本号。且要求写之前，客户必须先发送读请求。
- 客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值，这样就可以像购物车例子那样一步步链接起多个写入的值。
- 当服务器收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值（==因为知道这些值已经被合并到新传入的值集合中==），但必须保存更高版本号的所有值（因为这些值与当前的写操作属于并发）。
当写请求包含了前一次读取的版本号时，意味着修改的是基于以前的状态。如果一个写请求没有包含版本号，它将与所有其他写入同时进行，不会覆盖任何已有值，其传入的值将包含在后续读请求的返回值列表当中。
上述算法可以保证不会发生数据丢弃，但不幸的是，客户端需要做一些额外的工作：即如果多个操作并发发生，则客户端必须通过合并并发写入的值来继承旧值。
合并本质上与先前讨论的多节点复制冲突解决类似，一个简单的方法是基于版本号或时间戳（即最后写入获胜）来选择其中的一个值，但这意味着会丢失部分数据。所以，需要在应用程序代码中额外做些工作。
以购物车为例，合并并发值的合理方式是包含新值和旧值（union 操作）。图 5-14 中，两个客户端最后的值分别是 [牛奶, 面粉, 鸡蛋, 熏肉] 和 [鸡蛋, 牛奶, 火腿]。注意，虽然牛奶和鸡蛋只是写入了一次，但它在两个客户端中均有出现。合并的最终值应该是 [牛奶, 面粉, 鸡蛋, 培根, 火腿]，其中去掉了重复值。
然而，设想一下人们也可以在购物车中删除商品，此时把并发值都合并起来可能会导致错误的结果：如果合并了两个客户端的值，且其中有一个商品被某客户端删除掉，则被删除的项目会再次出现在合并的终值中。为了防止该问题，项目在删除时不能简单地从数据库中删除，系统必须保留一个对应的版本号以恰当的标记该项目需要在合并时被剔除。这种删除标记被称为==墓碑==（tombstone）。
图 5-13 中的示例只有一个副本。如果存在多个副本但没有主节点，算法又该如何呢？
图 5-13 使用单个版本号来捕获操作之间的依赖关系，当多个副本同时接受写入时，这是不够的。因此我们需要为每个副本和每个主键均定义一个版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本看到的版本号。通过这些信息来指示要覆盖哪些值、该保留哪些并发值。