On 01/21/2010 10:35 AM, alex wrote:
> Bear with me, please, my understanding of freenet is not deep. What are you
> referring to with DHT here? My guess would be that you refer to the keyspace
> that freenet manages (CHK --> Value).
Yes, i was just using it as a "catch-all" term. There are actually two DHTs,
the CHK space and the SSK space.
> If that's so, I already was of the idea that the b-tree is a construction
> done with some clever usage of freenet keys, that of course the node is
> unaware of (just like frost boards, the WoT, etc). My question is more if
> the insertion/access is done through one single USK subspace, or several, or
> what.
The nodes of the b-tree are CHKs, but you can access it through a SSK pointer
which also acts as an endorsement ("I, the owner of this SSK, like this b-tree
well enough to point to it").
> Since CHKs are immutable, I guess that the question makes not much sense for
> the leaves of the tree: they're what they are, with its CHK. Internal nodes,
> in the end, are also some data pointing to children that has an unique CHK.
>
> My guess is that one interesting property of the b-tree for freenet is that
> changes in its content require relatively few node modifications. In regular
> in-memory trees, changes stop "locally", since you can modify a node content
> without altering the pointers to it from the parent node. In freenet, given
> the direct relation from data to its reference (the CHK), I don't grasp how
> this doesn't propagate all the way to the root. Or it does and we are
> talking of an additional logarithmic cost anyway (in the number of keys to
> be modified)?
Yes, the data structure is "copy-on-write", so if you update a node, you also
have to update its parent etc. all the way up to the root. We alleviate this by
doing writes only in bulk.
> I hope I'm not making nonsensical questions, if that's the case just tell me
> :) Anyway, if there's some documentation around on how this works, this is
> very interesting stuff to me.
There is a lot of javadocs in plugin-Library but unfortunately i didn't get
around to making a "grand design" document. I expect i'll get around to it
eventually, but wrt the b-trees thing, we've covered most of the basics here
already :p
> Another guess is that, given a "snapshot" of the tree, with few insertions
> you can give a new root (CHK or USK, whatever) that points to the updated
> data. Basically, "forking" the tree is a cheap operation. I'm on the right
> track? This would answer my question four paragraphs back.
Yes
> And the ice in the cake is that searching any of these trees is made in
> logarithmic count of key retrievals, right?
Yes :)
X
