# 6. 复制


系统可扩展性

<!-- more -->
## 1. 系统的可扩展性
当负载增加需要更强的处理能力时，我们有两种扩展系统的方式:
1. 垂直扩展: 购买更强大的机器
2. 水平扩展: 组合更多数量的机器

垂直扩展通过共享内存和共享磁盘的方式，让操作系统管理更多的 CPU、内存和磁盘，从何获取更强劲的性能。但是这种方式有明显的缺陷:
1. 成本增长过快，并且由于性能，一台拥有两倍的硬件指标的机器不一定能处理两倍的负载
2. **共享架构**只能提供优先的容错能力，并且局限在特定的地理位置，无法提供异地的容错能力

水平扩展的无共享架构不需要专门的硬件，具有较高的性价比，可以跨多个地区。当采用这种架构时，运行软件的机器或者虚拟机称为节点，每个节点独立使用本地的 CPU、内存和磁盘。节点之间的所有协调通信等任务全部运行在传统网络之上且核心逻辑主要依靠软件来实现。

《微服务架构设计模式》阐述了一个概念扩展立方体，它定义在水平扩展下三种不同的扩展应用程序的方法:
1. X轴扩展: 
    - 又称为水平复制，通过克隆实例的方式扩展
    - 在多个相同实例之间实现请求的负载均衡
2. Y轴扩展:
    - 又称为功能性分解
    - 根据功能将应用拆分为服务
3. Z轴扩展:
    - 又称为数据分区，通过类似客户ID的方式，把相似的数据分区进行扩展
    - 根据请求的属性路由请求

![扩展立方体](/images/db/scalability.jpg)

所谓的 Z 轴扩展就与我们接下来要讲述的分布式数据系统有关。将数据分布在多个节点是有另种常见的方式:
1. 复制: 在多个节点上保存相同数据的副本，提供冗余
2. 分区: 将一大块数据拆分成多个较小的子集即分区，不同分区分配给不同节点，用来解决单台机器无法容纳整个数据集的情况

数据的复制和分区经常组合使用。本节我们将介绍数据复制的相关内容。

那么为什么需要多台机器上分布数据呢。通过数据复制，通常希望达到以下目的:
1. 在地理位置上更接近用户，从而降低访问延迟
2. 当部分组件出现故障，系统依然可以继续工作，从而提高可用性
3. 扩展至多台机器以同时提供数据访问服务，从而提高读吞吐量

复制的技术挑战在于处理那些**持续更改的数据**。接下来我们将讨论三种流行的复制数据变化的方法:
1. 主从复制
2. 多主节点复制
3. 无主节点复制

复制技术存在许多需要考虑的地方，例如采用同步复制还是异步复制，如何处理失败的副本，以及数据的一致性问题。接下来我们会一一详述。数据库复制其实是一个古老的问题，因为网络的基本约束条件至今没有发生本质的改变。

## 1. 主从复制
每个保存数据库完整数据集的节点称之为副本，当有多个副本时，不可避免的引入一个问题: 如何确保所有副本之间的数据是一致的。主从复制就是我们经典的解决方案。主从复制的工作原理如下:

![主从复制](/images/db/copy_master.png)

1. 指定一个副本为主副本(主节点)，所有**写请求必须发送给主节点**，主节点首先将更新数据写入本地存储
2. 其他所有副本称为从副本(从节点)，主副本将**数据更改**作为**复制日志或者更改的流**发送给所有从节点。从节点获得更改日志后，严格按照**与主节点相同的写入顺序**更新本地存储
3. 从节点都是只读的

在复制的过程中就有可能存在以下问题:
1. 采用同步复制还是异步复制
2. 如何新增从节点
3. 节点失效如何处理，包括从节点失效和主节点失效问题
4. 复制滞后问题

在介绍这些问题之前，我们先来看看复制日志的实现。

### 1.1 复制日志的实现
复制日志主要有如下几种实现方式:
1. 基于语句的复制
2. 基于预写日志(WAL)的复制
3. 基于行的逻辑日志复制
4. 基于触发器的复制

#### 基于语句的复制
主节点记录下它执行的每个写入请求（语句（statement））并将该语句日志发送给其从库。这种复制有一些不适用的场景:
1. 任何调用非确定性函数（nondeterministic）的语句，可能会在每个副本上生成不同的值，日入 NOW() 获取的当前时间
2. 如果语句使用了自增列（auto increment），或者依赖于数据库中的现有数据（例如，UPDATE ... WHERE <某些条件>），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生不同的效果。当有多个并发执行的事务时，这可能成为一个限制。
3. 有副作用的语句（例如，触发器，存储过程，用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定的。

的确有办法绕开这些问题，但是由于边缘情况实在太多了，现在通常会选择其他的复制方法。

#### 基于预写日志的复制
前面我们介绍存储引擎的索引时，说到写操作通常会先以追加的方式写入到预写日志中:
1. 对于日志结构存储引擎（请参阅“SSTables和LSM树”），日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
2. 对于覆写单个磁盘块的B-tree，每次修改都会先写入预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态

所以无论哪种情况，都可以通过分发日志的方式进行复制。基于预写日志的方式主要缺点是日志记录的数据非常底层：WAL包含哪些磁盘块中的哪些字节发生了更改。这使复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主库和从库上运行不同版本的数据库软件。

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

#### 基于行的逻辑日志复制
另一种方法是，复制和存储引擎使用不同的日志格式，这样可以**使复制日志从存储引擎内部分离出来**。这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。

关系数据库的逻辑日志通常是以行的粒度描述对数据库表的写入的记录序列：
- 对于插入的行，日志包含所有列的新值。
- 对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，但是如果表上没有主键，则需要记录所有列的旧值。
- 对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

MySQL的二进制日志（当配置为使用基于行的复制时）使用这种方法。

对于外部应用程序来说，逻辑日志格式也更容易解析。如果要将数据库的内容发送到外部系统（如数据），这一点很有用，例如复制到数据仓库进行离线分析，或建立自定义索引和缓存。 这种技术被称为 **数据变更捕获**（change data capture）


#### 基于触发器的复制
到目前为止描述的复制方法是由数据库系统实现的，一些工具，如 Oracle Golden Gate ，可以通过读取数据库日志，使得其他应用程序捕获数据变更，从而将复制控制交给应用层，实现特定的复制逻辑。

另一种方式是借助关系型数据的触发器和存储过程实现类似的功能:
1. 触发器将数据变更记录到一个单独的表中
2. 外部处理逻辑通过访问该表获取变更数据

Databus for Oracle 和Bucardo for Postgres 就是这样工作的。

基于触发器的复制通常比其他复制方法具有更高的开销，并且比数据库的内置复制更容易出错，也有很多限制。然而由于其灵活性，仍然是很有用的。

主从复制的原理至此我们就说的差不多，接下来我们来解决主从复制中的那些棘手问题。

### 1.2 同步复制与异步复制
复制非常重要的一个设计选项是：同步复制（synchronously）异步复制（asynchronously）。下面是一个用户更新头像的流程:
1. 从节点1的复制是同步的，主节点需要等待直至从节点1确认了写入，才能向用户报告完成，并将最新的写入对其他客户端可见
2. 从节点2的复制是异步的，主节点发送完消息后立即返回，无需等待从节点2的完成确认

![更新头像](/images/db/update_picture.png)

#### 同步复制
对于同步复制:
1. 优点是: 从库保证有与主库一致的最新数据副本，主库崩溃后，不会丢失最近的更新
2. 缺点是: 如果同步的从节点无法完成确认，写入就不能成功，主节点会阻塞其后的所有的写操作直至同步完成

显然，把所有从节点都设置成同步的有些不切实际，因为任何一个节点的中断都会导致整个系统停滞不前。更常见的配置是半同步:
1. 某一个从节点是同步的，其他节点是异步的
2. 同步的从节点不可用，将另一个异步从节点提升为同步模式
3. 这样可以保证至少有两个节点拥有最新数据

#### 异步复制
异步复制跟同步复制刚好相反，主节点不用任何等待因此系统的吞吐量更好，但是如果主节点失效期不可恢复，那尚未复制到从节点的写请求就会丢失。意味着即使向客户端确认了写操作，仍然无法保证数据的持久化。

异步模式的这种弱化的持久性听起来非常不靠谱，但是异步复制还是被广泛使用，特别是那些从节点数量巨大或者分布与广域地理环境。

因为异步复制无法保证主从节点什么时候，是否一定完成复制，就会产生"复制滞后问题"。

### 1.3 复制滞后问题
主从复制要求所有写请求必须发送给主节点，从节点都是只读的，对于读操作密集的负载是可行。创建多个副本，就可以提高读请求的吞吐量。但是这种情况下只能使用异步复制，因为试图同步所有副本，任何一个节点的中断都会导致整个系统停滞不前。

使用异步复制，因为主节点不会等待从节点确认，主从复制会存在延时。在主从同步的过程中，主从节点可能处于不一致的状态，这种不一致只是一种暂时状态，从节点最终会赶上主节点保持，这种效应被称为**最终一致性**。最终一致性是一个非常弱的保证，副本落后的程度理论上没有上线。接下来我们就来介绍复制滞后可能出现的三个问题:
1. 读自己写
2. 单调读
3. 前缀一致性读

#### 读自己写
读自己写描述的是，用户发起读请求，然后在滞后副本上读取数据，而无法**立即**查看到自己写入的数据。这种情况下我们需要**写后读一致性**。

![写后读](/images/db/reade_after_writer.png)


写后读一致性，又称为读写一致性，保证如果用户重新加载页面，总是能看到自己最近提交的更新。但对其他用户没有任何保证。实现读写一致性有如下几个方法:
1. 如果用户可能访问被修改的内容，直接从主节点读取
3. 如果数据分布在多个数据中心，必须把请求路由到主节点所在的数据中心
2. 使用同步位点的方式，判断从节点是否已经包含用户最近的更新

如果用户可能从多个设备访问数据，例如在桌面 Web 浏览器修改，在移动端设备上立刻查看，情况会更复杂，此时要提供**跨设备的读写一致性**。

如果副本分布在不同的数据中心，很难保证来自不同设备的连接会路由到同一数据中心。 （例如，用户的台式计算机使用家庭宽带连接，而移动设备使用蜂窝数据网络，则设备的网络路线可能完全不同）。如果你的方法需要读主库，可能首先需要把来自同一用户的请求路由到同一个数据中心。

#### 单调读
单调读描述的是: 用户看到了最新内容之后又读到了过期的内容，好像时间被回拨。此时需要**单调读一致性**。

![单调读](/images/db/continue_read.png)

单调读是一个比强一致性弱，但比最终一致性强的保证，其保证某个用户一次进行多次读取，不会看到回滚现象(在读取较新值之后又发生读旧值的情况)。

实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取（不同的用户可以从不同的副本读取）。例如，可以基于用户ID的散列来选择副本，而不是随机选择副本。但是，如果该副本失败，用户的查询将需要重新路由到另一个副本。

#### 前缀一致读
前缀一致读描述的是: 分区数据经多副本复制后出现了不同程度的之后，导致用户先看到果(后发生的事)后看到因(先发生的事)。

![前缀一致读](/images/db/prefix_read.png)

这是分区数据库中出现的一个特殊问题，**如果数据库总是以相同的顺序写入，则读取总是看到一致的序列**，不会发生这种反常。然而在许多分布式数据库中，**不同的分区独立运行，因此不存在全局写入顺序**。这就导致当用户从数据库中读取数据时，可能看到数据库的某部分旧值和另一部分新值。

**前缀一致读**保证的是，对于一系列按照某个顺序发生的写请求，读取这些内容时也会按照当时写入的顺序。

一种解决方案是，确保**任何具有因果顺序关系的写入交给一个分区来完成。但这个方案的真实效果会打打折扣，难点就在于如何判断不同操作之间的因果关系。还有一些显式跟踪因果依赖关系的算法，我们待会再来详细介绍。

#### 总结
使用最终一致性系统时，最好先考虑这样的问题: **如果复制延迟增加到几分钟甚至几小时，那么应用层的行为会是什么样子**。如果带来糟糕的用户体验，那么在设计系统时 就要考虑提供一个更强的一致性保证，比如**写后读一致性**，**单调读**，**前缀读**。 

在应用层可以提供比底层数据库更强有力的保证，而代价是应用层代码处理这些问题通常会非常复杂。如果假定数据库在做正确的事，情况会变得简单，而这也是事务存在的原因，**事务是数据库提供更强保证的一种方式**。


### 1.4 配置新的从节点
如果需要增加新的副本，如何确保新的从节点与主节点保持一致呢，逻辑上的主要操作如下:
1. 在某个时刻获取主库的一致性快照
2. 将此快照拷贝到新的节点
3. 从库连接到主库，并拉取快照之后发生的所有数据变更，这要求快照与主库复制日志中的位置精确关联

### 1.5 处理节点失效
节点失效与系统的高可用性有关，我们的目标是，尽管个别节点会出现中断，但要保持系统总体的持续运行，并尽可能减少节点中断带来的影响。那如何使用主从复制实现系统的高可用呢?
1. 从节点失效: 追赶式恢复
2. 主节点失效: 节点切换

#### 从节点失效
在主从复制下，失效的从节点在恢复正常后会自动恢复


#### 主节点失效
主节点失效需要进行节点切换:
1. 选择某一从节点为主节点
2. 客户端需要更新，保证后续写请求路由到新的主节点
3. 其他从节点需要更新，以从新的主节点接收并更数据

切换可以手动进行，也可以自动切换，通常步骤如下:
1. 确认主节点失效，大多数都基于超时机制，节点之间相互发送心跳信息
2. 选取新的主节点
    - 可以通过选举方式进行，让所有从节点同意新的主节点属于典型的共识问题，
    - 也可以让系统中的控制器来指定新的主节点，候选节点最好与原主节点的数据差异最小，最小化数据丢失
3. 重新配置系统使得主节点生效，包括客户端、从节点的主节点指向
4. 确保原来的主节点恢复后降级为从节点，并认可新的主节点

切换过程中充满变数:
1. 产生冲突写
2. 有外部数据库依赖当前数据库进行协同使用
3. 脑裂
4. 超时时间设置
5. 系统已经处于高压状态或者出现网络拥堵导致主节点失效，不必要的切换会加重系统负担。因此有些运维团队更加愿意手动控制整个切换过程

上述这些问题，包括节点失效、网络不可靠、副本一致性、持久性、可用性与延迟之间的各种细微权衡。没有简单的解决方案。

## 2. 多主复制
主从复制有一个明显缺点，系统只有一个主节点，所有写入必须经由主节点。对主从复制的自然扩展就是配置多个主节点，每个主节点都可以接受写操作。

在一个数据中心内部使用多个主节点基本没有太大意义，其复杂度已经超过所能带来的好处。但是在多数据中心下，多主复制是合理的:

为了容忍数据中心级别故障或者更接近用户，设置多个数据中心；每个数据中心一个主节点，在**数据中心内部采用主从复制**，数据中心之间，由各个数据中心的**主节点负责同其他数据中心主节点进行数据交换和更新**。**多个数据中心之间采用异步复制**，可以更好的容忍广域网带来的网络延迟。CouchDB 是为这种操作模式而设计的。

![多数据中心](/images/db/multi_center.png)

**多主复制的最大问题是可能发生写冲突**。

### 2.1 处理写冲突
多主复制会产生冲突的原因在于多个主节点都只是按照它所看到的写入顺序执行，缺乏全局的写入顺序。数据库最终将处于不一致的状态。

![两个主节点同时编译同一条记录而导致写冲突](/images/db/multi_writer_confict.png)


所有的复制模型至少应该确保数据在所有副本中最终状态一定是一致的。因此数据库必须以一种收敛趋同的方式来解决冲突。这也意味着所有更改最终被复制、同步之后，所有副本的最终值是相同的。

实现收敛的冲突解决有以下几种可能的方式:
1. 最终写入者获胜: 给每个写入分配一个唯一 ID，挑选最高 ID 的写入作为胜利者，覆盖其他写入。这种方法很容造成数据丢失
2. 值组合: 记录和保留冲突相关的所有信息，由用户或者应用程序逻辑决定如何解决写入冲突

理论上我们还有两种方式解决写冲突问题:
1.同步冲突检测:
    - 可以在多主复制中同步进行冲突检测，即等待写请求完成对所有副本的同步，然后在通知用户写入成功。
    - 但是这样做将失去多主节点的优势: 允许每个主节点独立接收写请求
    - 如果想实现同步冲突检测，或许更应该考虑采用单主节点的主从复制。
2. 避免冲突:
    - 应用程序保证对特定记录的写请求总是路由到同一主节点，从用户角度这基本等价于主从复制模型
    - 但是无法保证路由的始终一致，比如数据中心已经发生故障，或者用户已经漫游到另一位置，因而更靠近新的数据中心，所以从冲突无法根本避免

最后冲突解决通常用于单个行或文档。因此如果一个原子事务包括多个不同写请求，每个写请求仍然是分开解决冲突的。

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

### 2.3 复制拓扑
复制拓扑描述了写请求从一个节点传播到其他节点的通信路径。如果存在多个主节点，会有多个可能的同步拓扑:

![复制拓扑](/images/db/sync_topo.png)

复制拓扑需要解决的一个问题是**防止无限循环**，每个节点需要赋予一个唯一的标识符，在复制日中的每个写请求都标记了已通过的节点标识。如果节点收到了包含自身标识符的数据修改则忽略请求，避免重复转发。

另一个问题则是复制拓扑中可能存在某些网络链路比其他链路更快的情况，从而导致复制日志之间的覆盖:

![复制日志覆盖问题](/images/db/topo_over.png)

在上图的更新序列中，主节点3 是执行插入然后在更新，新插入的行被更新。但是在主节点2 中，由于网络延迟先执行了更新后执行的插入，插入的行则未被更新。

这里涉及到一个因果关系问题，类似前面的前缀一致读: 更新操作一定是依赖于先前完成的插入，因此我们需要确保所有节点上一定要先接收插入之日，在处理更新。在每笔写入中简单添加时间戳是不够的，因为无法保证时钟同步。

为了使得日志消息正确有序，可以使用一种称为**版本矢量**的计数(后面会详细介绍)。需要指出冲突检测计数在许多多主复制系统中还不够完善。

## 3. 无主节点复制
单主节点和多主节点复制都基于这样一种核心思路，即客户端先向某个节点(主节点)发送写请求，然后数据库系统负责将写请求复制到其他副本。主节点决定操作的写入顺序，从节点按照相同的顺序来应用主节点所发送的写日志。

而对于无主节点复制的系统，允许任何副本直接接受来自客户端的写请求，并没有固定的写入顺序。

Riak，Cassandra和Voldemort是由Dynamo启发的无主节点、开源数据库，所以这类数据库也被称为Dynamo风格。

### 3.1 无主节点的 quorum 读写
无主节点复制模型允许多个客户端对相同的键同时发起写操作:
1. 如果总共有 n 个副本，写入需要 w 个节点确认，读取需要查询 r 个节点，则只要 w + r > n，读取的节点中一定包含最新值。
2. 仲裁条件 w + r > n 定义了系统可容忍的失效节点数:
3. w,r 参数只是决定要等待的节点数，读写请总是并行发送到所有 n 个副本的
4. quorum 不一定非得是多数，读写的节点集合有一个重叠的节点才是最关键的。

最后，无主节点的数据库使用**版本矢量**确定哪个值更新，版本矢量技术我们待会详述。

### 3.2 无主模型的数据复制
因为读写请总是并行发送到所有 n 个副本的，所以在没有节点失效的情况下，无需进行数据的复制操作。但是节点失效后恢复上线，如何确保所有数据复制到这些失效副本中。通常有两种机制:
1. 读修复:
    - 客户端读取时，可以检测到过期的返回值，并在此时执行复制
    - 此方法适用于频繁读取的场景
2. 反熵过程:
    - 又后台进程不断查找副本之间的数据差异并执行复制
    - 与基于主从复制中的复制日志不同，此反熵过程不保证以特定的顺序复制写入，并且会引入明显的同步滞后

### 3.3 quorum 一致性的局限性
与多主复制一样，无主复制一样缺乏全局的写入顺序，如果两个写操作同时发生，会导致数据冲突。而且即便 w + r > n 的情况下，也可能返回旧值:
1. 如果写操作与读操作同时发生，**写操作还未返回，但是可能已经反映在某些副本上**。在这种情况下，不能确定读取的是旧值还是新值
2. 如果写操作在某些副本上成功，而在其他节点上失败（例如，因为某些节点上的磁盘已满），在小于w个副本上写入成功。所以**整体判定写入失败**，但整体写入失败并没有在写入成功的副本上回滚。这意味着如果一个写入虽然报告失败，后续的读取仍然可能会读取这次失败写入的值
3. 如果携带新值的节点失败，但是恢复数据来自某个旧值，则总的新值副本数会低于 w，这就打破了 w + r > n 的判定条件

因此，尽管 quorum 设计上似乎可以保证读取最新值，但在实践中并不那么简单。 Dynamo风格的数据库通常针对最终一致性场景而优化。但是最好不要把 w 和 r 视为绝对的保证。而是一种灵活可调的读取新值的概率。

无法保证得到前面所说的任意一致性保证，包括: 写后读、单调读、前缀一致读。如果需要更强的保证，需要考虑事务和共识。

## 4. 检测并发写
前面我们多次提到版本矢量技术。这是一种确定并发写入顺序以解决写入冲突的一种技术。副本应该收敛于相同的内容，这样才能达到最终一致。因此我们必须了解数据库内部冲突处理机制。在详细介绍冲突处理之前，我们首先需要确定**如何判断两个操作是并发的？**。

### 4.1 happen before 和并发
我们可以简单的说，如果两个操作都不在另一个之前发生，那么操作就是并发的(或者**两者都不知道对方的存在**)。我们需要一个算法来判断两个操作是否并发:
1. 如果一个操作发生在另一个操作之前，则后面的操作可以覆盖较早的操作
2. 如果属于并发，就需要解决潜在的冲突问题

### 4.2 版本矢量
我们来看一个确定操作并发性的算法--版本矢量，算法的工作流程如下:
1. 服务器为每个主键维护一个版本号，每当主键对应的记录变化时，递增版本号，并将新的版本号和写入的值一起保存
2. 客户端读取主键时，服务器返回所有当前值，以及最新的版本号，其要求**写之前，客户端必须先发送读请求**，即确定新的写请求依赖哪些的版本号
3. 客户端写主键，写请求必须包含之前读到的版本号、**读到的值和新值合并后的集合**(执行数据合并，合并并发写)
4. 当服务器接收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值(因为知道这些值已经被合并到新传入的集合中)。但是必须保存更高版本号的所有值(因为这些值和当前的写操作属于并发)。

版本矢量保证不会发生数据丢失，客户端需要做一些额外工作: 如果多个操作并发，客户端必须通过合并并发写入的值来继承旧值。考虑到数据合并非常复杂且容易出错，因此可以设计一些专门的数据结构来自动执行合并。例如 Riak 支持称为 **CRDT 一系列数据结构**，以合理的方式高效自动合并，包括支持删除标记。

注意上面描述的是只有一个副本的情况，如果存在多个副本(多主复制中的多个主节点，无主复制中的所有副本)需要为每个副本和每个主键都定义一个版本号，每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本看到的版本号。所有副本的版本号集合称为版本矢量。具体的工作流程与上面介绍的类似。

版本矢量技术是数据库可以区分哪些值更新，应该覆盖写还是保留并发值。

### 4.2 最终写入者获胜
解决写入冲突是为了让副本趋于一致，所以我们也可以不管是否发生并发写入，只要保证数据一致即可，只要我们有一个明确的方法确定哪一个写入时最新的，副本就可以最终收敛到相同的值。即便无法确定写请求的自然顺序，我们也可以强制进行排序。

这种冲突解决算法被称为最后写入胜利（LWW, last write wins），是Cassandra 唯一支持的冲突解决方法。

LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写入将被静默丢弃。如果丢失数据不可接受，LWW是解决冲突的一个很烂的选择。

要确保 LWW 安全无副作用的唯一方法是，值写入一次然后视为不可变，这样就避免了对同一主键的并发写。例如，Cassandra推荐使用的方法是使用UUID作为键，从而为每个写操作提供一个唯一的键。

### 4.4 总结
写入冲突的根本原因是没有全局的写入顺序，因此写入冲突不会发生在主从复制中，因为只有单一的主节点，它掌握了全局的写入顺序。

主从复制非常流行，因为它很容易理解，也不需要担心冲突问题，但是万一出现节点失效、网络中断和抖动，多主节点和无主节点则更加可靠，不过背后的代价是系统的复杂性和弱一致性保证。