Re: Lock-free databases

"Mark D Powell" <Mark.Powell_at_eds.com> wrote in message news:1131377410.830202.214120_at_o13g2000cwo.googlegroups.com...
> Even for read only access where multiversioning with timestamp ordering
> exists (basically what Oracle uses) access to the block where the
> consistent view of the data is built has to be restricted. In Oracle's
> case latches would be used.
>
> Remember that any single threading mechanism no matter if you call it a
> lock, latch, enqueue, or other name is a lock for the purpose of this
> discussion which is about "lock free" database products.

I am afraid you are confused at least on two counts.

1. Database concurrency control. When one talks about concurrency control, one assumes atomic reads and writes (in order to make concurrency treatement manageable). How a specific product, be it Oracle or SQL Server or something else, chooses to protect its internal memory structures in order to emulate atomic reads is an irrelevant implementation feature. What's relevant is the user level of abstraction, how a data item(row) is handled to ensure data integrity. In Oracle, to describe concurrency one would say that there is only the write lock (TX) and no read locks (forgetting for a moment about various DLL and table locks), that's what's the user sees and uses to implement concurrent transactions efficiently.

By the way Oracle is not MVTSO. Since it has the TX lock, it's a mongrel, multiversioning plus write locking (as is Postgres or Interbase). There are other non-locking database concurency control mechanisms, such as different kinds of SGT (serialization graph testing), Basic TSO, etc. For details, see the Bernstein book I mentioned earlier.

2. It's possible to implement lock-free data structures such as lists, hashes, etc (I believe Joe Seigh mentioned that). So, hypothetically, it's possible to get rid of latches, enqueues, etc. even at the various memory structures implementation level, be it data cache handling or library cache management. You might want to google for MCAS or STM to find ample literature on the subject.

Since the OP was interested in memory resident databases, (2) maybe quite relevant. Also, it might be intersting to know that Java 5 offers some tools to implement lock-free concurrent algorithms.

> I say it is
> not really possible.

Well, not true.

>
> HTH -- Mark D Powell --
>
Received on Mon Nov 07 2005 - 18:18:35 CST