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

[Fuad Tabba]

I understand that, but what if that structure (binary tree) is needed to
store some sort of persistent state for all processes to see - reservations
table for example or something like that. I know there's ETS, but what I'm
trying to do is understand the basics...

Thanks Hynek,
/Fuad

On Wed, Jun 25, 2008 at 9:40 PM, Hynek Vychodil <vychodil.hynek@REDACTED>
wrote:

> 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/a75a972f/attachment.htm>