Eventual consistency

{{Short description|Consistency model used in distributed computing to achieve high availability}}

Eventual consistency is a consistency model used in distributed computing to achieve high availability. Put simply: if no new updates are made to a given data item, eventually all accesses to that item will return the last updated value.{{Cite journal | last1 = Vogels | first1 = W. | author-link = Werner Vogels| doi = 10.1145/1435417.1435432 | title = Eventually consistent | journal = Communications of the ACM | volume = 52 | pages = 40–44 | year = 2009 | doi-access = free }} Eventual consistency, also called optimistic replication,{{Cite journal | last1 = Vogels | first1 = W. | author-link1 = Werner Vogels| title = Eventually Consistent | doi = 10.1145/1466443.1466448 | journal = Queue | volume = 6 | issue = 6 | pages = 14–19 | year = 2008 | doi-access = free }} is widely deployed in distributed systems and has origins in early mobile computing projects.{{Cite book | last1 = Terry | first1 = D. B. | last2 = Theimer | first2 = M. M. | last3 = Petersen | first3 = K. | last4 = Demers | first4 = A. J. | last5 = Spreitzer | first5 = M. J. | last6 = Hauser | first6 = C. H. | chapter = Managing update conflicts in Bayou, a weakly connected replicated storage system | doi = 10.1145/224056.224070 | title = Proceedings of the fifteenth ACM symposium on Operating systems principles - SOSP '95 | pages = 172 | year = 1995 | isbn = 978-0897917155 | citeseerx = 10.1.1.12.7323 | s2cid = 7834967 }} A system that has achieved eventual consistency is often said to have converged, or achieved replica convergence.{{Cite journal | last1 = Petersen | first1 = K. | last2 = Spreitzer | first2 = M. J. | last3 = Terry | first3 = D. B. | last4 = Theimer | first4 = M. M. | last5 = Demers | first5 = A. J. | title = Flexible update propagation for weakly consistent replication | doi = 10.1145/269005.266711 | journal = ACM SIGOPS Operating Systems Review | volume = 31 | issue = 5 | pages = 288 | year = 1997 | citeseerx = 10.1.1.17.555 }} Eventual consistency is a weak guarantee – most stronger models, like linearizability, are trivially eventually consistent.

Eventually-consistent services are often classified as providing BASE semantics (basically-available, soft-state, eventual consistency), in contrast to traditional ACID (atomicity, consistency, isolation, durability).{{Cite journal | last1 = Pritchett | first1 = D. | title = Base: An Acid Alternative | doi = 10.1145/1394127.1394128 | journal = Queue | volume = 6 | issue = 3 | pages = 48–55 | year = 2008 | doi-access = free }}{{Cite journal | last1 = Bailis | first1 = P. | last2 = Ghodsi | first2 = A. | doi = 10.1145/2460276.2462076 | title = Eventual Consistency Today: Limitations, Extensions, and Beyond | journal = Queue | volume = 11 | issue = 3 | pages = 20 | year = 2013 | doi-access = free }} In chemistry, a base is the opposite of an acid, which helps in remembering the acronym.{{cite web |last1=Roe |first1=Charles |title=ACID vs. BASE: The Shifting pH of Database Transaction Processing |url=https://www.dataversity.net/acid-vs-base-the-shifting-ph-of-database-transaction-processing/# |website=DATAVERSITY |date=March 2012 |publisher=DATAVERSITY Education, LLC |access-date=29 August 2019}} According to the same resource, these are the rough definitions of each term in BASE:

Basically available: reading and writing operations are available as much as possible (using all nodes of a database cluster), but might not be consistent (the write might not persist after conflicts are reconciled, and the read might not get the latest write)
Soft-state: without consistency guarantees, after some amount of time, we only have some probability of knowing the state, since it might not yet have converged
Eventually consistent: If we execute some writes and then the system functions long enough, we can know the state of the data; any further reads of that data item will return the same value

Eventual consistency faces criticismH{{Citation|author=Yaniv Pessach|title=Distributed Storage|date=2013|edition=Distributed Storage: Concepts, Algorithms, and Implementations|publisher=Amazon|quote=Systems using Eventual Consistency result in decreased system load and increased system availability but result in increased cognitive complexity for users and developers|ol=25423189M}} for adding complexity to distributed software applications. This complexity arises because eventual consistency provides only a liveness guarantee (ensuring reads eventually return the same value) without safety guarantees—allowing any intermediate value before convergence. Application developers find this challenging because it differs from single-threaded programming, where variables reliably return their assigned values immediately. With weak consistency guarantees, developers must carefully consider these limitations, as incorrect assumptions about consistency levels can lead to subtle bugs that only surface during network failures or high concurrency.{{Cite book |last=Kleppmann |first=Martin |title=Designing data-intensive applications: the big ideas behind reliable, scalable, and maintainable systems |date=2017 |publisher=O'Reilly |isbn=978-1449373320 |edition=1 |location=Beijing Boston Farnham Sebastopol Tokyo}}

Conflict resolution

In order to ensure replica convergence, a system must reconcile differences between multiple copies of distributed data. This consists of two parts:

exchanging versions or updates of data between servers (often known as anti-entropy);{{Cite book | last1 = Demers | first1 = A. | last2 = Greene | first2 = D. | last3 = Hauser | first3 = C. | last4 = Irish | first4 = W. | last5 = Larson | first5 = J. | doi = 10.1145/41840.41841 | chapter = Epidemic algorithms for replicated database maintenance | title = Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87 | pages = 1 | year = 1987 | isbn = 978-0-89791-239-6| s2cid = 1889203 }} and
choosing an appropriate final state when concurrent updates have occurred, called reconciliation.

The most appropriate approach to reconciliation depends on the application. A widespread approach is "last writer wins". Another is to invoke a user-specified conflict handler. Timestamps and vector clocks are often used to detect concurrency between updates. Some people use "first writer wins" in situations where "last writer wins" is unacceptable.Rockford Lhotka.

[http://www.lhotka.net/Article.aspx?id=890d3e3c-8a49-486c-ae48-a44e7e1f7844 "Concurrency techniques"] {{Webarchive|url=https://web.archive.org/web/20180511145619/http://www.lhotka.net/Article.aspx?id=890d3e3c-8a49-486c-ae48-a44e7e1f7844 |date=2018-05-11 }}.

2003.

Reconciliation of concurrent writes must occur sometime before the next read, and can be scheduled at different instants:

{{cite web

| access-date = 2011-03-23

| author = Olivier Mallassi

| date = 2010-06-09

| publisher = OCTO Talks!

| title = Let's play with Cassandra… (Part 1/3)

| quote = Of course, at a given time, chances are high that each node has its own version of the data. Conflict resolution is made during the read requests (called read-repair) and the current version of Cassandra does not provide a Vector Clock conflict resolution mechanisms [sic] (should be available in the version 0.7). Conflict resolution is so based on timestamp (the one set when you insert the row or the column): the higher timestamp win[s] and the node you are reading the data [from] is responsible for that. This is an important point because the timestamp is specified by the client, at the moment the column is inserted. Thus, all Cassandra clients’ [sic] need to be synchronized...

| url = http://blog.octo.com/en/nosql-lets-play-with-cassandra-part-13/}}

Read repair: The correction is done when a read finds an inconsistency. This slows down the read operation.
Write repair: The correction takes place during a write operation, slowing down the write operation.
Asynchronous repair: The correction is not part of a read or write operation.

Strong eventual consistency

Whereas eventual consistency is only a liveness guarantee (updates will be observed eventually), strong eventual consistency (SEC) adds the safety guarantee that any two nodes that have received the same (unordered) set of updates will be in the same state. If, furthermore, the system is monotonic, the application will never suffer rollbacks. A common approach to ensure SEC is conflict-free replicated data types.{{cite journal| last1 = Shapiro| first1 = Marc| last2 = Preguiça| first2 = Nuno| first3 = Carlos| last3 = Baquero| first4 = Marek| last4 = Zawirski| date = 2011-10-10| title = Conflict-free replicated data types| journal = SSS'11 Proceedings of the 13th International Conference on Stabilization, Safety, and the Security of Distributed Systems| publisher = Springer-Verlag Berlin, Heidelberg| pages = 386–400}}

Eventual consistency

Conflict resolution

Strong eventual consistency

See also

References

Further reading