Eventual consistency

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Eventual consistency is a consistency model used in distributed computing that informally guarantees that, if no new updates are made to a given data item, eventually all accesses to that item will return the last updated value.[1] Eventual consistency is widely deployed in distributed systems, often under the moniker of optimistic replication,[2] and has origins in early mobile computing projects.[3] A system that has achieved eventual consistency is often said to have converged, or achieved replica convergence.[4] While stronger models, like linearizability are trivially eventually consistent, the converse does not hold.[clarification needed]

Eventually consistent services are often classified as providing BASE (Basically Available, Soft state, Eventual consistency) semantics, in contrast to traditional ACID (Atomicity, Consistency, Isolation, Durability) guarantees.[5][6] Eventual consistency is sometimes criticized[7] as increasing the complexity of distributed software applications. This is partly because eventual consistency is purely a liveness guarantee (reads eventually return the same value) and does not make safety guarantees: an eventually consistent system can return any value before it converges.

Conflict resolution[edit]

In order to ensure replica convergence, a system must reconcile differences between multiple copies of distributed data. This process, often known as anti-entropy, requires exchanging versions of data between servers.[8] The appropriate mechanism for choosing an appropriate final state depends on the application and the system but may come in the form of "last writer wins" reconciliation[1] or user-specified conflict handling.[4] Timestamps and vector clocks are often used to detect concurrency between updates.

In practice, conflict resolution is often performed in one of three processes:[3][9]

  • 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, if an inconsistency has been found, slowing down the write operation.
  • Asynchronous repair: The correction is not part of a read or write operation.

See also[edit]

References[edit]

  1. ^ a b Vogels, W. (2009). "Eventually consistent". Communications of the ACM 52: 40. doi:10.1145/1435417.1435432.  edit
  2. ^ Vogels, W. (2008). "Eventually Consistent". Queue 6 (6): 14. doi:10.1145/1466443.1466448.  edit
  3. ^ a b Terry, D. B.; Theimer, M. M.; Petersen, K.; Demers, A. J.; Spreitzer, M. J.; Hauser, C. H. (1995). "Managing update conflicts in Bayou, a weakly connected replicated storage system". Proceedings of the fifteenth ACM symposium on Operating systems principles - SOSP '95. p. 172. doi:10.1145/224056.224070. ISBN 0897917154.  edit
  4. ^ a b Petersen, K.; Spreitzer, M. J.; Terry, D. B.; Theimer, M. M.; Demers, A. J. (1997). "Flexible update propagation for weakly consistent replication". ACM SIGOPS Operating Systems Review 31 (5): 288. doi:10.1145/269005.266711.  edit
  5. ^ Pritchett, D. (2008). "Base: An Acid Alternative". Queue 6 (3): 48. doi:10.1145/1394127.1394128.  edit
  6. ^ Bailis, P.; Ghodsi, A. (2013). "Eventual Consistency Today: Limitations, Extensions, and Beyond". Queue 11 (3): 20. doi:10.1145/2460276.2462076.  edit
  7. ^ Yaniv Pessach (2013), Distributed Storage (Distributed Storage: Concepts, Algorithms, and Implementations ed.), Amazon, "Systems using Eventual Consistency result in decreased system load and increased system availability but result in increased cognitive complexity for users and developers" 
  8. ^ Demers, A.; Greene, D.; Hauser, C.; Irish, W.; Larson, J. (1987). "Epidemic algorithms for replicated database maintenance". Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87. p. 1. doi:10.1145/41840.41841. ISBN 978-0-89791-239-6.  edit
  9. ^ Olivier Mallassi (2010-06-09). "Let’s play with Cassandra… (Part 1/3)". http://blog.octo.com/en/: OCTO Talks!. Retrieved 2011-03-23. "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..."