Re: Concurrency in an RDB

On 2006-12-15, David wrote:

> I've had a (very) brief look at the paper "Semantic Concurrency
> Control in Object-Oriented Database Systems" by Muth et al. Is this
> representative? In that paper they look for methods on objects that
> commute and use this to provide a locking protocol with increased
> concurrency.

Representative, but far from comprehesive. For example note that since subtransactions are committed before their parents, changes that might still be rolled back at a higher level become visible early at the lower levels. The effects of such transactions will have to be compensated later on. Combined with a subsequent transaction that relies on the compensation, I think you'll get a composite transaction that is precisely equivalent to an OT. The difference is that open nested transactions are built dynamically, at a lower level of granularity, they are more general in that they consider the ordering of noncommutative actions as well, and they can even automatically handle a situation where a compensation commutes with a transaction relying on the compensated object.

> However OT assumes that *all* changes on the data (however simple or
> complex) can be represented by operations that can be applied in
> different orders at different sites in order to synchronise replicated
> data.

Yes. It's the special case which admits arbitrary commutation and static combination of the compensation code to the following transaction. Unfortunately there are updates which cannot be so decomposed, and an even larger set which could in theory be decomposed like this but which either does not admit any tractable means of deriving the correct update protocol or leads to an update protocol which is too complex for efficient implementation.

> It is not about providing increased concurrency on top of a single,
> centralised DB with (ultimately) a pessimistic locking model.

Who said anything about centralization? It's well known that you can transform pessimistic protocols to optimistic ones with timestamps, priorities and validation. And secondly, *if* you can commute two method invocations as in OT, then I think you *can* express that fact under Muth et al's protocol as a set of semantic lock modes, methods of different levels, and compensations which ends up being nonexclusive. That's not exactly pessimistic to my eye.

> OT doesn't limit itself to commuting operations (say).

On top of the entire set of valid database states times valid state independent updates, yes it does; otherwise it annuls some of the transactions. Furthermore, it fails to handle the case where even this more general form of commutativity does not hold.

For example, what would it do with two concurrent account withdrawal transactions, either but not both of which can be completed successfully because of a balance constraint? Open nested transactions e.g. permit a situation where the pair gets executed at the lowest levels, leading to a visible inconsistency, and then the first transaction gets compensated before any hard cash is dispensed or subsequent high level transactions have had a chance to proceed. That's rather extreme as far as commutativity, concurrency and average latency go.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2