Clojure and concurrency

[Øyvind Teig]

I have been reading myself up on Clojure concurrency, starting at [1]. In [2] I read that

The Clojure STM uses multiversion concurrency control with adaptive history queues for snapshot isolation, and provides a distinct commute operation

but it still needs some explanation to me. Software transactional memory (STM) is described ok. 

But the "adaptive history queues" looks like implementation. In ADA, tasks on rendezvous queue up (so the Ravenscar high security profile prohibits them because they are non-deterministic). In Go goroutines on selective choice's select are queued (also nondeterministic). In occam the there is no such queue on the ALT. How is the Clojure queue, and what does it contain?

I see that exchanging data between Clojure concurrent functions (threads?) described. But I haven't discovered how a "thread" that succeeds in writing, followed by a successful write immediately after by another thread - is "signalled" to the first thread? Is there any wait type of mechanism? 

If a write fails and there is a retry, what's the limit of retries, is there a yield in between, and in case, how is this entry queued?

Is it correct to say that never to block means never to be 100% sure that a transaction succeeds at first attempt?

[3] states on commute that "Thus fun should be commutative, or, failing that, you must accept last-one-in-wins behavior.  commute allows for more concurrency than ref-set.". What's the metric of concurrency? No, little, some, more, much, max?

I would have more questions, but they will come.

I plan to blog about these matters at [4]. It's a do-for-fun only blog, with no money or ads involved. I try to read myself up via atomic to several other concurrency models than CSP, which is flowing in my veins the last 25 years.

Øyvind Teig, Trondheim, Norway

[1] - http://clojure.org/concurrent_programming

[2] - http://clojure.org/Refs

[3] - http://clojure.github.io/clojure/clojure.core-api.html#clojure.core/commute

[4] - http://www.teigfam.net/oyvind/home/technology/

[Leon Grapenthin]

On Sunday, October 26, 2014 11:37:43 AM UTC+1, Øyvind Teig wrote:

I have been reading myself up on Clojure concurrency, starting at [1]. In [2] I read that

The Clojure STM uses multiversion concurrency control with adaptive history queues for snapshot isolation, and provides a distinct commute operation

but it still needs some explanation to me. Software transactional memory (STM) is described ok. 

But the "adaptive history queues" looks like implementation. In ADA, tasks on rendezvous queue up (so the Ravenscar high security profile prohibits them because they are non-deterministic). In Go goroutines on selective choice's select are queued (also nondeterministic). In occam the there is no such queue on the ALT. How is the Clojure queue, and what does it contain?

I see that exchanging data between Clojure concurrent functions (threads?) described. But I haven't discovered how a "thread" that succeeds in writing, followed by a successful write immediately after by another thread - is "signalled" to the first thread? Is there any wait type of mechanism? 

 

There is no signalling. The "write" in the first thread always succeeds within the transaction but the "real world" is not affected until the transaction succeeds as a whole. If during the transaction another transaction succeeded, it is retried as a whole, potentially with the new values written by the other transaction, until it has also succeeded. 

 

If a write fails and there is a retry, what's the limit of retries, is there a yield in between, and in case, how is this entry queued?

 

There is no limit. (Unfortunately I don't know about the implementation details and hopefully somebody else can enlighten you on that.)

 

Is it correct to say that never to block means never to be 100% sure that a transaction succeeds at first attempt?

Yes. 

[3] states on commute that "Thus fun should be commutative, or, failing that, you must accept last-one-in-wins behavior.  commute allows for more concurrency than ref-set.". What's the metric of concurrency? No, little, some, more, much, max?

 

How much happens at the same time in contrast to being queued up. Remember that only successful transactions affect the outside world. E. g.: Of two successful transactions, one had to be restarted because of the other completed during its first try => The two successful transactions didn't happen in parallel. Using commute reduces the potential of a retry and thus allow more successful transactions in parallel => more concurrency.

[Gary Verhaegen]

Transactions themselves are not queued (besides the obvious queueing
of threads when you have more threads than cores). What gets
adaptively queued is the historical values of refs involved in
transactions.

So if you have three concurrent transactions running, and three refs
are involved in two of these transactions, and a fourth refs in
involved in all three, the system will probably need to keep two
previous values for the first three refs and three previous values for
the last ref.

Code within a transaction should not have any other visible effect
than updating refs. When a transaction reaches its end, the system
checks the (current) value of all involved refs and retries if any has
changed.

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Øyvind Teig]

Loan, thank you!

kl. 21:03:59 UTC+1 søndag 26. oktober 2014 skrev Leon Grapenthin følgende:

On Sunday, October 26, 2014 11:37:43 AM UTC+1, Øyvind Teig wrote:

I have been reading myself up on Clojure concurrency, starting at [1]. In [2] I read that

The Clojure STM uses multiversion concurrency control with adaptive history queues for snapshot isolation, and provides a distinct commute operation

but it still needs some explanation to me. Software transactional memory (STM) is described ok. 

But the "adaptive history queues" looks like implementation. In ADA, tasks on rendezvous queue up (so the Ravenscar high security profile prohibits them because they are non-deterministic). In Go goroutines on selective choice's select are queued (also nondeterministic). In occam the there is no such queue on the ALT. How is the Clojure queue, and what does it contain?

I see that exchanging data between Clojure concurrent functions (threads?) described. But I haven't discovered how a "thread" that succeeds in writing, followed by a successful write immediately after by another thread - is "signalled" to the first thread? Is there any wait type of mechanism? 

 

There is no signalling. The "write" in the first thread always succeeds within the transaction but the "real world" is not affected until the transaction succeeds as a whole. If during the transaction another transaction succeeded, it is retried as a whole, potentially with the new values written by the other transaction, until it has also succeeded. 

So, this is basically as with atomics, no signalling? Is this because as such signalling is not needed, the basic algorithms that this is used on don't need such signalling? And if it's needed, then semaphors etc. may be built on top of these? A critical region has no signalling either, and it's ok in the context I, as an embedded programmer would most often see it: communication with interrupts. But of course, this involves some kind of polling to pick up something that's delivered from an interrupt.

 

If a write fails and there is a retry, what's the limit of retries, is there a yield in between, and in case, how is this entry queued?

 

There is no limit. (Unfortunately I don't know about the implementation details and hopefully somebody else can enlighten you on that.)

 

Is it correct to say that never to block means never to be 100% sure that a transaction succeeds at first attempt?

Yes. 

Good to have this confirmed, it helps my understanding; I haven't seen that sentence before. 

[3] states on commute that "Thus fun should be commutative, or, failing that, you must accept last-one-in-wins behavior.  commute allows for more concurrency than ref-set.". What's the metric of concurrency? No, little, some, more, much, max?

 

How much happens at the same time in contrast to being queued up. Remember that only successful transactions affect the outside world. E. g.: Of two successful transactions, one had to be restarted because of the other completed during its first try => The two successful transactions didn't happen in parallel. Using commute reduces the potential of a retry and thus allow more successful transactions in parallel => more concurrency.

Very interesting! 

[Øyvind Teig]

Gary, thank you!

kl. 22:41:02 UTC+1 søndag 26. oktober 2014 skrev Gary Verhaegen følgende:

Transactions themselves are not queued (besides the obvious queueing
of threads when you have more threads than cores). What gets
adaptively queued is the historical values of refs involved in
transactions.

So if you have three concurrent transactions running, and three refs
are involved in two of these transactions, and a fourth refs in
involved in all three, the system will probably need to keep two
previous values for the first three refs and three previous values for
the last ref.

Interesting. In my "Atomic for all?" blog (http://www.teigfam.net/oyvind/home/technology/090-atomic-for-all/ (*)) I wrote about some implementation details of atomic, where I quoted a guy I had talked with at a conference: "For some atomic implementations the hardware needs four copies of the atomic variable, and there are four booleans – three written by the writer and one by the reader.". Would the ideas behind the clojure transactions be  along that line, or am I shooting too far out: Make a table of the possibilities of getting something wrong then store what you need to be able to get things in order? (I do have a thick book about transactions, a friend said I needed it, but it's too thick for one life! But I know what might happen when I book a flight; it happened today! I came home, but 4 h late and one leg too much!)

(*) My blog, no ads, no money involved, just curriculum.

[Gary Verhaegen]

Transactions in Clojure are "optimistic": the runtime assumes that everything will work out, and if not, it retries.

Basically, when a transaction starts, the runtime makes a copy of the current value of all refs involved in the transaction (these are assumed to be immutable values, so copies are cheap). It then executes the transaction in an isolated context, i.e. it runs the code of the dosync based only on the values it has cached, with no regard for potentially concurrent transactions at all.

When the code in the dosync is finished, the result is a set of new values for the involved refs. At that point, the runtime "stops the world" (prevents write access to exactly these refs) and compares the current values of the refs with the values it had saved at the beginning of the dosync.

If they are the same, the system now stops the world even more (prevents reading from these refs) and updates all of the involved refs. Once all the new values are written and properly published, the protection is lifted and other threads trying to read or write these refs (if there are any) are unblocked.

If the old values are not equal to the current values, the system discards the new values, stores de current values in place of the old values for this thread, lifts the protection on the refs, and runs all of the dosync code again.

This is a basic mental model that is going to be mostly accurate from a user point of view. The real system is more complex and involves support for commutative operations (just rerun the code to update this one ref instead of all of the transaction if only this ref has changed) and some support for priority management - it is easy to imagine, with the structure painted above, a situation in which a stream of fast transactions force a slow transaction to restart indefinitely. I think I remember reading somewhere that the system made some attempt at preventing that.

Disclaimer: I've never needed refs, so all of my knowledge comes from dimly remembered readings when I was first learning Clojure three years ago. Someone please correct me if the above is not correct.