freenet/fred-staging — pull request #211 by waldheinz (2014-03-24 12:44:36+00:00)
Title: Unified store

Because issue #210 already proposes using a new store layout for new nodes, I'd like to go one step further with the stores. The basic idea I'm following here goes like this:

* we want to maximize the success rate of our store
* because the store size is bounded, the best thing we can do is to make the key distribution in the store match the incoming request distribution

So I propose having a only a single store, which

* when not full, simply stores every block coming across the node
* when full, stores some block `B` with probability `P_store(B)`

So what should `P_store` look like? What I'm currently experimenting with is a normal distribution around the node's location, like this:

~~~java
final double p = Math.random() * Math.random();
final double twoDist = 2 * Location.distance(block.location(), node.location());
return twoDist < p;
~~~

This superimposes a distribution which prefers nearby keys atop the incoming request distribution. I'm not sure if this is really needed, as the routing already prefers giving us requests which are close to our location. But it might help in some degenerate situations.

An even simpler scheme, closer to the original idea would be to just store blocks with an fixed probability `P`. This would be a tuneable which determines how much the store prefers keeping old data over storing new data.

This unified store would serve the purposes of the current store and cache, because:

* there is a good chance that it contains data close to our node (because (a) data close to our location is more likely to be handled by our node and possibly (b) preferring locations close to out location by other means, like in the code above)
* there is a good chance that it contains data requested often (because the more often some data is requested, the more often it get's a chance to make it into the store)

I currently have two nodes running in a "shootout" for a little over a week:

* the "classic" node has a success rate of __1,1949%__
* 0,4978% for the CHK store
* 0,6971% for the CHK cache
* the "unified store" node has a success rate of __1,9228%__

That's an improvement of 60%, which seems promising.

PS: I'm fully aware that this pull request cannot be merged in it's current for, but I'd like to get some input on this, and maybe someone wants to play with it, too.