Holistic Consistency Models for Faster Applications and Systems

Abstract

The correctness and performance of today’s applications are heavily influenced by the consistency models of their supporting services. Strong consistency models, like strict serializability and linearizability, restrict the space of possible service behaviors and in turn, simplify application programming. In exchange for their strong guarantees, however, strictly serializable and linearizable services incur worse performance than those with weaker consistency. But switching to such services can break applications. Consistency models thus offer a harsh trade-off between application correctness and service performance. Despite impacting both applications and services, most existing work on consistency models has taken a limited view. A long line of research sought to weaken the consistency of common services in an effort to improve their performance, largely without considering the impacts of weaker consistency on application correctness. A separate line of work investigated the impacts of weaker consistency on applications. In contrast, this dissertation takes a holistic approach, considering applications and services together to develop better consistency models. First, we introduce Regular Sequential Serializability (RSS) and Regular Sequential Consistency (RSC). They are respectively as strong as strict serializability and linearizability for applications: we prove any application that is correct when using a strictly serializable (respectively linearizable) service is also correct when using an RSS (RSC) service. And yet, they enable new, better-performing services, thus circumventing the correctness-performance trade-off. To demonstrate the latter, we design, implement, and evaluate variants of two systems, Spanner-RSS and Gryff-RSC. The variants achieve lower tail read latency than their existing counterparts. Second, we introduce Multi-dispatch Linearizability (MD-Linearizability), which relaxes linearizability’s assumption that a client is sequential and instead explicitly allows it to issue multiple operations concurrently. This can help reduce an application’s end-to-end latency. To this end, we present Ellis, the first multi-shard system to guarantee MD-Linearizability, and show it reduces end-to-end application latency by up to 75%. Importantly, we also describe how to rewrite applications built atop linearizable services into ones that interact with comparable MD-Linearizable services. Following the transformation ensures the new applications behave identically to the originals, so programmers can reap MD-Linearizability’s performance benefits without worrying about breaking their applications.