Tracking Back References in a Write-Anywhere File System

DSpace/Manakin Repository

Tracking Back References in a Write-Anywhere File System

Citable link to this page


Title: Tracking Back References in a Write-Anywhere File System
Author: Macko, Peter; Seltzer, Margo I.; Smith, Keith A.

Note: Order does not necessarily reflect citation order of authors.

Citation: Macko, Peter, Margo Seltzer, and Keith A. Smith. 2010. Tracking back references in a write-anywhere file system. Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST'10): February 23-26, 2010, San Jose, CA.
Full Text & Related Files:
Abstract: Many file systems reorganize data on disk, for example to
defragment storage, shrink volumes, or migrate data between
different classes of storage. Advanced file system features such as snapshots, writable clones, and deduplication make these tasks complicated, as moving a single block may require finding and updating dozens, or even hundreds, of pointers to it.
We present Backlog, an efficient implementation of explicit back references, to address this problem. Back references are file system meta-data that map physical block numbers to the data objects that use them. We show that by using LSM-Trees and exploiting the write-anywhere behavior of modern file systems such as NetApp R WAFL R or btrfs, we can maintain back reference meta-data with minimal overhead (one extra disk I/O per 102 block operations) and provide excellent query performance for the common case of queries covering ranges of physically adjacent blocks.
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search