并发性,时间和相对性(1)-确定前后关系

x33g5p2x  于2022-08-17 转载在 其他  
字(1.5k)|赞(0)|评价(0)|浏览(300)

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

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

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

确定前后关系

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

图-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时,写请求必须包含之前读的版本号、之前读取的所有值合并后的集合。 写请求的响应可以像读请求一样,返回所有当前值,这样就能像购物车示例那样将多个写入串联起来。)
  • 当服务器接收到待有特定版本号的写入时,覆盖版本号或更低版本的所有值(因为知道这些值已被合并到新传入的值集合中),但必须保存更高版本号的所有值(因为这些值与当前的写是并发)

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

相关文章

微信公众号

最新文章

更多