Software Transactional Memory - Composability Example

Question

One of the major advantages of software transactional memory that always gets mentioned is composability and modularity. Different fragments can be combined to produce larger components. In lock-based programs, this is often not the case.

I am looking for a simple example illustrating this with actual code. I'd prefer an example in Clojure, but Haskell is fine too. Bonus points if the example also exhibits some lock-based code which can't be composed easily.

Bugaboo

Answer 1

An example where locks don't compose in Java:

class Account{
  float balance;
  synchronized void deposit(float amt){
    balance += amt;
  }
  synchronized void withdraw(float amt){
    if(balance < amt)
      throw new OutOfMoneyError();
    balance -= amt;
  }
  synchronized void transfer(Account other, float amt){
    other.withdraw(amt);
    this.deposit(amt);
  }
}

So, deposit is okay, withdraw is okay, but transfer is not okay: if A begins a transfer to B when B begins a transfer to A, we can have a deadlock situation.

Now in Haskell STM:

withdraw :: TVar Int -> Int -> STM ()
withdraw acc n = do bal <- readTVar acc
                    if bal < n then retry
                    writeTVar acc (bal-n)

deposit :: TVar Int -> Int -> STM ()
deposit acc n = do bal <- readTVar acc
                   writeTVar acc (bal+n)

transfer :: TVar Int -> TVar Int -> Int -> STM ()
transfer from to n = do withdraw from n
                        deposit to n

Since there is no explicit lock, withdraw and deposit compose naturally in transfer. The semantics still ensure that if withdraw fails, the whole transfer fails. It also ensures that the withdraw and the deposit will be done atomically, since the type system ensures that you cannot call transfer outside of an atomically.

atomically :: STM a -> IO a

This example comes from this: http://cseweb.ucsd.edu/classes/wi11/cse230/static/lec-stm-2x2.pdf Adapted from this paper you might want to read: http://research.microsoft.com/pubs/74063/beautiful.pdf

Pollinize

@luqui Never happened to me to get a Money overflow though :\ I do wonder why... If people could send me money so that I could debug this path of my code. – Pollinize

Your Java transfer example has a bigger issue: you don't lock on other. Both problems would be solved by wrapping the two calls inside transfer with synchronized(other) { ... } – Samarasamarang

That seems right. But if you do so, you are still in a deadlock situation, since a.transfer(b, 1) requires lock on a then lock on b, and b.transfer(a, 1) requires the same locks in opposite order, am I wrong? – Pollinize

That last paper you mention is just wonderful, read it some time ago. – Unscreened

The problem on the java code is the double lock order which is inherently different (ie. always the current object first). It vanishes when you remove the synchronized on transfer, downgrading the lock need to successive single locks. Good example though, and excellent link (+1). – Brasilin

Answer 2

A translation of Ptival's example to Clojure:

;; (def example-account (ref {:amount 100}))

(defn- transact [account f amount]
  (dosync (alter account update-in [:amount] f amount)))

(defn debit [account amount] (transact account - amount))
(defn credit [account amount] (transact account + amount))
(defn transfer [account-1 account-2 amount]
  (dosync
    (debit account-1 amount)
    (credit account-2 amount)))

So debit and credit are fine to call on their own, and like the Haskell version, the transactions nest, so the whole transfer operation is atomic, retries will happen on commit collisions, you could add validators for consistency, etc.

And of course, semantics are such that they will never deadlock.

Tomlin

But you don't check that we don't withdraw more than the account has so it's a bit different. But it's Clojure so that will be interesting for dbyrne. Also nice reuse by aav. – Pollinize

That's fair. For that you'd use validators: – Tomlin

Whoops. For that you'd use the validators that I mentioned, e.g. (def account (ref {:amount 100} :validator (fn [act] (>= (:amount act) 0)))) I'd split the validator function out to a named function in real code. That provides the consistency guarantee that I mention. – Tomlin

Answer 3

Here's a Clojure example:

Suppose you have a vector of bank accounts (in real life the vector may be somewhat longer....):

(def accounts 
 [(ref 0) 
  (ref 10) 
  (ref 20) 
  (ref 30)])

(map deref accounts)
=> (0 10 20 30)

And a "transfer" function that safely transfers an amount between two accounts in a single transaction:

(defn transfer [src-account dest-account amount]
  (dosync
    (alter dest-account + amount)
    (alter src-account - amount)))

Which works as follows:

(transfer (accounts 1) (accounts 0) 5)

(map deref accounts)
=> (5 5 20 30)

You can then easily compose the transfer function to create a higher level transaction, for example transferring from multiple accounts:

(defn transfer-from-all [src-accounts dest-account amount]
  (dosync
    (doseq [src src-accounts] 
      (transfer src dest-account amount))))

(transfer-from-all 
  [(accounts 0) (accounts 1) (accounts 2)] 
  (accounts 3) 
  5)

(map deref accounts)
=> (0 0 15 45)

Note that all of the multiple transfers happened in a single, combined transaction, i.e. it was possible to "compose" the smaller transactions.

To do this with locks would get complicated very quickly: assuming the accounts needed to be individually locked then you'd need to do something like establishing a protocol on lock acquisition order in order to avoid deadlocks. As Jon rightly points out you can do this in some cases by sorting all the locks in the system, but in most complex systems this isn't feasible. It's very easy to make a hard-to-detect mistake. STM saves you from all this pain.

Elative

@Jon - of course a sort works in simple cases for lock ordering. But it isn't so easy in an enterprise application with hundreds of classes each with their own locking strategy and the need to co-ordinate different types of transactions across all of this. This is when the "locks don't compose" starts to really hurt. – Elative

I agree completely. I just thought it might be useful to point out that the solution is at least simple in theory. – Felicidadfelicie

Even ignoring the large application case, what would a locking protocol look like in this example? – Margertmargery

@Ganesh - you could give each an account an account ID, and acquire the individual locks for each account you want to modify in account-ID order. If you do it this way you can avoid deadlocks – Elative

Is that assuming re-entrant locks, so that we can first acquire them outside transfer and then let transfer re-acquire them? Without that I think we would need an alternate version of transfer without locking. – Margertmargery

Answer 4

And to make trprcolin's example even more idiomatic i would suggest changing parameter order in transact function, and make definitions of debit and credit more compact.

(defn- transact [f account amount]
    ....  )

(def debit  (partial transact -))
(def credit (partial transact +))

Monolithic

In fact this is not more idiomatic in Clojure. For idiomatic Clojure the account should go first. – Jacinto