Too Much Code

Not enough cohesion

The Imaginary Concurrency Debate

It’s finally being accepted: the shared memory, critical region model for concurrent programming is broken. Even good programmers slip up and introduce race conditions, and bad programmers don’t even understand the semantics. (You mean I have to lock an object just to read its values?)

The question is: how do we fix it? Two proposals have drawn attention: The Actor/Message model and Software-Transactional Memory (STM). The former eliminates shared state entirely, using messaging primitives for communication between threads, which may or may not be in the same process or physical machine. The latter preserves shared memory, but each thread has a consistent view of shared state during an operation and makes updates atomically, much like a database transaction. We’ll refer to these as the Erlang model and the Haskell model (pdf), respectively, referring to the programming languages that most visibly use these synchronization techniques.

A debate between these models has quietly arisen. Proponents of the shared-nothing model point out the scalability and simplicity of Erlang. Proponents of STM point out the composability of guaranteeing updates to two components can be made atomically. Incredibly, it seems like this entire debate is ill-formed, and can be resolved with some simple generalization.

First we realize nearly all non-trivial applications use both a form of messaging and shared resources. A simple web application accepts messages from clients and shares state in a database. Therefore, any widely used programming environment must offer first-class support for transacted resources and messaging.

Now, suppose we view transacted memory simply as a hidden optimization of a transacted resource. In Erlang I can send messages to an Erlang process in the same physical address space or on a different machine – the former is simply a runtime optimization and not the concern of the developer. STM is just a local optimization of a transacted resource; with abstraction we can also host the resource remotely like a database or distributed cache.

In fact, the Erlang and Haskell models are closer than they first appear. The STM proposal for Haskell has almost nothing to suggest a TVar must be locally hosted. There are Erlang libraries allowing use of an RDBMS. Both of these could be implementations of a general “transacted resource” API or Monad. Similar parallels can be made for the messaging model. Of course the languages have other significant differences, but these concepts are not so far apart.

So where does this leave us in the concurrency debate? I think we can draw some conclusions:
  • Today’s concurrency primitives can be abandoned, replaced by messaging and transacted resources
  • Messaging and shared resources are complementary constructs used in most applications
  • Shared memory is to transacted resources what in-process messaging is to general messaging: a hidden optimization
  • Applications should use messages, transactions, or an appropriate combination depending on their needs
Now we need to ask why no widespread language has yet to replace critical region primitives with messaging and transacted memory. I think this is largely because such languages are hard to design. Notice how I’m generalizing STM and transacted databases to the same concept, but they have very different usage patterns in practice. It will be a challenge to design something this general yet simple enough so people will actually want to use it. But I’m an optimist.

One final note: both of these models are more easily implemented using a functional programming style. Something as simple as immutable objects makes both local messaging and transactions much simpler and more efficient. It’s funny how good practices pay off in ways we don’t expect.