I think I understand what you're saying here; but I still can't wrap my head around putting that into code. Is there similar code that you know of available online? The structure doesn't have to be a BST, just anything that demonstrates the idea of having a structure that stores lots persistent data to be viewed/modified by many processes and is scalable...<br clear="all">
<br>Thanks,<br>/Fuad
<br><br><div class="gmail_quote">On Wed, Jun 25, 2008 at 9:57 PM, Hynek Vychodil <<a href="mailto:vychodil.hynek@gmail.com">vychodil.hynek@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
You should store "persistent" state in server process. When you fall in performance problem you can partition this state in sub processes and server starts work as dispatcher. If dispatching is algorithmic you can spawn many dispatchers of course, but it usually performs better. You can repeat this fragmentation again and again on sub processes and you end up with process per node. For performance reasons there will be best solution some sort of hybrid structure. IMHO ets not performs fully scalable because I think there is only one "process" which can every time update it.<div>
<div></div><div class="Wj3C7c"><br>
<br><div class="gmail_quote">On Wed, Jun 25, 2008 at 11:46 AM, Fuad Tabba <<a href="mailto:fuad@cs.auckland.ac.nz" target="_blank">fuad@cs.auckland.ac.nz</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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...<br>
<br>Thanks Hynek,<br><font color="#888888">/Fuad</font><div><div></div><div><br><br><div class="gmail_quote">On Wed, Jun 25, 2008 at 9:40 PM, Hynek Vychodil <<a href="mailto:vychodil.hynek@gmail.com" target="_blank">vychodil.hynek@gmail.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br>I know, it sounds weird, but may be help you :-)<br>
<br><div class="gmail_quote">2008/6/25 Fuad Tabba <<a href="mailto:fuad@cs.auckland.ac.nz" target="_blank">fuad@cs.auckland.ac.nz</a>>:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div><div></div><div>
Hi,<br><br>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.<br>
<br>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.<br>
<br>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.<br>
<br>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?<br>
<br>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 :)<br><br>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.<br>
<br>The code for the tree itself is pretty much the same as that in Concurrent Programming in Erlang.<br><br>% No changes pending for the tree<br>parallelServer(Tree, stable, _) -><br> receive<br> {Requester, insert, Key} -><br>
Self = self(),<br> spawn(fun() -> insertProcessor(Self, Key, Tree) end),<br> parallelServer(Tree, changing, Requester);<br><br> {Requester, delete, Key} -><br> Self = self(),<br>
spawn(fun() -> deleteProcessor(Self, Key, Tree) end),<br> parallelServer(Tree, changing, Requester);<br><br> {Requester, contains, Key} -><br> spawn(fun() -> containsProcessor(Requester, Key, Tree) end),<br>
parallelServer(Tree, stable, void);<br><br> {Requester, dump} -><br> Requester ! Tree,<br> parallelServer(Tree, stable, void)<br> end;<br><br>% Tree is being modified<br>parallelServer(Tree, changing, Requester) -><br>
receive<br> {Requester, contains, Key} -><br> spawn(fun() -> containsProcessor(Requester, Key, Tree) end),<br> parallelServer(Tree, changing, Requester);<br><br> {Requester, dump} -><br>
Requester ! Tree,<br> parallelServer(Tree, changing, Requester);<br><br> {update, NewTree} -><br> Requester ! done,<br> parallelServer(NewTree, stable, void)<br> end.<br>
<br><br>% insertProcessor and deleteProcessor cannot notify the requester directly to<br>% ensure that parallelServer knows what the new tree is like first for<br>% consistency.<br><br>insertProcessor(Server, Key, Tree) -><br>
Server ! {update, insert(Key, Tree)}.<br><br><br>deleteProcessor(Server, Key, Tree) -><br> Server ! {update, delete(Key, Tree)}.<br><br><br>containsProcessor(Requester, Key, Tree) -><br> Requester ! contains(Key, Tree). % Can report it directly<br>
<br><br><br>Thanks !<br clear="all"><br>Cheers,<br><font color="#888888">/Fuad
</font><br></div></div>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br></blockquote></div><font color="#888888"><br><br clear="all"><br>-- <br>--Hynek (Pichi) Vychodil
</font></blockquote></div><br>
</div></div></blockquote></div><br><br clear="all"><br></div></div><font color="#888888">-- <br>--Hynek (Pichi) Vychodil
</font></blockquote></div><br>