Eventual consistency

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

Eventual consistency is a consistency model used in distributed computing to achieve high availability 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.

Strong eventual consistency[edit]

Systems in which replica conflicts are impossible by design exhibit Strong Eventual Consistency (SEC). Any two nodes in a SEC system that have received the same (unordered) set of updates are guaranteed to be in the same state, because the operation of merging local state with remote state is both commutative and idempotent. The system must be monotonically increasing in state; since this implies a partial ordering on system states, the set of all system states is a semilattice with the merge operation as a set join. SEC is implemented with conflict-free replicated data types.[10]

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..." 
  10. ^ Shapiro, Marc; Preguiça, Nuno (2011-10-10). "Conflict-free replicated data types". SSS'11 Proceedings of the 13th international conference on Stabilization, safety, and the security of distributed systems (Springer-Verlag Berlin, Heidelberg): 386–400.