Composable Blocking Transactions

Background: Software Transactional Memory (STM) is a foundation for atomic composable non-blocking transactions. An STM transaction consists of a set of variables and a monadic sequence of read/write operations on those variables. As the transaction progresses, a transaction table is constructed detailing the specific variables to be modified. At the end of the transaction, either the changes are written atomically (that is, none of the intermediate modifications are visible to the outside world), or the transaction is aborted as though nothing had happened.

Blocking-transactions is an alternative library that implements atomic transactions using locks. This library is strictly less expressive than STM, but does have some advantages.

First, I will demonstrate why such a library is even possible. In order to implement a blocking transaction, we must:

  1. Sort all of the variables that could participate in the transaction.
  2. Sieze a lock on each variable in sorted order.
  3. Perform the transaction.
  4. Release all of the locks.
  5. Notify any waiting threads that the variables have been modified.

Acquiring locks in sorted order guarantees that the program can not deadlock. Acquiring a lock effectively acquires the exclusive right to acquire any greater-ordered locks before any thread that has acquired a lesser-ordered lock.

None of this is possible unless we know the entire set of variables before the transaction takes place. In traditional models of computation, this is impossible. However, arrows provide an environment of restricted flow control in which all computations are either inevitable or in which there is a finite set of branches. The StaticArrow is an example of an Arrow that can do this.

It is also possible to build a monad with similarly restricted flow control. If the side-effectful operations of a monad always return an opaque value (meaning that there is no function that can transform the value or any combination of values into a boolean) then no flow control within the monad is possible.

Such a library has a profound limitation: although we can store a transactional variable inside another transactional variable, we can not retrieve it without considerable contortions. Blocking transactions therefore do not seem to be suitable for working with complex graphs of transactional variables.

On the other hand, the restricted flow control that blocking transactions require presents an unexpected opportunity: transactions can be made inevitably lazy. A lazy transaction completes in the time it takes to entangle the variables in a system of unevaluated thunks. This means that the locks are held for the shortest time possible, but increases the CPU time needed to complete the entire program.

These systems of unevaluated thunks constitute a potentially hazardous memory leak. I choose to write the library in such a way that each variable is forced after the transaction completes, by means of a parallel spark.

This is not the only strategy for evaluating a transaction. We could also choose to:

  • Allow values to be forced within the transaction, but locks could be held while an expensive and unimportant computation completes. We would then want a strategy to release unneeded locks early, but this would add overhead.
  • Sequentially force each variable after the transaction, but this was not efficient in the benchmark.
  • Specify a per-variable strategy for forcing each variable, but this is adds complexity with little apparent benefit.
  • Tolerate the memory leak on the assumption that the caller must manually force the contents of the transaction, but this had catastrophic implications for performance in the benchmark.

Note that the blocking transactions library at the moment is not exception safe.

My implementation is available as a git repository. You can also link directly to the source code and a simple benchmark.

$ git clone http://www.downstairspeople.org/git/blocking-transactions.git/

About these ads

About Christopher Lane Hinson

A hairy haskell hacker with interests in games, computer science, and social justice.
This entry was posted in Haskell. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s