Performance-Optimal Read-Only Transactions

Distributed storage systems are a fundamental building block of today's web applications. Read-only transactions guarantee that the reads in such systems reflect a consistent view of data spread across shards. In this dissertation, we present the first set of results on the performance-guarantee tradeoff in the sharding dimension with a focus on read-only transactions. ? We first present the SNOW Theorem, which shows that there is a fundamental tradeoff between the latency and guarantees of read-only transactions. Leveraging the SNOW Theorem we improve two existing systems by exploring two ends of the latency-guarantee tradeoff. ? We then study the tradeoff between the performance and guarantees of read-only transactions by considering both latency and throughput. We prove the NOCS Theorem: no read-only transaction algorithm can achieve optimal performance in strictly serializable systems. We explain PORT, the first design whose read-only transactions are both performance-optimal and process-ordered serializable, i.e., the strongest possible consistency to date. We also show how the NOCS Theorem helps improve an existing system, Eiger, to make its read-only transactions performance-optimal. ? The major contributions of this work are new theoretical findings in the sharding dimension and a set of novel, optimal designs of read-only transactions.