Is there a theory for "transactional" sequences of failing and no-fail actions?
- by Ross Bencina
My question is about writing transaction-like functions that execute sequences of actions, some of which may fail. It is related to the general C++ principle "destructors can't throw," no-fail property, and maybe also with multi-phase transactions or exception safety. However, I'm thinking about it in language-neutral terms. My concern is with correctly designing error handling in C++ functions that must be reliable. I would like to know what the concepts below are called so that I can learn more about them.
I'm sorry that I can't ask the question more directly. Since I don't know this area I have provided an example to explain my question. The question is at the end. Here goes:
Consider a sequence of steps or actions executed sequentially, where actions belong to one of two classes: those that always succeed, and those that may fail. In the examples below:
S stands for an action that always succeeds (called "no-fail" in some settings).
F stands for an action that may fail (for example, it might fail to allocate memory or do I/O that could fail).
Consider a sequences of actions (executed sequentially from left to right):
S->S->S->S
Since each action in the sequence above succeeds, the whole sequence succeeds.
On the other hand, the following sequence may fail because the last action may fail:
S->S->S->F
So, claim: a sequence has the no-fail (S) property if and only if all of its actions are no-fail.
Now, I'm interested in action sequences that form "atomic transactions", with "failure atomicity," i.e. where either the whole sequence completes successfully, or there is no effect. I.e. if some action fails, the earlier ones must be rolled back. This requires that any successfully executed actions prior to a failing action must always be able to be rolled back. Consider the sequence:
S->S->S->F
S<-S<-S
In the example above, the first row is the forward path of the transaction, and the second row are inverse actions (executed from right to left) that can be used to roll back if the final top row actions fails.
It seems to me that for a transaction to support failure atomicity, the following invariant must hold:
Claim: To support failure atomicity (either completion or complete roll-back on failure) all actions preceding the latest failable (F) action on the forward path (marked * in the example below) must have no-fail (S) inverses. The following is an example of a sequence that supports failure atomicity:
*
S->F->F->F
S<-S<-S
Further, if we want the transaction to be able to attempt cancellation mid-way through, but still guarantee either full completion or full rollback then we need the following property:
Claim: To support failure atomicity and cancellation mid-way through execution, in the face of errors in the inverse (cancellation) path, all actions following the earliest failable (F) inverse on the reverse path (marked *) must be no-fail (S).
F->F->F->S->S
S<-S<-F<-F
*
I believe that these two conditions guarantee that an abortable/cancelable transaction will never get "stuck".
My questions are:
What is the study and theory of these properties called? are my claims correct? and what else is there to know?
UPDATE 1: Updated terminology: what I previously called "robustness" is called atomicity in the database literature.
UPDATE 2: Added explicit reference to failure atomicity, which seems to be a thing.
