Re: Concurrency in an RDB

Sampo Syreeni wrote:
> On 2006-12-15, David wrote:
>
> > In a fully normalized database surely it makes it more not less likely
> > for mutative transactions to be simple and fine-grained.
>
> Correct, and I think I'm finally getting your point. You seem to be
> viewing transactions at a somewhat higher level than common DBMSs. From
> the latter point of view, we commonly expect even the simplest updates
> to be of the read-modify remotely-write kind. Your viewpoint seems to be
> that if at all possible, the transaction should consist of passing the
> new value to the DBMS, which then executes the transaction locally and
> reports success or failure.

In OT there is never a need to report failure. Transactions are guaranteed to succeed! A user makes a local modification on local state without any risk of a dirty read w.r.t the local database. Once the operation is generated, it can *always* be applied later (after transformation) at other sites, despite concurrent operations.

> In the former case, there's a data
> dependency between the read and the write, and so you cannot avoid
> locking the data for extended periods of time, except perhaps by
> optimism. In the second case the transaction executes entirely inside
> the DBMS and the read-write latency is entirely determined by how fast
> the CPU can handle it; when you force the transaction to operate blindly
> (you say "on constant data"), you also make it spoolable, which of
> course makes it easy on the locking subsystem.

Yes. An operation has a vector time which uniquely determines the context in which it was originally generated. OT is able to transform the operation to a different context (ie corresponding to a different vector time), thereby in a sense eliminating the dependency between read and write.

> I do understand the point, and when you can optimize for such
> constraints, the result can be very efficient. However, I think the
> important part is the principle that governs the interface, not the DBMS
> internals where the interfaces are so limited that you can always
> optimize for spoolability, or in fact CPU loading. I mean, there are
> still lots of applications where you cannot expect to be working blind
> or where the business logic cannot be pushed inside the DBMS the way the
> design would require.

Although OT allows for write transactions to be decoupled from reading it doesn't imply that you're "working blind". Changes are made by a user with a specific intention in the context of the state in which the operation was generated. OT tries its best to faithfully preserve that intention in the face of concurrent work.

> Again, it's this more general case DBMS designers
> are designing for. Sometimes you might be able to do with less and it
> might even make sense to switch to using coarser grained locks when your
> assumptions are fulfilled, but if you count on this, the DBMS is bound
> to become unstable when the first longer running transaction comes
> about.

Note that OT is perfectly suited for branching and merging in the style of CVS or Subversion. In that sense it is ideal for "long running transactions".

Unlike CVS, OT is able to merge changes with zero syntactic conflicts. Note however that there could easily be semantic conflicts. This all comes back to the question of integrity constraints.

If long running transactions are handled with pessimistic locking then expect to avoid semantic conflicts, but only because all work has been serialized.

> > Here is a non-relational example showing that strong integrity
> > constraints can be lousy. Imagine a DB that stores source code, and
> > there is an integrity constraint that the source must all compile
> > successfully. This will make mutative transactions *very* expensive -
> > so don't expect a high transaction throughput.
>
> Not necessarily true. You could batch the updates and leave the update
> transactions pending for a longer time, or go with open transactions and
> compensate by reporting failure later on. After this many modifications
> can be combined and most of the time the compilation will succeed. When
> it doesn't, you can you traitor tracing search for the precise
> transactions that caused the failure, roll them back, and retry.

I agree that with some effort it may be possible to increase performance. Note that if errors are common then this approach may not help much.

Your approach means that a transaction appears to commit even though in actual fact it may be discarded. i.e. it is breaking the durability assumption commonly expected on a DBMS. This will prevent it being used for distributed transactions. Do "open transactions" address this?

Anyway, I doubt whether the system will ever achieve the ingestion rate of a similar system without such an expensive integrity constraint.

IMO complex integrity constraints should generally be avoided. Instead a read only query on the DB can validate and report success/failure. Also when there is failure it reports precisely where there are problems that need to be corrected.

This will allow for OT to be used for truly concurrent editing of the data. Furthermore the CPU intensive, read only validation allows for testing merged work for semantic conflicts.

Note finally that sometimes it may be appropriate to allow a transaction to commit that causes a complex integrity constraint to fail. The problem may be with previously committed data. Sometimes you have to retract previous work in order to make progress!

> >> Try your example transaction, with the result cached for reuse. It makes
> >> sense precisely when the query load is read-mostly and complex queries
> >> recur.
> >
> > Sorry, I don't understand you.
>
> "Find the grandparents of people who have a brother in law that had open
> heart surgery before 2001." As such it's a relatively heavy read
> transaction. If you also want to store the result back into the
> database, it becomes a long running read-write transaction. The only way
> you're going to get any concurrency in that case is if you use finer
> grained locks or scale back on integrity guarantees.
>
> >> How about "Gimme everything you have on Bill. [For thirty seconds, draw
> >> forms and wait for the user to generate some unpredictable data
> >> dependencies.] Change Bill's wife to Mary Long."?
> >
> > Is this a user who analyses info on Bill before deciding to change
> > Bill's wife?
>
> Yes.
>
> >Isn't the change to Bill's wife a separate txn?
>
> Not necessarily, no. But the example is going to get contrived, so let's
> try another one. "Gimme everything medical you have on Bill. [Checks for
> inconsistensies with paper documentation.] Mark Bill as having had
> surgery." In this case you can't easily avoid locking because whether
> you want to perform the modification does depend on whether Bill has
> already been so marked. Not locking could lead to inconsistency if
> somebody modified Bill's patient record in the mean time.

Is the flag for whether Bill has had surgery, a functional dependency on other state, and therefore doesn't deserve to be part of the data model?

Functionally dependent state can be very expensive to calculate, and may need to persist in order to avoid unnecessary recalculation. But I regard that as a caching issue. In fact cache management is *much* easier with my proposal. Eager recalculation of cached state (as commonly done in OO designs with the observer pattern) is unsound in the general case because of a risk of dirty reads.

> In your paradigm you'd probably want to make such updates idempotent.
> But that's risky, because it calls for precision that human record
> keepers simply don't have, and it limits the kind of ad hoc work that is
> often necessary in such business.

I'm not sure what you mean here. Assignment (with the same value) is idempotent.

> > If I understand you this has complex, distributed integrity
> > constraints, which I think is a bad idea. What happens if a QA station
> > crashes and rolls back to an earlier state?
>
> You're going to mark that batch as being in an unknown condition, or
> sometimes you might have a pickup line to recycle items affected by such
> failure back to the beginning of the QA line. Still, this is a very
> typical O&M scenario.

It seems to me that there are two approaches

1. employ a distributed integrity constraint, and therefore need expensive and error prone distributed transactions, and employ very reliable hardware and backup systems to ensure durability of transactions.
2. only employ simple, local integrity constraints compatible with fast transactions that don't need to block on network I/O.

Note as well that a distributed integrity constraint may indicate a denormalised design. Can the redundancy be avoided?

Cheers,
David Received on Mon Dec 18 2006 - 02:43:16 CET