Re: Concurrency in an RDB

Sampo Syreeni wrote:
> 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.

Note that OT is not a locking protocol. In allows for multi-users with no locking at all.

> > 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.

OT imposes strong restrictions on the integrity constraints. It is not permissible to nul an operation once it has been generated. This limits the applications for which OT is suitable. Eg don't use OT for reserving seats on an aeroplane. However, collaborative, decentralised management of a company's geological data would be reasonable.

Cheers,
David Received on Sat Dec 16 2006 - 01:32:37 CET