Joint NFF: UNC - Maintaining locality in a space-constrained file system

Donald Porter Michael Bender Rob Johnson Martin Farach-Colton Donald Porter (UNC), Michael Bender and Rob Johnson (Stony Brook) & Martin Farach-Colton (Rutgers) have teamed up on the collaborative research entitled "Maintaining locality in a space-constrained file system" It is increasingly common for file systems to run out of space, especially on mobile phones, tablets, and laptops.  Under space pressure, common file system data placement heuristics abandon any attempt to preserve locality, and do little, if anything, to recover data locality once space pressure is relieved, such as by deleting data or offloading data to the cloud. Donald Porter & team proposes developing a variant of a packed memory array (PMA) data structure, suitable for use in a local file system, that can preserve locality at an acceptable cost; make reasonable trade-offs under extreme space pressure; and recover locality after space pressure is relieved.  This work builds on the success of the BetrFS team in bridging the gap between data structure theory and file system practice, and includes both work to adapt this data structure to meet the constraints of a file system, as well as file system design work to leverage PMAs.  In this project, Donald Porter will evaluate the technique in both a simple ext2-style file system, as well as within their ongoing BetrFS write-optimized file system project.  If successful, this work will improve file system performance, not just under ideal circumstances, but also under adverse, yet increasingly common, conditions.