| Article Index |
|---|
| STM Overview |
| Design Considerations |
| All Pages |
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.
There is one AtomicLong.incrementAndGet() that all transactions need to call to get a unique transaction ID.There is no locking of Ref objects for commit() or rollback(). Updates are done using AtomicReference.compareAndSet().
Transaction conflict can be detected early and one transaction can be rolled back or it can serialize-on-conflict; i.e. wait for the other conflicting transaction to finish before proceeding.
Performance Issues
A major issue with performance is the garbage collector (GC). Since the approach is mostly based around immutable objects, the GC gets to do a lot of forgetting. It can spend a lot of processor time doing this, but it doesn't have to. Some things I have discovered during performance testing.
-XX:+AggressiveHeap
This is very useful for achieving fast performance.
Also, leaving one "processor" free seems invaluable for allowing the GC to do its work without seriously impacting performance. I get better performance with one "processor" free than I do trying to use all "processor"s.
With default unconfigured GC, I have seen over 50% processor usage when only running one thread performing transactions. It should use less than 25%. For my tests, I can see less than 2M tx/sec with bad GC.
This is something to consider when testing STMs, make sure their performance isn't being affected by bad GC.
