Proceedings of the 2nd international Petascale Data Storage Workshop (PDSW '07) held in conjunction with Supercomputing '07. November 11, 2007, Reno, NV.
Swapnil V. Patil, Garth A. Gibson, Sam Lang, Milo Polte
Petascale Data Storage Institute
Carnegie Mellon University
Pittsburgh, PA 15213
http://www.pdl.cmu.edu/
http://www.pdsi-scidac.org/
Traditionally file system designs have envisioned directories as a means of organizing files for human viewing; that is, directories typically contain a few tens to thousands of files. Users of large, fast file systems have begun to put millions of files into single directories, for example, as simple databases. Furthermore, large-scale applications running on clusters with tens to hundreds of thousands of cores can burstily create files using all compute cores, amassing bursts of hundreds of thousands of creates or more.
In this paper, we revisit data-structures to build large file system directories that contain millions to billions of files and to quickly grow the number of files when many nodes are creating concurrently. We extend classic ideas of efficient resizeable hash-tables and inconsistent client hints to a highly concurrent distributed directory service. Our techniques use a dense bitmap encoding to indicate which of the possibly created hash partitions really exist, to allow all partitions to split independently, and to correct stale client hints with multiple changes per update.
We implement our technique, Giga+, using the FUSE user-level file system API layered on Linux ext3. We measured our prototype on a 100-node cluster using the UCAR Metarates benchmark for concurrently creating a total of 12 million files in a single directory. In a configuration of 32 servers, Giga+ delivers scalable throughput with a peak of 8,369 file creates/second, comparable to or better than the best current file system implementations.
KEYWORDS: scalability, weak consistency, directories, concurrency
FULL PAPER: pdf