The full path to full-path indexing

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

The full path to full-path indexing

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Full-path indexing can improve I/O efficiency 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 paper shows how to use full-path indexing in a file system to realize fast directory scans, writes, and renames. 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 API and simplifies the overall file system design. We implemented this mechanism in 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, XFS, and ZFS, across a variety of workloads.

Original language	English (US)
Title of host publication	Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018
Publisher	USENIX Association
Pages	123-138
Number of pages	16
ISBN (Electronic)	9781931971423
State	Published - 2018
Event	16th USENIX Conference on File and Storage Technologies, FAST 2018 - Oakland, United States Duration: Feb 12 2018 → Feb 15 2018

Publication series

Name	Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018

Conference

Conference	16th USENIX Conference on File and Storage Technologies, FAST 2018
Country/Territory	United States
City	Oakland
Period	2/12/18 → 2/15/18

ASJC Scopus subject areas

Hardware and Architecture
Software
Computer Networks and Communications

Cite this

Zhan, Y., Conway, A., Jiao, Y., Knorr, E., Bender, M. A., Farach-Colton, M., Jannen, W., Johnson, R., Porter, D. E., & Yuan, J. (2018). The full path to full-path indexing. In Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018 (pp. 123-138). (Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018). USENIX Association.

The full path to full-path indexing. / Zhan, Yang; Conway, Alex; Jiao, Yizheng et al.
Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018. USENIX Association, 2018. p. 123-138 (Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Zhan, Y, Conway, A, Jiao, Y, Knorr, E, Bender, MA, Farach-Colton, M, Jannen, W, Johnson, R, Porter, DE & Yuan, J 2018, The full path to full-path indexing. in Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018. Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018, USENIX Association, pp. 123-138, 16th USENIX Conference on File and Storage Technologies, FAST 2018, Oakland, United States, 2/12/18.

@inproceedings{2e4b9f7d6a264acbb0911870124cf988,

title = "The full path to full-path indexing",

abstract = "Full-path indexing can improve I/O efficiency 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 paper shows how to use full-path indexing in a file system to realize fast directory scans, writes, and renames. 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 API and simplifies the overall file system design. We implemented this mechanism in 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, XFS, and ZFS, across a variety of workloads.",

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

year = "2018",

language = "English (US)",

series = "Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018",

publisher = "USENIX Association",

pages = "123--138",

booktitle = "Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018",

note = "16th USENIX Conference on File and Storage Technologies, FAST 2018 ; Conference date: 12-02-2018 Through 15-02-2018",

}

TY - GEN

T1 - The full path to full-path indexing

AU - Zhan, Yang

AU - Conway, Alex

AU - Jiao, Yizheng

AU - Knorr, Eric

AU - Bender, Michael A.

AU - Farach-Colton, Martin

AU - Jannen, William

AU - Johnson, Rob

AU - Porter, Donald E.

AU - Yuan, Jun

PY - 2018

Y1 - 2018

N2 - Full-path indexing can improve I/O efficiency 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 paper shows how to use full-path indexing in a file system to realize fast directory scans, writes, and renames. 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 API and simplifies the overall file system design. We implemented this mechanism in 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, XFS, and ZFS, across a variety of workloads.

AB - Full-path indexing can improve I/O efficiency 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 paper shows how to use full-path indexing in a file system to realize fast directory scans, writes, and renames. 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 API and simplifies the overall file system design. We implemented this mechanism in 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, XFS, and ZFS, across a variety of workloads.

UR - http://www.scopus.com/inward/record.url?scp=85055378329&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85055378329&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85055378329

T3 - Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018

SP - 123

EP - 138

BT - Proceedings of the 16th USENIX Conference on File and Storage Technologies, FAST 2018

PB - USENIX Association

T2 - 16th USENIX Conference on File and Storage Technologies, FAST 2018

Y2 - 12 February 2018 through 15 February 2018

ER -

The full path to full-path indexing

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this