数据密集型应用——分布式数据复制

编程入门行业动态更新时间:2024-10-26 05:22:33

分布式数据

无共享架构中运行数据库软件的每台机器/虚拟机都称为节点，每个节点使用各自的处理器，内存和磁盘。节点之间的任何协调，都在软件层面使用传统网络实现。其数据分布在多个节点上有两种常见的方式：复制和分区。
复制：在几个不同的节点上保存数据的相同副本，可能存放在不同的位置。复制提供了冗余：如果一些节点不可用，剩余的节点仍然可以提供数据服务。
分区：将一个大型数据库拆分成较小的子集（称为分区partitions），从而不同的分区可以指派给不同的节点（node）（亦称分片）。

复制

复制意味着在通过网络连接的多台机器上保留相同数据的副本。我们希望能复制数据，可能出于各种各样的原因：使得数据与用户在地理上接近（从而减少延迟）、即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）、扩展可以接受读请求的机器数量（从而提高读取吞吐量）。讨论三种复制算法：单领导者（single leader）、多领导者（multi leader）、无领导者（leaderless）。
在复制时需要进行许多权衡，例如，使用同步复制还是异步复制，如何处理失败的副本，这些通常是数据库中的配置选项，细节因数据库而异，但原理在许多不同的实现中都类似。

领导者与追随者

存储数据库副本的每个节点称为副本（replica）。当存在多个副本时，会不可避免的出现一个问题：如何确保所有数据都落在了所有的副本上？每次想数据库的写入操作都需要传播到所有副本上，否则副本就会包含不一样的数据。最常见的解决方案被称为基于领导者的复制（leader-based replication）(也称主动/被动 active、passive)或主从复制。工作原理如下：

副本之一被指定为领导者，也称为主库(master)，首要(primary)。当客户端要向数据库写入时，它必须将请求发送给领导者，领导者会将新数据写入其本地存储。
其他副本被称为追随者(followers)，亦称为只读副本（read replicas），从库（slavers），次要（sencondaries），热备（hot-standby）。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为复制日志（replication log）记录或变更流（change stream）。每个跟随着从领导者拉取日志，并相应更新其本地数据副本，方法是按照领导者处理的相同顺序应用所有写入。
当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。但只有领导者才能接受写操作（从客户端的角度来看从库都只读的）

这种复制模式是许多关系数据库的内置功能，如PostgreSQL（从9.0版本开始）， MySQL， Oracle
Data Guard和SQL Server的AlwaysOn可用性组。它也被用于一些非关系数据库，包括MongoDB， RethinkDB和Espresso 。最后，基于领导者的复制并不不仅限于数据库：像Kafka和RabbitMQ⾼高可用队列这样的分布式消息代理理也使用它。某些网络文件系统，例如DRBD这样的块复制设备也与之类似。

同步复制与异步复制

复制系统的一个重要细节是：复制是同步（synchronouslg）发生还是异步（asynchronously）发生。从库1的复制是同步的：在向用户报告写入成功，并使结果对其他用户可见之前，主库需要等待从库1的确认，确保从库1已经收到写入操作。以及在使写入对其他客户端可见之前接收到写入。跟随者2的复制是异步的：主库发送消息，但不不等待从库的响应。

在这幅图中，从库2处理理消息前存在一个显着的延迟。通常情况下，复制的速度相当快：大多数数据库系统能在一秒向从库应⽤用变更更，但它们不不能提供复制用时的保证。有些情况下，从库可能落后主库几分钟或更更久；例例如：从库正在从故障中恢复，系统在最大容量量附近运行，或者如果节点间存在网络问题。
同步复制的优点是，从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上上找到。缺点是，如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。
因此，将所有从库都设置为同步的是不不切实际的：任何一个节点的中断都会导致整个系统停滞不不前。实际上，如果在数据库上启用同步复制，通常意味着其中一个跟随者是同步的，而其他的则是异步的。如果同步从库变得不不可用或缓慢，则使一个异步从库同步。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。这种配置有时也被称为半同步（semi-synchronous）。
通常情况下，基于领导者的复制都配置为完全异步。在这种情况下，如果主库失效且不不可恢复，则任何尚未复制给从库的写入都会丢失。这意味着即使已经向客户端确认成功，写入也不能保证持久（Durable）。然而，一个完全异步的配置也有优点：即使所有的从库都落后了了，主库也可以继续处理理写入。弱化的持久性可能听起来像是一个坏的折衷，无论如何，异步复制已经被广泛使用了，特别当有很多追随者，或追随者异地分布时。

对于异步复制系统而言，主库故障时有可能丢失数据。这可能是一个严重的问题，因此研究人员仍在研究不不丢数据但仍能提供良好性能和可用性的复制方法。例如，链式复制是同步复制的一种变体，已经在一些系统（如Microsoft Azure存储）中成功实现。

设置新从库

有时候需要设置一个新的从库：也许是为了增加副本的数量，或替换失败的节点。如何确保新的从库拥有主库数据的精确副本？简单地将数据文件从一个节点复制到另一个节点通常是不不够的：客户端不断向数据库写入数据，数据总是在不断变化，标准的数据副本会在不同的时间点总是不一样。复制的结果可能没有任何意义。
可以通过锁定数据库（使其不可用于写入）来使磁盘上的文件保持一致，但是这会违背高可用的目标。幸运的是，拉起新的从库通常并不不需要停机。从概念上讲，过程如下所示：

在某个时刻获取主库的一致性快照（如果可能），而不不必锁定整个数据库。大多数数据库都具有这个功能，因为它是备份必需的。对于某些场景，可能需要第三方工具，例例如MySQL的
innobackupex
将快照复制到新的从库节点。
从库连接到主库，并拉取快照之后发生的所有数据变更更。这要求快照与主库复制日志中的位置精确关联。该位置有不同的名称：例如， PostgreSQL将其称为日志序列列号（log sequence number,nLSN）， MySQL将其称为二进制日志坐标（binlog coordinates）。
当从库处理理完快照之后积压的数据变更，我们说它赶上（caught up）了主库。现在它可以继续处理主库产生的数据变化了
建立从库的实际步骤因数据库而异。在某些系统中，这个过程是完全自动化的，而在另外一些系统中，它可能是一个需要由管理员手动执行的，有点神秘的多步骤工作流。

处理节点宕机

系统中的任何节点都可能宕机，可能因为意外的故障，也可能由于计划内的维护（例如，重启机器器以安装内核安全补丁）。对运维而言，能在系统不中断服务的情况下重启单个节点好处多多。我们的目标是，即使个别节点失效，也能保持整个系统运行，并尽可能控制节点停机带来的影响。
如何通过基于主库的复制实现高可用？

从库失效：追赶恢复

在其本地磁盘上，每个从库记录从主库收到的数据变更。如果从库崩溃并重新启动，或者，如果主库和从库之间的网络暂时中断，则比较容易恢复：从库可以从日志中知道，在发生故障之前处理的最后一个事务。因此，从库可以连接到主库，并请求在从库断开连接时发生的所有数据变更。当应用完所有这些变化后，它就赶上了主库，并可以像以前一样继续接收数据变更流。

主库失效：故障切换

主库失效处理起来相当棘手：其中一个从库需要被提升为新的主库，需要重新配置客户端，以将它们的写操作发送给新的主库，其他从库需要开始拉取来自新主库的数据变更更。这个过程被称为故障切换（failover）。
故障切换可以手动进行（通知管理理员主库挂了，并采取必要的步骤来创建新的主库）或自动进行。自动故障切换过程通常由以下步骤组成：

确认主库失效。有很多事情可能会出错：崩溃，停电，网络问题等等。没有万无一失的方法来检测出现了什么问题，所以大多数系统只是简单使用超时（Timeout）：节点频繁地相互来回传递消
息，并且如果一个节点在一段时间内（例如30秒）没有响应，就认为它挂了（因为计划内维护而故意关闭主库不算）。
选择一个新的主库。这可以通过选举过程（主库由剩余副本以多数选举产生）来完成，或者可以由之前选定的控制器节点（controller node）来指定新的主库。主库的最佳人选通常是拥有旧主库
最新数据副本的从库（最小化数据损失）。让所有的节点同意一个新的领导者，是一个共识问题，
将在第9章详细讨论。
重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库（将在“请求路路由”中讨论这个问题）。如果老领导回来，可能仍然认为自己是主库，没有意识到其他副本已经让它下台了。系统需要确保老领导认可新领导，成为一个从库。

故障切换会出现很多大麻烦：
如果使用异步复制，则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后，如果
老主库重新加入集群，新主库在此期间可能会收到冲突的写入，那这些写入该如何处理理？最常见的解决方案是简单丢弃老主库未复制的写⼊入，这很可能打破客户对于数据持久性的期望。

如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的操作。例如在GitHub
的一场事故中，一个过时的MySQL从库被提升为主库。数据库使用自增ID作为主键，因为
新主库的计数器落后于老主库的计数器器，所以新主库重新分配了一些已经被老主库分配掉的ID作为主键。这些主键也在Redis中使用，主键重用使得MySQL和Redis中数据产生不一致，最后导致一些私有数据泄漏漏到错误的用户手中。

发⽣生某些故障时可能会出现两个节点都以为自己是主库的情况。这种情况称为脑裂
(split brain)，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制（参见“多领导
者复制”），那么数据就可能丢失或损坏。一些系统采取了了安全防范措施：当检测到两个主库节点
同时存在时会关闭其中一个节点 2 ，但设计粗糙的机制可能最后会导致两个节点都被关闭。

主库被宣告死亡之前的正确超时应该怎么配置？在主库失效的情况下，超时时间越长，意味着恢复
时间也越长。但是如果超时设置太短，⼜又可能会出现不不必要的故障切换。例如，临时负载峰值可能导致节点的响应时间超时，或网络故障可能导致数据包延迟。如果系统已经处于高负载或网络问题的困扰之中，那么不必要的故障切换可能会让情况变得更糟糕。

这些问题没有简单的解决方案。因此，即使软件支持自动故障切换，不少运维团队还是更更愿意手动执行故障切换。

复制日志的实现

基于主库的复制底层是如何工作的？实践中有好几种不同的复制方式，所以先简要地看一下。

基于语句的复制

在最简单的情况下，主库记录下它执行的每个写入请求（语句句（statement））并将该语句日志发送给其从库。对于关系数据库来说，这意味着每个 INSERT ， UPDATE 或 DELETE 语句都被转发给每个从库，每个从库解析并执行该SQL语句，就像从客户端收到一样。虽然听上去很合理理，但有很多问题会搞砸这种复制方式：

任何调用非确定性函数（nondeterministic）的语句，可能会在每个副本上生成不同的值。例如，使用 NOW() 获取当前日期时间，或使用 RAND() 获取一个随机数。
如果语句使用了自增列（auto increment），或者依赖于数据库中的现有数据（例如， UPDATE
… WHERE <某些条件> ），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生
不同的效果。当有多个并发执行的事务时，这可能成为一个限制。
有副作用的语句（例如，触发器，存储过程，用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定的。

的确有办法绕开这些问题 ——例如，当语句被记录时，主库可以用固定的返回值替换任何不确定的函数调用，以便从库获得相同的值。但是由于边缘情况实在太多了了，现在通常会选择其他的复制方法。

基于语句的复制在5.1版本前的MySQL中使用。因为它相当紧凑，现在有时候也还在用。但现在在默认情况下，如果语句句中存在任何不确定性， MySQL会切换到基于行的复制（稍后讨论）。 VoltDB使用了基于语句句的复制，但要求事务必须是确定性的，以此来保证安全【15】。

传输预写日志（WAL）

我们讨论了了存储引擎如何在磁盘上表示数据，并且我们发现，通常写操作都是追加到日志中：

对于日志结构存储引擎（请参阅“SSTables和LSM树”），日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
对于覆写单个磁盘块的B树，每次修改都会先写入预写式日志（Write Ahead Log, WAL），以便便崩溃后索引可以恢复到一个一致的状态。

在任何一种情况下，日志都是包含所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本：除了了将日志写入磁盘之外，主库还可以通过网络将其发送给其从库。

当从库应用这个日志时，它会建立和主库一模一样数据结构的副本。PostgreSQL和Oracle等使用这种复制方法。主要缺点是日志记录的数据非常底层： WAL包含哪些磁盘块中的哪些字节发生了更改。这使复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主库和从库上运行不同版本的数据库软件。

看上去这可能只是一个微小的实现细节，但却可能对运维产生巨大的影响。如果复制协议允许从库使用比主库更新的软件版本，则可以先升级从库，然后执行故障切换，使升级后的节点之一成为新的主库，从而执行数据库软件的零停机升级。如果复制协议不允许版本不匹配（传输WAL经常出现这种情况），则此类升级需要停机。

逻辑日志复制（基于行）

另一种方法是，复制和存储引擎使用不同的日志格式，这样可以使复制日志从存储引擎内部分离出来。这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。
关系数据库的逻辑日志通常是以行的粒度描述对数据库表的写入的记录序列：

对于插入的行，日志包含所有列的新值。
对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，但是如果表上没有主
键，则需要记录所有列的旧值。
对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

修改多行的事务会生成多个这样的日志记录，后面跟着一条记录，指出事务已经提交。 MySQL的二进制日志（当配置为使用基于行的复制时）使用这种方法。由于逻辑日志与存储引擎内部分离，因此可以更容易易地保持向后兼容，从而使领导者和跟随者能够运行不同版本的数据库软件至不同的存储引擎。对于外部应用程序来说，逻辑日志格式也更容易解析。如果要将数据库的内容发送到外部系统（如数据），这一点很有用，例例如复制到数据仓库进行离线分析，或建立自定义索引和缓存。这种技术被称为捕获数据变更（change data capture）

基于触发器的复制

到目前为止描述的复制方法是由数据库系统实现的，不涉及任何应用程序代码。在很多情况下，这就是你想要的。但在某些情况下需要更多的灵活性。例如，如果您只想复制数据的一个子集，或者想从一种数据库复制到另一种数据库，或者如果您需要冲突解决逻辑（参阅“处理理写入冲突”），则可能需要将复制移动到应用程序层。
一些工具，如Oracle Golden Gate，可以通过读取数据库日志，使得其他应用程序可以使用数
据。
另一种方法是使用许多关系数据库自带的功能：触发器和存储过程。

触发器允许您注册在数据库系统中发生数据更改（写入事务）时自动执行的自定义应用程序代码。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上任何业务逻辑处理理，会后将数据变更复制到另一个系统去。例例如， Databus for Oracle 和Bucardo for Postgres就是这样工作的。基于触发器的复制通常比其他复制方法具有更高的开销，并且比数据库的内置复制更容易出错，也有很多限制。然而由于其灵活性，仍然是很有用的。

复制延迟问题

容忍节点故障只是需要复制的一个原因，另一个原因是可扩展性（处理比单个机器更多的请求）和延迟（让副本在地理位置上更接近用户）。
基于主库的复制要求所有写入都由单个节点处理，但只读查询可以由任何副本处理。所以对于读多写少的场景（Web上的常见模式），一个有吸引力的选择是创建很多从库，并将读请求分散到所有的从库上去。这样能减小主库的负载，并允许向最近的副本发送读请求。

在这种扩展体系结构中，只需添加更多的追随者，就可以提高只读请求的服务容量。但是，这种方法实际上只适用于异步复制——如果尝试同步复制到所有追随者，则单个节点故障或网络中断将使整个系统无法写入。而且越多的节点越有可能会被关闭，所以完全同步的配置是非常不可靠的。

不幸的是，当应用程序从异步从库读取时，如果从库落后，它可能会看到过时的信息。这会导致数据库中出现明显的不一致：同时对主库和从库执行相同的查询，可能得到不同的结果，因为并非所有的写入都反映在从库中。这种不一致只是一个暂时的状态——如果停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致。出于这个原因，这种效应被称为最终一致性（eventuallyconsistency）

“最终”一词故意含糊不清：总的来说，副本落后的程度是没有限制的。在正常的操作中，复制延迟（replication lag），即写入主库到反映至从库之间的延迟，可能仅是几分之一秒，在实践中并不显眼。但如果系统在接近极限的情况下运行，或网络中存在问题，延迟可以轻而易举地超过几秒，甚至几分钟。
因为滞后时间太长引入的不一致性，可不不仅是一个理论问题，更是应用设计中会遇到的真实问题。本节将重点介绍三个由复制延迟问题的例子，并简述解决这些问题的一些方法。

读已之写

许多应用让用户提交一些数据，然后查看他们提交的内容。可能是用户数据库中的记录，也可能是对讨论主题的评论，或其他类似的内容。提交新数据时，必须将其发送给领导者，但是当用户查看数据时，可以从追随者读取。如果数据经常被查看，但只是偶尔写入，这是非常合适的。

但对于异步复制，问题就来了。如图5-3所示：如果用户在写入后马上就查看数据，则新数据可能尚未到达副本。对用户而言，看起来好像是刚提交的数据丢失了，⽤用户会不高兴，可以理理解。

在这种情况下，我们需要读写一致性（read-after-write consistency），也称为读己之写一致性（read-your-writes consistency）。这是一个保证，如果用户重新加载页面，他们总会看到他们自己提交的任何更新。它不不会对其他用户的写入做出承诺：其他用户的更新可能稍等才会看到。它保证用户自己的输入已被正确保存。

如何在基于领导者的复制系统中实现读后一致性？有各种可能的技术，这里说一些：

读用户可能已经修改过的内容时，都从主库读；这就要求有一些方法，不用实际查询就可以知道用户是否修改了某些东西。举个例子，社交网络上的用户个人资料料信息通常只能由用户本人编辑，而不能由其他人编辑。因此一个简单的规则是：从主库读取用户自己的档案，在从库读取其他用户的档案。
如果应用中的大部分内容都可能被用户编辑，那这种方法就没用了，因为大部分内容都必须从主库读取（扩容读就没效果了）。在这种情况下可以使用其他标准来决定是否从主库读取。例如可以跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。还可以监控从库的复制延迟，防止任向任何滞后超过一分钟到底从库发出查询。
客户端可以记住最近一次写入的时间戳，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了了本从库中。如果当前从库不够新，则可以从另一个从库读，或者等待从库追赶上来。
时间戳可以是逻辑时间戳（指示写入顺序的东西，例例如日志序列列号）或实际系统时钟（在这种情况下，时钟同步变得至关重要；参阅“不可靠的时钟”）。
如果您的副本分布在多个数据中心（出于可用性目的与用户尽量量在地理理上接近），则会增加复杂性。任何需要由领导者提供服务的请求都必须路由到包含主库的数据中心。

另一种复杂的情况是：如果同一个用户从多个设备请求服务，例如桌⾯面浏览器和移动APP。这种情况下可能就需要提供跨设备的写后读一致性：如果用户在某个设备上输入了一些信息，然后在另一个设备上查看，则应该看到他们刚输入的信息。
在这种情况下，还有一些需要考虑的问题：

记住用户上次更新时间戳的方法变得更更加困难，因为一台设备上运行的程序不知道另一台设备上发生了什么。元数据需要一个中心存储。
如果副本分布在不同的数据中⼼心，很难保证来自不同设备的连接会路由到同一数据中心。（例如，用户的台式计算机使用家庭宽带连接，而移动设备使用蜂窝数据网络，则设备的网络路线可能完全不同）。如果你的方法需要读主库，可能首先需要把来自同一用户的请求路由到同一个数据中

单调读

从异步从库读取第二个异常例例子是，用户可能会遇到时光倒流（moving backward in time）。
如果用户从不同从库进行多次读取，就可能发生这种情况。例例如，图5-4显示了用户2345两次进行相同的查询，首先查询了一个延迟很小的从库，然后是一个延迟较大的从库。（如果用户刷新网页，而每个请求被路路由到一个随机的服务器，这种情况是很有可能的。）第一个查询返回最近由用户1234添加的评论，但是第二个查询不返回任何东⻄西，因为滞后的从库还没有拉取写入内容。在效果上相比第一个查询，第二个查询是在更早的时间点来观察系统。如果第一个查询没有返回任何内容，那问题并不大，因为用户2345可能不知道用户1234最近添加了评论。但如果用户2345先看见用户1234的评论，然后又看到它消失，那么对于用户2345，就很让人头大了。

单调读（Monotonic reads）是这种异常不会发生的保证。这是一个比强一致性（strong
consistency）更更弱，但比最终一致性（eventually consistency）更强的保证。当读取数据时，您可能会看到一个旧值；单调读取仅意味着如果一个用户顺序地进行多次读取，则他们不会看到时间后退，即，如果先前读取到较新的数据，后续读取不会得到更旧的数据。
实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取（不同的用户可以从不同的副本读取）。例如，可以基于用户ID的散列来选择副本，而不是随机选择副本。但是，如果该副本失败，用户的查询将需要重新路由到另一个副本。

一致前缀读

第三个复制延迟例子违反了因果律律。想象一下Poons先⽣生和Cake夫人之间的以下简短对话：Mr. Poons Mrs. Cake，你能看到多远的未来？
Mrs. Cake 通常约十秒钟， Mr. Poons.
这两句句话之间有因果关系： Cake夫人听到了了Poons先⽣生的问题并回答了这个问题。现在，想象第三个人正在通过从库来听这个对话。 Cake夫人说的内容是从一个延迟很低的从库读取的，但Poons先生所说的内容，从库的延迟要大的多（⻅见图5-5）。于是，这个观察者会听到以下内容：
Mrs. Cake 通常约十秒钟， Mr. Poons.
Mr. Poons Mrs. Cake，你能看到多远的未来？
对于观察者来说，看起来好像Cake夫人在Poons先生发问前就回答了这个问题。这种超能力让人印象深刻，但也会把人搞糊涂。

防止这种异常，需要另一种类型的保证：一致前缀读（consistent prefix reads）。这个保证
说：如果一系列列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。
这是分区（partitioned）（分片（sharded））数据库中的一个特殊问题，将在第6章中讨论。如果数据库总是以相同的顺序应用写入，则读取总是会看到一致的前缀，所以这种异常不会发生。但是在许多分布式数据库中，不同的分区独立运行行，因此不存在全局写入顺序：当用户从数据库中读取数据时，可能会看到数据库的某些部分处于较旧的状态，而某些处于较新的状态。
一种解决方案是，确保任何因果相关的写入都写入相同的分区。对于某些无法高效完成这种操作的应用，还有一些显式跟踪因果依赖关系的算法，本书将在“关系与并发”一节中返回这个主题。

复制延迟的解决方案

在使用最终一致的系统时，如果复制延迟增加到几分钟甚至几小时，则应该考虑应用程序的行为。如果答案是“没问题”，那很好。但如果结果对于用户来说是不好体验，那么设计系统来提供更强的保证是很重要的，例如写后读。明明是异步复制却假设复制是同步的，这是很多麻烦的根源。
如前所述，应用程序可以提供比底层数据库更强有力的保证，例如通过主库进行某种读取。但在应用程序代码中处理理这些问题是复杂的，容易出错。
如果应用程序开发人员不必担心微妙的复制问题，并可以信赖他们的数据库“做了正确的事情”，那该多好呀。这就是事务（transaction）存在的原因： 数据库通过事务提供强大的保证，所以应用程序可以更加简单。单节点事务已经存在了很长时间。然而在走向分布式（复制和分区）数据库时，许多系统放弃了了事务。
声称事务在性能和可用性上的代价太高，并断言在可扩展系统中最终一致性是不可避免的。这个叙述有一些道理理，但过于简单了，本书其余部分将提出更为细致的观点。第七章和第九章将回到事务的话题，并讨论一些替代机制。

多主复制

本章到目前为止，我们只考虑使用单个领导者的复制架构。虽然这是一种常见的方法，但也有一些有趣的选择。
基于领导者的复制有一个主要的缺点：只有一个主库，而所有的写入都必须通过它。如果出于任何原因（例如和主库之间的⽹网络连接中断）无法连接到主库，就无法向数据库写入。
基于领导者的复制模型的自然延伸是允许多个节点接受写入。复制仍然以同样的方式发生：处理理写入的每个节点都必须将该数据更改转发给所有其他节点。称之为多领导者配置（也称多主、多活复制）。
在这种情况下，每个领导者同时扮演其他领导者的追随者。

多主复制的应用场景

在单个数据中心内部使用多个主库很少是有意义的，因为好处很少超过复杂性的代价。但在一些情况下，多活配置是也合理的。

运维多个数据中心

假如你有一个数据库，副本分散在好几个不同的数据中心（也许这样可以容忍单个数据中心的故障，或地理上更接近用户）。使用常规的基于领导者的复制设置，主库必须位于其中一个数据中心，且所有写入都必须经过该数据中心。
多领导者配置中可以在每个数据中心都有主库。图5-6展示了了这个架构的样子。在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。

性能
在单活配置中，每个写入都必须穿过互联网，进入主库所在的数据中心。这可能会增加写入时间，并可能违背了设置多个数据中心的初心。在多活配置中，每个写操作都可以在本地数据中心进行行处理，并与其他数据中心异步复制。因此，数据中心之间的网络延迟对用户来说是透明的，这意味着感觉到的性能可能会更更好。

容忍数据中心停机
在单主配置中，如果主库所在的数据中心发生故障，故障切换可以使另一个数据中心里的追随者成为领导者。在多活配置中，每个数据中心可以独立于其他数据中心继续运行，并且当发生故障的数据中心归队时，复制会自动赶上。

容忍网络问题
数据中心之间的通信通常穿过公共互联网，这可能不如数据中心内的本地网络可靠。单主配置对这数据中心间的连接问题非常敏敏感，因为通过这个连接进行的写操作是同步的。采用异步复制功能的多活配置通常能更好地承受网络问题：临时的网络中断并不会妨碍正在处理理的写入。
有些数据库默认情况下支持多主配置，但使用外部工具实现也很常⻅见，例如用于MySQL的Tungsten Replicator，用于PostgreSQL的BDR以及用于Oracle的GoldenGate 。

尽管多主复制有这些优势，但也有一个很大的缺点：两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的（如图5-6中“冲突解决”）。本书将在“处理写入冲突”中详细讨论这个问题。
由于多主复制在许多数据库中都属于改装的功能，所以常存在微妙的配置缺陷，且经常与其他数据库功能之间出现意外的反应。例如自增主键、触发器、完整性约束等，都可能会有麻烦。因此，多主复制往往被认为是危险的领域，应尽可能避免。

需要离线操作的客户端

多主复制的另一种适用场景是：应用程序在断网之后仍然需要继续工作。例如，考虑手机，笔记本电脑和其他设备上的日历应用。无论设备目前是否有互联网连接，你需要能随
时查看你的会议（发出读取请求），输入新的会议（发出写入请求）。如果在离线状态下进行行任何更改，则设备下次上线时，需要与服务器和其他设备同步。

在这种情况下，每个设备都有一个充当领导者的本地数据库（它接受写请求），并且在所有设备上的日历副本之间同步时，存在异步的多主复制过程。复制延迟可能是几小时甚至几天，具体取决于何时可以访问互联网。

从架构的⻆角度来看，这种设置实际上与数据中心之间的多领导者复制类似，每个设备都是一个“数据中心”，而它们之间的⽹网络连接是极度不可靠的。从历史上各类日历同步功能的破烂实现可以看出，想把多活配好是多么困难的一件事。
有一些⼯具旨在使这种多领导者配置更容易。例如， CouchDB就是为这种操作模式而设计的。

协同编辑

实时协作编辑应用程序允许多个人同时编辑文档。例例如， Etherpad和Google Docs允许
多人同时编辑文本文档或电子表格（该算法在“自动冲突解决”中简要讨论）。我们通常不会将协作式编辑视为数据库复制问题，但与前面提到的离线编辑用例有许多相似之处。当一个用户编辑文档时，所做的更改将立即应用到其本地副本（Web浏览器或客户端应用程序中的文档状态），并异步复制到服务器和编辑同一文档的任何其他用户。
如果要保证不会发生编辑冲突，则应用程序必须先取得文档的锁定，然后用户才能对其进行行编辑。如果另一个用户想要编辑同一个⽂文档，他们首先必须等到第一个用户提交修改并释放锁定。这种协作模式相当于在领导者上进行行交易易的单领导者复制。
但是，为了加速协作，您可能希望将更改的单位设置得非常小（例如，一个按键），并避免锁定。这种方法允许多个用户同时进行编辑，但同时也带来了多领导者复制的所有挑战，包括需要解决冲突

处理写入冲突

多领导者复制的最大问题是可能发生写冲突，这意味着需要解决冲突。例如，考虑一个由两个用户同时编辑的维基页面，如图5-7所示。用户1将页面的标题从A更改为B，并且用户2同时将标题从A更改为C。每个用户的更改已成功应用到其本地主库。但当异步复制时，会发现冲突。单主数据库中不会出现此问题。

同步与异步冲突检测

在单主数据库中，第二个写入将被阻塞，并等待第一个写入完成，或中止第二个写入事务，强制用户重试。另一方面，在多活配置中，两个写入都是成功的，并且在稍后的时间点仅仅异步地检测到冲突。那时要求用户解决冲突可能为时已晚。
原则上，可以使冲突检测同步 - 即等待写入被复制到所有副本，然后再告诉用户写入成功。但是，通过这样做，您将失去多主复制的主要优点：允许每个副本独立接受写入。如果您想要同步冲突检测，那么您可以使用单主程序复制。

避免冲突

处理冲突的最简单的策略就是避免它们：如果应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生。由于多领导者复制处理的许多实现冲突相当不好，避免冲突是一个经常推荐的方法。
例如，在用户可以编辑自己的数据的应用程序中，可以确保来自特定用户的请求始终路由到同一数据中心，并使用该数据中心的领导者进行读写。不同的用户可能有不同的“家庭”数据中心（可能根据用户的地理位置选择），但从任何用户的角度来看，配置基本上都是单一的领导者。
但是，有时您可能需要更更改指定的记录的主库——可能是因为一个数据中心出现故障，您需要将流量重新路由到另一个数据中心，或者可能是因为用户已经迁移到另一个位置，现在更接近不不同的数据中心。在这种情况下，冲突避免会中断，你必须处理不同主库同时写入的可能性。

收敛至一致的状态

单主数据库按顺序应用写操作：如果同一个字段有多个更新，则最后一个写操作将确定该字段的最终值。在多主配置中，写入顺序没有定义，所以最终值应该是什什么并不清楚。在图5-7中，在主库1中标题首先更新为B而后更更新为C；在主库2中，首先更更新为C，然后更新为B。两个顺序都不是“更正确”的。
如果每个副本只是按照它看到写入的顺序写入，那么数据库最终将处于不一致的状态：最终值将是在主库1的C和主库2的B。这是不可接受的，每个复制方案都必须确保数据在所有副本中最终都是相同的。因此，数据库必须以⼀一种收敛（convergent）的⽅方式解决冲突，这意味着所有副本必须在所有变更复制完成时收敛至一个相同的最终值。

实现冲突合并解决有多种途径：

给每个写入一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或者一个键和值的哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为最后写入胜利利（LWW, last write wins）。虽然这种方法很流行，但是很容易易造成数据丢失。我们将在本章末尾更详细地讨论LWW。
为每个副本分配一个唯一的ID， ID编号更更⾼高的写入具有更高的优先级。这种方法也意味着数据丢失。
以某种方式将这些值合并在一起 - 例如，按字母顺序排序，然后连接它们（在图5-7中，合并的标题可能类似于“B/C”）。
在保留留所有信息的显式数据结构中记录冲突，并编写解决冲突的应⽤用程序代码（也许通过提示用户方式）。

自定义冲突解决逻辑

作为解决冲突最合适的方法可能取决于应用程序，大多数多主复制工具允许使用应用程序代码编写冲突解决逻辑。该代码可以在写入或读取时执行行：

写时执行
只要数据库系统检测到复制更改日志中存在冲突，就会调用冲突处理理程序。例如， Bucardo允许您为此编写一段Perl代码。这个处理程序通常不能提示用户——它在后台进程中运行，并且必须快速执行。

读时执行
当检测到冲突时，所有冲突写入被存储。下一次读取数据时，会将这些多个版本的数据返回给应用程序。应用程序可能会提示用户或自动解决冲突，并将结果写回数据库。例如， CouchDB以这种方式工作。
请注意，冲突解决通常适用于单个行或文档层面，而不是整个事务。因此，如果您有一个事务会原子性地进行几次不同的写入（请参阅第7章），则对于冲突解决而言，每个写入仍需分开单独考虑。

题外话：自动冲突解决
冲突解决规则可能很快变得复杂，并且自定义代码可能容易易出错。亚马逊是一个经常被引用的例子，由于冲突解决处理程序令人惊讶的效果：一段时间以来，购物车上的冲突解决逻辑将保留添加到购物车的物品，但不包括从购物车中移除的物品。因此，顾客有时会看到物品重新出现在他们的购物车中，即使他们之前已经被移走。

已经有一些有趣的研究来自动解决由于数据修改引起的冲突。有几行研究值得一提：

无冲突复制数据类型（Conflict-free replicated datatypes）（CRDT）是可以由多个用户同时编辑的集合，映射，有序列列表，计数器器等的⼀一系列列数据结构，它们以合理理的方式自动解决冲突。一些CRDT已经在Riak 2.0中实现。
可合并的持久数据结构（Mergeable persistent data structures）显式跟踪历史记录，类似于Git版本控制系统，并使⽤用三向合并功能（而CRDT使用双向合并）。
可执行的转换（operational transformation）是Etherpad 【30】和Google Docs【31】等合作编辑应用背后的冲突解决算法。它是专为同时编辑项目的有序列列表⽽而设计的，例如构成⽂文本⽂文档的字符列列表。

这些算法在数据库中的实现还很年轻，但很可能将来它们将被集成到更多的复制数据系统中。自动冲突解决方案可以使应用程序处理理多领导者数据同步更更为简单。

什么是冲突

有些冲突是显⽽而易易⻅见的。在图5-7的例例⼦子中，两个写操作并发地修改了了同一条记录中的同一个字段，并将其设置为两个不同的值。毫⽆无疑问这是⼀一个冲突。其他类型的冲突可能更为微妙，难以发现。例如，考虑一个会议室预订系统：它记录谁腚了了哪个时间段的哪个房间。应用需要确保每个房间只有一组人同时预定（即不得有相同房间的重叠预订）。在这种情况下，如果同时为同⼀一个房间创建两个不不同的预订，则可能会发⽣生冲突。即使应⽤用程序在允许⽤用户进⾏行行

预订之前检查可⽤用性，如果两次预订是由两个不不同的领导者进行行的，则可能会有冲突。现在还没有⼀一个现成的答案，但在接下来的章节中，我们将追溯到对这个问题有很好的理理解。我们将在第7章中看到更更多的冲突示例例，在第12章中我们将讨论⽤用于检测和解决复制系统中冲突的可扩展⽅方法。

多主复制拓扑

复制拓拓扑描述写入从一个节点传播到另一个节点的通信路路径。如果你有两个领导者，如图5-7所示，只有⼀一个合理理的拓拓扑结构：领导者1必须把他所有的写到领导者2，反之亦然。有两个以上的领导，各种不同的拓拓扑是可能的。图5-8举例例说明了一些例例⼦子。

最普遍的拓扑是全部到全部（图5-8 [c]），其中每个领导者将其写入每个其他领导。但是，也会使用更多受限制的拓扑：例如，默认情况下， MySQL仅支持环形拓扑（circular topology），其中每个节点接收来自一个节点的写入，并将这些写入（加上自己的任何写入）转发给另一个节点。另一种流行的拓拓扑结构具有星形的形状。指定的根节点将写入转发给所有其他节点。星型拓拓扑可以推广到树。

在圆形和星形拓扑中，写入可能需要在到达所有副本之前通过多个节点。因此，节点需要转发从其他节点收到的数据更改。为了防止无限复制循环，每个节点被赋予一个唯一的标识符，并且在复制日志中，每个写入都被标记了了所有已经通过的节点的标识符【43】。当一个节点收到⽤用⾃自⼰己的标识符标记的数据更改时，该数据更改将被忽略略，因为节点知道它已经被处理理。

循环和星型拓拓扑的问题是，如果只有一个节点发生故障，则可能会中断其他节点之间的复制消息流，导致它们⽆无法通信，直到节点修复。拓拓扑结构可以重新配置为在发⽣生故障的节点上⼯工作，但在⼤大多数部署中，这种重新配置必须⼿手动完成。更密集连接的拓扑结构（例例如全部到全部）的容错性更更好，因为它允许消息沿着不同的路路径传播，避免单点故障。
另一方⾯面，全能拓扑也可能有问题。特别是，一些⽹网络链接可能⽐比其他⽹网络链接更快（例例如，由于⽹网络拥塞），结果是一些复制消息可能“超过”其他复制消息，如图5-9所示。

在图5-9中，客户端A向林林登万（Leader One）的表中插⼊入⼀一⾏行行，客户端B在主库3上更更新该⾏行行。然⽽而，主库2可以以不不同的顺序接收写⼊入：它可以⾸首先接收更更新（其中，从它的⻆角度来看，是对数据库中不不存在的⾏行行的更更新），并且仅在稍后接收到相应的插⼊入（其应该在更更新之前）。
这是⼀一个因果关系的问题，类似于我们在“⼀一致前缀读”中看到的：更更新取决于先前的插⼊入，所以我们需要确保所有节点先处理理插⼊入，然后再处理理更更新。仅仅在每⼀一次写⼊入时添加⼀一个时间戳是不不够的，因为时钟不不可能被充分地同步，以便便在主库2处正确地排序这些事件（⻅见第8章）。要正确排序这些事件，可以使⽤用⼀一种称为版本向量量（version vectors）的技术，本章稍后将讨论这种技术（参阅“检测并发写⼊入”）。然⽽而，冲突检测技术在许多多领导者复制系统中执⾏行行得不不好。例例如，在撰写本⽂文时， PostgreSQL BDR不不提供写⼊入的因果排序【27】，⽽而Tungsten Replicator for MySQL甚⾄至不不尝试检测冲突【34】。
如果您正在使⽤用具有多领导者复制功能的系统，那么应该了了解这些问题，仔细阅读⽂文档，并彻底测试您的数据库，以确保它确实提供了了您认为具有的保证。

无主复制

我们在本章到目前为止所讨论的复制方法 ——单主复制、多主复制——都是这样的想法：客户端向一个主库发送写请求，而数据库系统负责将写入复制到其他副本。主库决定写入的顺序，而从库按相同顺序应用主库的写入。

一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来⾃自客户端的写⼊入。最早的⼀一些的复制数据系统是⽆无领导的（leaderless）【1,44】，但是在关系数据库主导的时代，这个想法几乎已被忘却。在亚⻢马逊将其⽤用于其内部的Dynamo系统之后，它再一次成为数据库的一种时尚架构【37】。 Riak， Cassandra和Voldemort是由Dynamo启发的⽆无领导复制模型的开源数据存储，所以这类数据库也被称为Dynamo⻛风格。
在一些无领导者的实现中，客户端直接将写入发送到到几个副本中，而另一些情况下，一个协调者（coordinator）节点代表客户端进行行写入。但与主库数据库不同，协调者不执行特定的写入顺序。我们将会看到，这种设计上的差异对数据库的使⽤用⽅方式有着深远的影响。

当节点故障时写入数据库

假设你有一个带有三个副本的数据库，而其中一个副本目前不可用，或许正在重新启动以安装系统更新。在基于主机的配置中，如果要继续处理写入，则可能需要执行故障切换。
另一方面，在无领导配置中，故障切换不存在。图5-10显示了发⽣了什什么事情：客户端（用户1234）并行发送写入到所有三个副本，并且两个可用副本接受写入，但是不可用副本错过了它。假设三个副本中的两个承认写入是足够的：在用户1234已经收到两个确定的响应之后，我们认为写入成功。客户简单地忽略了其中一个副本错过了写入的事实。

现在想象一下，不可用的节点重新联机，客户端开始读取它。节点关闭时发生的任何写入都从该节点丢
失。因此，如果您从该节点读取数据，则可能会将陈旧（过时）值视为响应。
为了解决这个问题，当一个客户端从数据库中读取数据时，它不仅仅发送它的请求到一个副本：读请求
也被并行地发送到多个节点。客户可能会从不同的节点获得不同的响应。即来自一个节点的最新值和来
自另一个节点的陈旧值。版本号用于确定哪个值更新（参阅“检测并发写入”）。

读修复和反熵

复制方案应确保最终将所有数据复制到每个副本。在一个不可用的节点重新联机之后，它如何赶上它错
过的写入？在Dynamo⻛风格的数据存储中经常使⽤用两种机制：
读修复（Read repair）
当客户端并行读取多个节点时，它可以检测到任何陈旧的响应。例如，在图5-10中，用户2345获得了来
自Replica 3的版本6值和来⾃自副本1和2的版本7值。客户端发现副本3具有陈旧值，并将新值写回复制
品。这种方法适用于频繁阅读的值。

反熵过程（Anti-entropy process）
此外，一些数据存储具有后台进程，该进程不断查找副本之间的数据差异，并将任何缺少的数据从一个
副本复制到另一个副本。与基于领导者的复制中的复制日志不同，此反熵过程不会以任何特定的顺序复
制写入，并且在复制数据之前可能会有显着的延迟。并不是所有的系统都实现了了这两个;例如， Voldemort目前没有反熵过程。请注意，如果没有反熵过程，某些副本中很少读取的值可能会丢失，从而降低了持久性，因为只有在应用程序读取值时才执行读修复。

读写的法定人数

在图5-10的示例中，我们认为即使仅在三个副本中的两个上进行处理理，写入仍然是成功的。如果三个副本中只有一个接受了写入，会怎样？我们能推多远呢？
如果我们知道，每个成功的写操作意味着在三个副本中至少有两个出现，这意味着至多有一个副本可能是陈旧的。因此，如果我们从至少两个副本读取，我们可以确定至少有一个是最新的。如果第三个副本停机或响应速度缓慢，则读取仍可以继续返回最新值。

更一般地说，如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。（在我们的例子中， n = 3 ， w = 2 ， r = 2 n = 3， w = 2， r = 2 n=3，w=2，r=2）。只要 w + r > n w + r> n w+r>n，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值， w值的读写称为法定人数（quorum） 6 的读和写。【44】，你可以认为， r和w是有效读写所需的最低票数。
在Dynamo风格的数据库中，参数n， w和r通常是可配置的。一个常见的选择是使n为奇数（通常为3或5）并设置 w = r = （ n + 1 ） / 2 w = r =（n + 1） / 2 w=r=（n+1）/2（向上取整）。但是可以根据需要更更改数字。例例如，设置 w = n w = n w=n和 r = 1 r = 1 r=1的写入很少且读取次数较多的工作负载可能会受益。这使得读取速度更更快，但具有只有一个失败节点导致所有数据库写入失败的缺点。
集群中可能有多于n的节点。（集群的机器数可能多于副本数目），但是任何给定的值只能存储在n个节点上。这允许对数据集进行分区，从而支持可以放在一个节点上的数据集更大的数据集。将在第6章回到分区。

仲裁条件 w + r > n w + r> n w+r>n允许系统容忍不可用的节点，如下所示：
如果 w < n w <n w<n，如果节点不可用，我们仍然可以处理写入。
如果 r < n r <n r<n，如果节点不可用，我们仍然可以处理读取。
对于 n = 3 ， w = 2 ， r = 2 n = 3， w = 2， r = 2 n=3，w=2，r=2，我们可以容忍一个不可用的节点。
对于 n = 5 ， w = 3 ， r = 3 n = 5， w = 3， r = 3 n=5，w=3，r=3，我们可以容忍两个不可用的节点。这个案例例如图5-11所示。
通常，读取和写⼊入操作始终并⾏行行发送到所有n个副本。参数w和r决定我们等待多少个节点，即在我
们认为读或写成功之前，有多少个节点需要报告成功。

如果少于所需的w或r节点可用，则写入或读取将返回错误。由于许多原因，节点可能不可用：因为由于执行操作的错误（由于磁盘已满而无法写入）导致节点关闭（崩溃，关闭电源），由于客户端和服务器之间的⽹网络中断节点，或任何其他原因。我们只关心节点是否返回了成功的响应，而不不需要区分不同类型的错误。

仲裁一致性的局限性

如果你有n个副本，并且你选择w和r，使得 w + r > n w + r> n w+r>n，你通常可以期望每个读取返回为⼀一个键写的最
近的值。情况就是这样，因为你写的节点集合和你读过的节点集合必须重叠。也就是说，您读取的节点
中必须至少有一个具有最新值的节点（如图5-11所示）。
通常， r和w被选为多数（超过 n / 2 n/2 n/2 ）节点，因为这确保了了 w + r > n w + r> n w+r>n，同时仍然容忍多达 n / 2 n/2 n/2个节
点故障。但是，法定人数不一定必须是⼤大多数，只是读写使用的节点交集至少需要包括一个节点。其他法定人数的配置是可能的，这使得分布式算法的设计有一定的灵活性【45】。
您也可以将w和r设置为较⼩小的数字，以使 w + r ≤ n w + r≤n w+r≤n（即法定条件不不满⾜足）。在这种情况下，读取和写
入操作仍将被发送到n个节点，但操作成功只需要少量的成功响应。
较小的w和r更有可能会读取过时的数据，因为您的读取更有可能不包含具有最新值的节点。另一方面，这种配置允许更低的延迟和更高的可用性：如果存在网络中断，并且许多副本变得无法访问，则可以继续处理读取和写入的机会更大。只有当可达副本的数量低于w或r时，数据库才分别变得不可用于写入或读取。

但是，即使在 w + r > n w + r> n w+r>n的情况下，也可能存在返回陈旧值的边缘情况。这取决于实现，但可能的情况包括：

如果使⽤用松散的法定⼈人数（⻅见“松散法定⼈人数与带提示的接⼒力力”）， w个写⼊入和r个读取落在完全不不同的节点上，因此r节点和w之间不不再保证有重叠节点【46】。
如果两个写⼊入同时发⽣生，不不清楚哪⼀一个先发⽣生。在这种情况下，唯⼀一安全的解决⽅方案是合并并发写入（请参阅第171⻚页的“处理理写⼊入冲突”）。如果根据时间戳（最后写⼊入胜利利）挑选出胜者，则由于时钟偏差[35]，写⼊入可能会丢失。我们将返回“检测并发写⼊入”中的此主题。
如果写操作与读操作同时发⽣生，写操作可能仅反映在某些副本上。在这种情况下，不不确定读取是返回旧值还是新值。
如果写操作在某些副本上成功，⽽而在其他节点上失败（例例如，因为某些节点上的磁盘已满），在小于w个副本上写入成功。所以整体判定写入失败，但整体写入失败并没有在写入成功的副本上回滚。这意味着如果⼀一个写⼊入虽然报告失败，后续的读取仍然可能会读取这次失败写入的值【47】。
如果携带新值的节点失败，需要读取其他带有旧值的副本。并且其数据从带有旧值的副本中恢复，则存储新值的副本数可能会低于w，从⽽而打破法定⼈人数条件。
即使⼀一切⼯工作正常，有时也会不幸地出现关于时序（timing）的边缘情况，在这种情况下，您可能会感到不不安，因为我们将在第334⻚页上的“线性化和法定⼈人数”中看到。

因此，尽管法定⼈人数似乎保证读取返回最新的写⼊入值，但在实践中并不不那么简单。 Dynamo⻛风格的数据库通常针对可以忍受最终⼀一致性的⽤用例例进⾏行行优化。允许通过参数w和r来调整读取陈旧值的概率，但把它们当成绝对的保证是不不明智的。
尤其是，通常没有得到“与延迟有关的问题”（读取您的写⼊入，单调读取或⼀一致的前缀读取）中讨论的保证，因此前⾯面提到的异常可能会发⽣生在应⽤用程序中。更更强有⼒力力的保证通常需要事务或共识。我们将在第七章和第九章回到这些话题。

监控陈旧度

从运维的⻆角度来看，监视你的数据库是否返回最新的结果是很重要的。即使应用可以容忍陈旧的读取，您也需要了解复制的健康状况。如果显着落后，应该提醒您，以便您可以调查原因（例如，网络中的问题或超载节点）。

对于基于领导者的复制，数据库通常会公开复制滞后的度量量标准，您可以将其提供给监视系统。这是可能的，因为写⼊入按照相同的顺序应⽤用于领导者和追随者，并且每个节点在复制⽇日志中具有⼀一个位置（在本地应⽤用的写⼊入次数）。通过从领导者的当前位置中减去随从者的当前位置，您可以测量量复制滞后量量。

然而，在无领导者复制的系统中，没有固定的写入顺序，这使得监控变得更加困难。而且，如果数据库只使用读修复（没有反熵过程），那么对于一个值可能会有多大的限制是没有限制的 - 如果一个值很少被读取，那么由一个陈旧副本返回的值可能是古老的。已经有一些关于衡量量无主复制数据库中的复制陈旧度的研究，并根据参数n， w和r来预测陈旧读取的预期百分⽐比【48】。不幸的是，这还不是很常见的做法，但是将过时测量值包含在数据库的标准度量标准中是一件好事。最终的一致性是故意模糊的保证，但是对于可操作性来说，能够量量化“最终”是很重要的。

松散法定人数与带提示的接力

合理配置的法定人数可以使数据库无需故障切换即可容忍个别节点的故障。也可以容忍个别节点变慢，因为请求不必等待所有n个节点响应——当w或r节点响应时它们可以返回。对于需要高可用、低延时、且能够容忍偶尔读到陈旧值的应用场景来说，这些特性使无主复制的数据库很有吸引力。

然而，法定⼈人数（如迄今为止所描述的）并不像它们可能的那样具有容错性。网络中断可以很容易地将
客户端从大量的数据库节点上切断。虽然这些节点是活着的，而其他客户端可能能够连接到它们，但是
从数据库节点切断的客户端，它们也可能已经死亡。在这种情况下，剩余的可用节点可能会少于可用节
点，因此客户端可能无法达到法定人数。
在一个大型的群集中（节点数量明显多于n个），网络中断期间客户端可能连接到某些数据库节点，而不是为了为特定值组成法定人数的节点们。在这种情况下，数据库设计人员需要权衡⼀一下：
将错误返回给我们无法达到w或r节点的法定数量量的所有请求是否更好？或者我们是否应该接受写入，然后将它们写入一些可达的节点，但不在n值通常存在的n个节点之间？

后者被认为是⼀一个松散的法定人数（sloppy quorum）：写和读仍然需要w和r成功的响应，但是那些可能包括不在指定的n个“主”节点中的值。比方说，如果你把自己锁在房⼦子外⾯面，你可能会敲开邻居的门，问你是否可以暂时停留在沙发上。
一旦网络中断得到解决，代表另一个节点临时接受的一个节点的任何写入都被发送到适当的“本地”节点。这就是所谓的带提示的接力（hinted handoff）。（一旦你再次找到你的房⼦子的钥匙，你的邻居礼貌地要求你离开沙发回家。）
松散法定人数对写入可用性的提高特别有用：只要有任何w节点可⽤用，数据库就可以接受写入。然而，
意味着即使当 w + r > n w + r> n w+r>n时，也不能确定读取某个键的最新值，因为最新的值可能已经临时写入了之外的某些节点【47】。
因此，在传统意义上，一个松散的法定人数实际上不不是一个法定⼈人数。这只是一个保证，即数据存储在w节点的地方。不能保证r节点的读取直到提示已经完成。
在所有常见的Dynamo实现中，松散法定人数是可选的。在Riak中，它们默认是启用的，而在Cassandra和Voldemort中它们默认是禁用的【46,49,50】。

运维多个数据中心

我们先前讨论了跨数据中心复制作为多主复制的用例（参阅“多主复制”）。无主复制还适用于多数据中心操作，因为它旨在容忍冲突的并发写入，网络中断和延迟尖峰。
Cassandra和Voldemort在正常的无主模型中实现了他们的多数据中心支持：副本的数量包括所有数据中心的节点，在配置中，您可以指定每个数据中心中您想拥有的副本的数量。无论数据中⼼心如何，每个来自客户端的写入都会发送到所有副本，但客户端通常只等待来自其本地数据中心内的法定节点的确认，从而不会受到跨数据中心链路路延迟和中断的影响。对其他数据中心的高延迟写入通常被配置为异步发生，尽管配置有一定的灵活性【50,51】。
Riak将客户端和数据库节点之间的所有通信保持在一个数据中心本地，因此n描述了一个数据中心内的副本数量。数据库集群之间的跨数据中心复制在后台异步发生，其风格类似于多领导者复制【52】。

检测并发写入

Dynamo风格的数据库允许多个客户端同时写入相同的Key，这意味着即使使用严格的法定人数也会发生冲突。这种情况与多领导者复制相似（参阅“处理写入冲突”），但在Dynamo样式的数据库中，在读修复或带提示的接力期间也可能会产生冲突。
问题在于，由于可变的网络延迟和部分故障，事件可能在不同的节点以不同的顺序到达。例如，图5-12
显示了两个客户机A和B同时写入三节点数据存储区中的键X：
节点 1 接收来⾃自 A 的写入，但由于暂时中断，从不不接收来自 B 的写⼊入。
节点 2 首先接收来⾃自 A 的写入，然后接收来自 B 的写⼊入。
节点 3 首先接收来⾃自 B 的写入，然后从 A 写入。
如果每个节点只要接收到来自客户端的写入请求就简单地覆盖了某个键的值，那么节点就会永久地不一致，如图5-12中的最终获取请求所示：节点2认为 X 的最终值是 B，而其他节点认为值是 A 。
为了最终达成⼀一致，副本应该趋于相同的值。如何做到这一点？有人可能希望复制的数据库能够自动处理，但不幸的是，大多数的实现都很糟糕：如果你想避免丢失数据，你（应用程序开发人员）需要知道很多有关数据库冲突处理的内部信息。
在“处理写冲突”一节中已经简要介绍了一些解决冲突的技术。在总结本章之前，让我们来更更详细地探讨
这个问题。

最后写入胜利（丢弃并发写入）

实现最终融合的一种方法是声明每个副本只需要存储最“最近”的值，并允许“更旧”的值被覆盖和抛弃。然后，只要我们有一种明确的方式来确定哪个写是“最近的”，并且每个写入最终都被复制到每个副本，那么复制最终会收敛到相同的值。
正如“最近”的引号所表明的，这个想法其实颇具误导性。在图5-12的例子中，当客户端向数据库节点发送写入请求时，客户端都不知道另一个客户端，因此不清楚哪一个先发生了。事实上，说“发生”是没有意义的：我们说写入是并发（concurrent）的，所以它们的顺序是不确定的。
即使写入没有自然的排序，我们也可以强制任意排序。例如，可以为每个写入附加一个时间戳，挑选最“最近”的最大时间戳，并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为最后写入胜利（LWW, last write wins），是Cassandra 【53】唯一支持的冲突解决方法，也是Riak 【35】中的一个可选特征。
LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写⼊入将被静默丢弃。此外， LWW甚至可能会删除不是并发的写入，我们将在的“有序事件的时间戳”中讨论。
有一些情况，如缓存，其中丢失的写入可能是可以接受的。如果丢失数据不不可接受， LWW是解决冲突的
一个很烂的选择。
与LWW一起使用数据库的唯一安全方法是确保一个键只写入一次，然后视为不可变，从而避免对同一个
密钥进行行并发更更新。例如， Cassandra推荐使用的方法是使用UUID作为键，从而为每个写操作提供一个
唯一的键【53】。

“此前发生”的关系和并发

我们如何判断两个操作是否是并发的？为了建立一个直觉，让我们看看一些例⼦子：在图5-9中，两个写入不不是并发的： A的插入发生在B的增量之前，因为B递增的值是A插入的值。换句话说， B的操作建⽴立在A的操作上，所以B的操作必须有后来发生。我们也可以说B是因果依赖（causally dependent）于A
另一方⾯面，图5-12中的两个写入是并发的：当每个客户端启动操作时，它不知道另一个客户端也正在执行行操作同样的Key。因此，操作之间不存在因果关系。
如果操作B了解操作A，或者依赖于A，或者以某种方式构建于操作A之上，则操作A在另一个操作B之前发生。在另一个操作之前是否发生一个操作是定义什么并发的关键。事实上，我们可以简单地说，如果两个操作都不在另一个之前发生，那么两个操作是并发的（即，两个操作都不不知道另一个）【54】。
因此，只要有两个操作A和B，就有三种可能性： A在B之前发⽣生，或者B在A之前发生，或者A和B并发。
我们需要的是一个算法来告诉我们两个操作是否是并发的。如果一个操作发生在另一个操作之前，则后面的操作应该覆盖较早的操作，但是如果这些操作是并发的，则存在需要解决的冲突。

并发性，时间和相对性
如果两个操作“同时”发生，似乎应该称为并发——但事实上，它们在字面时间上重叠与否并不重要。由于分布式系统中的时钟问题，现实中是很难判断两个事件是否同时发生的，这个问题我们将在第8章中详细讨论。
为了定义并发性，确切的时间并不重要：如果两个操作都意识不到对方的存在，就称这两个操作并发，⽽而不不管它们发生的物理理时间。人们有时把这个原理理和狭义相对论的物理理学联系起来【54】，它引⼊入了了信息不不能比光速更更快的思想。因此，如果事件之间的时间短于光通过它们之间的距离，那么发⽣生⼀一定距离的两个事件不可能相互影响。

在计算机系统中，即使光速原则上允许一个操作影响另一个操作，但两个操作也可能是并行行的。例如，如果⽹网络缓慢或中断，两个操作间可能会出现一段时间间隔，且仍然是并发的，因为网络问题阻⽌止⼀一个操作意识到另⼀一个操作的存在。

捕获"此前发生"关系

来看一个算法，它确定两个操作是否为并发的，还是一个在另⼀一个之前。为了简单起⻅见，我们从一个只
有一个副本的数据库开始。一旦我们已经制定了了如何在单个副本上完成这项工作，我们可以将该方法概
括为具有多个副本的无领导者数据库。
图5-13显示了两个客户端同时向同一购物车添加⽬目。（如果这样的例子让你觉得太麻烦了了，那么可以
想象，两个空中交通管制员同时把飞机添加到他们正在跟踪的区域）最初，购物车是空的。在它们之
间，客户端向数据库发出五次写⼊入：

客户端 1 将⽜牛奶加⼊入购物⻋车。这是该键的第⼀一次写⼊入，服务器成功存储了它并为其分配版本号1，最后将值与版本号⼀一起回送给客户端。
客户端 2 将鸡蛋加⼊入购物⻋车，不知道客户端 1 同时添加了牛奶（客户端 2 认为它的鸡蛋是购物⻋车中的唯⼀一物品）。服务器器为此写⼊入分配版本号 2，并将鸡蛋和⽜牛奶存储为两个单独的值。然后它将
这两个值都反回给客户端 2 ，并附上版本号 2 。
客户端 1 不知道客户端 2 的写入，想要将⾯面粉加⼊入购物⻋车，因此认为当前的购物⻋车内容应该是 [⽜牛奶，⾯面粉]。它将此值与服务器先前向客户端 1 提供的版本号 1 一起发送到服务器器。服务器器可以从版本号中知道[⽜牛奶，⾯面粉]的写⼊入取代了了[⽜牛奶]的先前值，但与[鸡蛋]的值是并发的。因此，服务器器将版本 3 分配给[⽜牛奶，⾯面粉]，覆盖版本1值[⽜牛奶]，但保留留版本 2 的值[蛋]，并将所有的值返回给客户端 1 。
同时，客户端 2 想要加⼊入⽕火腿，不不知道客端户 1 刚刚加了了⾯面粉。客户端 2 在最后⼀一个响应中从服务器器收到了了两个值[⽜牛奶]和[蛋]，所以客户端 2 现在合并这些值，并添加⽕火腿形成⼀一个新的值，[鸡蛋，⽜牛奶，⽕火腿]。它将这个值发送到服务器器，带着之前的版本号 2 。服务器器检测到新值会覆盖版
本 2 [鸡蛋]，但新值也会与版本 3 [⽜牛奶，⾯面粉]并发，所以剩下的两个是v3 [⽜牛奶，⾯面粉]，和v4：[鸡蛋，⽜牛奶，⽕火腿]
最后，客户端 1 想要加培根。它以前在v3中从服务器器接收[⽜牛奶，⾯面粉]和[鸡蛋]，所以它合并这些，添加培根，并将最终值[⽜牛奶，⾯面粉，鸡蛋，培根]连同版本号v3发往服务器器。这会覆盖v3[⽜牛奶，⾯面粉]（请注意[鸡蛋]已经在最后⼀一步被覆盖），但与v4[鸡蛋，⽜牛奶，⽕火腿]并发，所以服务器器保留留这两个并发值。
图5-13中的操作之间的数据流如图5-14所示。箭头表示哪个操作发⽣生在其他操作之前，意味着后⾯面的操
作知道或依赖于较早的操作。在这个例例⼦子中，客户端永远不不会完全掌握服务器器上的数据，因为总是有另一个操作同时进⾏行行。但是，旧版本的值最终会被覆盖，并且不不会丢失任何写⼊入。

请注意，服务器可以通过查看版本号来确定两个操作是否是并发的——它不不需要解释该值本身（因此该值可以是任何数据结构）。该算法的⼯工作原理理如下：服务器为每个键保留一个版本号，每次写入键时都增加版本号，并将新版本号与写入的值一起存储。

当客户端读取键时，服务器器将返回所有未覆盖的值以及最新的版本号。客户端在写⼊入前必须读取。客户端写⼊入键时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在⼀一起。（来自写⼊入请求的响应可以像读取⼀一样，返回所有当前值，这使得我们可以像购物⻋车示例例那样连接多个写⼊入。）

当服务器器接收到具有特定版本号的写⼊入时，它可以覆盖该版本号或更更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须保持所有值更更⾼高版本号（因为这些值与传⼊入的写⼊入同时发⽣生）。

当⼀一个写⼊入包含前⼀一次读取的版本号时，它会告诉我们写⼊入的是哪⼀一种状态。如果在不不包含版本号的情况下进⾏行行写操作，则与所有其他写操作并发，因此它不不会覆盖任何内容 —— 只会在随后的读取中作为其中⼀一个值返回。

合并同时写入的值

这种算法可以确保没有数据被⽆无声地丢弃，但不不幸的是，客户端需要做⼀一些额外的⼯工作：如果多个操作并发发⽣生，则客户端必须通过合并并发写⼊入的值来擦屁股。 Riak称这些并发值兄弟（siblings）。合并兄弟值，本质上是与多领导者复制中的冲突解决相同的问题，我们先前讨论过（参阅“处理理写⼊入冲突”）。⼀一个简单的⽅方法是根据版本号或时间戳（最后写⼊入胜利利）选择⼀一个值，但这意味着丢失数据。所以，你可能需要在应⽤用程序代码中做更更聪明的事情。

以购物⻋车为例例，⼀一种合理理的合并兄弟⽅方法就是集合求并。在图5-14中，最后的两个兄弟是[⽜牛奶，⾯面粉，鸡蛋，熏⾁肉]和[鸡蛋，⽜牛奶，⽕火腿]。注意⽜牛奶和鸡蛋出现在两个，即使他们每个只写⼀一次。合并的价值可能是像[⽜牛奶，⾯面粉，鸡蛋，培根，⽕火腿]，没有重复。
然⽽而，如果你想让⼈人们也可以从他们的⼿手推⻋车中删除东⻄西，⽽而不不是仅仅添加东⻄西，那么把兄弟求并可能不不会产⽣生正确的结果：如果你合并了了两个兄弟⼿手推⻋车，并且只在其中⼀一个兄弟值⾥里里删掉了了它，那么被删除的项⽬目会重新出现在兄弟的并集中【37】。为了了防⽌止这个问题，⼀一个项⽬目在删除时不不能简单地从数据库中删除;相反，系统必须留留下⼀一个具有合适版本号的标记，以指示合并兄弟时该项⽬目已被删除。这种删除标记被称为墓碑碑（tombstone）。（我们之前在“哈希索引”中的⽇日志压缩的上下⽂文中看到了了墓碑碑。）
因为在应⽤用程序代码中合并兄弟是复杂且容易易出错的，所以有⼀一些数据结构被设计出来⽤用于⾃自动执⾏行行这种合并，如“⾃自动冲突解决”中讨论的。例例如， Riak的数据类型⽀支持使⽤用称为CRDT的数据结构家族【38,39,55】可以以合理理的⽅方式⾃自动合并兄弟，包括保留留删除。

版本向量

图5-13中的示例例只使⽤用⼀一个副本。当有多个副本但没有领导者时，算法如何修改？
图5-13使⽤用单个版本号来捕获操作之间的依赖关系，但是当多个副本并发接受写⼊入时，这是不不够的。相反，除了了对每个键使⽤用版本号之外，还需要在每个副本中版本号。每个副本在处理理写⼊入时增加⾃自⼰己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了了要覆盖哪些值，以及保留留哪些值作为兄弟。
所有副本的版本号集合称为版本向量量（version vector）【56】。这个想法的⼀一些变体正在使⽤用，但最有趣的可能是在Riak 2.0 【58,59】中使⽤用的分散版本⽮矢量量（dotted version vector）【57】。我们不不会深⼊入细节，但是它的⼯工作⽅方式与我们在购物⻋车示例例中看到的⾮非常相似。
与图5-13中的版本号⼀一样，当读取值时，版本向量量会从数据库副本发送到客户端，并且随后写⼊入值时需要将其发送回数据库。（Riak将版本向量量编码为⼀一个字符串串，它称为因果上下⽂文（causalcontext））。版本向量量允许数据库区分覆盖写⼊入和并发写⼊入。
另外，就像在单个副本的例例⼦子中，应⽤用程序可能需要合并兄弟。版本向量量结构确保从⼀一个副本读取并随后写回到另⼀一个副本是安全的。这样做可能会创建兄弟，但只要兄弟姐妹合并正确，就不不会丢失数据。

版本向量量和向量量时钟
版本向量量有时也被称为⽮矢量量时钟，即使它们不不完全相同。差别很微妙——请参阅参考资料料的细节【57,60,61】。简⽽而⾔言之，在⽐比较副本的状态时，版本向量量是正确的数据结构。

案例

Kafka

Greenplum

greenplum的方案：segment分primary和mirror，一一对应的关系，也就是使用基于领导者的复制（主从复制）方式来复制数据。在执行写操作时，会产生xlog事务日志。xlog既可以作为数据库Crash时进行数据恢复的依据，同时也可以作为增量更新传递给从节点。xlog存储在数据目录的pg_xlog目录下。

在主节点上会存在wal-sender进程，从节点上会存在wal-receiver进程，wal-sender进程会将产生的写日志同步给wal-receiver进程来实现冗余。Primary节点和Mirror节点上的wal sender和wal receiver进程可以通过ps命令看到。

复制只是将xlog拷贝到从节点，复制分为同步复制和异步复制。对于同步复制来说，commit操作在xlog同步到从节点后才返回。对于异步复制，xlog刷新到本地磁盘即返回，并不等待从节点提交完，所以xlog同步到从节点是异步的，可能立刻完成，也可能有很大延迟。同步复制保证了主从的一致性，但是增加了事务提交的延迟，另外如果从节点出现了故障，则事务将一会hang住无法提交。异步复制降低了延迟，但是可能存在主从不一致。
为了保证高可用性，目前Greenplum采用的是同步复制。通过GUC synchronous_commit和synchronous_standby_names来控制。其中synchronous_standby_names配置设置同步的子节点信息，通常设置成’*’来表示在所有从节点上使用同步复制（目前最多只支持一个从节点）。synchronous_commit则必须设置成on。

参考文献：

Bruce G. Lindsay, Patricia Griffiths Selinger, C. Galtieri, et al.: “Notes on Distributed
Databases,” IBM Research, Research Report RJ2571(33471), July 1979.
“Oracle Active Data Guard Real-Time Data Protection and Availability,” Oracle White Paper,
June 2013.
“AlwaysOn Availability Groups,” in SQL Server Books Online, Microsoft, 2012.4. Lin Qiao, Kapil Surlaker, Shirshanka Das, et al.: “On Brewing Fresh Espresso: LinkedIn’s
Distributed Data Serving Platform,” at ACM International Conference on Management of Data
(SIGMOD), June 2013.
Jun Rao: “Intra-Cluster Replication for Apache Kafka,” at ApacheCon North America, February
“Highly Available Queues,” in RabbitMQ Server Documentation, Pivotal Software, Inc., 2014.
Yoshinori Matsunobu: “Semi-Synchronous Replication at Facebook,”
yoshinorimatsunobu.blogspot.co.uk, April 1, 2014.
Robbert van Renesse and Fred B. Schneider: “Chain Replication for Supporting High
Throughput and Availability,” at 6th USENIX Symposium on Operating System Design and
Implementation (OSDI), December 2004.
Jeff Terrace and Michael J. Freedman: “Object Storage on CRAQ: High-Throughput Chain
Replication for Read-Mostly Workloads,” at USENIX Annual Technical Conference (ATC), June
Brad Calder, Ju Wang, Aaron Ogus, et al.: “Windows Azure Storage: A Highly Available Cloud
Storage Service with Strong Consistency,” at 23rd ACM Symposium on Operating Systems
Principles (SOSP), October 2011.
Andrew Wang: “Windows Azure Storage,” umbrant, February 4, 2016.
“Percona Xtrabackup - Documentation,” Percona LLC, 2014.
Jesse Newland: “GitHub Availability This Week,” github, September 14, 2012.
Mark Imbriaco: “Downtime Last Saturday,” github, December 26, 2012.
John Hugg: “‘All in’ with Determinism for Performance and Testing in Distributed Systems,” at
Strange Loop, September 2015. Amit Kapila: “WAL Internals of PostgreSQL,” at PostgreSQL
Conference (PGCon), May 2012.
MySQL Internals Manual. Oracle, 2014.
Yogeshwer Sharma, Philippe Ajoux, Petchean Ang, et al.: “Wormhole: Reliable Pub-Sub to
Support Geo-Replicated Internet Services,” at 12th USENIX Symposium on Networked Systems
Design and Implementation (NSDI), May 2015.
“Oracle GoldenGate 12c: Real-Time Access to Real-Time Information,” Oracle White Paper,
October 2013.
Shirshanka Das, Chavdar Botev, Kapil Surlaker, et al.: “All Aboard the Databus!,” at ACM
Symposium on Cloud Computing (SoCC), October 2012.
Greg Sabino Mullane: “Version 5 of Bucardo Database Replication System,”
blog.endpoint, June 23, 2014.
Werner Vogels: “Eventually Consistent,” ACM Queue, volume 6, number 6, pages 14–19,
October 2008. doi:10.1145/1466443.1466448
Douglas B. Terry: “Replicated Data Consistency Explained Through Baseball,” Microsoft
Research, Technical Report MSR-TR-2011-137, October 2011.
Douglas B. Terry, Alan J. Demers, Karin Petersen, et al.: “Session Guarantees for Weakly
Consistent Replicated Data,” at 3rd International Conference on Parallel and Distributed
Information Systems (PDIS), September 1994. doi:10.1109/PDIS.1994.331722
Terry Pratchett: Reaper Man: A Discworld Novel. Victor Gollancz, 1991. ISBN: 978-0-575-04979-
6
“Tungsten Replicator,” Continuent, Inc., 2014.
“BDR 0.10.0 Documentation,” The PostgreSQL Global Development Group, bdr-project,
Robert Hodges: “If You Must Deploy Multi-Master Replication, Read This First,” scale-outblog.blogspot.co.uk, March 30, 2012.
J. Chris Anderson, Jan Lehnardt, and Noah Slater: CouchDB: The Definitive Guide. O’Reilly
Media, 2010. ISBN: 978-0-596-15589-6
AppJet, Inc.: “Etherpad and EasySync Technical Manual,” github, March 26, 2011.
John Day-Richter: “What’s Different About the New Google Docs: Making Collaboration Fast,”
googledrive.blogspot, 23 September 2010.
Martin Kleppmann and Alastair R. Beresford: “A Conflict-Free Replicated JSON Datatype,”
arXiv:1608.03960, August 13, 2016.
Frazer Clement: “Eventual Consistency – Detecting Conflicts,” messagepassing.blogspot.co.uk,
October 20, 2011.
Robert Hodges: “State of the Art for MySQL Multi-Master Replication,” at Percona Live: MySQL
Conference & Expo, April 2013.
John Daily: “Clocks Are Bad, or, Welcome to the Wonderful World of Distributed Systems,”
basho, November 12, 2013.
Riley Berton: “Is Bi-Directional Replication (BDR) in Postgres Transactional?,” sdf, January
4, 2016.
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, et al.: “Dynamo: Amazon’s Highly
Available Key-Value Store,” at 21st ACM Symposium on Operating Systems Principles (SOSP),
October 2007.
Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski: “A Comprehensive Study
of Convergent and Commutative Replicated Data Types,” INRIA Research Report no. 7506,
January 2011.
Sam Elliott: “CRDTs: An UPDATE (or Maybe Just a PUT),” at RICON West, October 2013.
Russell Brown: “A Bluffers Guide to CRDTs in Riak,” gist.github, October 28, 2013.
Benjamin Farinier, Thomas Gazagnaire, and Anil Madhavapeddy: “Mergeable Persistent Data
Structures,” at 26es Journées Francophones des Langages Applicatifs (JFLA), January 2015.
Chengzheng Sun and Clarence Ellis: “Operational Transformation in Real-Time Group Editors:
Issues, Algorithms, and Achievements,” at ACM Conference on Computer Supported
Cooperative Work (CSCW), November 1998.
Lars Hofhansl: “HBASE-7709: Infinite Loop Possible in Master/Master Replication,”
issues.apache, January 29, 2013.
David K. Gifford: “Weighted Voting for Replicated Data,” at 7th ACM Symposium on Operating
Systems Principles (SOSP), December 1979. doi:10.1145/800215.806583
Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman: “Flexible Paxos: Quorum
Intersection Revisited,” arXiv:1608.06696, August 24, 2016.
Joseph Blomstedt: “Re: Absolute Consistency,” email to riak-users mailing list, lists.basho,
January 11, 2012.
Joseph Blomstedt: “Bringing Consistency to Riak,” at RICON West, October 2012.
Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, et al.: “Quantifying Eventual
Consistency with PBS,” Communications of the ACM, volume 57, number 8, pages 93–102,
August 2014. doi:10.1145/2632792
Jonathan Ellis: “Modern Hinted Handoff,” datastax, December 11, 2012.
“Project Voldemort Wiki,” github, 2013.
“Apache Cassandra 2.0 Documentation,” DataStax, Inc., 2014.
“Riak Enterprise: Multi-Datacenter Replication.” Technical whitepaper, Basho Technologies,
Inc., September 2014.
Jonathan Ellis: “Why Cassandra Doesn’t Need Vector Clocks,” datastax, September 22013.
Leslie Lamport: “Time, Clocks, and the Ordering of Events in a Distributed System,”
Communications of the ACM, volume 21, number 7, pages 558–565, July 1978.
doi:10.1145/359545.359563
Joel Jacobson: “Riak 2.0: Data Types,” blog.joeljacobson, March 23, 2014.
D. Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, et al.: “Detection of Mutual Inconsistency
in Distributed Systems,” IEEE Transactions on Software Engineering, volume 9, number 3, pages
240–247, May 1983. doi:10.1109/TSE.1983.236733
Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida, et al.: “Dotted Version Vectors: Logical
Clocks for Optimistic Replication,” arXiv:1011.5808, November 26, 2010.
Sean Cribbs: “A Brief History of Time in Riak,” at RICON, October 2014.
Russell Brown: “Vector Clocks Revisited Part 2: Dotted Version Vectors,” basho,
November 10, 2015.
Carlos Baquero: “Version Vectors Are Not Vector Clocks,” haslab.wordpress, July 8, 2011.
Reinhard Schwarz and Friedemann Mattern: “Detecting Causal Relationships in Distributed
Computations: In Search of the Holy Grail,” Distributed Computing, volume 7, number 3,
pages 149–174, March 1994. doi:10.1007/BF02277859