This article is a description of a simple software transaction memory (STM) I wrote in Scala in order to better understand STMs. I'll start with a summary of performance and then go into some details. For a good introduction to writing an STM in Scala, look at the article in code commit. These are all MVCC-style STMs that guarantee transactions read from a consistent snapshot of data. Unlike other similar approaches, they don't allow write-skew - so your transactions give the same result running in parallel as they would if they ran serially; no surprises. The all provide nested transactions.

9.5 million transactions / second

very optimistic for low contention transactions

uses CAS instead of locking

snapshot history is limited to allow good garbage collection performance - meaning some transactions may retry due to not finding the required history

4.5 million transactions / second

pessimistic, transactions are isolated until commit time

uses locking instead of CAS - better for high concurrency implementations

also has limited snapshot history for good, fast GC performance

3.5 million transactions / second  (new alpha version)

has precise snapshot history management - you can start a transaction, sleep for a year, then continue on - the transaction will still be able to access a full snapshot history, using minimal memory to store the snapshot - based on a distributed snapshot tree for concurrent updating - read only transactions never retry

This is running on a 2.8GHz quad-core i7-860, Java 6u20. Basic test of 1024 accounts, each transaction moves a random amount of money from one random account to another. There is also one transaction that periodically sums all the accounts and ensures that no money is lost or gained. The test is aimed at finding the overhead of the STM, nothing more. STMs aren't good for many conflicts, so the conflicts are kept relatively low.

The snapshot history is guaranteed to be available for every transaction running in the system, they grow to the correct length, no longer and no shorter than required. This is different to, say Clojure, which keeps more history than needed for most transactions and fails transactions that need more history than available. Clojure adjusts history length after a failure. It's harder to design a system like Clojures; correct lengths are easier and have less overhead. But you can do insane things like start a transaction, wait for 1 second, then sum all accounts. With other threads running at 7M tx/sec, histories are thousands of values long.

The MVCC STM keeps a history of old Ref Values. This needs to be managed so the list doesn't get too long. You would think there is a way to have the Garbage Collector do the work of getting rid of old values that are no longer required. After some designing, then thinking, then more designing, I found a way that makes this work quite nicely.

The Garbage Collected History List

I couldn't find a reference to anything like this - I guess I don't know the right keywords to Google on. Anyway, a fundamentally simple concept that allows the tail of a list to be GC'd at the point where there are no references to the list below that point.

Perfect for a history where you only need to keep values that are still possibly likely to be used.