Over the years, different meanings have been associated to the word consistency in the distributed systems community. While in the ’80s “consistency” typically meant strong consistency, later defined also as linearizability, in recent years, with the advent of highly available and scalable systems, the notion of “consistency” has been at the same time both weakened and blurred. In this paper we aim to fill the void in literature, by providing a structured and comprehensive overview of different consistency notions that appeared in distributed systems, and in particular storage systems research, in the last four decades. We overview more than 50 different consistency notions, ranging from linearizability to eventual and weak consistency, defining precisely many of these, in particular where the previous definitions were ambiguous. We further provide a partial order among different consistency predicates, ordering them by their semantic “strength”, which we believe will reveal useful in future research. Finally, we map the consistency semantics to different practical systems and research prototypes. The scope of this paper is restricted to non-transactional semantics, i.e., those that apply to single storage object operations. As such, our paper complements the existing surveys done in the context of transactional, database consistency semantics. ar X iv :1 51 2. 00 16 8v 4 [ cs .D C ] 1 2 A pr 2 01 6
* Distributed storage systems In more recent years, researchers have been proposing categorizations of the most influential consistency models for modern storage systems. Namely, Tanenbaum.Steen:07 proposed the client-centric versus data-centric classification, while Bermbach.Kuhlenkamp:13 , expanded such classification and provided descriptions for the most popular models. While practical and instrumental in attaining a good understanding of the consistency spectrum, these works propose informal treatments based on a simple dichotomous categorization which falls short of capturing some important consistency semantics. With this survey we aim at improving over these works, as we adopt a formal model based on first-order logic predicates and graph theory. We derived this model from the one proposed in @cite_38 , which we modified and expanded in order to enable the definition of a wider and richer range of consistency semantics. Moreover, whereas Burckhardt:14 focuses mostly on session and eventual semantics, we cover a broader ground including more than 50 different consistency semantics.
@cite_38
1530638770 2585325056 2087536500 12688243
Large-scale key-value storage systems sacrifice consistency in the interest of dependability (i.e., partition-tolerance and availability), as well as performance (i.e., latency). Such systems provide eventual consistency, which--to this point--has been difficult to quantify in real systems. Given the many implementations and deployments of eventually-consistent systems (e.g., NoSQL systems), attempts have been made to measure this consistency empirically, but they suffer from important drawbacks. For example, state-of-the art consistency benchmarks exercise the system only in restricted ways and disrupt the workload, which limits their accuracy. In this paper, we take the position that a consistency benchmark should paint a comprehensive picture of the relationship between the storage system under consideration, the workload, the pattern of failures, and the consistency observed by clients. To illustrate our point, we first survey prior efforts to quantify eventual consistency. We then present a benchmarking technique that overcomes the shortcomings of existing techniques to measure the consistency observed by clients as they execute the workload under consideration. This method is versatile and minimally disruptive to the system under test. As a proof of concept, we demonstrate this tool on Cassandra. Cloud storage services and NoSQL systems, which have recently found widespread adoption, typically offer only "Eventual Consistency", a rather weak guarantee covering a broad range of potential data consistency behavior. The degree of actual (in-)consistency as a service quality, however, is always unknown. To avoid cost of opportunity or actual costs, resulting data inconsistencies have to be resolved within the application layer. Without detailed knowledge on consistency behavior, though, inconsistency handling is inefficient and for some kinds of inconsistency outright impossible. Furthermore, due to the way consistency behavior impacts applications, consistency as a system quality should also be considered during the selection and deployment optimization of cloud storage offerings and NoSQL systems. This as well as studying the impact of system design decisions on consistency behavior requires the necessary means to analyze consistency behavior of eventually consistent storage systems. In this work, we present four main contributions to address the problems outlined above: First, we develop novel consistency metrics which describe consistency behavior for all kinds of consistency, in a precise way, without needless aggregation, and in way that is meaningful to application or storage system developers as well as systems researchers. Second, we identify key influence factors on consistency behavior and combine them into a model of a storage system. We then present two distinct approaches, which predict consistency behavior based on simulations on top of this model. Third, we also present a set of system benchmarking approaches to accurately determine consistency behavior of eventually consistent distributed storage systems via experiments with actually deployed systems. Results of both simulation and system benchmarking are expressed using our novel set of consistency metrics. Fourth, building on 15 extensive experiments with actual systems and a multitude of simulation runs, we demonstrate how inconsistencies can be handled more efficiently leveraging these results. For this purpose, we describe based on a use case how inconsistencies can be resolved in application engineering. We also develop a new middleware-based approach which adds additional consistency guarantees externally to the eventually consistent storage system, thus, alleviating complexity for application developers. Replicated storage for large Web services faces a trade-off between stronger forms of consistency and higher performance properties. Stronger consistency prevents anomalies, i.e., unexpected behavior visible to users, and reduces programming complexity. There is much recent work on improving the performance properties of systems with stronger consistency, yet the flip-side of this trade-off remains elusively hard to quantify. To the best of our knowledge, no prior work does so for a large, production Web service. We use measurement and analysis of requests to Facebook's TAO system to quantify how often anomalies happen in practice, i.e., when results returned by eventually consistent TAO differ from what is allowed by stronger consistency models. For instance, our analysis shows that 0.0004 of reads to vertices would return different results in a linearizable system. This in turn gives insight into the benefits of stronger consistency; 0.0004 of reads are potential anomalies that a linearizable system would prevent. We directly study local consistency models---i.e., those we can analyze using requests to a sample of objects---and use the relationships between models to infer bounds on the others. We also describe a practical consistency monitoring system that tracks p-consistency, a new consistency metric ideally suited for health monitoring. In addition, we give insight into the increased programming complexity of weaker consistency by discussing bugs our monitoring uncovered, and anti-patterns we teach developers to avoid. We present the first scalable, geo-replicated storage system that guarantees low latency, offers a rich data model, and provides "stronger" semantics. Namely, all client requests are satisfied in the local datacenter in which they arise; the system efficiently supports useful data model abstractions such as column families and counter columns; and clients can access data in a causally-consistent fashion with read-only and write-only transactional support, even for keys spread across many servers. The primary contributions of this work are enabling scalable causal consistency for the complex columnfamily data model, as well as novel, non-blocking algorithms for both read-only and write-only transactions. Our evaluation shows that our system, Eiger, achieves low latency (single-ms), has throughput competitive with eventually-consistent and non-transactional Cassandra (less than 7 overhead for one of Facebook's real-world workloads), and scales out to large clusters almost linearly (averaging 96 increases up to 128 server clusters).