William Jannen

Type

Text

Type

Dissertation

Advisor

Bender, Michael A. | Porter, Donald E. | Johnson, Rob | Zadok, Erez | Kuenning, Geoff

Date

2017-12-01

Keywords

Computer science | B?-trees | File systems | Shingled magnetic recording | Storage | Write optimization

Department

Department of Computer Science

Language

en_US

Source

This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.

Identifier

http://hdl.handle.net/11401/78242

Publisher

The Graduate School, Stony Brook University: Stony Brook, NY.

Format

application/pdf

Abstract

Write-optimized dictionaries (WODs) are useful building blocks for storage systems. A good WOD implementation performs both small writes and large scans efficiently; transfers data in large enough units to utilize most of the device’s available bandwidth; and aggregates many logical operations into each I/O. A Bϵ-tree is an asymptotically optimal WOD with several implementations that exhibit these desirable qualities. By analyzing three uses of Bϵ-trees in storage systems, this dissertation shows that the conventional wisdom that storage system designs must choose either efficient sequential reads or efficient random writes is false. Bϵ-tree-based storage systems overcome this perceived trade-off by deferring and applying related operations in large batches, and as a result, Bϵ-tree-based systems have well-rounded performance profiles. This dissertation details SMRTr, a Bϵ-tree-based host-managed SMR translation layer that performs random write workloads an order of magnitude faster than firmware-based SMR translation layers; BetrFS, an in-kernel Bϵ-tree-based file system that performs small writes and directory scans orders of magnitude faster than traditional file systems and performs comparably on other microbenchmark and application workloads; and derange queries, a query model that has the potential to provide the same I/O savings for queries that write optimization provides for inserts. | 126 pages

Download

Share

COinS