Question about implementation

104 views
Skip to first unread message

tkue...@gmail.com

unread,
Aug 31, 2013, 3:47:32 PM8/31/13
to scala-stm-e...@googlegroups.com
I am new to ScalaSTM and have some questions on the implementation of the STM?
It is written that is similiar to the STM of clojure, so my questions:

- Does ScalaSTM use an optimistic approach or not (CojureSTM doesn't)?
- Are reads impeded by writes?

Nathan Bronson

unread,
Sep 2, 2013, 3:38:19 PM9/2/13
to scala-stm-e...@googlegroups.com
The similarity between Clojure's STM and ScalaSTM is mainly in their interface. Both STM's operate only on mutable boxes (Ref[T] in Scala and ref in Clojure), and both advocate designs that minimize mutable state by using immutable data structures where possible. This is in contrast to most STMs, which try to coordinate access to every mutable value in the heap. Haskell's STM is also in the same camp as Clojure's and ScalaSTM (their box is called TVar).

The algorithms underneath Clojure's STM and ScalaSTM are at pretty different points on the design space. ScalaSTM starts with optimistic concurrency control, then falls back to pessimistic conflict detection if the optimism isn't succeeding. This provides the scalability advantages of invisible reads in most cases with reasonable performance for all use cases. ScalaSTM's transactions are always serializable and have lower CPU and memory overhead than Clojure's, but are more likely to require retry, since we don't retain more than one old version of a ref (unlike Clojure's MVCC with adaptive per-ref history).

Neither STM can guarantee that any particular transaction attempt will succeed. True snapshot isolation would allow this for read-only transactions, but a ref might not have enough history on the first try in Clojure's STM. Neither STM makes it safe to perform I/O inside a transaction.

From the programmer's perspective, the most important difference between the STMs is the consistency model. ScalaSTM's transactions are always serializable, which is a stronger guarantee than snapshot isolation. Clojure's STM serializes reads at the beginning of the transaction and writes at the end of the transaction. This allows what is known as a "write skew" anomaly. You can prevent this by calling ensure or ref-set on every ref that is read in a transaction, or you can apply whole-program application reasoning to argue that the result is correct despite write skew.

As an example of write skew, let's say your library application logic says you can only check out a book if you don't have a dvd checked out, and vise versa:
  (dosync (if-not @book-out (ref-set dvd-out true)))
  (dosync (if-not @dvd-out (ref-set book-out true)))
With ClojureSTM it is possible that you will end up checking out both a book and a dvd. They don't write to the same ref, so their commit can proceed in parallel, and they are reading from a stale snapshot that indicates that nothing has been checked out. (This is the same behavior that requires the use of "SELECT FOR UPDATE" in Oracle.) To make this example work in Clojure, you need to add calls to ensure, while it works out of the box in ScalaSTM.

For some use cases, ScalaSTM's TMap and TSet can provide the concurrency benefits of snapshot isolation without the loss of atomicity. TMap and TSet provide an O(1) clone operation that takes a snapshot, and the snapshot can be retained outside a transaction. Once the transaction has finished then you can iterate or modify the snapshot with a hard guarantee that no rollback is possible. (Think of TMap and TSet as a ref that holds an immutable map or set, but that performs conflict detection per-key instead of per-map, with no need to call alter.)

If you really want details, ScalaSTM is based on the SwissTM algorithm (http://lpdserver.epfl.ch/transactions/wiki/doku.php?id=swisstm), using the GV6 timestamp algorithm from the TL2 STM. To the basic algorithm I have added nested transactions, a more robust conflict detection mechanism, full support for the retry/orElse waiting mechanism introduced by Haskell's STM (called retry/orAtomic to avoid naming conflicts with idiomatic Scala), fast single-operation transactions, and "unrecorded" nested transactions that allow for good debugger integration.

(*) - I have not used Clojure's STM except in toy examples. This email is based on my reading of the Clojure documentation and source code.

Regards,
   Nathan


--
 
---
You received this message because you are subscribed to the Google Groups "Scala STM Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-stm-expert-...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.



--
Nathan Grasso Bronson
ngbr...@gmail.com

tkue...@gmail.com

unread,
Sep 3, 2013, 4:58:30 AM9/3/13
to scala-stm-e...@googlegroups.com
Wow, a detailed an impressive reply. Thank you very much :)
Reply all
Reply to author
Forward
Message has been deleted
0 new messages