A Scalable Red Black Tree Based Structure with Hashing

I've been trying to figure out the best way to write scalable shared data structures in Erlang. In my last post, I talked about writing one based on regular binary search trees. That implementation would create a number of processes, and divide a pre-determined key range onto those processes.

That implementation suffered from a few problems; first of all, the keys had to be integers, the range of those integers had to be known. It performed well and scaled well as long as the keys were well distributed; but if they weren't well distributed, and in the real world they probably aren't, then things would get ugly.

Fortunately the solution to all these problems turned out to be quite simple. In that last post, autrepack commented that I should use a hash (I'm glad I have a blog), and that's what I did.

No need to know the range of the keys, I just create as many processes as needed and whenever a request comes along, I hash its key using erlang:phash2 and based on that I decide which bucket (process) needs to handle it.

This automatically solved three problems; I no longer am limited to integers as key values, I don't need to predetermine the range of my keys, and load should be balanced (since I'm assuming that phash2 is a good hash function). Three birds in one stone - merci autrepack!

Also, to balance things a bit more, instead of using normal binary search trees, the data structure is now based on red black trees. The cool thing about them is that key keep the tree kinda balanced and offer worst-case scenario performance guarantees.

The result of my work can be found at:-
http://www.cs.auckland.ac.nz/~fuad/hrb.erl

I haven't tested this yet, but I imagine that under the tests I already have it would perform slightly worse than before - that's because my previous tests used uniformly generated random numbers, which pretty much guarantees that everything is well distributed - therefore the overhead of using a red black tree isn't utilized. However, I believe than under real world load this should perform better

The cool thing is, this really was easy to write compared to implementing a similar solution in other languages.