Skip to Content.
Sympa Menu

bluesky - Re: Content based addressing

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: hal AT finney.org
  • To: bluesky AT franklin.oit.unc.edu
  • Subject: Re: Content based addressing
  • Date: Thu, 15 Feb 2001 20:29:35 -0800


Wei writes:
> I think there are fundamental problems with the Freenet content
> location system. I posted these concerns to freenet-chat, but never got
> a meaningful response. I'll copy it here:
>
> Freenet's search algorithm is characterized as "steepest-ascent hill
> climbing search with backtracking". I wonder how it deals with landscapes
> that doesn't have a single hill top. There seem to be two problems.

Let me briefly describe the Freenet search algorithm for the benefit of
other readers (if there are any). More detail is available at
http://freenet.sourceforge.net/index.php?page=icsi-revised.

Each document is identified by a key, typically a 160 bit hash.
Each node stores a set of documents which have been sent to it and
requested for storage. Along with the document it of course stores the
key, but also the address of another node which has or had the document.
(Over time, documents may be expunged to save space, but the key and
node address are preserved for a longer period to help with finding the
document on another node.)

The search algorithm is simple. When the node receives a request for a
given key, if it has the corresponding document it returns it. If not,
it looks through its data store for the closest key to the requested one,
and forwards the request to the corresponding node. Then, when the data
streams back (if it is found) the node saves a copy and sets the node
pointer to the node from which the data came.

The same routing algorithm is used for insertion as for data requests.
When the data is inserted it is stored on this node and then the data
store is searched for the closest key, and the data is forwarded to
that node to be stored there as well. Both requests and inserts have
"hops to live" (HTL) values which tell how far the forwarding should go,
and are expected to be roughly logarithmic in the size of the network.

The effect of these two algorithms is that nodes will tend to acquire
data which is close together in hash. Nodes which hold documents with
similar hashes will be likely to point to each other. The network will
self-organize into nodes with a degree of specialization (in hash value).
Popular data will spread out over more nodes.

> First is multiple hill tops, or multiple nodes that specialize in nearby
> keys. When you insert a document with a key near these keys, the insert
> request will be attracted to one of these nodes. But requests for the
> document may be initially attracted to the other nodes. Is there some
> provision for quickly going back downhill when the document you're
> looking for is not at the local hilltop, instead of wasting time
> searching the slopes of the hill?

No, there is no such provision. What happens is that if a request is
forwarded to the nearest "uphill" node, it may send back a rejection
saying that it has already seen that request (and in fact is still
waiting for a response from when it forwarded it). In that case the
node falls back to the second-best key, and so on. This will tend to
move us around the slopes and not jump over to another hill.

However I think the hill-climbing metaphor is not that accurate
for Freenet. What is the height? It is how close the node is to the
desired key. This means that there is not just one fitness landscape,
there is a virtually infinite set of them, one for every possible key.
Furthermore the distance between nodes in this model depends on what
connections they have to each other with respect to keys close to the
target, which may also be different for different keys. Therefore as we
move through the key space, the network's metric and height will change
dramatically. No simple picture of hills and valleys will capture the
essence of the Freenet data distribution.

The network is also likely to be high dimensional, with each node having
a number of connections to other nodes with close keys. This increases
connectivity and helps hill climbing to work better.

My feeling is that the dynamic process of inserting and fetching
documents, combined with the variation in the shape and topology of the
fitness landscape with different keys, will facilitate connectivity and
help different parts of the landscape to be informed about each other.
If there is a split in the network at a certain key value, looking at
it with a different key value will see those regions as being connected.
Activity on the keys intermediate between the two will help bridge
the two parts.

Ultimately we need either a mathematical analysis or more detailed
simulation results to know whether segmentation becomes a problem in
practice.

> The second problem is a flat landscape. Suppose you insert a document
> with a key near the key of a very popular document that is cached
> everywhere. The insert request and subsequent data requests for this
> document will then be routed randomly and probably no one will be able to
> find it.

This could be a problem, but it is an extreme case. If there are other
documents in the network closer to the inserted one than the widespread
document, eventually the insertion path will divert towards the other
documents, after thrashing around randomly for a while. It may be
necessary to have a large HTL value for the insertion to work well in
this case.

If this does become a problem, it might be possible to introduce some new
routing rules to break the symmetry. This is done for now in the initial
state, which is conceptually perfectly flat. To fix this, initial nodes
get random values assigned to them so as to promote self-sorting behavior
from the beginning. Perhaps when a single document is found everywhere
and we are just following it around, some similar rule could be added.

Hal




Archive powered by MHonArc 2.6.24.

Top of Page