复制（replication）意味着在通过网络连接的多台机器上保留相同数据的副本：
如果要复制的数据不随时间变化，复制就很简单；只需把数据复制到每个节点一次，复制的全部难点在于处理被 复制数据的 变更。
复制与备份的概念不同，二者目的不同，副本会迅速把一个节点上的写入反映到其他节点，而备份保存的是数据在过去某一时刻的快照，以便恢复到先前状态。如果不慎删除了某些数据，复制帮不上忙，因为删除操作也会传播到所有副本；要恢复这些数据，仍然需要备份。
也称 主从复制（master-salve replication）。
每个保存数据库拷贝的节点都称为一个 副本（replica） 。存在多个副本时，一个问题不可避免：如何确保所有数据最终都出现在所有副本上？
基于领导者的复制（leader-based replication），也称 主备复制（primary-backup）或 主动/被动复制（active/passive）。
如果数据库做了分片，每个分片都有一个领导者，不同分片的领导者可以位于不同节点，但每个分片仍必须有且一个领导者。
单主复制，是 PostgreSQL、MySQL、SQL Server 许多关系数据库的内置功能。MongoDB、DynamoDB 等文档数据库、 Kafka 等消息代理、Raft 等许多共识算法同样以单个领导者为基础。TiDB、etcd、RabbitMQ 法定人数队列等系统用它来实现复制，并在原领导者失效时自动选举新领导者。
复制究竟 同步（synchronous）进行还是 异步（asynchronous）进行。在关系型数据库中，这通常是一个配置项。
同步复制的优点是，追随者保证拥有与领导者一致的最新数据副本。领导者突然失效时，可以确信数据仍可从追随者取得。缺点是，如果同步追随者没有响应——无论因为崩溃、网络故障还是其他原因——写入就无法继续。领导者必须阻塞所有写入，直至同步副本重新可用。
所有追随者都设为同步并不现实，任意一个节点停机都会拖垮整个系统，实践中，数据库所谓的同步复制，通常是指 一个 追随者同步，其余追随者异步。如果同步追随者不可用或过慢，就把某个异步追随者切换为同步。这样可以保证至少有两个节点持有最新数据：领导者和一个同步追随者。这种配置有时也称为 半同步（semi-synchronous） 。
有时系统会同步更新多数副本，其余少数副本异步更新。
有时，基于领导者的复制会配置为完全异步。如果领导者失效且无法恢复，所有尚未复制到追随者的写入都会丢失。也就是说，即使已经向客户端确认成功，写入仍不保证持久。不过，完全异步配置也有一个优点：即使所有追随者都已落后，领导者仍可继续处理写入。
有时需要设置新的追随者，也许是为了增加副本数量，也许是为了替换失效的节点。怎样才能确保新追随者拿到领导者数据的准确副本？
简单地把数据文件从一个节点复制到另一个节点通常不够，客户端一直在修改数据库内容，数据一直在变化。
可以锁住数据库，让磁盘上文件保持不变，但违背了高可用的目标。
还可以把复制日志归档到对象存储，再定期把数据库的快照保存到对象存储，就形成了一套很好的数据库备份与灾难恢复方案。
系统中的任何节点都可能停机，故障意外、计划内维护、重启机器安装内核补丁都有可能。
目标是：即使个别节点失效，整个系统仍能继续运行，并尽可能减小节点停机的影响。
每个追随者都会在本地磁盘上记录从领导者收到的数据变更。追随者可以从日志中得知故障发生前处理的最后一个事务。它随后连接领导者，请求自己断开期间发生的所有数据变更。应用完这些变更后，它便赶上领导者。
追随者恢复在概念上很简单，性能上可能很棘手，如果数据库写入吞吐量很高，或追随者离线很久，需要追赶的写入可能非常多。追赶期间，正在恢复的追随者和领导者都会承受很高负载——领导者还要把积压的写入发送给追随者。
而且领导者本地存的日志有可能只存一定时间，超过一定时间可能会删除。
领导者失效处理起来更加棘手：必须把一个追随者提升为新领导者，重新配置客户端以便把写入发给新领导者，并让其他追随者开始消费新领导者的数据变更。这个过程称为 故障切换（failover） 。
故障切换过程中有很多地方可能出错：
基于领导者的复制在底层究竟如何工作？实践中采用了几种不同的复制方式。如下：
领导者会记录自己执行的每个写入请求（即 语句），并把这份语句日志发送给追随者。对于关系数据库，这意味着每条 INSERT、UPDATE 或 DELETE 语句都会转发给追随者；每个追随者解析并执行这条 SQL 语句，就像它直接来自客户端一样。
这种复制方式有许多可能出错的地方：
NOW() 取得当前日期和时间，或用
RAND() 取得随机数UPDATE … WHERE <some condition>
），就必须在每个副本上按完全相同的顺序执行，否则可能产生不同结果。有多个事务并发执行时，这会成为限制。可以绕开这些问题，领导者在记录语句时，可以用固定的返回值替换非确定性函数调用。
B 树存储引擎需要预写日志才能可靠工作：每次修改都先写入 WAL，以便崩溃后把树恢复到一致状态。WAL 包含把索引和堆恢复到一致状态所需的全部信息，因此同一份日志也能用来在另一个节点上建立副本：领导者除了把日志写入磁盘，还通过网络把它发送给追随者。追随者处理日志后，就会构建出与领导者完全相同的文件副本。
PostgreSQL、Orcle 等数据库采用这种复制方式，其主要缺点是，日志在非常低的层次描述数据：WAL 记录了哪个磁盘块中的哪些字节发生变化。因此，复制与存储引擎紧密耦合。数据库从一个版本升级到另一个版本、存储格式随之改变时，通常无法在领导者和追随者上运行不同版本的数据库软件。
让复制和存储引擎使用不同的日志格式，从而使复制日志与存储引擎的内部实现解耦。这种复制日志称为 逻辑日志（logical log），以区别于存储引擎的（物理，physical）数据表示。
关系数据库的逻辑日志通常由一系列记录组成，以行的粒度描述对数据库表的写入：
修改多行的事务会生成多条这样的日志记录，随后再跟一条表示事务已经提交的记录。
MySQL 配置为基于行的复制时，除了 WAL 之外，还会维护一份称为 binlog 的独立逻辑复制日志。PostgreSQL 则把物理 WAL 解码成行插入、更新和删除事件，以实现逻辑复制。
由于逻辑日志与存储引擎的内部实现解耦，更容易保持向后兼容，因而领导者与追随者可以运行不同版本的数据库软件，也就能以极少的停机时间升级到新版本。
基于领导者的复制要求所有写入经过一个节点，但只读查询可以发往任意副本。
在这种 读扩展 架构中，只需增加追随者，便可提高只读请求的处理能力。不过，只适用于异步复制，节点越多，越可能有某个节点停机，因此完全同步的配置会极不可靠。
同时在领导者和追随者上执行同一查询，结果可能不同，因为追随者尚未反映所有写入。这种不一致只是暂时的——如果停止写入并等待一段时间，追随者最终会赶上领导者，恢复一致。因此，这种现象称为 最终一致性（eventual consistency） 。
许多应用程序允许用户提交数据，随后查看自己提交的内容。
异步复制在这里会产生问题，用户刚写入数据不久便查看它，新数据可能尚未到达该副本，用户看来 自己刚刚提交的数据仿佛丢失了。
种情况下需要 写后读一致性（read-after-write consistency），也称 读己之写一致性（read-your-writes consistency）。
如何在基于领导者的复制系统中实现写后读一致性？有多种办法，例如：
同一用户通过多个设备访问服务，还可能需要提供 跨设备 写后读一致性。用户在一台设备上输入信息，随后在另一台设备上查看时，应当看到刚才输入的内容。
从异步追随者读取时，用户可能会看到 时光倒流。
用户连续几次从不同副本读取时，就可能发生这种情况。
单调读，保证这种异常不会发生。它弱于强一致性，却强于最终一致性。读取数据时仍可能看到旧值；单调读只保证同一用户顺序执行多次读取时，不会看到时间倒退，一旦读到较新的数据，以后就不会再读到更旧的数据。
实现单调读的一种办法，是确保每个用户始终从同一个副本读取（不同用户可以选择不同副本）。例如，可以根据用户 ID 的哈希选择副本，而不是随机选择。如果该副本失效，则需要把用户的查询重新路由到其他副本。
第三种复制延迟异常违反了因果关系，比如
这两句话之间存在因果依赖：Cake 夫人听到 Poons 先生的问题，然后作出回答。
现在设想第三个人通过追随者旁听这段对话。Cake 夫人的话经过复制延迟较小的追随者，Poons 先生的话经过延迟更大的追随者。于是，这位旁听者会听到：
防止这种异常需要另一种保证：一致前缀读（consistent prefix reads）。它保证，如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看到它们以相同顺序出现。
使用最终一致的系统时，值得认真考虑：需要理清楚对自己应用的表现。
对应用程序开发者而言，最简单的编程模型，是选择一个能为副本提供强一致性保证（例如线性一致性）和 ACID 事务 的数据库。这样就可以基本忽略复制带来的挑战，把数据库看作只有一个节点。2010 年代初兴起的 NoSQL 运动曾宣扬一种观点：这些特性会限制可伸缩性，大规模系统不得不接受最终一致性。
此后，许多数据库开始在提供强一致性和事务的同时，保留分布式数据库在容错、高可用和可伸缩性方面的优势。
单主复制有一个主要缺点：所有写入都必须经过唯一的领导者，无论出于什么原因，只要连接不上领导者，例如 客户端与领导者之间的网络中断，酒无法写入数据库。
每个处理写入的节点都必须把数据变更转发给其他所有节点。我们把这种配置称为 多主复制（multi-leader replication） ，也称 主动/主动复制（active/active） 或 双向复制（bidirectional replication） 。在这种配置中，每个领导者同时也是其他领导者的追随者。
与单主复制一样，多主复制也可以选择同步或异步。
在单个地区内使用多主配置通常没有多少意义，因为所得好处很少能抵消额外的复杂性。
设想一个数据库在多个地区都有副本，也许是为了在整个地区失效时仍能运行，也许是为了在地理上更接近用户。这种部署称为 地理分布式（geographically distributed）、跨地域分布式（geo-distributed）或 跨地域复制（geo-replicated）。采用单主复制时，领导者必须位于其中 一个 地区，所有写入都要经过该地区。
在多主配置中，每个 地区都可以有一个领导者。
比较单主与多主配置在多地区部署中的表现：
性能：单主每次写入都必须通过互联网发往领导者所在的地区，可能因为距离远延迟高容忍地区停机：在单主配置中，如果领导者所在的地区不可用，可以通过故障切换把另一个地区的追随者提升为领导者。在多主配置中，各地区可以彼此独立地继续运行；离线地区恢复上线后，复制会赶上进度。容忍网络问题：地区之间网络链路很关键，单主配置对地区链路很敏感，多主每个地区都有一个领导者一致性：单主系统可以提供可串行化事务等强一致性保证，多主系统能提供的一致性要弱得多。多主复制不如单主复制常见，但 MySQL、Oracle、SQL Server 等许多数据库仍提供支持。
复制拓扑（replication topology） 描述写入从一个节点传播到另一个节点时所经过的通信路径。
环形拓扑、星形拓扑、全对全拓扑。
环形和星形拓扑只要一个节点失效，就可能中断其他节点之间的复制消息流。连接更密集的拓扑 全对全 容错性更好。
全对全拓扑，不同网络链路的速度可能不同，导致某些复制消息“超越”另一些消息。
更新依赖先前的插入，因此必须保证所有节点先处理插入，再处理更新。仅仅给每次写入附加时间戳并不够，因为不能相信各节点的时钟同步得足以让领导者 2 正确排列这些事件。
要正确排列这些事件，可以采用 版本向量 version vector 。
应用程序需要在断网时继续工作，是另一个适合多主复制的场景。
以手机、笔记本电脑和其他设备上的日历应用为例。无论设备有没有联网，你都需要随时查看会议（发出读请求）和添加会议（发出写请求）。离线期间所作的变更，应在设备下次上线时与服务器及其他设备同步。
这种情况下，每台设备都有一个充当领导者的本地数据库副本，可以接受写入；各设备上的日历副本之间则通过异步多主复制过程进行同步。复制延迟可能长达数小时甚至数天，取决于设备何时重新联网。
从架构上看，这种配置相当于把地区间多主复制推到极致：每台设备都是一个“地区”，它们之间的网络连接极不可靠。
许多现代 Web 应用还提供 实时协作 功能，例如用于文档和电子表格的 Google Docs 与 Sheets、用于图形设计的 Figma，以及用于项目管理的 Linear。这同样形成 多主架构。
离线也可以编辑，在线后自动同步修改，应用程序还要接收协作者的变更，将其合并到用户的本地文件副本，并更新界面以显示最新版本。
支持这一过程的软件库称为 同步引擎（sync engine） 。
允许用户离线时继续编辑文件的应用程序称为 离线优先（offline-first） 应用，它可以用同步引擎来实现。。
同步引擎，本地优先，然后再同步，不影响本地性能。允许用户离线可以工作很有价值。
多人视频游戏也需要立即响应玩家的本地操作，再与通过网络异步收到的其他玩家操作协调。在游戏开发术语中，与同步引擎对应的部分称为 网络代码（netcode） 。
多主复制最大的难题——无论是地理分布式的服务端数据库，还是终端用户设备上的本地优先同步引擎——都是不同领导者上的并发写入可能彼此冲突，需要解决。
一种策略是从一开始就避免冲突，确保某条记录的所有写入都经过同一个领导者。
用户只能编辑自己数据的应用中，可以确保用户的请求总路由到同一个读取，并使用该地区的领导者读写。
例如，插入新记录，并用自增计数器生成唯一ID，两个领导者，可以一个只生成奇数、另一个只生成偶数。
每次写入加附加时间戳，并始终采用时间戳最大的值。这种方法称为 最后写入者胜（last write wins，LWW） 。
LWW 的真正含义是：同一条记录在不同领导者上并发写入时，随机挑选其中一次作为胜者，其他写入则静默丢弃，即使它们都已在各自的领导者上成功处理。这样固然能让所有副本最终收敛到一致状态，代价却是数据丢失。
用 UUID 那种唯一标识可能就避免冲突了，用时间戳还需要考虑时钟各主机不同步问题。
在数据库中，让一次冲突阻塞整个复制过程，直到有人解决，显然并不现实。数据库通常会保存一条记录的所有并发写入值。这些值有时称为 兄弟值（siblings）。 下次查询该记录时，数据库返回 全部 值，而不只是最新的一个。随后可以任意选择解决办法：在应用代码中自动处理（例如把 B 与 C 拼成“B/C”），或询问用户；最后再向数据库写回一个新值，消解冲突。
则基本上算是扯淡，但还真有这样的 CouchDB 系统采用这种冲突解决方式。
最佳方式，是用算法自动把并发写入合并成一致状态。自动冲突解决可以保证所有副本 收敛 到同一状态：只要处理过相同的一组写入，各副本的状态就相同，与写入到达的顺序无关。
Cart = {Soap} 。实现自动冲突解决时，通常使用两类算法：无冲突复制数据类型（CRDT） 和 操作变换（OT） 。
展示了 OT 和 CRDT 分别如何合并文本的并发更新。假设两个副本起初都保存文本“ice”。一个副本在开头插入字母“n”，得到“nice”；与此同时，另一个副本在末尾插入感叹号，得到“ice!”。
OT：
记录字符插入或删除位置的索引：“n”插入索引 0，“!”插入索引 3。然后两个副本交换操作。在索引 0 插入“n”可以原样应用；但如果直接在状态“nice”的索引 3 插入“!”，结果会变成错误的“nic!e”。因此，必须根据已经应用的并发操作变换每个操作的索引。这里，为了计入较小索引处插入的“n”，需要把“!”的插入位置变换为索引 4。
CRDT：
大多数 CRDT 不使用索引，而是给每个字符分配唯一且不可变的 ID，再据此确定插入和删除位置。“i”的 ID 是 1A，“c”的 ID 是 2A，依此类推。插入感叹号时，生成的操作既包含新字符的 ID（4B），也包含插入位置之前那个现有字符的 ID（3A）。要插在字符串开头，就把前驱字符 ID 设为“nil”。同一位置的并发插入按字符 ID 排列。这样无需变换操作，也能保证各副本收敛。
有些冲突显而易见。如，两次写入并发修改同一条记录的同一个字段，把它设成两个不同的值。毫无疑问，这就是冲突。
另一些冲突则更为微妙，不易发现。以会议室预订系统为例，它记录哪个房间在什么时间由哪组人预订。应用程序必须确保同一时刻每个房间只分配给一组人，也就是说，同一房间的预订不能重叠。如果两项不同预订在同一时间占用同一房间，就会产生冲突。即使应用程序在允许预订前检查空闲情况，只要两次预订分别在不同领导者上进行，仍可能发生冲突。
放弃领导者概念，允许任何副本直接接受客户端写入。最早的一些复制数据系统采用的就是无主模型，但在关系数据库占据主导地位的年代，这个思路几乎被遗忘。2007 年，亚马逊把它用于内部的 Dynamo 系统，无主架构由此再度流行。Riak、Cassandra 和 ScyllaDB 都是受 Dynamo 启发、采用无主复制模型的开源数据存储，因此这类数据库也称为 Dynamo 风格（Dynamo-style）数据库。
假设一个数据库有三个副本，其中一个暂时不可用，无主配置则根本没有故障切换。
展示了此时的情形：客户端（用户 1234）把写入并行发给三个副本；两个可用副本接受写入，不可用副本则错过了它。假设三个副本中有两个确认就足以判定写入成功：用户 1234 收到两个 ok 响应后，系统便认为写入成功，客户端直接忽略有一个副本漏掉写入这一事实。
复制系统应当保证所有数据最终都会复制到每个副本。不可用节点恢复上线后，怎样补上停机期间错过的写入？Dynamo 风格的数据存储会使用以下几种机制：
读修复（read repair）：
客户端并行读取多个节点时，可以发现陈旧响应。例如在 图 6-12 中，用户 2345 从副本 3 得到版本 6 的值，从副本 1 和副本 2 得到版本 7 的值。客户端发现副本 3 的值已经过时，于是把较新的值写回这个副本。对于经常读取的值，这种方法很有效。
提示移交（hinted handoff）：
某个副本不可用时，另一个副本可以替它保存写入，并把这些写入记录为 提示。原本应接收这些写入的副本恢复后，保存提示的副本会将它们发送过去，然后删除提示。即使某些值从未被读取、无法通过读修复更新，这个 移交 过程也能让副本赶上进度。
反熵（anti-entropy）：
此外，还有一个后台进程定期查找副本之间的数据差异，把缺失的数据从一个副本复制到另一个。与基于领导者的复制日志不同，这个 反熵过程（anti-entropy process）并不按特定顺序复制写入，数据得到复制之前可能有很长延迟。
在 图 6-12 的例子中，写入只在三个副本中的两个上完成，我们仍判定它成功。如果只有一个副本接受写入呢？这个下限究竟能压到多低？
如果能保证每次成功写入至少保存在三个副本中的两个上，那么最多只有一个副本是陈旧的。因此，只要读取至少两个副本，就可以确信其中至少一个是最新的。即使第三个副本停机或响应缓慢，读取仍能返回最新值。
更一般地说，假设有 n 个副本，每次写入必须得到 w
个节点确认才算成功，每次读取则至少查询 r 个节点。（上述例子中，n = 3、w
= 2、r = 2。）只要 w + r > n
，读取时就有望得到最新值，因为所查询的 r
个节点中，至少有一个必然是最新的。遵守这些 r、w 取值的操作称为
仲裁读（quorum read）和 仲裁写（quorum write）。可以把 r 和 w
看作一次读或写要成立所需的最低票数。
在 Dynamo 风格的数据库中，参数 n、w、r 通常都可以配置。常见做法是让 n
取奇数（通常为 3 或 5），并令
w = r = (n + 1) / 2（向上取整）
；不过也可以根据需要调整。例如，写少读多的工作负载可能适合设为 w = n、r
= 1。这样读取更快，缺点是只要一个节点失效，所有数据库写入都会失败。
w < n，有一个节点不可用时仍可处理写入。r < n，有一个节点不可用时仍可处理读取。n = 3、w = 2、r = 2 时，可以像 图 6-12
那样容忍一个节点不可用。n = 5、w = 3、r = 3 时，可以容忍两个节点不可用，如
图 6-13 所示。
如果有 n 个副本，并选择满足 w + r > n 的 w 和
r，通常可以期望每次读取都返回某个键最近写入的值。这是因为写入所涉及的节点集合与读取所涉及的节点集合必然有交集；也就是说，读取的节点中至少有一个保存着最新值，如
图 6-13 所示。
r 和 w 通常取节点的多数（多于 n/2），因为这样既能保证
w + r > n，又能容忍最多 n/2（向下取整）
个节点失效。不过，法定人数并不一定非得是多数；真正重要的是，读操作与写操作所用的节点集合至少有一个共同节点。法定人数还可以有其他安排，为分布式算法的设计提供一定灵活性。
也可以把 w 和 r 设得更小，使
w + r ≤ n，即不满足仲裁条件。此时读写请求仍会发往 n
个节点，只是操作成功所需的成功响应更少。
w 和 r 越小，越容易读到陈旧值，因为读操作更可能没有覆盖保存最新值的节点。好处则是延迟更低、可用性更高：网络中断导致许多副本不可达时，系统仍有更大机会继续处理读写。只有可达副本数低于 w 或 r 时，数据库才会分别变得不可写或不可读。
然而，即使
w + r > n，仍有一些边缘情况会让一致性属性变得难以理解，例如：
从运维角度看，监控数据库返回的结果是否最新非常重要。即使应用程序能够容忍陈旧读取，也必须了解复制是否健康。如果复制大幅落后，系统应发出告警，以便调查网络故障、节点过载等原因。
采用基于领导者的复制时，数据库通常会暴露复制延迟指标，供监控系统采集。这是因为写入在领导者和追随者上按相同顺序应用，每个节点都有自己在复制日志中的位置，也就是已经在本地应用了多少次写入。用领导者当前位置减去追随者当前位置，便可度量复制延迟。
无主复制系统没有固定的写入应用顺序，监控起来更加困难。副本为了移交而保存的提示数量可以作为一项健康指标，却很难作出有意义的解释。最终一致性有意给出了一项模糊保证，但为了可运维性，必须能够量化“最终”究竟有多远。
基于单个领导者的复制系统能够提供强一致性保证，而无主系统很难甚至不可能做到。在基于领导者的复制系统里，如果从异步更新的追随者读取，同样可能得到陈旧值。
从领导者读取可以保证响应最新，却存在性能问题：
无主架构的一大优点，是面对这些问题时韧性更强。系统无需故障切换，而且请求原本就会并行发往多个副本，因此一个副本变慢或不可用，对响应时间的影响很小：客户端只需采用响应较快的其他副本所返回的结果。采用最快响应的做法称为 请求对冲（request hedging） ，可以显著降低尾延迟。
无主系统也可能遇到性能问题：
多主复制抵御网络中断的能力甚至可能强于无主复制，因为读写只需与一个领导者通信，而领导者可以与客户端位于同一地区。不过，一个领导者上的写入会异步传播给其他领导者，读取结果因而可能任意陈旧。仲裁读写提供了一种折中：既有良好的容错能力，也有很高概率读到最新数据。
Cassandra 和 ScyllaDB 在常规无主模型中实现多地区支持：客户端把写入直接发往所有地区的副本，并可选择多种一致性级别，规定请求至少得到多少响应才算成功。例如，可以要求所有地区的全部副本共同组成一个法定人数，也可以要求每个地区各自组成法定人数，或只要求客户端所在地区达到法定人数。本地法定人数无需等待其他地区的慢请求，但也更容易返回陈旧结果。
Riak 则把客户端与数据库节点之间的所有通信限制在本地地区，因此 n 表示一个地区内的副本数。数据库集群之间的跨地区复制在后台异步进行，方式与多主复制相似。
与多主复制一样，无主数据库允许对同一个键并发写入，由此产生需要解决的冲突。冲突可能在写入发生时出现，但并非总是如此；它也可能到读修复、提示移交或反熵阶段才被发现。
网络延迟会变化，系统还可能部分失效，所以事件抵达不同节点的顺序可能不同。
图 6-14 展示了客户端 A 和 B 同时写入三节点数据存储中的键 X：
为了达到最终一致，各副本必须收敛到同一个值。可以采用 “处理写入冲突” 中讨论过的任意冲突解决机制，例如 Cassandra 和 ScyllaDB 使用的最后写入者胜、手工解决，或 “CRDT 与操作变换” 中介绍且 Riak 使用的 CRDT。
最后写入者胜很容易实现：给每次写入附加时间戳，时间戳较大的值总是覆盖较小的值。但时间戳无法告诉你两个值究竟是否冲突：它们可能是并发写入的，也可能先后写入。如果要显式解决冲突，系统必须更仔细地检测并发写入。
如果操作 B 知道 A、依赖 A，或以某种方式建立在 A 之上，就称操作 A 先发生于（happens before）操作 B。一项操作是否先发生于另一项操作，是定义并发的关键。事实上，只要两个操作谁也不先发生于另一个——也就是说，谁都不知道对方——就可以称它们 并发（concurrent）。
因此，对于任意两个操作 A 与 B，只有三种可能：A 先发生于 B；B 先发生于 A；或者 A 与 B 并发。我们需要一种算法判断两次操作是否并发。如果一项操作先发生于另一项，后发生的操作就应覆盖先前操作；如果两者并发，则出现了需要解决的冲突。
下面看一种算法，它可以判断两项操作是并发的，还是一项先发生于另一项。为简单起见，先从只有一个副本的数据库开始。弄清单副本的做法后，再推广到拥有多个副本的无主数据库。
milk
加入购物车。这是该键的第一次写入，服务器成功保存它并分配版本
1；然后把值和版本号一起返回给客户端。eggs 加入购物车，却不知道客户端 1
同时加入了 milk（它以为 eggs
是购物车中唯一的商品）。服务器为这次写入分配版本 2，把 eggs
和 milk 保存为两个独立的值（兄弟值），再把 两个
值连同版本号 2 一起返回给客户端。flour，因此它认为购物车内容应为
[milk, flour]。它把这个值连同服务器此前给出的版本号 1
一起发送。服务器可以根据版本号判断：[milk, flour]
取代了先前的 [milk]，却与 [eggs]
并发。因此，服务器为 [milk, flour] 分配版本 3，覆盖版本 1
的 [milk]，保留版本 2 的
[eggs]，并把剩下的两个值都返回给客户端。ham，并不知道客户端 1
刚刚加入 flour。客户端 2 在上一次响应中收到了
[milk] 和 [eggs]，于是将两者合并，再加入
ham，形成新值
[eggs, milk, ham]。它把这个值连同先前的版本号 2
一起发给服务器。服务器判断版本 2 可以覆盖 [eggs]，但与
[milk, flour] 并发；剩下的两个值便是版本 3 的
[milk, flour] 和版本 4 的
[eggs, milk, ham]。bacon。它此前在版本 3
的响应中收到 [milk, flour] 和
[eggs]，于是合并二者，加入 bacon，把最终值
[milk, flour, eggs, bacon] 连同版本号 3
发给服务器。这个值覆盖 [milk, flour]（[eggs]
已在上一步被覆盖），却与 [eggs, milk, ham]
并发，因此服务器保留这两个并发值。图 6-15 中各操作之间的数据流，在 图 6-16 中以图形表示。箭头指出哪项操作 先发生于 另一项，也就是说，后发生的操作 知道 或 依赖 先发生的操作。在这个例子里，客户端从未完全掌握服务器上的最新数据，因为始终有另一项操作并发进行。但值的旧版本最终会被覆盖，而且不会丢失任何写入。
请注意，服务器仅凭版本号就能判断两项操作是否并发，无需解释值本身，因此值可以是任意数据结构。算法如下：
写入带上前一次读取所得的版本号，就说明这次写入基于哪个先前状态。如果写入不含版本号，它就与其他所有写入并发，因而不会覆盖任何内容，只会作为后续读取返回的值之一。
图 6-15 的例子只有一个副本。如果没有领导者，而且多个副本都能接受写入，算法需要怎样改变？
图 6-15 用一个版本号捕获操作之间的依赖关系，但多个副本并发接受写入时，一个版本号就不够了。此时必须针对每个键，给 每个副本 分别维护版本号。副本处理写入时递增自己的版本号，同时记录自己见过的其他副本版本号。这些信息表明哪些值应当覆盖，哪些值应作为兄弟值保留。
所有副本的版本号集合称为 版本向量 。这种思路有若干变体，其中最值得关注的也许是 点化版本向量（dotted version vector） ，Riak 2.0 采用了这种变体 。这里不展开细节；它的工作方式与购物车例子非常相似。
与 图 6-15 中的版本号一样，读取时数据库副本会把版本向量发给客户端，随后写入时客户端必须再把它带回数据库。（Riak 把版本向量编码成一个字符串，称为 因果上下文，causal context。）版本向量让数据库能够区分覆盖写入和并发写入。
版本向量还保证：先从一个副本读取，再把写入发给另一个副本，是安全的。这样做可能产生兄弟值，但只要正确合并兄弟值，就不会丢失数据。