PARALLEL DATA LAB 

PDL Abstract

Paxos Quorum Leases: Fast Reads Without Sacrificing Writes

Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-14-105. May 2014.

Iulian Moraru1, David G. Andersen1, Michael Kaminsky2

1Carnegie Mellon University
2 Intel Labs

http://www.pdl.cmu.edu/

This paper describes quorum leases, a new technique that allows Paxos-based systems to perform reads with high throughput and low latency. Quorum leases do not sacrifice consistency or write latency, and have only minimal impact on system availability. Quorum leases allow a majority of replicas to perform strongly consistent local reads, which substantially reduces read latency at those replicas (e.g., by two orders of magnitude in wide-area scenarios). Previous techniques for performing local reads in Paxos systems either (a) sacrifice consistency; (b) allow only one replica to read locally; or (c) decrease the availability of the system and increase the latency of updates by requiring all replicas to be notified synchronously. We describe the design of quorum leases and evaluate their benefits compared to previous approaches through an implementation running in five geo-distributed Amazon EC2 datacenters.

KEYWORDS: Distributed Consensus, Paxos

FULL TR: pdf