Mentions légales du service

Skip to content

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 allocates st ≔ 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