From: Prasanna Kumar Jayapal (prasak_at_winse.microsoft.com)
Date: Wed Mar 03 2004 - 17:30:55 PST
This paper (Storage management and Caching in PAST) discusses the design and evaluation of PAST, a large-scale peer-to-peer persistent storage utility. PAST's goal is to achieve load balance and high storage utilization in a distributed file system environment.
PAST is basically an application layer built on top of the pastry protocol. Pastry is responsible for providing the ability to quickly locate and easily retrieve the data stored in the network.
PAST system exposes to the clients operations like "Insert" - to insert a file, which takes in a parameter (k) to indicate number of replicas to be created, "Lookup"- to search a file and "Reclaim" - kind of delete the file. It depends to pastry to do its operations. Each node in PAST is assigned a 128-bit node identifier (called NodeId) by hashing (eg: SHA1) the node's public key. Files (to be inserted/searched/deleted) are also assigned a FileId (160-bit) and it is based on hashing the filename, owner's public key and randomly chosen salt. When presented with a FileId to Pastry, it effectively routes the message to a node that is numerically closest to the FileId, among all live pastry nodes. Each node maintains a routing table, a neighborhood set and a leaf set. Neighborhood set contains NodeIds and IP address of nodes that are close to the local node according to proximity metric. Routing table contains log N rows, each row containing nodes which share certain length of prefix with the current node. Leaf set contain the nodes which are numerically closer to the current node.
For a given FileId, the node first checks to see if it happens to fall within the range of the leaf set. If so, the message is directly forwarded to the closest leaf node. Else it forwards the message to the node in the routing table which shares a greater prefix length with the message key than the current node. This routing algorithm always converges, because each step takes the message closer to the actual node. Whenever a new node arrives, it sends a message to a node which it already knows, which would then propagate a join message to the given FileId. Table information are exchanged with the new nodes and all the tables would get eventually stabilized to reflect the new node.
PAST relies on smartcards to provide security and authentication. Each node in the system and each writing user must have a smartcard with an identifying public/private key pair. Smartcards, being physical objects, are totally external to the PAST system and I am not fully convinced that it is a good way to achieve security.
PAST primarily uses two mechanisms in Storage management to achieve load balance. First one is the "Replica diversion", which takes care of balancing the free storage space among the nodes in the leaf set. If a node cannot accommodate a copy locally, it sends the replica to other nodes in the same leaf set and enters an entry for the file in its table with a pointer to other node. Second one is the "File diversion", which balances the free space storage among different portions of the nodeId space. It sends the original file (and its k replicas) to another leaf set entirely. This is done by re-computing the FileId for the file using a different salt (which then results in a different leaf set).
Caching is done in PAST mainly to minimize the client access latencies, to maximize the query throughput and to balance the query load in the system. The nodes use the unused portion of their advertised disk space to cache files and these cached copies can be evicted and discarded at any time.
The authors present an elaborate experimental section where in they talk about different workloads and discuss optimal settings for the PAST system. I thought this section was very impressive, although I am not convinced that this system is "the solution" for an efficient storage system. I would like to see more comparisons with other protocols and other peer-to-peer file systems. But, overall this was an interesting paper.
This archive was generated by hypermail 2.1.6 : Wed Mar 03 2004 - 17:30:48 PST