并发性，时间和相对性

若两个操作同时发生，则称为并发，但事实上，操作是否在时间上重叠并不重要。由于分布式系统复杂的时钟同步问题，现实中很难严格判断两个事件是否同时发生。

为更好定义并发性，并不依赖确切发生时间，即若两个操作并不需要意识到对方，就能说它们是并发操作，而不管它们发生的物理时间。

计算机系统中，即使光速快到允许一个操作影响另一个操作，但两个操作也可能并发。如网络拥塞或中断，可能就会出现两个操作由于网络问题导致一个操作无法感知另一个，因此二者成为并发。

确定前后关系

来看确定两个操作是否为并发的算法。从只有一个副本的数据库开始。

图-13显示两个客户端同时向购物车添加商品。最初，购物车为空。然后两个客户端向DB发出五次写入操作：

1. 客户端1先将牛奶加入购物车。这是第一次写入该 K 的值，服务器成功存储并为其分配版本号1，最后将值与版本号一起返回给客户端1
2. 客户端2将鸡蛋加入购物车，此时不知客户端1已经添加了牛奶（客户端2认为它的鸡蛋是购物车中的唯一物品）。服务器为此写入分配版本号2，并将鸡蛋和牛奶存储为两个单独的值。最后将这两个值都反回给客户端 2 ，并附上版本号2
3. 同理，客户端1也不知道客户端2的写入，想要将面粉加入购物车，因此认为当前购物车应该是[牛奶，面粉]。将此值与服务器先前向客户端1提供的版本号1一起发送到服务器。服务器可从版本号中知道[牛奶，面粉]的新值写入要取代[牛奶]的先前值，但与[鸡蛋]值是并发的。因此，服务器将版本3分配给[牛奶，面粉]，并覆盖版本1的[牛奶]，但同时保留版本2的值[鸡蛋]，将二者的值同时返回给客户端1
4. 同时，客户端 2 想要加入火腿，不知道客端户 1 刚刚加了面粉。客户端 2 在最后一个响应中从服务器收到了两个值[牛奶]和[蛋]，所以客户端 2 现在合并这些值，并添加火腿形成一个新的值，[鸡蛋，牛奶，火腿]。它将这个值发送到服务器，带着之前的版本号 2 。服务器检测到新值会覆盖版本 2 [鸡蛋]，但新值也会与版本 3 [牛奶，面粉]并发，所以剩下的两个是v3 [牛奶，面粉]，和v4：[鸡蛋，牛奶，火腿]
5. 最后，客户端 1 想要加培根。它以前在v3中从服务器接收[牛奶，面粉]和[鸡蛋]，所以它合并这些，添加培根，并将最终值[牛奶，面粉，鸡蛋，培根]连同版本号v3发往服务器。这会覆盖v3[牛奶，面粉]（请注意[鸡蛋]已经在最后一步被覆盖），但与v4[鸡蛋，牛奶，火腿]并发，所以服务器保留这两个并发值

图-13操作之间的数据流如图-14。 箭头表示哪个操作先于发生其他操作，即后面操作知道或依赖前面的操作。 该例中，客户端永远不会完全掌握服务器上的数据，因为总有另一个操作同时进行。 但新版本值最终会覆盖旧值，且不会发生已写入值的丢失。

服务器判断操作是否并发的依据主要依靠对比版本号，无需解释该新旧值本身（值能是任何数据结构）。算法工作流程：

• 服务器为每个K保留一个版本号，每次K新值写入时递增版本号，并将新版本号与写入的值一起保存
• 当客户端读取K时，服务器将返回所有（未覆盖的值）当前值及最新版本号。且要求写之前，客户端须先发送读请求
• 客户端写K时，写请求必须包含之前读的版本号、之前读取的所有值合并后的集合。 写请求的响应可以像读请求一样，返回所有当前值，这样就能像购物车示例那样将多个写入串联起来。）
• 当服务器接收到待有特定版本号的写入时，覆盖版本号或更低版本的所有值（因为知道这些值已被合并到新传入的值集合中），但必须保存更高版本号的所有值（因为这些值与当前的写是并发）

当写请求包含前一次读取的版本号时，意味着修改的是基于之前的状态。若一个写请求不包含版本号，他讲和所有其他写操作并发，不会覆盖任何已有值，其传入的值将包含在后续读请求的返回值列表当中。