From: Jeff Duzak (jduzak_at_exchange.microsoft.com)
Date: Tue Mar 02 2004 - 22:47:09 PST
This paper describes CFS, a peer-to-peer filesystem. CFS is very
similar to PAST. The primary differences are (1) the Chord lookup
scheme is used instead of Pastry, (2) files are not stored intact, but
rather are broken into blocks and organized in a manner analagous to a
filesystem, and (3) there is no explicit revocation mechanism, but
rather files expire after some time period if they are not renewed.
The Chord lookup scheme is very similar to Pastry with Pastry's
configuration parameter b set to 1. In Pastry, in order to route a
request, a node looks in its table of other nodes for a node with more
significant digits in common with the target id. In Chord, each node
has a table of other nodes with addresses up to 2^n distant, for each
value of n. In order to route a request, the Chord node looks for the
node in its table that is closest to the target id. Both Chord and
Pastry with b = 1 halve the distance to the target id with each node
hop. Therefore, both systems arrive at the node closest to the target
id in log N time, where N is the size of the network.
CFS is implemented in three layers. The lowest layer is Chord, which is
in charge of routing. The next layer up is DHash, which is in charge of
storing and requesting blocks. Finally, the filesystem translates a
user's request for a file into the appropriate block requests, which it
passes along to DHash. Once the blocks are returned from DHash, the
filesystem reconstructs the file.
The paper describes a method for routine lookups in order to reduce
network latency. The method depends on the idea that the network
latency for a call from node A to node C, for example, should correlate
somewhat with the total latency for calls from node A to node B and from
node B to node C. I found this a bit hard to buy, but the performance
testing reported in the paper shows that the idea works.
This archive was generated by hypermail 2.1.6 : Tue Mar 02 2004 - 22:47:10 PST