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\)):
If \(WTS(R_j) \gt TS(T_i)\), then abort \(T_i\);
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\),
If \(RTS(R_j) \gt TS(T_i)\), then abort;
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);
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,
check if any transaction in \(DEP(T_i)\) is in progress, wait for all of them ended
if any transaction in \(DEP(T_i)\) aborted, then abort
otherwise, do commit
On abort,
- 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)\)