多主复制下处理写冲突(3)-收敛至一致的状态及自定义冲突解决逻辑

3.2.3 收敛至一致的状态

主从复制模型，数据更新符合顺序性原则，即若同一字段有多个更新，则最后一个写操作将决定该字段最终值。

多主复制模型中，由于不存在这样的写入顺序，所以最终值也不确定。图-7中：

• 主节点1中标题首先更新为B而后更新为C
• 主节点2中，首先更新为C，然后更新为B

二者无法辨识谁“更正确”。

若每个副本都按其看到写入的顺序执行，则DB最终将处于不一致状态，如主节点1看到最终值C，而主节点2看到B。这是不可接受的，所有复制模型至少须确保数据在所有副本中的最终状态都一致。因此，DB必须以一种收敛（convergent）方式解决冲突，这意味着所有副本必须在所有变更复制完成时，所有副本最终值相同。

3.2.3.1 收敛冲突解决方案

• 给每个写入一个唯一ID（如一个时间戳，一个长随机数，一个UUID或一个哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。若基于时间戳，这种技术称为最后写入胜利（LWW, last write wins）。虽然这种方法很流行，但很容易造成数据丢失。后文再详细讨论。
• 为每个副本分配一个唯一ID并制定规则，如ID编号更高的副本写入始终具有更高优先级。不过也可能数据丢失
• 某种方式将这些值合并，如按字母排序，然后连接（图-7，合并的标题可能类似“B/C”）
• 利用预定义好的格式记录和保留冲突相关的所有信息，然后依靠应用层逻辑，事后解决冲突 （可能会提示用户）

3.2.4 自定义冲突解决逻辑

解决冲突最合适的可能还是得依靠应用层，所以不少的多主节点复制模型都有工具，允许使用应用代码解决冲突，可在写入或读取时执行这些代码逻辑：

写时执行

只要DB系统检测到复制变更日志时存在冲突，就会调用冲突处理程序。如Bucardo允许编写一段Perl代码。该处理程序通常不能在线提示用户，只能在后台进程运行

读时执行

检测到冲突时，所有冲突写入值都会被暂存。下次读时，会将数据的多版本返回给应用层。应用可能会提示用户或自动解决冲突，并将最后结果写回DB。如CouchDB。

冲突解决通常适用于单行或文档，而非整个事务。因此，若有一个原子事务包含多个不同写请求，每个写请求仍需分开考虑来解决冲突。

什么是冲突？

有些冲突显而易见，如图-7的两个写操作并发修改同一条记录中的同一字段，并设为两个不同值。

其他类型的冲突可能就微妙了。如会议室预订系统，记录谁订了哪个时间段的哪个房间。应用需确保每个房间只有一组人同时预定（不得有相同房间的重复预订）。此时，若同时为同一房间创建两个不同预订，就冲突了。尽管应用在预订时会检查房间可用性，但若两次预订由两个不同主节点进行，则还是可能冲突。

自动冲突解决

冲突解决规则可能会愈来愈复杂，且自定义代码易出错。亚马逊是经典反例：有段时间，购物车上的冲突解决逻辑依靠用户的购物车页面（保存了所有的物品），但顾客有时发现之前已被拿掉的商品，再次出现在他们的购物车。

一些有趣研究尝试自动解决由于数据并发修改引起的冲突：

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

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

可惜没有现成答案，后文将更深入解析。