[e-lang] Consequences of transactional E?

[David Hopwood]

James Graves wrote:
> I don't have the have the brainpower to spare right now to think about 
> building robust applications over a distributed object-cap network.  And 
> I haven't fully read all the stuff in this thread yet either.
> 
> But here's my 2 cents anyway...
> 
> Multi-Version Concurrency Control running on each vat.  Three-phase 
> commit protocol (which is non-blocking), run by the application 
> initiating the transaction.
> 
> Vats are really databases, after all.

No, they aren't. Databases typically have data access patterns that are
more likely to favour speculative execution than those of general-purpose
applications. Typically, there are a bunch of mostly-independent "things"
(users, orders, products, etc.) such that any two transactions that are
submitted at about the same time, are likely not to conflict (one writes
to a "thing" that the other accesses) with reasonably high probability.

Having said that, speculation can cause problems even in databases.
Consider the comments below by one of the most enthusiastic proponents
of optimistic/speculative transactional memory, Maurice Herlihy:

[<http://www.uwtv.org/programs/displayevent.aspx?rID=9300>
Note that this video requires either a 1.3 Mbit/s Internet connection,
or an MPEG 4 (.m4v) player for the downloadable version.]

At 37 minutes 45 seconds in:

  Most transactional memory systems -- not all, but certainly all of the
  early ones, are based on optimistic synchronization. The idea here is
  that you charge ahead and you do stuff, and then afterwards you check
  and see whether it's OK. This is opposed to conventional, say, 2-phase
  locking schemes where you always check before doing something whether
  or not it's OK. Now, this is the sort of thing where if you talk to
  [processor] architects and you call it "speculative synchronization",
  then they all look up and nod approvingly; if you talk to database people
  and say it's "optimistic synchronization", they look alarmed, because the
  database community had a brief fling with optimistic synchronization in
  the '80s, and it didn't work out very well. The reason is simple: just
  because the cost of misprediction -- of rolling back a transaction -- is
  huge compared to most synchronization costs. So optimistic synchronization
  works really well when your optimism is justified, and it does not work
  so well when the conflict rate is high.

(Multi-Version Concurrency Control is optimistic in the sense Herlihy is
talking about. It was proposed in the 1980's
<http://en.wikipedia.org/wiki/Multiversion_concurrency_control>, although
I'm not sure that's what he's referring to specifically.)

Here's another relevant comment from the same talk, 37 minutes in, again
talking about transactions with optimistic scheduling:

  If you take a sequential program, put transactions around the parts that
  need to be done atomically, then your program will almost certainly work,
  but we don't have any particular way of predicting, or even analysing the
  complexity, in terms of the amount of concurrency that we get.


The presentation then goes on to talk about "contention managers" and some
recent results concerning them, but I am quite skeptical about the extent
to which they'll be able to help. The range of data access patterns in
general-purpose applications is *far* wider than in a database. In many
situations, optimistic scheduling can lead to performance significantly
worse than doing everything sequentially.

Note that transactions don't need to be long and to access many objects
in order to see this effect. Individual operations on some data structures
(including anything that does internal cacheing) require writes to memory
for what are "logically" read operations. This results in "false conflicts",
which means that such structures don't work at all well in an optimistic
transaction setting.

If our goal in supporting transactions is to improve {consistency/integrity,
security, fault isolation}, and we rely on other means (concurrent vats) to
provide parallelism, then pessimistic transactions + message passing is a
very attractive option. It has all of the "atomic composable goodness" and
deadlock-avoidance properties of transactions, but with much more predictable
performance.


As far as performance is concerned, there is an obvious caveat: what if we
cannot find enough parallelism by partitioning an application into vats, to
fully exploit the available hardware parallelism (especially given the
possibility of chips with 80 or more processor cores in the relatively
near future)? I think I'll post this now and discuss that question in
another message.

-- 
David Hopwood <david.nospam.hopwood at blueyonder.co.uk>