Re: Lock-free databases

From: VC <>
Date: Sat, 5 Nov 2005 19:18:55 -0500
Message-ID: <>

"Christopher Browne" <> wrote in message
>> "Joachim Pense" <> wrote in message
>> news:dkiaao$r43$05$
>>> VC:
>>>> In MVTSO, a data item in addition to the transaction timestamp
>>>> that created the item has a read timestamp. In this model reads
>>>> always succeed, and writes are rejected and restarted if their
>>>> timestamp is smaller than the data item read timestamp.
>>> What does "restarted" mean here? Can that mean "automatically", or
>>> does it just mean "rejected and reconsidered by the application if
>>> the write should still be done"?
>> The standard MVTSO model implies automatic restart.
> If a legal update is blocked from proceeding, then that's more than
> close enough to being a "lock" that it surely ought to feel
> uncomfortable to claim "it's a non-locking model."

You did not read carefully. If the two transactions happen to proceed like

R1; R2; W1; W2;

then it's not a serializable history which would fail in a locking database with a deadlock and in a database like Oracle with a message 'cannot serialize'. The history rejection, as non-serializable, by a MVTSO scheduler is correct, and the restart is just a convenience, not some delay or "lock". There is no locking unless you wish to warp the word meaning to suit your argument. Again, I refer you to the book I mentioned earlier -- it's pretty well known stuff people figured out close to 20 years ago.

> --
> let name="cbbrowne" and tld="" in String.concat "_at_" [name;tld];;
> Rules of the Evil Overlord #222. "I reserve the right to execute any
> henchmen who appear to be a little too intelligent, powerful, or
> devious. However if I do so, I will not at some subsequent point shout
> "Why am I surrounded by these incompetent fools?!"
> <>
Received on Sun Nov 06 2005 - 01:18:55 CET

Original text of this message