PBS: Better understanding latency vs. consistency trade-offs in Voldemort

[Peter Bailis]

We recently completed research at UC Berkeley that's highly relevant to Voldemort configurations and are interested in feedback from the Voldemort user community. In brief, eventually consistent replication (which is often faster than strongly consistent replication) provides no *guarantees* about the recency of data returned. However, we can accurately provide *expectations* of data recency. Our work, which we call Probabilistically Bounded Staleness (PBS), helps make these predictions. Using PBS, we can optimize the trade-off between latency and consistency provided by partial quorums (R+W <= N) by predicting both with high accuracy.

Currently, in quorum-replicated data stores like Voldemort, there's no good way to predict the benefit of using partial quorums or the consistency they provide. By measuring the latency of messaging and using modeling techniques we've developed, Voldemort can do better by describing the probability of consistency according to both time and versions (see an interactive demo in your browser at http://cs.berkeley.edu/~pbailis/projects/pbs/#demo).

Thus far, in addition to general Dynamo-style replication analysis, we've developed a patch for Cassandra that performs the required latency profiling and are interested in potentially working to integrate PBS analysis into additional data stores like Riak, which can also benefit from PBS analysis (see code and documentation at https://github.com/pbailis/cassandra-pbs). These techniques are broadly applicable: for example, in our Technical Report (http://cs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-4.pdf), in addition to examining Cassandra and Riak, we predicted the latency-consistency trade-offs of a production Voldemort deployment at LinkedIn (thanks again to Alex Feinberg!). The sample analysis script we've written for Cassandra will work for Voldemort as well given the proper input format.

We'd welcome any feedback or questions you might have.

Thanks!

Peter Bailis

UC Berkeley

More info:

DataStax wrote a great explanatory blog post on PBS last week: http://www.datastax.com/dev/blog/your-ideal-performance-consistency-tradeoff

You can read an overview of PBS on our project page: http://cs.berkeley.edu/~pbailis/projects/pbs/

You can also read our technical report on PBS that has more technical detail: http://cs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-4.pdf

Daniel Abadi recently blogged about the latency-consistency trade-off: http://dbmsmusings.blogspot.com/2011/12/replication-and-latency-consistency.html

Henry Robinson (Cloudera) also blogged about PBS: http://the-paper-trail.org/blog/?p=334