CODEWITHSUNDEEP
concurrencytransactionsdistributed-systemoptimistic-locking
yvetterowe
yvetterowe

Reputation: 1269

backward/forward validation in optimistic concurrency control

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!

Upvotes: 3

Views: 5990

Answers (2)

yeah
yeah

Reputation: 11

  • 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;

  • forward validation of Tv:

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

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

Upvotes: -1

Andrei
Andrei

Reputation: 7607

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 Ti and Tj, where i < j ( Ti entered validation phase before Tj):

  1. Ti must not read objects written by Tj

  2. Tj must not read objects written by Ti

  3. Ti must not write objects written by Tj and Tj must not write objects written by Ti

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

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

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

Upvotes: 4

Related Questions