Efficient directory mutations in a full-path-indexed file system

Yang Zhan, Yizheng Jiao, Donald E. Porter, Alex Conway, Eric Knorr, Martin Farach-Colton, Michael A. Bender, Jun Yuan, William Jannen, Rob Johnson

    Research output: Contribution to journalArticlepeer-review


    Full-path indexing can improve I/O eficiency for workloads that operate on data organized using traditional, hierarchical directories, because data is placed on persistent storage in scan order. Prior results indicate, however, that renames in a local file system with full-path indexing are prohibitively expensive. This article shows how to use full-path indexing in a file system to realize fast directory scans, writes, and renames. The article introduces a range-rename mechanism for eficient key-space changes in a write-optimized dictionary. This mechanism is encapsulated in the key-value Application Programming Interface (API) and simplifies the overall file system design. We implemented this mechanism in B ϵ -trees File System (BetrFS), an in-kernel, local file system for Linux. This new version, BetrFS 0.4, performs recursive greps 1.5x faster and random writes 1.2x faster than BetrFS 0.3, but renames are competitive with indirection-based file systems for a range of sizes. BetrFS 0.4 outperforms BetrFS 0.3, as well as traditional file systems, such as ext4, Extents File System (XFS), and Z File System (ZFS), across a variety of workloads.

    Original languageEnglish (US)
    Article number22
    JournalACM Transactions on Storage
    Issue number3
    StatePublished - Nov 2018

    ASJC Scopus subject areas

    • Hardware and Architecture


    Dive into the research topics of 'Efficient directory mutations in a full-path-indexed file system'. Together they form a unique fingerprint.

    Cite this