Re: Concurrency in an RDB

Bob Badour wrote:
> monarodan_at_gmail.com wrote:
>
> > To all those stating that David should do some background reading - did
> > you bother to look into Operational Transform (OT) as mentioned by
> > David? There is potentially a whole new way of thinking about databases
> > and distributed systems that should not be ignored.
>
> What's new about it? I saw nothing novel in his suggestion.
>
>
> > Given David's area of research, perhaps his views are indeed valid and
> > rather than being completely dismissive, this community should
> > investigate what impact OT may have on DBMS implementations. I've
> > heard no innovative comments here other that those made by David trying
> > to link OT to distributed computing using a functional programming
> > model. I would tend to agree with many of Davids comments that
> > mutative operations are short-lived if (and only if) you are mutating
> > "free" data.
>
> Mutative operations perhaps but we are discussing transactions.
> Transactions comprise multiple mutative operations that must complete as
> if atomic or must not happen at all. In a distributed system, a
> transaction may alter state in different distributed components and
> still exhibit apparent atomiticity.
>
> I suggest to you what I suggested to David: open any book on
> transactions and catch a clue about the prior work.
>
> [snip]

Bob goes on about prior work like a broken record. His comments indicate good understanding of how conventional databases work - ie using pessimistic and fine-grained locking. However he betrays his arrogance. Although clearly very intelligent and knowledgeable he doesn't take the effort to understand me.

For anyone interested (other than Bob who has stuck his fingers in his ears), my previous discussion of the Operational Transform (OT) approach was rather brief so I will elaborate to avoid confusion.

I restrict the system to mutative transactions that are only issued by a thread within the process that is managing a local database on that machine. What I mean is that the thread will begin the mutative transaction by exclusive write locking the entire database, read/write state then commit the transaction and release the mutex. The local DBMS must ensure the local transaction is atomic. While the thread holds the mutex it must not interact with other processes (more precisely, it must not block on network I/O). In particular, a remote client may not use some protocol to begin a transaction, issue updates then later end the transaction). Therefore we see that the transaction is not influenced by network latency.

Now if transactions are fine-grained, and write caching is available, and all the state needed by the transaction is memory resident then the transaction can proceed very quickly. I claim that it is indeed possible to meet these conditions most of the time, so that the amortized transaction rate can be extremely high. Achieving hundreds of thousands of transactions per second is quite plausible.

The network related restriction means we throw out the whole idea of a distributed transaction. ie a transaction that needs to atomically change multiple, geographically separate databases. There is no concept of multiphase commit protocols. Also, because a remote client never holds a lock on a database, we don't have to deal with the problem of releasing the lock if the client appears to have failed or network connectivity has been lost.

So how can data be shared amongst multiple users? Well the proposal is to use replication of data and OT. Consider a number of sites that each independently store their own copy of the database. We allow these databases to temporarily diverge.

A locally performed transaction to be regarded as a "delta" (or operation) with an associated vector time that can be transmitted *asynchronously* to other sites which apply the operation as a delta in order to eventually synchronise the replicated data. This is achieved without any need for multiphase commit or even the idea of remotely locking resources on another database. It is kind of like an optimistic concurrency control except that the mathematics of OT allows for convergence to be achieved without any concept of conflict, even though different sites apply operations in different orders. I hope this sounds impossible to you (if it seems quite plausible then perhaps you don't realise the astonishing feat that OT achieves).

This is a radically different way of thinking about distributed computing and concurrency.

Cheers,
David Received on Tue Dec 12 2006 - 17:56:55 CET