Crisp Reading Notes on Latest Technology Trends and Basics

http://www.cs.cityu.edu.hk/~cs4404/08_occ_ts.ppt

http://www-i4.informatik.rwth-aachen.de/content/teaching/lectures/sub/vs/vsSS06/08_Transactions2_1P.pdf

Conservative Timestamp Ordering

Introduction

  • With Timestamp Ordering schemes, there is no Locking
  • We assign timestamps to Transactions and to data-items
  • We describe below, one of the techniques of Timestamping, which is conservative, and to a large extent, Single Versioned
  • I will add notes for Multi-Versioned Timestamping at a later point in time

Terminology

TS(Ti) Starting time of Transaction – Ti

The starting time forms the Id of the transaction

RTS(Oj) Read timestamp of item

The most recent transaction that have read the item

WTS(Oj) Write timestamp of item

The most recent transaction that have written the item

  • The reads and writes to the database are executed without locking
  • Instead, the following two conditions should be satisfied with each read/write

Read rule

  • If Ti reads Oj,
    • If WTS(Oj) > TS(Ti), a later transaction has written the data. So, abort current transaction
    • Else RTS(Oj) ß max( RTS(Oj), TS(Ti) ), and
      • add a dependency DEP(Ti ).add(WTS(Oj) à TS(Ti))

Write Rule

  • If Ti writes Oj,
    • If RTS(Oj) > TS(Ti), a later transaction has read data. So, abort transaction if Isolation level is Read Committed
    • If WTS(Oj) > TS(Ti), a later transaction has written the data. So, skip the write
    • Else
      • OLD(Ti).add(Oj,WTS(Oj))
      • update Oj

Commit Rule

  • It Ti wants to commit,
    • If there is a transaction in DEP(Ti)- an aborted transaction from which Tihas read data,
      • then abort the transaction
      • If there is a transaction in DEP(Ti), – a running transaction from which Tihas read data,
        • then either abort the transaction, or wait till the running transaction completes

Abort Rule

  • If Tiwants to abort,
    • For every item in <Oj,oldOj> in OLD(Ti), if WTS(Oj) = TS(Ti),
      • WTS(Oj) ß oldOj

Summary

Read from

Older Txn

Write from

Older Txn

Read from

Newer Txn

Write from

Newer Txn

Read Object OK OK OK Abort.

Cannot serialize

Write Object OK OK Abort.

Cannot serialize

OK

No overwriting

Older Txn Aborted Older Txn Committed Older Txn Pending
Commit OK

if no read dep

from older to newer

OK

 

Wait

On completion,

check for read dep or commit

Abort OK OK OK

Notes on wait state during commit

  • An observant reader will notice that there is a “Wait State” during the “Commit” of a transaction
  • This state could be easily engineered as an Abort action. In that case, the later transaction will also be forced to Abort, causing “Cascading Aborts”. This is something we seek to avoid
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Tag Cloud

%d bloggers like this: