  NoSQL storage systems are used extensively by web applications and provide an
attractive alternative to conventional databases when the need for scalability
outweighs the need for transactions. Several of these systems provide
quorum-based replication and present the application developer with a choice of
multiple client-side "consistency levels" that determine the number of replicas
accessed by reads and writes, which in turn affects both latency and the
consistency observed by the client application. Since using a fixed combination
of read and write consistency levels for a given application provides only a
limited number of discrete options, we investigate techniques that allow more
fine-grained tuning of the consistency-latency trade-off, as may be required to
support consistency-based service level agreements (SLAs). We propose a novel
technique called \emph{continuous partial quorums} (CPQ) that assigns the
consistency level on a per-operation basis by choosing randomly between two
options, such as eventual and strong consistency, with a tunable probability.
We evaluate our technique experimentally using Apache Cassandra and demonstrate
that it outperforms an alternative tuning technique that delays operations
artificially.
