294119 (31) [Avatar] Offline
#1
Is STM only in effect when a thread is in a dosync?

How is MVCC affected by use of commute?

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

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?
2) What if the code calls for using commit? What happens then?

I realize my newbie underwear is showing here smilie
Francis Avila (16) [Avatar] Offline
#2
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))))
    
    294119 (31) [Avatar] Offline
    #3
    Thank you for your prompt, and very detailed, reply. If you don't teach or mentor in conjunction with coding, you should!

    I will spend some time going over your points. Your code examples really help as I wasn't sure how to test my understanding in the REPL.

    The link to the documentation opened my eyes. I am new to Clojure with no real Java experience. I've looked up functions in documentation, but hadn't seen/wasn't aware of more in-depth discussions and overviews.

    Your book is very well written and has really opened my eyes to the power of Clojure.

    Thanks again!
    Francis Avila (16) [Avatar] Offline
    #4
    Glad to help!

    Another thread on this forum goes into STM problems in more detail. At the bottom of that thread I have a link to a gist of mine with some helper functions for running many dosyncs in parallel for testing.

    Like I say there, though, I still haven't encountered a good practical use for STM. It's an amazing system, but immutability (and maybe an atom) seems like a better approach the vast majority of the time.