Lambda the Ultimate

The big difficulty with transactions is that they don't scale: the larger transactions get, the more difficulties you start to have with starvation/contention. That doesn't mean they aren't useful, but they need to be used sparingly.

What? Surely they scale just as well as any other means of synchronisation? I mean you wouldn't start using STM in places where you wouldn't otherwise use locks (or some other means of ensuring atomicity), right? STM is for TRANSACTIONS only, nothing else (so it should be used very sparingly). If you want something to happen atomicaly you need to ensure it happens atomically somehow (STM, locks...). So the lack of scaling you're talking about is inherent (rewrite your program so it doesn't need large transactions!) and doesn't have anything to do with STM specifically.

As far as I can tell the BENEFIT of STM is that it DOES scale, since it can be implemented with optimistic concurrency. So the areas of your program that need to be atomic can scale better with STM than without it.

Not all means of synchronization scale the same. STM (even in lock-based implementations) has been shown to scale better than the explicit use of locks. Having said that, my original statement that it doesn't scale at all was unjustified hyperbole.

But is there a scalability advantage to STM over other lockfree approaches, besides the ability to trivially compose STM programs into larger ones? (Which should be done sparingly -- as you point out, writing large transactions usually isn't desirable.)

So far as I can tell, message-passing over lockfree queues can be implemented with little overhead, doesn't require a centralized transaction manager, and is less prone to starvation because the only required atomic operations are trivially short and roughly the same length.

STM, on the other hand, involves a non-trivial amount of overhead and indirection, requires some amount of centralized arbitration (e.g. reaping invalid/diverging transactions), and can have comparatively long-lived atomic operations of mismatched sizes, all of which contribute negatively to scalability and throughput.

(That isn't to say transactions are entirely avoidable -- even Erlang has Mnesia, after all... STM just wouldn't be my first choice as a programming model.)

The obvious scalability advantage is in project size - getting programmers for STM is going to be easy sooner than for message passing.

getting programmers for STM is going to be easy sooner than for message passing.

I'm not sure this is true. Transactions and message passing both require a level of understanding from the programmer to do things right (what doesn't?)

The existing evidence based on built-in transactions in databases is that transactions are NOT already well understood by programmers (though they may think otherwise) and this lack of understanding causes big problems.

I think having a range of tools, including STM, is great, but when it comes to concurrency, there ain't no such thing as a free lunch: many programmers need new skills.

any favourite docs (hopefully with an eye towards how to use them correctly, rather than just what they are) a transactional newbie could read? many thanks.

The obvious scalability advantage is in project size - getting programmers for STM is going to be easy sooner than for message passing.

Whether they know STM or message passing well, programmers that are good can surely pick up either one pretty quickly. Programmers that aren't much good, even if they know STM well, will harm your project in other ways. STM is supposed to allow you to be dumb about concurrency and get away with it; sadly, being dumb spills over so easily. In general, picking folks because they know your toolset well is a good way to miss out on bright people.

I don't think you can get away with being dumb about STM, either; the natural temptation is to make ginormous transactions ("Look ma, my transactions are composable!") and have the software thrash itself to death due to excessive retries (but only under production load).

One nice thing about STM is that it offers the tantalising possibility of a scale-invariance: a concurrency model which is homogenous with respect to transformations of scale. The advantage (should this possibility be realised) being that we don't have to learn different mechanisms for building applications of different sizes. I tend to think of abstraction as a way of making a big program look like a little program "from the outside", and a scale-invariant computational model is perhaps essential to this.

A relevant question then is this. To what extent are the "scalability risks" associated with composing transactions into ever-larger ones more properly attributed to limitations of current implementation techniques? To take the case of retry-thrashing, an incremental execution model might turn "retrying" into a case of incrementally adjusting the last (failed) execution of the transaction to accommodate what has happened since it started. In the general case that might be as expensive as ab initio re-execution, but in many important specific cases (e.g. if there is some orthogonality among the proper parts of a composite transaction, or more generally when the new computation includes the previous one as a sub-case) it might be very efficient.

an incremental execution model might turn "retrying" into a case of incrementally adjusting the last (failed) execution of the transaction to accommodate what has happened since it started

This sounds like this to me: if we could only attach a smart enough oracle to the transaction manager, it would sort our failures out for us. ;-)

The problem is that reasonable optimizations with acceptable losses is a very relative problem, and the wiggle room gets less not more as the size of the problem scales up, since the number of constraints tend to grow as the application gets more complex.

Let me reiterate: I'm not knocking STM. I welcome it as a tool in the tool belt of concurrency solutions.

The idea I'm knocking is that it is suddenly going to open up worlds of painless concurrency for programmers who aren't already good at concurrency, or that large transactional concurrency will somehow require less effort with STM than it does with current database transactional concurrency.

People who are sitting around waiting for STM should spend the time mastering declarative and message passing concurrency so that, when STM becomes widely available, they will be good enough to use it effectively. ;-)
(I smile, but I'm not joking...)

In programming languages like Java, a VM could:

1) ignore the synchronization statement.
2) make every object a different thread.
3) make every invocation a job for the thread behind the object.
4) introduce locks when waiting for results to become available.

I think the Actor model is more painless than STM, and it also helps expose whatever concurrency is there in programs.

It sounds like you're thinking of the join calculus.

But the description sounds closer to the Actor Model to me. I think there's a discussion here about the issue.

This is prone to deadlocks on object re-entrancy (depending on the details of per-actor locking).

There's also the issue that (loosely speaking) the more clever the transaction manager, the more serialization it imposes.

That wasn't quite what I meant, although I could see how you might take what I wrote that way. What I meant to suggest was that a more mature notion of what concurrently executing (and potentially conflicting) transactions "are" and how they are re-executed when conflicts occur might turn some of the prima facie scalability issues into non-issues. Not through omniscient oracles or super-duper optimisations, but just through an execution model which better suits what's going on.

A GUI system which re-computed its entire state from scratch in response to every interaction would probably be considered a naive implementation, and I guess my claim is really just that the current implementation approach for transactions (transaction logs and ab initio retry) will probably turn out to be naive, in hindsight, as better (but not magical or even difficult to implement) models become available.

I don't have much yet to back up my claim. It's a topic I plan to investigate as part of my PhD (I start next week), so any pointers to papers which discuss the poor scalability of transactions would be very welcome.

It's a topic I plan to investigate as part of my PhD (I start next week)

I certainly wouldn't discourage anyone from researching any topic. I only object if people claim it has practical application before it is done. ;-)

Good luck!

so any pointers to papers which discuss the poor scalability of transactions would be very welcome.

I don't know of any papers off hand that discuss this (though I may have read one at some time; I forget what I've read half the time...)

The practical problem in a nutshell is this:
- if the transaction is going to fail you can either throw it out or try again

- if you throw it out, you can tell your user/system there is a problem so a course correction can happen, manually or automatically as appropriate. The catch is, you lose some work, so the cost of this choice goes up with the amount of work done and the perceived value of the work and its timely execution.

- if you try again, you have just delayed telling the user/system of the failure, potentially increasing the cost of the failure. This might make sense if the timeliness of the work is more important than the cost of doing the work (e.g. real time system), but again, without understanding the human values behind the system.

So trying to make either strategy automatic by general policy will probably produce results that are worse than a custom system when the cost associated with timeliness or the cost to redo the work goes up.

Thanks! (If you do come across, or remember, any papers let me know.)

I will take minor issue with your summary of the transaction problem, though. Don't transactions often serve just to achieve a consistent history of interactions? In other words, most "retries" don't correspond to a failure at the application level (an application-level failure being something like: insufficient funds in your bank account) but to the computation having been carried out on a version of the system (call it x) which is now stale. Retrying is then fine to do automatically, because there was no requirement that the transaction apply specifically to version x in the first place: the requirement was simply that it apply to the latest version, whatever that may be.

In this sort of case (which I suggest is actually pretty representative) it would be inappropriate to inform the user of consistency failures, as they are in effect just a feature of the concurrency model, rather than application-level events. The transaction model simply serves to induce a single consistent picture of "what happened".

the requirement was simply that it apply to the latest version, whatever that may be

Remember that what you are trying to do is preserve consistency of the data. If you've done a calculation on stale data, saving the result might might put your data into an inconsistent state.

Let's take a simple case. I read a value from the store. I then do some complicated logic that takes a while and choose to update the store with a new value based on this logic.

In the meantime, someone else has done the same thing. This causes optimistic locking to fail.

Now, if you understand the data, you might say, "Well, I just want to update the spelling of someone's name; that can't hurt", so I retry the save without redoing the work, it works and everything is fine.

In which case, why bother with the transaction at all?

But let's say I'm about to change a counter that tells me how many transactions I have had. If I just retry the save, I'm going to damage the integrity of the data if I overwrite it.

So let's say that instead, I redo the work and retry. This might work, if my transaction is small and doesn't involve much work.
It still might fail again, and some intervention will be required to prevent permanent deadlock.

In this case, a pessimistic lock with waiting might have been a better choice.

Now imagine the case where the logic of my data requires me to make a lot of changes across many data relationships. There's no way that just retrying the save will be safe and the cost of redoing the work is higher, it takes longer, and the odds that someone else will make changes in the meantime goes up, so I really don't want to retry that. I pretty much need intervention if that goes wrong. (And probably need to redesign to a simpler locking scheme.)

Transactions really only win when either operations are very small, or the chances of collisions between writes are very low, meaning essentially that most data operations are independent of volatile data. Also when things do go wrong, prompt notification of a human who can judge what to do is probably essential.

Getting that right in complex systems is a significant design challenge, and just adding transactions is often the wrong thing to do.

How about something like this:

The transaction log stores a list of transactional variables that are written to, each of those is paired up with a function and a tuple of variables from which the final value in the variable can be computed. If you validate the log and realise that the read-from variables are not consistent you could just re-read the ones that have changed so that all of them are "latest" and re-run the computation to produce the new output variable. Seems semantically correct to me at an initial glance.

This saves you from doing a complete retry, you'd only need to recompute the stuff that belongs to written-to TVars that depend on the modified read-from TVars, which hopefully isn't all of the! But you might be able to take it further. The implementation is free to "cache" the thunks of this computation by assuming that the input variables are bound to the values that were in the variables when they were read, and you'd only need to recompute parts of the call graph that depend on the variables that were invalid, which saves you from having to do a complete retry. Not sure how efficient you could make that though.

At any rate, I think the point he was making was that we don't have to do a full retry on collision, there could be optimizations that will save that effort and improve scalability even more, and they don't have to be "magical" or anything, it might turn out that most of these collisions are simple to resolve mechanically.

Yes that kind of approach is what I was alluding to when I mentioned incrementally re-evaluating invalidated transactions. Umut Acar's work on adaptive computation (or self-adjusting computation, as he also calls it) looks promising. The approach uses just the kind of dependency tracking you describe to incrementally adjust a completed computation (understood as a persistent structure encoding its execution history) in response to changes to its inputs.

Clearly there's no case for just blatting the result of a stale transaction over the latest version of the system. If that were consistently safe then, as Marc pointed out, we wouldn't need transactions at all. Any automated system has to re-do the calculation, at least abstractly (and in the contexts of STM, that's just what "retrying" means). It's just that "abstractly" re-doing the calculation may concretely involve very little work, with a suitable but otherwise mundane implementation.

I agree with Marc's point that concurrent transactions that want to make lots of changes across many data relationships are problematic. But such issues are surely inherent to making simultaneous wide-ranging changes to a shared data structure. They aren't obviously more problematic for transactions than they are for lock-based approaches, and indeed most of the work so far suggests the contrary. When the likelihood of write collisions is high and the operations affect large amounts of data then locks perform badly too, resulting in deadlock, livelock and other problems.

They aren't obviously more problematic for transactions than they are for lock-based approaches, and indeed most of the work so far suggests the contrary. When the likelihood of write collisions is high and the operations affect large amounts of data then locks perform badly too, resulting in deadlock, livelock and other problems.

Absolutely true, in the sense that transactions are really just a sophisticated locking mechanism that make it harder for a bad design to kill your application completely, even though you can still blow its foot off. ;-)

In a sense you are pointing out the false premise lurking in the discussion about transactions: that the goal of locking mechanisms is to enable bad design. ;-)

The cure for bad design of concurrent systems is to follow the CTM hierarchy: start with a declarative design until you can't sensibly (or possibly) do what you want, then introduce message passing. When you get to the limits of what you need to do with that, then and only then introduce shared state, and only as much as is absolutely necessary.

Some problems are inherently shared-stateful, and when you get to those, transactions are an awesome tool to help you out.

The moral is that the only way to improve the reliability of concurrency overall is for developers to learn how to reduce shared-state and reduce state overall. Anyone who lacks this set of skills is doomed to build unreliable concurrent systems, no matter how powerful the locking mechanism at their disposal.

So making even smarter locking mechanisms won't really help, except in some very rare edge cases. They'll come in really handy in those cases though, so it's good we keep making them. ;-)

It's just that they won't revolutionize the field of concurrency the way some people seem to hope.

Clearly there's no case for just blatting the result of a stale transaction over the latest version of the system.

There is one very compelling case: hard real time systems.

Many systems, going back to the 60s, follow this model: all "threads" are finite state machines (FSM); the system operates "systolically" --

• the global state is frozen
• all FSMs are stepped based on global state
• outputs from the FSMs are written to the global state
• repeat

If there are conflicts in the writes, a priority scheme is employed, e.g., safety monitoring threads have priority over process threads. Physical I/O (sensors, actuators) is processed in parallel with the threads systolically as well.

This system is like STM in that no locks are employed in user code, and updates are atomic. It has the advantage that updates are also hard real time (as long as the FSMs have execution time limits). Of course, there are disadvantages as well!

There seems to be more than just a whiff of dataflow programming in the system design you described.

From Uniqueness logic:

A uniqueness type system is used to distinguish values which are referenced at most once from values which may be referenced an arbitrary number of times in a program. Uniqueness type systems are used in the Clean and Mercury programming languages to provide efficiently updatable data-structures and I/O without compromising referential transparency.

Uniqueness types are a form of substructural typing, like linear types. One use of this form of type system is deadlock freedom analysis.