Simplify Timestamp Generator / beginTxn-commit synchronisation path
Simplify timestamp generator, while ensuring that noInversion holds during the whole duration of the commit path (it's stronger than a precondition: it's a guarantee).
My idea is to advance the max_allowed_st once it is proven that there can be no new transactions that commit with a lower ct, and no sooner.
Timestamp variables:
max_dense_ct % atomic, initially 0. Replaces max_allowed_st
last_ct % atomic, initially -1
recent_cts % set, initially empty (implemented as an array, sized as the number of Transaction Coordinators, or possibly 2*number of TCs)
In beginTransaction:
- ensure
¬(st > max_dense_ct+1)
. Implemented as wait on a condition variable (or just a spin loop). -
beginTransaction()
by default allocatesst ≔ max_dense_ct+1
. - in order to get read-my-writes, a client may force
beginTransaction(last_observed_ct)
, which may cause a wait.
Commit (non read-only txn) {
ct ≔ -1
try {
<ct += last_ct>. % atomic, return new value
.... do commit stuff, may take a long time, may fail...
} finally {
if (ct == -1) exit
% recent_cts . add(): if implemented as a set, bound its size
% if implemented as array, make sure you don't overwrite an entry currently in use.
recent_cts . add (ct)
t := max_dense_ct+1
while (recent_cts . contains (t)) {
if t == max_dense_ct+1 % may have changed in the meantime
&& <compare-and-swap (max_dense_ct, t-1, t)> % atomic
then recent_cts . remove (t)
}
}
}
Edited by Marc Shapiro