Building Efficient and Secure Storage Systems with Write-Optimized Dictionaries

This dissertation investigates the performance benefits of Write-Optimized Dictionaries (WODs) to file systems on commodity SSDs and integrity protection for key-value stores. WODs accelerate random writes and updates by aggregating small changes into larger, sequential writes for file systems on hard disk drives (HDDs). For instance, BetrFS outperforms conventional file systems on an HDD by orders of magnitude in the best cases and has comparable performance in the worst cases (e.g., sequential IOs). In short, the literature in file systems research shows that write-optimization can effectively yield a strict performance improvement over traditional file systems on HDDs. However,for file systems on SSDs, despite the existence of file systems tailored for commodity SSDs and over a decade of research into flash file systems, our evaluation shows that no single Linux file system performs consistently well on an SSD across different workloads. One of the contributions of this dissertation is to investigate whether the benefits of WODs on HDDs can translate to SSDs. Concretely, this dissertation demonstrates that one can construct a single, general-purpose file system for commodity SSDs and HDDs. The dissertation introduces four groups of key techniques to improve SSD performance for a file system built on a WOD, as demonstrated in the BetrFS file system. Our file system also shows performance benefits over existing file systems for file search, recursive grep, and random update, even on NVMe devices. In addition to performance, the security of storage systems is a growing concern in research and practice. In cloud computing, end users outsource data storage to systems owned and administered by cloud service providers. When data owners outsource storage to a third party, the owners may be concerned about the additional risk of data tampering or corruption. On the other hand, the cloud service provider wishes to demonstrate that they return the same data to the client as initially stored. However, most of the existing techniques for integrity protection suffer from large performance penalties. This dissertation demonstrates that write-optimization and routing filters can improve the performance of authenticated key-value stores. This dissertation presents a new authenticated key-value store, named Auth-BεKV. Auth-BεKV indexes data with an STBε-tree, a write-optimized B-tree variant. Auth-BεKV has strong integrity guarantees (i.e., authenticity, correctness, freshness). This dissertation contributes four techniques to ensure the performance and integrity of Auth-BεKV. First, to ensure the authenticity, completeness, and freshness of a user’s data, we implement a Merklized Bε-tree-based key-value store (KVS), in which we authenticate all pointers (i.e., disk addresses) so that the query process authenticates the results transparently. Second, to mitigate the concurrency bottleneck of the Merkle-tree authentication scheme, we leverage copy-on-write to create a consistent snapshot of Auth-BεKV so that writes do not block reads. Third, we demonstrate that adding authentication to routing filters can reduce the total number of cryptographic operationsand the number of IOs to read data pages needed to authenticate query results. Fourth, in refactoring SplinterDB, a representative KVS codebase, to use a trusted execution environment (TEE), we demonstrate that the caching layer is a natural division point for partitioning SplinterDB into trusted (inside TEE) and untrusted (outside TEE) components. The dissertation evaluates the performance of Auth-BεKV with YCSB benchmarks on physical machines with SGX1 and SGX2 hardware. We also compare the performance of Auth-BεKV with a recent, state-of-the-art authenticated KVS namedTWEEZER. The evaluation results show Auth-BεKV performs strictly better than TWEEZER for YCSB load, workloads A, B, C, D, and F, by up to 2.3x; the only exception is workload E, for which Auth-BεKV is 1.9x slower than TWEEZER. The evaluation results also show that Auth-BεKV scales better than TWEEZER when we increase the number of threads. For the YCSB load workload, Auth-BεKV’s throughput increases by 28% and 11% when we increase the number of threads from 1 to 2 and 2 to 4, respectively. We also find that routing filters improve query performance ofAuth-BKV by up to 1.6x and 30% on SGX1 and SGX2, respectively.