Concurrent and Shared Binary Search Tree in Erlang

So, wanting to work a bit more with Erlang, and to try and get a better understanding of how to write parallel programs in Erlang, I decided to write a concurrent Binary Search Tree (a basic one, not balanced) and see how that goes. I though a binary search tree would be a good candidate since operations normally affect only a small subset of the tree, so quite a bit of concurrency should be doable. Of course the more balanced the tree the better the expected concurrency.

Since I'm new to Erlang, I started by trying to parallelize a simple Erlang implementation, similar to the one in Concurrent Programming in Erlang. This implementation is essentially a tuple, and adding or removing nodes consists of modifying the tuple.

What I did was create a process that hold the current state of the BST tuple, and waits for messages that tells it what to do. It could either insert, delete or lookup a node in the tree. Of course, this basic implementation would process such requests sequentially.

I think I managed to successfully parallize the operation, since I would spawn a new process to search through the tree, but I couldn't figure out a way to parallelize insert or delete. Spawning a new processes to modify the tree in the same manner wouldn't work since I need all the modifications to be consolidated somewhere. But at least this implementation should be able to have multiple lookups running in parallel with at most one insert/delete operation.

Here's a link to the code I've mentioned above.

* * *

So I asked the Erlang questions mailing list what the best way to go about solving the problem would be, and the answer I got is that I need to think of each node as a process in itself. While this isn't how you'd tack such a problem in C, in Erlang processes are quite cheap.

So each node is a spawned instance of the following function (sorry about the lack of proper indentation):-

% Maintains the state of the node
nodeState(Node) ->
receive
{contains, Key, Requester} ->
contains(Key, Node, Requester),
nodeState(Node);

{insert, Key} ->
nodeState(insert(Key, Node));

{delete, Key} ->
nodeState(delete(Key, Node));

{node, Requester} ->
Requester ! Node,
nodeState(Node);

{dump, Requester} ->
dump(Node, Requester),
nodeState(Node)
end.

Whenever a node gets a request, it either processes it itself if it has the correct key, or it passes it on down the tree.

The complete code is here.

Implementing contains and insert were pretty straightforward since data flows in only one direction (down the tree). delete was a bit more challenging, since when deleting a node that has children, you need to find a good replacement for it and delete the replacement (i.e. replace it with the maximal node in it's left subtree and then delete that node instead). This means that messages can be exchanged in the opposite direction, which might create some potential for deadlock.

That said, I have to admit that it was significantly easier writing this kind of algorithm in Erlang as it would have been in C; that is of couse assuming that my code is correct.

A note about the interface (the rpcs for insert, delete, contains); no acknowledgement is sent after an insert or a delete. contains of course waits until a response is received. I hope that this implementation is correct in the sense that if something is inserted, then contains is called the response should be positive unless another process deleted what was inserted and vice versa.

Now what's still remaining is performing a sanity test to see whether my implementation is correct (Dijkstra: testing can be used to show the presence of bugs, but never to show their absence). But that's what I can do for the time being.

I also need to figure out a way to write a benchmark to test performance. This is going to be tricky since processes do not acknowledge that operations have been completed. I could add that, but by adding that I would be adding more overhead....

So, what I like about this implementation is that it was relatively easy to reason about; what I don't like is the overhead of a process per node. I recall reading that an Erlang process uses up something in the neighbourhood of 200 bytes; so if the data stored per process is small, this overhead is substantial.

Next step; write a concurrent Red-Black tree!