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!

Full Red Black Tree Implementation in Erlang

In my previous post I talked about Red Black trees and how to implement them in Erlang. I only dealt with inserting into a Red Black tree. I finally got around to finalizing this implementation by adding the code for deleting from a Red Black tree.

There were some challenges; the ones that stand out the most are:-

• The algorithm for deleting is not an easy one, and I actually had to understand it this time (as opposed to just rewriting pseudocode into C as when I did the C implementation). This link, that Robert Virding pointed out to me was really helpful in this respect.
  
• The fact that variables are immutable in Erlang, and the whole functional programming way of thinking is still not coming naturally to me. I guess I need to practice more.
• Erlang doesn't allow functions as guards, even if those functions don't have side effects. You'd think it would be trivial to actually have the compiler check for that or for the VM to throw an exception at runtime if it encounters a guard with side-effects; but apparently that's completely not allowed for historical reasons or something. Fortunately with help from the erlang questions list, I was able to get around this limitation by using macros.

With all of that being said, and with the learning curve involved, I found it significantly easier to write what seems to be a correct implementation of a Red Black Tree in Erlang than it was in C. The code is significantly more concise and easier to read/understand I believe.

For those who are interested, here's a link to my full Erlang Red Black Tree implementation. As I mentioned before, I'm still new to Erlang, so I would greatly appreciate any comments you might have on my code; whether it's related to style or the actual algorithm. That said, I know a couple of places where my code could be optimised, but I was aiming for clarity. But if you have any suggestions that could improve both, then I'd like to know about them.

Now off to do some work...

Erlang and Red-black Trees

Update: Full RBTree implementation in Erlang.

Recently I've been trying to pick up Erlang, a message-based concurrent functional programming language. The main difficulty I'm having is wrapping my head around the whole functional thing and dealing with single assignment (immutable data). I thought what better way to try and get it than to implement my favourite data structure - the venerable Red-black tree!

The RB Tree is a self-balancing binary tree, and all the colouring and rebalancing business can be a bit tricky. To give you an idea, my C implementation is roughly around 1000 lines of code (including comments/spaces).

To be honest, it hasn't been easy. Fortunately, I stumbled upon this entry which mentioned a functional implementation in Haskell. With my good friend Nick's help in understanding the Haskell bit, I managed to whip up an Erlang implementation in less than an hour and less than 50 lines! One caveat - so far it only inserts, but I'll be working on it more.

To understand this implementation, make sure to refer to the paper I mentioned above first, since the algorithm is described there.

So, here's the code:-

-module(rbtree).
-export([insert/3, test/0]).

% Node description:-
% {Key, Value, Color, Left, Right}

balance({Kz, Vz, b, {Ky, Vy, r, {Kx, Vx, r, A, B}, C}, D}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

balance({Kz, Vz, b, {Kx, Vx, r, A, {Ky, Vy, r, B, C}}, D}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

balance({Kx, Vx, b, A, {Kz, Vz, r, {Ky, Vy, r, B, C}, D}}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

balance({Kx, Vx, b, A, {Ky, Vy, r, B, {Kz, Vz, r, C, D}}}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

% No rebalancing needed
balance({Key, Value, Color, Left, Right}) ->
{Key, Value, Color, Left, Right}.

% Inserting into an empty tree
ins(Key, Value, {}) ->
{Key, Value, r, {}, {}};

% Collision with an existing key : leave it as it is
ins(Key, _, {Key, Value, Color, Left, Right}) ->
{Key, Value, Color, Left, Right};

ins(Key, Value, {Key2, Value2, Color, Left, Right}) when Key <>
balance({Key2, Value2, Color, ins(Key, Value, Left), Right});

ins(Key, Value, {Key2, Value2, Color, Left, Right}) when Key > Key2 ->
balance({Key2, Value2, Color, Left, ins(Key, Value, Right)}).

% Ensures that the root is black
makeBlack({Key, Value, _, Left, Right}) ->
{Key, Value, b, Left, Right}.

insert(Key, Value, Tree) ->
makeBlack(ins(Key, Value, Tree)).