Chapter 6: STM, MVCC & commute

You can find more precise explanations of the behavior of Clojure's STM system on their documentation website.

To answer your questions:

Is STM only in effect when a thread is in a dosync?

The body of a dosync is transactional: all refs will act as if they were read at the same snapshot in time, and all writes will be applied at the same moment in time, and any changes you make to refs' values within the dosync are visible later in the same dosync but not to any other dosync.

You can still read a ref's value outside a dosync, but there is no snapshot--you are just sampling a single ref's value at a single moment in time.

You cannot change a ref's value outside a dosync.

How is MVCC affected by use of commute?

deref (@) does not cause transactions to retry. This rule is expressed as "Reads do not block."

ref-set, alter, and ensure will retry a transaction if the refs they touch have changed since the transaction started. This rule can be expressed as "Writes and ensures block writes."

commute will do another read+write to its ref at the very moment a transaction is applied (when contention is impossible). This means it will never block reads or writes: it is a non-blocking write. This also means that the dosync that contains the commute may not ever actually see the true final value of that ref. This is the price paid for a non-blocking write.

How is the CONSISTENT principle enforced when commute is being used?

"Consistency" merely means no data invariants or constraints are violated. There are two kinds of these:

Constraints on a single ref's value, in isolation. To ensure a particular ref is consistent, attach a validation function to the ref: the validation function is called with the new value that will be placed in the ref, and it may return false or throw an exception to reject the new value (and thus the transaction). For example, (ref 1 :validator pos?) would require that ref always have a numeric value greater than 0.

Constraints satisfied among refs. For example, if one ref is a sum of some other refs, you need to ensure the sum is accurate. You cannot enforce this automatically with a ref-level validation function. Nor can you naively read (deref) the inputs to the sum, because reading (and commuting) does not block other writers--another transaction may have occurred "simultaneously" which wrote a new value that your transaction will never see. In these cases, you use the ensure function: this tells the STM that the ref's value must not change even though you are not writing to it.

This is how you would write a fully-consistent summation function:

(def a (ref 0 :validator number?))
;=> #'user/a
(def b (ref 0 :validator number?))
;=> #'user/b
(def sum (ref 0 :validator number?))
;=> #'user/sum
(dosync
  (let [av (alter a inc)
        bv (ensure b)] ;; We don't change b, but we need to ensure b does not change!
    (ref-set sum (+ av bv))))
;=> 1
(dosync [@a @b @sum]) ;; Done inside a dosync so we read all refs at same instant.
;=> [1 0 1]

If two threads try to increment 50 ref counters in a dosync:
1) If the code calls for using alter, I assume that one will finish, commit and the other will have to start over. Is that correct?

Correct. If the input ref to alter has a different value at the beginning vs the end of the transaction, the whole transaction must retry.

2) What if the code calls for using commit? What happens then?

(I assume you mean "commute" not "commit"?) Commute does not block writes, so in your example no transactions will ever have to retry.

I.e., this dosync, running in 50 threads, will never have to retry because of contention:

;; Vector of 50 ref counters
(def counters (vec (repeatedly 50 #(ref 0))))
;=> #'user/counters
;; Now run this dosync in parallel on many threads
;; It will never have contention.
(dosync
  (run! #(commute % inc) counters))
;=> nil
;; This will return the value of all counters.
(dosync (mapv deref counters))

There is an important thing to note when using commute. Remember our sum-ref example? Suppose you used commute instead of alter to increment counter a:

(dosync
  (let [av (commute a inc)
        bv (ensure b)]
 ;; OOPS! av may be stale!
    (ref-set sum (+ av bv))))

What is the problem here? Remember that commutes do not block other writes, so it is possible that some other dosync incremented ref a, and our dosync may not see the most up-to-date value of av! This means our (ref-set sum (+ av bv))) may be wrong!

(Practically, this transaction acts safely because every dosync that ref-sets sum also commutes a or b, but theoretically it is not safe.)

Basically, if you set the value of a ref based on the values of other refs read within your transaction, and you require strong consistency among those refs, you must inform the STM that your dosync requires those read refs not change. You mark a ref in this way when you alter, ref-set, or ensure it, but not when you commute or deref it!

Another way of thinking of it: you probably don't want to use the value of a (commute) call to update another ref's value. Even though the operation on the individual ref is commutative, the whole transaction is not commutative.

This example is safe:

(dosync
  (let [av (alter a inc)
        bv (ensure b)]
    (ref-set sum (+ av bv))))

So is this, but the commute doesn't actually give you any extra concurrency because you ensure the same variable:

(dosync
  (commute a inc) ; Run for side effects, return value is not trustworthy because it may be stale.
;; (ensure a) will always see the latest value of a
  (ref-set sum (+ (ensure a) (ensure b))))