Clojure STM not serializable

[Eric Willigers]

Hi all,

I'm enjoying using Clojure. It is clean, concise and powerful.

The containers and even defmacro are easy to use correctly. However,
I'm yet to be convinced the same applies with the STM implementation.

In the user code below, people might expect b == a + 1 after the two
transactions run. Unfortunately, that isn't the case, as no read locks
are being taken. (It would have been true if the transactions ran
sequentially, in either order.)

Is the lack of isolation affecting people, or do most users use idioms
that avoid the problem?
Example idioms would be writing every ref that is read, or using a
single ref to switch to a new immutable data structure (as opposed to
implementing mutable data structures using numerous refs).

Regards,
Eric.

P.S. I'm aware Oracle and PostgreSQL similarly have non-serializable
transactions.



(def a (ref 0))
(def b (ref 0))

(.start
(Thread.
#(dosync
(let [old-a @a]
(Thread/sleep 2000) ; or any slow computation
(ref-set b (inc old-a))))))

(.start
(Thread.
#(dosync
(let [old-b @b]
(Thread/sleep 2000) ; or any slow computation
(ref-set a (dec old-b))))))

(Thread/sleep 6000) ; or join the above threads
(println "a=" @a ", b=" @b)

a= -1 , b= 1

[Christian Vest Hansen]

You can use `ensure` if you want to make sure that the transaction
fails if a or b are altered while the threads are sleeping in your
example:

http://clojure.org/api#ensure

Otherwise, regarding serializable concurrency level: If you want
mutual exclusion, then that's what locks are for.

--
Venlig hilsen / Kind regards,
Christian Vest Hansen.

[Rich Hickey]

On Jun 18, 2009, at 2:38 AM, Eric Willigers wrote:

>
> Hi all,
>
> I'm enjoying using Clojure. It is clean, concise and powerful.
>
> The containers and even defmacro are easy to use correctly. However,
> I'm yet to be convinced the same applies with the STM implementation.
>
> In the user code below, people might expect b == a + 1 after the two
> transactions run. Unfortunately, that isn't the case, as no read locks
> are being taken. (It would have been true if the transactions ran
> sequentially, in either order.)
>
> Is the lack of isolation affecting people, or do most users use idioms
> that avoid the problem?
> Example idioms would be writing every ref that is read, or using a
> single ref to switch to a new immutable data structure (as opposed to
> implementing mutable data structures using numerous refs).
>
> Regards,
> Eric.
>
> P.S. I'm aware Oracle and PostgreSQL similarly have non-serializable
> transactions.
>

It's not a lack of isolation. It is snapshot isolation, and is subject
to write-skew.

http://en.wikipedia.org/wiki/Snapshot_isolation

As documented here:

http://clojure.org/refs

point #8:

"If a constraint on the validity of a value of a Ref that is being
changed depends upon the simultaneous value of a Ref that is not being
changed, that second Ref can be protected from modification by calling
ensure. Refs 'ensured' this way will be protected (item #3), but don't
change the world (item #2)."

That describes your situation, and you can use 'ensure' to ensure the
serializability of your reads. This is better than the "dummy write"
solution in that multiple ensures of the same refs don't conflict.

You should be able to use ensure to avoid write skew in all cases, e.g.

(let [old-a (ensure a)] ...

Rich

[Eric Willigers]

On Jun 18, 9:35 pm, Rich Hickey <richhic...@gmail.com> wrote:
> http://clojure.org/refs
>
> point #8:
>
> "If a constraint on the validity of a value of a Ref that is being  
> changed depends upon the simultaneous value of a Ref that is not being  
> changed, that second Ref can be protected from modification by calling  
> ensure. Refs 'ensured' this way will be protected (item #3), but don't  
> change the world (item #2)."
>
> That describes your situation, and you can use 'ensure' to ensure the  
> serializability of your reads.

Thanks, that was all very helpful. With ensure, there's no write skew.

> This is better than the "dummy write"  
> solution in that multiple ensures of the same refs don't conflict.

I haven't been able to verify this part - are you refering to
Clojure's current implementation? In my experiment below using Clojure
1.0.0, I'm seeing conflicts.


No conflict when we use deref:-

(def a (ref 0))
(def b (ref 0))

(def c (ref 0))

(.start
(Thread.
#(dosync
(println "Reading a to update b")
(let [old-a (deref a)]
(Thread/sleep 2000)
(println "Updating b")

(ref-set b (inc old-a))))))

(.start
(Thread.
#(dosync

(println "Reading a to update c")
(let [old-a (deref a)]
(Thread/sleep 2000)
(println "Updating c")
(ref-set c (inc old-a))))))

(Thread/sleep 3000)
(dosync
(println "a=" @a ", b=" @b ", c=" @c))

(Thread/sleep 3000)
(dosync
(println "a=" @a ", b=" @b ", c=" @c))



Reading a to update b

Reading a to update c

Updating b

Updating c

a= 0 , b= 1 , c= 1

a= 0 , b= 1 , c= 1

(all output as expected)



Conflict when we use ensure:-

Replace each
(let [old-a (deref a)]
with
(let [old-a (ensure a)]



Reading a to update b

Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c
Reading a to update c

Updating b

Reading a to update c

a= 0 , b= 1 , c= 0

Updating c

a= 0 , b= 1 , c= 1


(I expected the same output as for deref, because a is never updated.)

[Rich Hickey]

On Fri, Jun 19, 2009 at 9:35 AM, Eric Willigers<ewill...@gmail.com> wrote:
>
> On Jun 18, 9:35 pm, Rich Hickey <richhic...@gmail.com> wrote:
>> http://clojure.org/refs
>>
>> point #8:
>>
>> "If a constraint on the validity of a value of a Ref that is being
>> changed depends upon the simultaneous value of a Ref that is not being
>> changed, that second Ref can be protected from modification by calling
>> ensure. Refs 'ensured' this way will be protected (item #3), but don't
>> change the world (item #2)."
>>
>> That describes your situation, and you can use 'ensure' to ensure the
>> serializability of your reads.
>
> Thanks, that was all very helpful. With ensure, there's no write skew.
>
>
>> This is better than the "dummy write"
>> solution in that multiple ensures of the same refs don't conflict.
>
> I haven't been able to verify this part - are you refering to
> Clojure's current implementation? In my experiment below using Clojure
> 1.0.0, I'm seeing conflicts.
>

They don't conflict, but you are correct that Clojure's STM currently
doesn't leverage that fact. It is my intention that at some point it
will, so please use ensure rather than dummy writes.

Rich

[Rich Hickey]

On Jun 19, 2:44 pm, Rich Hickey <richhic...@gmail.com> wrote:

I've implemented overlapping ensure in the ensure branch:

http://github.com/richhickey/clojure/tree/ensure

Everyone using the STM please try it out.

Thanks,

Rich