主从复制模型的数据更新符合顺序性原则:若同一字段有多个更新,则最后一个写操作决定该字段的终值。
而多主复制模型不存在这样的写入顺序,所以终值不确定。图-7中:
主节点1中title,先更新为B,再更新为C
主节点2中,先更新为C,再更新为B
二者无法辨识谁“更正确”。
若每个副本都按其看到写入的顺序执行,则DB最终将处于不一致状态,如主1看到终值C,而主2看到B。这是不可接受的,所有复制模型至少须确保数据在所有副本中的最终状态一致。因此,DB必须以一种收敛方式解决冲突,即所有副本必须在所有变更复制完成时,所有副本的终值相同。
3.2.3.1 收敛冲突解决方案
给每个写入一个唯一ID(如一个时间戳,一个长随机数,一个UUID或一个哈希),挑选最高ID的写入作为胜利者,并丢弃其他写入。若基于时间戳,这种技术称为最后写入胜利(LWW, last write wins)。虽然这种方法很流行,但很容易造成数据丢失。后文再详细讨论。
为每个副本分配一个唯一ID并制定规则,如ID编号更高的副本写入始终具有更高优先级。不过也可能数据丢失
某种方式将这些值合并,如按字母排序,然后连接(图-7,合并的标题可能类似“B/C”)
利用预定义好的格式记录和保留冲突相关的所有信息,然后依靠应用层逻辑,事后解决冲突 (可能会提示用户)
3.2.4 自定义冲突解决逻辑
解决冲突最合适的可能还得仰仗应用层,所以多主节点复制模型都有工具,允许应用代码解决冲突,可在写或读时执行这些代码逻辑:
① 写时执行
只要DB系统检测到复制变更日志时存在冲突,就调用冲突处理程序。如Bucardo允许编写一段Perl代码。该处理程序通常不能在线提示用户,只能在后台进程运行
② 读时执行
检测到冲突时,所有冲突写入值都会被暂存。下次读时,会将数据的多版本返回给应用层。应用可能会提示用户或自动解决冲突,并将最后结果写回DB。如CouchDB。
冲突解决通常适用于单行或文档,而非整个事务。因此,若有一个原子事务包含多个不同写请求,每个写请求仍需分开考虑来解决冲突。
3.2.5 什么是冲突?
有些冲突显而易见,如图-7的两个写操作并发修改同一条记录中的同一字段,并设为两个不同值。其他类型的冲突可能就微妙了。
如会议室预订系统,记录谁订了哪个时间段的哪个房间。应用需确保每个房间只有一组人同时预定(禁止相同房间的重复预订)。此时,若同时为同一房间创建两个不同预订,就冲突了。尽管应用在预订时会检查房间可用性,但若两次预订由两个不同主节点进行,则还是可能冲突。
3.2.6 自动冲突解决
冲突解决规则可能会愈来愈复杂,且自定义代码易出错。亚马逊就是经典反例:有段时间,购物车上的冲突解决逻辑依靠用户的购物车页面(保存了所有的物品),但顾客有时发现之前已被拿掉的商品,再次出现在他们的购物车。
一些有趣的研究尝试自动解决由于数据并发修改引起的冲突:
无冲突复制数据类型(Conflict-free replicated datatypes,CRDT)
可由多个用户同时编辑的集合,映射,有序列表,计数器等数据结构,它们以合理方式自动解决冲突。一些CRDT已在Riak 2.0实现
可合并的持久数据结构(Mergeable persistent data structures)
显式跟踪历史记录,类似Git,并使用三向合并功能(而CRDT使用双向合并)
可执行的转换(operational transformation)
Etherpad和Google Docs等合作编辑应用背后的冲突解决算法。专为同时编辑项目的有序列表而设计的,例如构成文本文档的字符列表
这些算法在DB中的实现还很年轻,但很可能将来它们将被集成到更多的复制数据系统中。自动冲突解决方案可以使应用程序处理多领导者数据同步更为简单。可惜没有现成答案。