Eventual consistency
   HOME

TheInfoList



OR:

Eventual consistency is a
consistency model In computer science, a consistency model specifies a contract between the programmer and a system, wherein the system guarantees that if the programmer follows the rules for operations on memory, memory will be consistent and the results of read ...
used in
distributed computing A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
to achieve
high availability High availability (HA) is a characteristic of a system which aims to ensure an agreed level of operational performance, usually uptime, for a higher than normal period. Modernization has resulted in an increased reliance on these systems. F ...
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. Eventual consistency, also called
optimistic replication Optimistic replication, also known as lazy replication, is a strategy for replication, in which replicas are allowed to diverge. Traditional pessimistic replication systems try to guarantee from the beginning that all of the replicas are identi ...
, is widely deployed in distributed systems and has origins in early mobile computing projects. A system that has achieved eventual consistency is often said to have converged, or achieved replica convergence. Eventual consistency is a weak guarantee – most stronger models, like
linearizability In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that: # The extended list can be re-e ...
, 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). In chemistry, a base is the opposite of an acid, which helps in remembering the acronym. 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 is sometimes criticized as increasing the complexity of distributed software applications. This is partly because eventual consistency is purely a
liveness Properties of an execution of a computer program —particularly for concurrent and distributed systems— have long been formulated by giving ''safety properties'' ("bad things don't happen") and ''liveness properties'' ("good things do happen"). ...
guarantee (reads eventually return the same value) and does not guarantee
safety Safety is the state of being "safe", the condition of being protected from harm or other danger. Safety can also refer to the control of recognized hazards in order to achieve an acceptable level of risk. Meanings There are two slightly dif ...
: an eventually consistent system can return any value before it converges.


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); 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 A timestamp is a sequence of characters or encoded information identifying when a certain event occurred, usually giving date and time of day, sometimes accurate to a small fraction of a second. Timestamps do not have to be based on some absolut ...
and
vector clock A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's ...
s are often used to detect concurrency between updates. Some people use "first writer wins" in situations where "last writer wins" is unacceptable. Reconciliation of concurrent writes must occur sometime before the next read, and can be scheduled at different instants: *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 Properties of an execution of a computer program —particularly for concurrent and distributed systems— have long been formulated by giving ''safety properties'' ("bad things don't happen") and ''liveness properties'' ("good things do happen"). ...
guarantee (updates will be observed eventually), strong eventual consistency (SEC) adds the
safety Safety is the state of being "safe", the condition of being protected from harm or other danger. Safety can also refer to the control of recognized hazards in order to achieve an acceptable level of risk. Meanings There are two slightly dif ...
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 In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
, the application will never suffer rollbacks. A common approach to ensure SEC is conflict-free replicated data types.


See also

* ACID * CAP theorem *


References

{{DEFAULTSORT:Eventual Consistency Consistency models de:Konsistenz (Datenspeicherung)#Verteilte Systeme