Wanjia Huang

西南交通大学 软件工程

0%

CMU15445-017-TimestampOrderingConcurrencyControl

发表于 更新于 分类于

Timestamp Ordering Concurrency Control

时间戳排序（Timestamp ordering T/O）是一种乐观的并发控制协议

其中DBMS假设事务冲突很少。DBMS不要求事务在被允许读/写数据库对象之前获取锁，而是使用时间戳来确定事务的可串行化顺序。

每个事务Ti被分配一个唯一的固定时间戳TS（Ti），其单调递增。不同的方案在事务期间的不同时间分配时间戳。一些高级方案甚至为每个事务分配多个时间戳。

如果TS（Ti）<TS（Tj），则DBMS必须确保执行计划等同于串行计划，其中Ti出现在Tj之前。

有多种时间戳分配实现策略。DBMS可以使用系统时钟作为时间戳，但在夏时制等边缘情况下会出现问题。另一种选择是使用逻辑计数器。但是，这存在溢出问题，以及在具有多台计算机的分布式系统中维护计数器的问题。也有混合方法使用这两种方法的组合。

Basic Timestamp Ordering (BASIC T/O)

基本时间戳排序协议（basic T/O）允许在不使用锁的情况下读取和写入数据库对象。相反，每个数据库对象X都标记有成功执行该对象上的读取（表示为R-TS（X））或写入（表示为W-TS（X））的最后一个事务的时间戳。然后，DBMS检查每个操作的这些时间戳。如果事务试图以违反时间戳顺序的方式访问对象，则事务将中止并重新启动。潜在的假设是，违规行为将非常罕见，因此这些重启也将非常罕见。

Read Operations

如果TS(Ti）<W-TS（X），表明读取时候还没有写入，因此该读取操作是无效的，Ti被中止并使用新的时间戳重新启动。

如果TS(Ti）>W-TS（X），读取是有效的，允许Ti读取X。然后DBMS将R-TS（X）更新为R-TS（X）和TS（Ti）的最大值。它还必须制作X的本地副本，以确保Ti的可重复读取。

Write Operations

对于写操作，如果TS（Ti）<R-TS（X）或TS（Ti）<W-TS（X），则必须重新启动Ti。否则，DBMS允许Ti写入X并更新W-TS（X）。同样，它需要制作X的本地副本，以确保Ti的可重复读取。

优化:Thomas Write Rule

如果TS（Ti）<W-TS（X），DBMS可以忽略这个写操作并且允许事务继续而不是abort或者restart。请注意，这违反了Ti的时间戳顺序，但这没关系，因为没有其他事务会读取Ti对对象X的写入。

如果基本T/O协议不使用Thomas写入规则，它将生成一个可冲突序列化的调度。它不能有死锁，因为没有事务等待。但是，如果短事务持续引发冲突，则可能会导致长事务的匮乏。

——缺陷：

  1. 将数据复制到事务工作区和更新时间戳的高开销。
  2. 长时间运行的事务可能会饥饿。事务从较新的事务中读取内容的可能性增加。
  3. 在高度并发的系统上存在时间戳分配瓶颈。

Optimistic Concurrency Control (OCC)

乐观并发控制（OCC）是另一种乐观并发控制协议，它还使用时间戳验证事务。当冲突数量较低时，OCC工作得最好。这是当所有事务都是只读的或者当事务访问不相交的数据子集时。如果数据库很大，并且工作负载没有扭曲，那么冲突的概率很低，这使OCC成为一个不错的选择。

在OCC中，DBMS为每个事务创建一个专用工作区。事务的所有修改都应用于此工作区。读取的任何对象都将复制到工作区，写入的任何对象将复制到该工作区并在其中进行修改。没有其他事务可以读取其私有工作区中另一个事务所做的更改。

当事务提交时，DBMS将比较事务的工作区写入集，以查看它是否与其他事务冲突。如果没有冲突，写入集将安装到“全局”数据库中。

OCC由三个阶段组成：

  1. Read Phase：在这里，DBMS跟踪事务的读写集，并将其写入存储在私有工作区中

  2. Validation Phase：当事务提交时，DBMS检查它是否与其他事务冲突。

    1. DBMS在事务进入验证阶段时分配事务时间戳。为了确保只允许串行化调度，DBMS根据其他事务检查Ti是否存在RW和WW冲突，并确保所有冲突都是单向的（从较老的事务到较新的事务）。
    2. DBMS检查提交事务与所有其他正在运行的事务的时间戳顺序。尚未进入验证阶段的事务将被分配一个时间戳∞.
    3. 如果TS（Ti）<TS（Tj），则必须满足以下三个条件之一：
      1. Ti在Tj开始之前完成所有三个阶段
      2. Ti在Tj开始其写入阶段之前完成，并且Ti不会写入Tj读取的任何对象。
      3. Ti在Tj完成读取阶段之前完成读取阶段，并且Ti不会写入Tj读取或写入的任何对象。

  5. Write Phase：如果验证成功，DBMS将对数据库应用私有工作区更改。否则，它将中止并重新启动事务。

——缺陷：

  1. 将数据本地复制到事务的私有工作区的开销很高。
  2. 验证/写入阶段是瓶颈
  3. 中止可能比其他协议更浪费，因为它们仅在事务已经执行之后发生
  4. 存在时间戳分配瓶颈。

Isolation Levels

异常现象：

  1. Dirty Read脏读：正在读取未提交的数据
  2. Unrepeatable Reads不可重复读取：再次读取的结果与先前不同
  3. Phantom Reads幻读：插入或删除会导致相同范围扫描查询的不同结果。

隔离级别：

  1. SERIALIZABLE：没有幻读，所有读取都是可重复的，没有脏读
  2. REPEATABLE READS：幻读可能会发生
  3. READ-COMMITTED：幻读和不可重复读取可能会发生。
  4. READ-UNCOMMITTED：所有异常都可能发生。

SQL-92有额外的两个隔离级别：

  1. CURSOR STABILITY
  2. SNAPSHOT ISOLATION