{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:17:02Z","timestamp":1759133822143,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,8,31]],"date-time":"2018-08-31T00:00:00Z","timestamp":1535673600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000098","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["CA198952-01"],"award-info":[{"award-number":["CA198952-01"]}],"id":[{"id":"10.13039\/100000098","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1409238, CNS-1408782, CNS-1408695, CNS-1405641, IIS 1251137, IIS-1247750, CCF 1617618, CCF 1439084, CCF-1314547,"],"award-info":[{"award-number":["CNS-1409238, CNS-1408782, CNS-1408695, CNS-1405641, IIS 1251137, IIS-1247750, CCF 1617618, CCF 1439084, CCF-1314547,"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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 efficient 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.<\/jats:p>\n          <jats:p>\n            We implemented this mechanism in B\n            <jats:sup>\u03b5<\/jats:sup>\n            -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.\n          <\/jats:p>","DOI":"10.1145\/3241061","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T13:18:59Z","timestamp":1543324739000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient Directory Mutations in a Full-Path-Indexed File System"],"prefix":"10.1145","volume":"14","author":[{"given":"Yang","family":"Zhan","sequence":"first","affiliation":[{"name":"The University of North Carolina at Chapel Hill, Chapel Hill, NC"}]},{"given":"Yizheng","family":"Jiao","sequence":"additional","affiliation":[{"name":"The University of North Carolina at Chapel Hill, Chapel Hill, NC"}]},{"given":"Donald E.","family":"Porter","sequence":"additional","affiliation":[{"name":"The University of North Carolina at Chapel Hill, Chapel Hill, NC"}]},{"given":"Alex","family":"Conway","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}]},{"given":"Eric","family":"Knorr","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}]},{"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}]},{"given":"Michael A.","family":"Bender","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]},{"given":"Jun","family":"Yuan","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY"}]},{"given":"William","family":"Jannen","sequence":"additional","affiliation":[{"name":"Williams College, Williamstown, MA"}]},{"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, CA"}]}],"member":"320","published-online":{"date-parts":[[2018,11,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687592"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872854"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064193"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740801"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"volume-title":"An introduction to B-trees and write-optimization. :login","year":"2015","author":"Bender Michael A.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Brodal Gerth St\u00f8lting","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","year":"2003","author":"Brodal Gerth Stolting","key":"e_1_2_1_9_1"},{"volume-title":"Westbrook","year":"2000","author":"Buchsbaum Adam L.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168854"},{"volume-title":"File systems fated for senescence? Nonsense, says science&excl","author":"Conway Alex","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1457838.1457895"},{"volume-title":"Proceedings of the 4th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201912)","author":"Esmet John","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","unstructured":"Facebook Inc.RocksDB. Retrieved April 26 2018 from http:\/\/rocksdb.org\/.  Facebook Inc.RocksDB. Retrieved April 26 2018 from http:\/\/rocksdb.org\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794369"},{"key":"e_1_2_1_18_1","unstructured":"FUSE. Retrieved April 26 2018 from https:\/\/github.com\/libfuse\/libfuse.  FUSE. Retrieved April 26 2018 from https:\/\/github.com\/libfuse\/libfuse."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945450"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_1_21_1","unstructured":"Google Inc.LevelDB. Retrieved April 26 2018 from https:\/\/github.com\/google\/leveldb.  Google Inc.LevelDB. Retrieved April 26 2018 from https:\/\/github.com\/google\/leveldb."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247564"},{"volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Jannen William","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2798729"},{"volume-title":"Proceedings of the 12th USENIX Conference on File and Storage Technologies (FAST\u201914)","year":"2014","author":"Johnson Charles","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168839"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151374.1151375"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485732.2485741"},{"volume-title":"Retrieved","year":"2018","author":"Linux","key":"e_1_2_1_30_1"},{"volume-title":"Retrieved","year":"2004","author":"Lovelace Mary","key":"e_1_2_1_31_1"},{"volume-title":"Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST\u201916)","author":"Lu Lanyue","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","volume-title":"Ottowa Linux Symposium (OLS)","volume":"2","author":"Mathur Avantika","year":"2007"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/989.990"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3127479.3127486"},{"volume-title":"Enhance your apps with file system transactions. MSDN Magazine (July","year":"2007","author":"Olson Jason","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","unstructured":"ZFS on Linux. Retrieved April 26 2018 from http:\/\/zfsonlinux.org\/.  ZFS on Linux. Retrieved April 26 2018 from http:\/\/zfsonlinux.org\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"volume-title":"Proceedings of the 2016 USENIX Conference on USENIX Annual Technical Conference (USENIX ATC\u201916)","year":"2016","author":"Papagiannis Anastasios","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31838-5_14"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629591"},{"volume-title":"Proceedings of the 2013 USENIX Conference on Annual Technical Conference (USENIX ATC\u201913)","year":"2013","author":"Ren Kai","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501620.2501623"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453914"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591272.2591275"},{"volume-title":"Proceedings of the 7th Conference on File and Storage Technologies (FAST\u201909)","author":"Spillane Richard P.","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1268299.1268300"},{"volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Thomson Alexander","key":"e_1_2_1_49_1"},{"key":"e_1_2_1_50_1","unstructured":"Tokutek Inc.TokuDB. Retrieved April 26 2018 from https:\/\/github.com\/Tokutek\/ft-index.  Tokutek Inc.TokuDB. Retrieved April 26 2018 from https:\/\/github.com\/Tokutek\/ft-index."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815405"},{"volume-title":"Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI\u201906)","year":"2006","author":"Weil Sage A.","key":"e_1_2_1_52_1"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2004.22"},{"volume-title":"Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201915)","year":"2015","author":"Wu Xingbo","key":"e_1_2_1_54_1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3032969"},{"volume-title":"Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST\u201916)","author":"Yuan Jun","key":"e_1_2_1_56_1"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/1298455.1298481"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3241061","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3241061","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3241061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:46Z","timestamp":1750207426000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3241061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,31]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3241061"],"URL":"https:\/\/doi.org\/10.1145\/3241061","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2018,8,31]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}