Concurrent updates to immutable data structures: trouble in paradise?

[Ben Hutchison]

Spend 5 minutes googling "immutable data structures" and you'll be
told, repeatedly, how good immutable data structures are for
concurrency.

Er...a clarification: /read/ concurrency. Immutable data structures
are brilliant for readers, since any number can read the structure
without any contention or consistency problems.

But for writers it ain't so pretty. Every write creates a new variant
of the structure that needs to be 'published'. Assume we use some
thread-safe mutable reference to the root node of the structure: the
readers grab the latest copy and query it, the writers write back a
new version.

The bit that really troubles me is the obvious scalability bottleneck
on the mutable root-node ref. At some level of concurrency, updates to
this ref will max out due to contention.

The only way out seems to be split the contended ref, by introducing
more mutation spread across the structure. Then writers in different
regions of the tree will not contend with each other, and we can scale
further.

But its very unclear to me how far to take this? Make every node a
thread-safe ref with read/write locks, and the tree essentially
mutable? Or is there some hybrid approach that keeps immutability in
local regions of the structure?

Ideally, we'd have a dial to smoothly vary "immutability level",
according to the desired tradeoff between read vs write performance.
Yet the two programming approaches that feel most consistent and sane
are at the extremes: all-immutable, and all-mutable. Is there any
plausible middle ground?

-Ben

[Ben Hutchison]

To partially answer my own question: googling around I noticed this
2010 paper by the rather brilliant Nathan Bronson of Stanford, who is
also the lead author of ScalaSTM. Nathan's work tends to be right on
the cutting edge of available technology, IME.

He outlines a mutable concurrent "snaptree", which supports a fast
clone operation. Clone yields a snapshot of the tree, while the
orignal tree can continue to be updated. The tree is updated via
copy-on-write, so the snapshot shares most of its content with the
original tree. Impressive performance results.

http://ppl.stanford.edu/papers/ppopp207-bronson.pdf

So the state-of-the-art seems to be mutable structures that can yield
immutable "snapshot views" onto their state.

This lets you do things like backup a concurrent datastore without any
interruption to service.

-Ben

[Ben Hutchison]

The plot thickens, even Odersky's fingerprints are all over this stuff:

http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

This structure, like the binary tree, provides lazy snapshots, but
differs in that:

(a) It uses an array-based hash table rather than a tree
(b) is lock free, using Compare-and-Swap (CAS), which is better

They say something at the end about back-porting the lock-free
technique to trees.

Interesting to see how core Scala people seem to be so involved with
high-performance concurrent data structure research.

-Ben

[Lachlan O'Dea]

Did you see the notes for the 2.10 milestone that just dropped?

* should be able to implement a combiner using a concurrent (thread-safe) collection.
* Ctries added to the standard library. Implement parallel ctries using the above mechanism.

http://www.scala-lang.org/node/12659

[Ben Hutchison]

On Tue, May 1, 2012 at 5:53 PM, Ben Hutchison <brhut...@gmail.com> wrote:
> http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf
>
> This structure, like the binary tree, provides lazy snapshots, but
> differs in that:
>
> (a) It uses an array-based hash table rather than a tree

Actually, I was wrong above. Ctries use a Tree of very short arrays (a
bit like Scala's immutable vectors which AFAIK are a tree of 32-cell
vectors).

I'd guess Ctries have some wins over binary trees due to space
efficiency and "data clumping", but if someone knows better, please do
educate me.

-Ben

[Tony Morris]

Why can we not use the usual techniques of updating immutable data
structures, such as lenses and zippers?

--
Tony Morris
http://tmorris.net/

[Ben Hutchison]

Consider what happens when two threads A and B simultaneously want to
make updates to a shared data structure S.

If immutable update techniques are used, each thread will create a
copy of S with their own changes only, ie S_A and S_B.

But how to see the impact of both updates together, S_AB?

Either:
- A and B have to serialize their changes, in which case we don't have
any write concurrency
- A mutable structure is used that can be updated at multiple points at once.

Generally data structures supporting concurrent writes are mutable.
But this brings it own challenges: traversing over a structure
undergoing modification is a nightmare.

So the current state of the art are "snapshot-able" structures, which
can flip-flop between mutable and immutable modes. When flipped into
immutable mode, they can leave behind an immutable snapshot of their
state for readers to work off, then flip back to mutable mode and
continue to mutate in parallel.

The price of the snapshot is a brief throttling back of write
activity, to allow the structure to stabilise enough to form a
consistent snapshot, and one copy-on-write whenever a node diverges
from the last snapshotted state.

-Ben

> --
> You received this message because you are subscribed to the Google Groups "Melbourne Scala User Group" group.
> To post to this group, send an email to scala...@googlegroups.com.
> To unsubscribe from this group, send email to scala-melb+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/scala-melb?hl=en-GB.
>

[Andy Gelme]

hi Ben,

On 2012-06-26 15:26 , Ben Hutchison wrote:
> Consider what happens when two threads A and B simultaneously want to
> make updates to a shared data structure S.
>
> If immutable update techniques are used, each thread will create a
> copy of S with their own changes only, ie S_A and S_B.
>
> But how to see the impact of both updates together, S_AB?

If the application lends itself to updates that can be handled by an
Operational Transform, would that help you ?

Early research: Jupiter collaboration system:
ftp://ftp.lambda.moo.mud.org/pub/MOO/papers/JupiterWin.ps

And of course, more recently ... Google Wave.

Note: I don't think this will solve the problem of "The Curious Case of
the Vanishing Scala Meeting" ... where there was no way to properly
reconcile S_A and S_B in that particular case :(

--
-O- cheers = /\ /\/ /) `/ =
--O -- http://www.geekscape.org --
OOO -- an...@geekscape.org -- http://twitter.com/geekscape --

[Ben Hutchison]

On Tue, Jun 26, 2012 at 3:37 PM, Andy Gelme <an...@geekscape.org> wrote:
> On 2012-06-26 15:26 , Ben Hutchison wrote:
>> Consider what happens when two threads A and B simultaneously want to
>> make updates to a shared data structure S.
>>
>> If immutable update techniques are used, each thread will create a
>> copy of S with their own changes only, ie S_A and S_B.
>>
>> But how to see the impact of both updates together, S_AB?
>
> If the application lends itself to updates that can be handled by an
> Operational Transform, would that help you ?

Andy's going hardcore! Thanks for the heads up, those Operational
Transforms are certainly out there. They make snapshot-able structures
look positively conservative, with their assumption that all writers
share the same consistent (if volatile) state.

If I understand correctly, Operational Transformations seem to relax
things in the Eventual Consistency direction, allowing writers to
update local copies of the state, providing some process is in place
to derive a global view of state that "converges" towards consistency.

-Ben

[Tony Morris]

On Jun 26, 2012 3:26 PM, "Ben Hutchison" <brhut...@gmail.com> wrote:
>
> Consider what happens when two threads A and B simultaneously want to
> make updates to a shared data structure S.
>
> If immutable update techniques are used, each thread will create a
> copy of S with their own changes only, ie S_A and S_B.
>
> But how to see the impact of both updates together, S_AB?

:m + Control.Arrow
:type (&&&, ***)

<snip nasty stuff>