在 TLA+ 中指定可串行化性

主要观点:并发对于人类来说很难理解,TLA+源于莱斯利·兰伯特对编写无错误并发算法的困难的挫折。数据库系统中的并发控制是 TLA+的一个很好的用例,本文主要建模可序列化。通过定义一系列操作和变量,如 op、arg、rval、tr 等,来描述数据库事务的隔离级别和可序列化性,还讨论了活性条件(包括对于中止和提交的公平性)以及如何通过细化映射到顺序规范来验证可序列化规范等。

关键信息

  • TLA+由莱斯利·兰伯特因并发算法困难而产生。
  • 数据库建模只需关注行(对象),忽略表等细节。
  • 可序列化定义及相关例子,如不同事务的读写顺序。
  • 规定了规范中的外部可见变量及初始状态。
  • 描述了规范允许的操作(如提交、中止、读、写)及约束。
  • 提到活性条件(弱公平性和强公平性)以确保事务最终提交或中止。
  • 可通过细化映射到顺序规范来验证可序列化规范,还可通过不变量进一步验证。

重要细节

  • 用不同的符号表示读(r[obj, val])和写(w[obj, val])操作。
  • 举例说明事务的局部环境(tenv)随时间和写操作而变化。
  • 详细阐述弱公平性和强公平性在不同场景下的应用。
  • 给出具体的可序列化 TLA+模型及相关文件位置。
  • 提到后续将用模型检查器找出多版本并发控制不满足可序列化规范的反例。
阅读 16
0 条评论