The Full Path to Full-Path Indexing


Yang Zhan, The University of North Carolina at Chapel Hill; Alex Conway, Rutgers University; Yizheng Jiao, The University of North Carolina at Chapel Hill; Eric Knorr, Rutgers University; Michael A. Bender, Stony Brook University; Martin Farach-Colton, Rutgers University; William Jannen, Williams College; Rob Johnson, VMware Research; Donald E. Porter, The University of North Carolina at Chapel Hill; Jun Yuan, Stony Brook University


This paper shows how to use full-path indexing in a file system to realize fast directory scans, writes, and renames. Prior results indicated that renames are prohibitively expensive in full-path indexing.

The paper introduces a range-rename mechanism for efficient key-space changes in a write-optimized dictionary. This mechanism is encapsulated in the key-value-store API, and simplifies the overall design of the file system.

We implemented this mechanism in ArborFS, an extension of the BetrFS in-kernel, local file system for Linux. For instance, ArborFS performs recursive greps 1.5x faster and random writes 1.2x faster than BetrFS, but renames are competitive with standard, indirection-based file systems for a range of sizes. ArborFS outperforms relative-path file systems such as BetrFS as well as traditional file systems such as ext4, xfs and zfs across a variety of workloads.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {210540,
author = {Yang Zhan and Alex Conway and Yizheng Jiao and Eric Knorr and Michael A. Bender and Martin Farach-Colton and William Jannen and Rob Johnson and Donald E. Porter and Jun Yuan},
title = {The Full Path to Full-Path Indexing},
booktitle = {16th {USENIX} Conference on File and Storage Technologies ({FAST} 18)},
year = {2018},
isbn = {978-1-931971-42-3},
address = {Oakland, CA},
pages = {123--138},
url = {},
publisher = {{USENIX} Association},