In-order triggering of watches on mutable state

[Michael Drogalis]

Problem:

I have a ref representing a queue of people in line.

I add a watch to the ref to print out the contents of the queue whenever it changes.

Naturally, and expected, the following can happen if queuing happens in rapid succession:

Queue: []

<add "Mike" to queue>

<add "John" to queue>

console: "Queue is Mike, John"

console: "Queue is Mike"

I'd like to write a UI for this program, but I clearly can't reliably render based on the result delivered

by the add-watch hook. What's the solution for this problem?

[Timothy Baldridge]

Code? It's hard to debug if we can't see what's going on. 

--
--
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/groups/opt_out.
 
 

--
“One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
(Robert Firth)

[Aaron Cohen]

A watcher fn has 4 parameters: key, reference, old-state, new-state

If you use old-state and new-state rather than the reference, you should not see your problem.

--Aaron

--

[Michael Drogalis]

Aaron: Yep, I'm aware - and am using the value provided by the last parameter.

This is going to be tough to show the problem without bringing more details of my concurrency set up.

I'm not sure if this will exhibit the problem, but this is what it boils down to:

https://gist.github.com/MichaelDrogalis/6122834

When enough threads are trying to write to the queue, the watches

triggered later can finish before watches triggered earlier.

[Michael Drogalis]

I can precisely exemplify the behavior here:

https://gist.github.com/MichaelDrogalis/6123177

[Timothy Baldridge]

The answer is here: 

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/LockingTransaction.java#L361

Agents and watches are dispatched outside of the transaction locking. This means that multiple transactions could be executing watches in parallel, and hence execute out of order. 

Timothy Baldridge

[Mike Drogalis]

Thanks for the link. :) I understand that the behavior I'm seeing is correct. Any idea how to achieve the desired behavior, though?

You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/0b5HWJE6Jx4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.

[Timothy Baldridge]

You might want to consider switching to agents (or something else) I don't think it's possible to do what you want with refs.

Timothy Baldridge

[Mike Drogalis]

I'll play around with agents for this when I get some more free time.

I find it odd that, as the sole perceiver of an indentity, events are capable of being perceived out of order.

If I were watching a line queue up in person, events are obviously "dispatched" in order through my visual perception.

I trust there's a good reason it's designed this way, at any rate.

[Timothy Baldridge]

Deadlocks? Imagine a watch that ended up running a transaction against the ref it was triggered from. Sounds insane, but it could be fairly easy to do in a situation like this:

ref -> calls watchers -> calls fn1 -> calls fn 2 -> calls fn3 -> starts transaction on ref

Since watchers are notified outside of a ref transaction deadlocking is impossible. Inside a transaction you'd have a instant deadlock. 

Timothy Baldridge

[Mike Drogalis]

Good reasoning; that makes a lot of sense -- even if intuitively it doesn't follow through.

I'll do some more thinking about my concurrency needs and come back with a follow up question later. Thanks man!

[Cedric Greevey]

Try using an agent send from inside a transaction. Such sends are only dispatched if the transaction commits, and successive sends to the same agent from a single thread are run by the agent in the same order the thread sent them.

[Mike Drogalis]

Cedric: Will agents give me the guarantee that if I have something in Agent A, and I want to move it to agent B, and I do this inside a transaction:

- perceivers will see it in A at read point

- perceivers will see it in B at write point

- perceivers will never see it in neither nor both?

If that's the case, which is effectively synchronous coordination (I think?), what do refs buy you that agents don't?

[Timothy Baldridge]

"

Try using an agent send from inside a transaction. Such sends are only dispatched if the transaction commits, and successive sends to the same agent from a single thread are run by the agent in the same order the thread sent them."

That's not the problem. The problem is that agent sends (just like watchers) are dispatched outside of the transaction. So multiple threads accessing the same refs can be releasing sends to agents at the same time. This in turn means that the messages being sent to the agents can arrive out-of-order since one thread could pause allowing the other to send messages. 

Something to think about though is that you probably should be dealing with commutative operations. So instead of sending "set bank account to X" to refs/agents, instead send "increment bank account by 10". In this way many of these race-conditions no longer exist. 

Timothy

[Mike Drogalis]

Unfortunately, my problem is not one where the operation is communitive. To be concrete,

I am dealing with multiple threads plucking elements off the top of many different queues, and

putting them into a new queue. So adding element A, then B results in line [A, B], whereas

adding element B, then A results in line [B, A], which aren't equal.

Maybe I'm misunderstanding my problem, perhaps it is communitive. I just don't see it though.

[Timothy Baldridge]

Ding! You said the magic words! For queues, can I recommend one of the following?

http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html

According to Rich "why doesn't Clojure provide queues? The Java ones are just fine! Use them"

Also, if you have a large number of queues and don't want to tie up threads, have a look a core.async (http://github.com/clojure/core.async) it's designed exactly for this sort of thing.

With either of these you may still have some fun with having shared state between the threads, but perhaps these approaches may help a bit. 

Timothy

[Mike Drogalis]

Wooo! Magic words!

Yeah probably should have mentioned queuing up front - my apologies. core.async really confused me the first time 

I tried to give it a serious read. I'll give Blocking Queues a go and let you know how it wraps up. Thanks Timothy :)

[Mike Drogalis]

After thought: If Java's queues or core.async are indeed good solutions to data movement, isn't perceiving events in order still a problem?

add-watch doesn't apply at this point since it's not an IRef. Would this be a situation to use a Java observer?

Other after thought: If I was using add-watch, I could actually deref the reference (rather than using the 4th parameter value),

which always gives me the latest value. I might see duplicates, but I guess that depends on your use case whether that's okay or not.