并发性，时间和相对性(2)

4.4.2 合并同时写入的值

该算法可确保不会发生数据丢弃，但客户端要做额外工作：若多个操作并发，则客户端必须通过合并并发写入的值来继承旧值。

合并本质和多节点复制中的冲突解决类似，即处理写冲突。一个简单方案：基于版本号或时间戳（即最后写入胜利）选择一个值，但这意味着会丢失数据。所以，需要在应用程序代码中做额外工作。

如购物车，合理的合并并发值是包含新值和旧值。在图-14中，两个客户端最后的值是[牛奶，面粉，鸡蛋，熏肉]和[鸡蛋，牛奶，火腿]。虽然牛奶、鸡蛋在两个客户端都出现了，虽然只写入了一次。合并最终值应该是[牛奶，面粉，鸡蛋，培根，火腿]，其中去掉了重复值。

设想人们也可以从他们的购物车删除商品，此时把并发值都合并起来可能会导致错误结果：若合并了两个客户端的值，且其中有一个商品被某客户端删掉，则被删除的项目会再次出现在合并的最终值中。为防止该问题，项目在删除时不能简单从DB删除，系统必须保留一个对应版本号以恰当的标记该项目需要在合并时被删除。这种删除标记被称为墓碑（逻辑删除）。

考虑到应用程序代码中合并非常复杂且易出错，可设计一些数据结构自动执行合并。

4.4.3 版本向量

图-13示例只有一个副本。若存在多个副本但无主节点，算法该如何修改？

图-13使用单个版本号来捕获操作之间的依赖关系，当多个副本同时接受写入时，这不够。因此，需要为每个K、每个副本都定义一个版本号。每个副本在处理写入时，增加自身版本号，并跟踪从其他副本中看到的版本号。通过这些信息指示要覆盖哪些值、保留哪些并发值。

所有副本的版本号集称为版本向量。与图-13版本号一样，当读数据时，版本向量会从数据库副本发送到客户端，随后写入值时需将版本信息包含在请求中一起发送回数据库。版本向量使得DB 可以区分应该覆盖写还是保留并发值。

就像单副本，应用程序仍需执行合并操作。版本向量可确保从某副本读取，随后写入到另一个副本。这些值可能导致在其他副本上衍生出新的兄弟值，但至少不会丢失数据且能正确合并所有并发值。

版本向量和向量时钟

版本向量有时也称为矢量时钟，但不完全相同，简而言之，需要比较副本状态时，应使用版本向量。