Problems Writing a Scalable Shared Data Structure

[Fuad Tabba-2]

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
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Robert Raschke-5]

Hi Fuad,

a shared data structure is going to be the major limiting factor of
your parallelisation. Are you aware of Amdahl's Law (e.g.,
http://home.wlu.edu/~whaleyt/classes/parallel/topics/amdahl.html)?

I must admit I have not read your code. But at least all the writes to
your shared data structure have to be serial in order to ensure its
integrity. So that is an immediate limiting factor. You cannot get
faster than all the serialised writes to your structure.

One of the easiest shared data structures you can use is a database.
It'll handle all the horrible details of transactions for you. In
Erlang, you can have a look at Mnesia for that.

Robby
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Fuad Tabba-2]

Thanks Robert,

Yes I am familiar with Amdahl's law. That said, it's not true that all writes need to be serialized; it's a binary tree, and unless the modifications happen to be to the same node, there's no reason why they need to be serialized.

A database would solve the problem kinda; but that's like using a steamroller to crack a nut. What I'm looking for a lightweight option that could temporarily store data shared between threads, and would scale well as the number of threads accessing/modifying this structure increases. I know how to solve this problem in C (writing a concurrent binary search tree that scales well), but since I'm new to Erlang I was unsuccessful trying to solve this problem in Erlang.

Thanks again,
/Fuad

On Mon, Jul 7, 2008 at 8:22 PM, Robert Raschke <rtrlists@...> wrote:

Hi Fuad,

a shared data structure is going to be the major limiting factor of
your parallelisation. Are you aware of Amdahl's Law (e.g.,
http://home.wlu.edu/~whaleyt/classes/parallel/topics/amdahl.html)?

I must admit I have not read your code. But at least all the writes to
your shared data structure have to be serial in order to ensure its
integrity. So that is an immediate limiting factor. You cannot get
faster than all the serialised writes to your structure.

One of the easiest shared data structures you can use is a database.
It'll handle all the horrible details of transactions for you. In
Erlang, you can have a look at Mnesia for that.

Robby
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Hynek Vychodil]

I peeped to your code briefly and it looks good. It can be wrote little simpler but looks correct for this proof purpose. Just to be sure, did you tried to start erl with different number of  schedulers e.g. +S parameter or only changed number of client threads?

I also think, your tree is may be too small.

2008/7/7 Fuad Tabba <fuad@...>:

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
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

--
--Hynek (Pichi) Vychodil
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Robert Raschke-5]

Hi Fuad,

On 7/7/08, Fuad Tabba <fuad@...> wrote:

> Thanks Robert,
>
> Yes I am familiar with Amdahl's law. That said, it's not true that all
> writes need to be serialized; it's a binary tree, and unless the
> modifications happen to be to the same node, there's no reason why they need
> to be serialized.
>
> A database would solve the problem kinda; but that's like using a
> steamroller to crack a nut. What I'm looking for a lightweight option that
> could temporarily store data shared between threads, and would scale well as
> the number of threads accessing/modifying this structure increases. I know
> how to solve this problem in C (writing a concurrent binary search tree that
> scales well), but since I'm new to Erlang I was unsuccessful trying to solve
> this problem in Erlang.

OK, I see.

So, if I read your code correctly, your rpcInserts() and rpcDeletes()
return quick, because your request is trickling down the tree on its
own. Its the rpcContains() that need to wait for a proper result.

It might be interesting to test the individual operations on their
own, and then combinations thereof. That might give a quicker insight
into what is causing the lack of speedup. My (uneducated) hunch is
that the rpcContains() calls are where your "threads" are getting
stuck (due in part to all the inserts and deletes clogging up the
tree).

Very unscientific, sorry.

Robby
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Fuad Tabba-2]

Thanks Robert and Hynek.

Hynek; playing around with the number of scheduler threads (+S) or asynchronous threads (surprisingly) does not significantly alter the results. As for the tree size, on average it should be around 500 nodes, assuming it's balanced this gives us a bst that's roughly 8 nodes deep. A tree this big should scale well with 8 processors. Moreover, I'd expect a tree this big to  scale almost perfectly going from 1 to 2 processors; especially if the ratio of lookups (contains()), that don't modify the data structure, is high. However, all I'm seeing is minor improvements. Moreover, increasing the size of the tree from 1000 to 10000 does improve scalability a bit, but not by all that much either.

Robert; I think you're referring to an earlier version of my code, where I don't wait for the results of an insert or a delete. The lastest one (http://www.cs.auckland.ac.nz/~fuad/cbst.erl), the final node inserted/deleted does inform the client whether the operation was successful or not. I can't confirm, but on a big enough tree stacking shouldn't be an issue since each node will probably only relay its request. But then again you're right, deeper analyses seems to be in order before I could make such statements with any kind of certainty.

That said, I feel that this solution doesn't seem to be the best one. I'm sure other Erlang programmers must have had to solve a similar problem, maintaining shared data between different threads in a scalable way.

Thanks again,
/Fuad

On Mon, Jul 7, 2008 at 9:58 PM, Robert Raschke <rtrlists@...> wrote:

Hi Fuad,

On 7/7/08, Fuad Tabba <fuad@...> wrote:
> Thanks Robert,
>
> Yes I am familiar with Amdahl's law. That said, it's not true that all
> writes need to be serialized; it's a binary tree, and unless the
> modifications happen to be to the same node, there's no reason why they need
> to be serialized.
>
> A database would solve the problem kinda; but that's like using a
> steamroller to crack a nut. What I'm looking for a lightweight option that
> could temporarily store data shared between threads, and would scale well as
> the number of threads accessing/modifying this structure increases. I know
> how to solve this problem in C (writing a concurrent binary search tree that
> scales well), but since I'm new to Erlang I was unsuccessful trying to solve
> this problem in Erlang.

OK, I see.

So, if I read your code correctly, your rpcInserts() and rpcDeletes()
return quick, because your request is trickling down the tree on its
own. Its the rpcContains() that need to wait for a proper result.

It might be interesting to test the individual operations on their
own, and then combinations thereof. That might give a quicker insight
into what is causing the lack of speedup. My (uneducated) hunch is
that the rpcContains() calls are where your "threads" are getting
stuck (due in part to all the inserts and deletes clogging up the
tree).

Very unscientific, sorry.

Robby
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Fuad Tabba-2]

Adding some observations; I've tried disabling smp all together (on the 8 core machine), and ironically the tests run more than twice as fast with smp disabled. It's probably a cache-locality thing, since the tests are small therefore all the data could easily fit in one processor's cache. The thing is though, I do not get the same effect using +S 1, performance doesn't vary all that much...

Another thing I've tried is I created a base for the tree; what I mean is that there's a known root, a known node to the left of the root and a known node that's to the right of the root. These nodes are always there. Whenever the insert/delete/contains functions are called, rather than send the request to the Root, they send it to one of those three depending on the value of the key. To make a long story short, this didn't help either (even going from 1 to 2 threads), which might imply that contention at the root isn't the bottleneck in my case.

/Fuad

On Tue, Jul 8, 2008 at 11:20 AM, Fuad Tabba <fuad@...> wrote:

Thanks Robert and Hynek.

Hynek; playing around with the number of scheduler threads (+S) or asynchronous threads (surprisingly) does not significantly alter the results. As for the tree size, on average it should be around 500 nodes, assuming it's balanced this gives us a bst that's roughly 8 nodes deep. A tree this big should scale well with 8 processors. Moreover, I'd expect a tree this big to  scale almost perfectly going from 1 to 2 processors; especially if the ratio of lookups (contains()), that don't modify the data structure, is high. However, all I'm seeing is minor improvements. Moreover, increasing the size of the tree from 1000 to 10000 does improve scalability a bit, but not by all that much either.

Robert; I think you're referring to an earlier version of my code, where I don't wait for the results of an insert or a delete. The lastest one (http://www.cs.auckland.ac.nz/~fuad/cbst.erl), the final node inserted/deleted does inform the client whether the operation was successful or not. I can't confirm, but on a big enough tree stacking shouldn't be an issue since each node will probably only relay its request. But then again you're right, deeper analyses seems to be in order before I could make such statements with any kind of certainty.

That said, I feel that this solution doesn't seem to be the best one. I'm sure other Erlang programmers must have had to solve a similar problem, maintaining shared data between different threads in a scalable way.

Thanks again,
/Fuad

On Mon, Jul 7, 2008 at 9:58 PM, Robert Raschke <rtrlists@...> wrote:

Hi Fuad,

On 7/7/08, Fuad Tabba <fuad@...> wrote:
> Thanks Robert,
>
> Yes I am familiar with Amdahl's law. That said, it's not true that all
> writes need to be serialized; it's a binary tree, and unless the
> modifications happen to be to the same node, there's no reason why they need
> to be serialized.
>
> A database would solve the problem kinda; but that's like using a
> steamroller to crack a nut. What I'm looking for a lightweight option that
> could temporarily store data shared between threads, and would scale well as
> the number of threads accessing/modifying this structure increases. I know
> how to solve this problem in C (writing a concurrent binary search tree that
> scales well), but since I'm new to Erlang I was unsuccessful trying to solve
> this problem in Erlang.

OK, I see.

So, if I read your code correctly, your rpcInserts() and rpcDeletes()
return quick, because your request is trickling down the tree on its
own. Its the rpcContains() that need to wait for a proper result.

It might be interesting to test the individual operations on their
own, and then combinations thereof. That might give a quicker insight
into what is causing the lack of speedup. My (uneducated) hunch is
that the rpcContains() calls are where your "threads" are getting
stuck (due in part to all the inserts and deletes clogging up the
tree).

Very unscientific, sorry.

Robby
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions

[Scott Lystig Fritchie]

Hi, Fuad.  Sorry this is a month and a half late.  Recently I came
across a tech report from HP Labs that sounded similar, at least in
intent, to the problem you were working on back in July.

Fuad Tabba <fuad@...> wrote:

ft> Another thing I've tried is I created a base for the tree; what I
ft> mean is that there's a known root, a known node to the left of the
ft> root and a known node that's to the right of the root.  [...]

This sounds like a small scale version of what the HP researchers did,
except they applied client-side caching for *all* internal B-tree nodes.

  A practical scalable distributed B-tree
  Aguilera and Golab
  HPL-2007-193

In the event that client caches are stale, the clients can figure that
out and get up-to-date copies of the internal nodes.

-Scott
_______________________________________________
erlang-questions mailing list
erlang-questions@...
http://www.erlang.org/mailman/listinfo/erlang-questions