Subject: Re: [boost] NuDB: A fast key/value insert-only database for SSD drives in C++11
From: Gavin Lambert (gavinl_at_[hidden])
Date: 2017-03-29 22:53:06
On 30/03/2017 05:19, Peter Dimov via Boost wrote:
> Niall Douglas wrote:
>> Consistency is time invariant. If two transactions each affect totally
>> unrelated data, if B was committed after A in time originally then
>> during recovery if B was recoverable but A was not, B is indeed
>> recovered without A.
> You can define it to be time-invariant if you assume that all invariants
> of the data are contained in the database and none are external to it;
> or, in other words, that the state "B without A" can never be considered
> inconsistent by the outside world if it's not described as inconsistent
> in the invariants the database knows about. Or in yet other words, you
> assume that the database knows which data are related and which
> unrelated, and that none of this knowledge is external to it.
I don't think any database can generally make this claim, as usually it
has no knowledge what the application is doing with the data.
The app can insert into table A, read data from table B, and insert into
table C. To the database, these all appear to be completely independent
(especially if they're on different connections or have no foreign key
relationships), and indeed they might be -- but it could also be true
that the insert into C used some values calculated from and dependent on
what was inserted into A or read from B, and the application might be
very confused if the table C data is present without the table A data.
The problem compounds if there was also an insert into table B just
So I agree with Peter: it should be illegal for transaction C to appear
in the recovered database if transaction A was committed first but
recovery resulted in rolling it back.
You could argue that it might be ok if you can prove that transaction A
and C were concurrent (and thus most likely independent), or from
different connections, but this still provides no guarantees that the
app wasn't still calculating one from the other, or assuming that the
order it chose to commit the transactions could be inverted or even
Commit time is the ultimate proof of unrelated data, due to causality.
(Even then, you can be tripped up by the app committing related
transactions in the "wrong" order, but in this case the app shouldn't be
surprised by the database enforcing that order during recovery.)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk