Problems Writing a Scalable Shared Data Structure in Erlang

[This is adapted from a post I sent to erlang-questions.]

A while back I posted a question asking how to write a scalable shared data structure in Erlang; it can be anything really but I decided to go with a binary search tree (bst) since it's a simple data structure that should scale well with load (as long as it's balanced). I talked about that attempt in my previous post.

Anyway, I finished writing the code, which I'm assuming (read: hoping) is correct. :) What I found though is that it's not scaling at all. By that I mean that as the number of threads/processes accessing the bst increases, throughput doesn't improve by as much.

I've implemented the nodes as processes, and all operations on the tree are relayed to the node that needs to do something about it. The code for this implementation can be found here:-
http://www.cs.auckland.ac.nz/~fuad/cbst.erl

I did my tests on a Sun Fire V880 with 8 900-MHz UltraSPARC-III processors and 16 GBs of main memory; running Solaris 10 and Erlang (BEAM) 5.6.3.

My tests consisted of randomly creating and populating a tree that has a key range of 0-1000; and then performing at random (uniform distribution) either an insert(), delete() or a contains() done 100,000 times. I would vary the number of threads from 1 to 8, and the load (100,000 operations) would be divided by the number of processors available. I also performed the tests where the only operation performed is a contains() operation (designated by 1:0:0), or 8 contains() operations, 1 insert() and 1 delete() (8:1:1), or an equal mix of all three (1:1:1).

In a perfect world, 2 threads would do the job in half the time 1 thread would, but of course nothing is perfect. So as a baseline I performed another test whereby each thread would just call a function (repeated for a number of times) that does nothing but return true, to see how well that scales (in the graph: Best Scalability). This used the same functions to distribute the load, except that randOperation() would only return true rather than do anything useful.

Anyway, you can find the graph (where the results are normalized to the wall time for one processor) at:-
http://www.cs.auckland.ac.nz/~fuad/bst-scale.png (the lower the lines goes, better the scalability)

and the raw data (showing the wall time in ms) at:-
http://www.cs.auckland.ac.nz/~fuad/bst-scale.csv


As you can see, my data structure isn't scaling well at all regardless of the kind of workload it has. I would expect it to scale well since the tree should be kind of balanced. In C I would know how to write an implementation where at least contains() scales well; writing something where tree modification scales is a bit more difficult but should be doable. However, I am new to Erlang and I can't really reason about all the issues well enough to pull off a similar implementation.

In a nutshell my question is; what am I doing wrong? Is there a better way to have a place that stores shared data in a scalable manner?