Replication protocols in distributed storage systems are fundamentally constrained by the finite propagation speed of information, which necessitates trade-offs among performance metrics even in the absence of failures. We make two contributions toward a clearer understanding of such trade-offs. First, we introduce a probabilistic model of eventual consistency that captures precisely the relationship between the workload, the network latency, and the consistency observed by clients. Second, we propose a technique for adaptive tuning of the consistency-latency trade-off that is based partly on measurement and partly on mathematical modeling. Experiments demonstrate that our probabilistic model predicts the behavior of a practical storage system accurately for low levels of throughput, and that our tuning framework provides superior convergence compared to a state-of-the-art solution.

Today's online applications depend on fast storage and retrieval of up-to-date data at web scale. To meet this growing demand, the designers of distributed storage systems have devised a rich variety of data replication protocols, offering different trade-offs between consistency, latency, and availability. Understanding the sweet spot, and testing whether a system delivers a particular level of consistency, are challenging problems as consistency itself is difficult to reason about. This demo paper describes an interactive software tool for measuring and visualizing the consistency actually observed by client applications accessing a key-value storage system in real time. The tool can be used to evaluate performance trade-offs in a system with tunable consistency, or to verify the correctness of a storage system that guarantees certain forms of so-called “strong consistency”.