[erlang-questions] Writing a Concurrent Binary Search Tree Data Structure in Erlang

[Hynek Vychodil]

Because there is no shared state between processes in Erlang, I would start
think about process per tree node, not process per action as usual in
classic shared memory (for example C) implementations.
I know, it sounds weird, but may be help you :-)

2008/6/25 Fuad Tabba <fuad@REDACTED>:

> Hi,
>
> I'm trying to write a concurrent Binary Search Tree (BST) in Erlang with
> the operations insert/delete/contains. My goal is for multiple processes to
> be able to concurrently modify this structure and query it correctly.
>
> My problem is, I can't think of a way to take advantage of the inherent
> parallelism in the BST structure. BSTs should be easy to parallelize, since
> different inserts/deletes of nodes from the tree could be in completely
> different branches. In C for example, it's not hard to write a nonblocking
> implementation (lock-free) where adding nodes to the tree can happen
> concurrently (unless there's a conflict) using Compare and Exchange (CAS).
> Adding concurrency with deleting nodes is a bit more challenging but should
> still be doable.
>
> That said, I've only managed to think of an Erlang implementation that is
> capable of running contains() in parallel with an insert or delete. However,
> I cannot think of a way where I could have the server thread somehow
> distribute its updates if they are to nonconflicting branches. I feel like
> the solution should be a simple, recursive one, and that the answer is on
> the tip of my brain so to speak :) But I'm still baffled.
>
> My question is this; I can reason about shared memory objects and how
> concurrent accesses should be, either using locks or for the simpler cases
> using atomic instructions such as CAS. However, I'm finding it difficult to
> do that with Erlang/functional languages in general. I did a google search,
> couldn't really find any examples of what I'm looking for. Any tips or
> pointers?
>
> Here's what my code looks like (the whole thing is attached to this email).
> Apologies in advance for the quality of my code, still learning :)
>
> The basic idea, to be able to have contains() run in parallel with
> insertions and deletions, is that whenever the server gets a request to add
> something or remove something from the tree, its continue applying
> contains() to the old version until it receives the modifications back.
>
> The code for the tree itself is pretty much the same as that in Concurrent
> Programming in Erlang.
>
> % No changes pending for the tree
> parallelServer(Tree, stable, _) ->
>     receive
>         {Requester, insert, Key} ->
>             Self = self(),
>             spawn(fun() -> insertProcessor(Self, Key, Tree) end),
>             parallelServer(Tree, changing, Requester);
>
>         {Requester, delete, Key} ->
>             Self = self(),
>             spawn(fun() -> deleteProcessor(Self, Key, Tree) end),
>             parallelServer(Tree, changing, Requester);
>
>         {Requester, contains, Key} ->
>             spawn(fun() -> containsProcessor(Requester, Key, Tree) end),
>             parallelServer(Tree, stable, void);
>
>         {Requester, dump} ->
>             Requester ! Tree,
>             parallelServer(Tree, stable, void)
>     end;
>
> % Tree is being modified
> parallelServer(Tree, changing, Requester) ->
>     receive
>         {Requester, contains, Key} ->
>             spawn(fun() -> containsProcessor(Requester, Key, Tree) end),
>             parallelServer(Tree, changing, Requester);
>
>         {Requester, dump} ->
>             Requester ! Tree,
>             parallelServer(Tree, changing, Requester);
>
>         {update, NewTree} ->
>             Requester ! done,
>             parallelServer(NewTree, stable, void)
>     end.
>
>
> % insertProcessor and deleteProcessor cannot notify the requester directly
> to
> % ensure that parallelServer knows what the new tree is like first for
> % consistency.
>
> insertProcessor(Server, Key, Tree) ->
>     Server ! {update, insert(Key, Tree)}.
>
>
> deleteProcessor(Server, Key, Tree) ->
>     Server ! {update, delete(Key, Tree)}.
>
>
> containsProcessor(Requester, Key, Tree) ->
>     Requester ! contains(Key, Tree). % Can report it directly
>
>
>
> Thanks !
>
> Cheers,
> /Fuad
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>



-- 
--Hynek (Pichi) Vychodil
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080625/2549115f/attachment.htm>