Peer-to-peer storage networks aim at aggregating the unused storage in today's resource-abundant computers to form a large, shared storage space. To lay over the extremely variant machines, networks and administrative organizations, peer-to-peer storage networks must be aware of the capabilities of the constituent components to leverage their resources, performance and reliability. This paper reports our design of such a peer-to-peer storage network, called Tornado. Tornado is built on top of two concepts. The first is the virtual home concept, which adds an extra level of abstraction between data and storage nodes to mask the underlying heterogeneity. The second concept is the classification of the storage nodes into "good" and "bad" according to their static and dynamic capabilities. Only "good" peers can host virtual homes, whereby introducing quality of services into the storage network. We evaluate Tornado via simulation. The results show that Tornado is comparable with previous systems, where each route takes at most [log N] hops, anew node takes [log N]2 messages to join, and the memory overhead in each node is O(log N). Moreover, Tornado is able to provide comprehensive services with features scattered in different systems previously, and takes account of and exploits the heterogeneity in the underlying network environment.