[erlang-questions] Problems Writing a Scalable Shared Data Structure

[Fuad Tabba]

Hi,

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).

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?

Thanks,
/Fuad
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080707/f506a11e/attachment.htm>