| 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 Bepsilon-tree is an asymptotically optimal WOD with several implementations that exhibit these desirable qualities.;By analyzing three uses of Bepsilon-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. Bepsilon-tree-based storage systems overcome this perceived trade-off by deferring and applying related operations in large batches, and as a result, Bepsilon-tree-based systems have well-rounded performance profiles.;This dissertation details SMRTr, a Bepsilon-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 Bepsilon-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. |
