Ximin Luo wrote:
(stuff)
Ok, thanks for the clarifications. I think I have all the answers I needed
right now :)
> 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
