Prodesse Quam Conspici

timestamp-based concurrency control

Timestamp-based concurrency control is a non-block (optimistic) concurrency control method for executing concurrent transactions.

Timestamp could be real (read from the wall clock) or logical (using a counter) provided that it is monotonically increasing and will not produce duplicate timestamps.

Each transaction \(T_i\) acquires its timestamp \(TS_i\) at the beginning. The transaction also maintains the following data, \(DEP(T_i)\)-the set of dependent transactions, \(OLD(T_i)\)-the set of original values of updated data. While on the other side, each record \(R_j\) holds two extended fields, \(RTS(R_j)\)-timestamp of latest read, \(WTS(R_j)\)-timestamp of latest update.

Then for each read of \(T_i\) (suppose the reading record is \(R_j\)):

  1. If \(WTS(R_j) \gt TS(T_i)\), then abort \(T_i\);

  2. Otherwise, add the latest transaction that updated \(R_j\) into \(DEP(T_i)\), and set \(RTS(R_j)=max{RTS(R_j), TS(T_i)}\).

For each update of \(T_i\),

  1. If \(RTS(R_j) \gt TS(T_i)\), then abort;

  2. If \(WTS(R_j) \gt TS(T_i)\), then skip (according to Thomas Write Rule, the value will finally be overwritten by the succeeding transaction);

  3. Otherwise, add the original value \(<R_j, WTS(R_j)>\) into \(OLD(T_i)\), set \(WTS(R_j)=TS(T_i)\), and update \(R_j\).

On commit,

  1. check if any transaction in \(DEP(T_i)\) is in progress, wait for all of them ended

  2. if any transaction in \(DEP(T_i)\) aborted, then abort

  3. otherwise, do commit

On abort,

  1. for each original value \((R_j, WTS(R_j))\) in \(OLD(T_i)\), if \(WTS(R_j)==TS(T_i)\), then restore the original value and \(WTS(R_j)\)
Tags: database.