Crisp Reading Notes on Latest Technology Trends and Basics

Timestamping with Multi-Version Concurrency Control


  • Multi-version Concurrency Control allows the designer to take snapshots, and verify their data at commit/abort time.
  • Every transaction goes through three phases
    • Read / Local Modify
    • Validation
    • Write
  • The Timestamp of each transaction Tiis created at Validation time
    • Note that it is not necessary to have timestamps while tracking Read/Write.


ST(Ti) Starting time of Transaction Ti
TS(Ti) Validation time of Transaction Ti
RS(Ti) Read-set of Transaction Ti
WS(Ti) Write-set of Transaction Ti
  • Note that this is a Snapshot abstraction. Changes of Ti are not visible until Ti decides to commit.
  • While validating a Transaction,
    • Consider transactions that were active and have validated, since this transaction started

Backward Validation of Transaction

B(T) { Tj | Tjis active when T started, andTS(Tj) < TS(T), that is Tj preceeds T in timestamp ordering }
  • For each of these transactions Tj,
    • Transaction T should not have read from Tj
      • There should be no RS(T) à WS(Tj) dependency
      • This is because T would have picked up its snapshot before Tj wrote the values back
  • So, the algorithm is
sub validate(T) {valid ß truefor all Tj in B(T) {

if RS(T) ∩ WS(Tj) == Φ

valid ß false



Forward Validation of Transactions

  • In addition to the above technique of looking back at the transaction, we could look forward at the Transactions that are currently active.
  • If anything in the Write-Set of the current transaction has been read by the Transactions that have not yet got the Validation Timestamp, then
    • These transactions will most likely get aborted when they try to Commit
    • So, we could abort these new transactions right at this stage.

Backward Validation is required even if we use Forward Validations

  • Note that through “Forward Validations”, we do not know the Full Read-Set of the forward transactions
    • So, some of the Forward transactions may actually abort when they try to commit.
    • This check can be made only when the Forward transaction tries to Commit, and the check is a “Backward Validation”.
    • For this reason, “Forward Validation” is required, even if we use “Backward Validation”.

Why Forward Validations

  • Forward Transactions abort Active Transactions.
  • It is less expensive to abort “Validating Transactions”, as opposed to “Active Transactions”.

Distributed Optimistic Control

  • The “Validation Timestamps” have to be strictly ordered.
    • On multiple nodes, there needs to be a mechanism to generate strict ordering

Locking on a Single Node

  • Also, when we are validating a Transaction,
    • If there is only “Backward Validation”, no locking is needed
    •  For “Forward Validation”, locks are needed for the Read-Set and Write-Set of all items on the list

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Tag Cloud

%d bloggers like this: