Optimizing System I/Os with Bϵ Trees
Optimizing System I/Os with Bϵ Trees
| dc.identifier.uri | http://hdl.handle.net/11401/78242 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.type | Dissertation | |
| dcterms.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. | |
| dcterms.available | 2018-06-21T13:38:41Z | |
| dcterms.contributor | Porter, Donald E. | en_US |
| dcterms.contributor | Bender, Michael A. | en_US |
| dcterms.contributor | Johnson, Rob | en_US |
| dcterms.contributor | Zadok, Erez | en_US |
| dcterms.contributor | Kuenning, Geoff | en_US |
| dcterms.creator | Jannen, William | |
| dcterms.dateAccepted | 2018-06-21T13:38:41Z | |
| dcterms.dateSubmitted | 2018-06-21T13:38:41Z | |
| dcterms.description | Department of Computer Science | en_US |
| dcterms.extent | 126 pg. | en_US |
| dcterms.format | Monograph | |
| dcterms.format | Application/PDF | en_US |
| dcterms.identifier | http://hdl.handle.net/11401/78242 | |
| dcterms.issued | 2017-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2018-06-21T13:38:41Z (GMT). No. of bitstreams: 1 Jannen_grad.sunysb_0771E_13590.pdf: 786854 bytes, checksum: 30fb5b17f59159ed29c9b7129f87a459 (MD5) Previous issue date: 12 | en |
| dcterms.subject | Computer science | |
| dcterms.subject | B?-trees | |
| dcterms.subject | File systems | |
| dcterms.subject | Shingled magnetic recording | |
| dcterms.subject | Storage | |
| dcterms.subject | Write optimization | |
| dcterms.title | Optimizing System I/Os with Bϵ Trees | |
| dcterms.title | Optimizing System I/Os with Bϵ Trees | |
| dcterms.type | Dissertation |
