- Previous message: Tarik Nesh-Nash: ""Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility" Review"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Storage Management and Caching in PAST: a large scale, persistent, peer to
peer system - Rowland and Druschel
The past system is a distributed global store designed for
strong persistence, high availability, scalability and security. The Pastry
algorithm routes clients to storage that is network close to them in
logarithmic time to the number of nodes in the system.
The file's publisher can specify the amount of redundancy at creation time.
The nodes are named with a SHA-1 hash of their 160 bit identifiers. Each
file is stored on the k nodes closest to its id and this is maintained on
membership changes. Pastry finds a file in steps where b is the number of
bits in the identifier and N the number of nodes in that network. This is a
very tight and surprising bound. The system is configured to work with l/2
neighbors and can guarantee delivery unless ceiling(l/2) neighbors are down.
Nearby neighbors are queried to find storage and Pastry can find the nearest
copy in 76% of all lookups. The nodes perform keep alive tests on their
neighbors and adjust these sets on node failure and addition.
PAST stores files by hashing the file id to a node and then giving it a
signed copy of the file. It then replicates this to the k nearest neighbors
and returns a storage receipt. The client then performs a similar hash to
access a file and the first node found searches the neighbors to return the
file. Security is implemented using smart cards and some randomization to
prevent malicious nodes from blocking searches.
The storage is balanced by replica and file diversion. If a node is becoming
too full, it can break the invariant of the k closest nodes storing the file
by passing it on to one of its leaf closets nodes. Files themselves can also
be passed on by changing the salt with which they are initially hashed to
find a node and neighbor set with more space.
The system was simulated to test the cost of replication, diversion, file
insertion, availability and other properties.
