乐观并发控制中的后向/前向验证

I am new to "concurrency" & "transactions" and I feel a little confused about backward/forward validation in optimistic concurrency control. Just take backward validation for an example. Suppose Tv is the transaction being validated and Ti is the committed transactions. I was wondering why we just check the Tv's read set vs.Ti's write set . Why don't we check Tv's write set vs.Ti's write set and Tv's write set vs.Ti's read set too? Since write-write and write-read are also conflict operations...Any explanation would be appreciated!

我是“并发”和“事务”的新手,我对乐观并发控制中的后向/前向验证感到有些困惑。只需对示例进行反向验证。假设Tv是正在验证的事务,而Ti是已提交的事务。我想知道为什么我们只检查电视的读取设置vs.Ti的写入集。为什么我们不检查Tv的写集vsTi的写集和Tv的写集vsTi的读集呢?由于写 - 写和写 - 读也是冲突操作......任何解释都将不胜感激!

2 个解决方案

#1

Validation uses the read-write conflict rules to ensure that the scheduling of a particular transaction is serially equivalent to all overlapping transations. This means that once entered the validation phase, no changes to read/write sets can be further performed.

验证使用读写冲突规则来确保特定事务的调度序列等效于所有重叠的转换。这意味着一旦进入验证阶段,就不能进一步执行对读/写集的更改。

There are 3 rules that need to be satisfied by any two transactions T_i and T_j, where i < j ( T_i entered validation phase before T_j):

任何两个事务Ti和Tj都需要满足3条规则,其中i (ti在tj之前进入验证阶段):

1. T_i must not read objects written by T_j

   Ti不能读取Tj写的对象

2. T_j must not read objects written by T_i

   Tj不能读取Ti写的对象

3. T_i must not write objects written by T_j and T_j must not write objects written by T_i

   Ti不能写由Tj写的对象,Tj不能写Ti写的对象

Backward validation assumes that all read operations of T_i were performed before validation of T_j started. This means that T_i is already in the validation phase. (rule 1 is satisfied)

向后验证假定在Tj开始验证之前执行了Ti的所有读取操作。这意味着Ti已经处于验证阶段。 (规则1满足)

During validation of T_j, the read set of T_j is checked against write set of T_i. If there is no overlap, then (rule 2 is satisfied).

在Tj的验证期间,针对Ti的写集检查Tj的读集。如果没有重叠,则(满足规则2)。

If Rule 1 and Rule 2 are satified, Rule 3 is implicitly satisfied. All the changes commited will be done sequentially because T_i entered validation phase before T_j. T_i's write set will be validated and commited before T_j's write set.

如果满足规则1和规则2,则隐含地满足规则3。提交的所有更改将按顺序完成,因为Ti在Tj之前进入验证阶段。 Ti的写集将在Tj的写集之前被验证并提交。

#2

• backward validation of Tv:

  电视的后向验证:

  • read operations of earlier overlapping transactions (performed before validation of Tv) cannot be affected by the writes ot Tv. The validation checks Tv's read set against write sets of earlier transactions, failing if there is any conflict;

  早期重叠事务的读操作(在验证Tv之前执行)不受Tv写入的影响。验证检查Tv的读取集对早期事务的写集,如果有任何冲突则失败;

• forward validation of Tv:

  电视的前向验证:

  • write set of Tv is compared with the read sets of all overlapping active transactions;

    将Tv的写集与所有重叠的活动事务的读集进行比较;

  • differently from backward validation, in forward validation there are choices of which transaction to abort (Tv or any of the conflicting active transactions);

    与后向验证不同,在前向验证中,可以选择中止哪个事务(Tv或任何冲突的活动事务);