EVE N T U A L LY the different trade-offs together in a keynote address to
the PODC (Principles of Distributed Computing) conference in 2000.1 He presented the CAP theorem, which states
CONSISTENT that of three properties of shared-data systems—data
consistency, system availability, and tolerance to network
partition—only two can be achieved at any given time. A
more formal confirmation can be found in a 2002 paper
by Seth Gilbert and Nancy Lynch.
4
A system that is not tolerant to network partitions can
achieve data consistency and availability, and often does
so by using transaction protocols. To make this work,
client and storage systems must be part of the same environment; they fail as a whole under certain scenarios, and
as such, clients cannot observe partitions. An important
observation is that in larger distributed-scale systems,
network partitions are a given; therefore, consistency and
availability cannot be achieved at the same time. This
means that there are two choices on what to drop: relaxing consistency will allow the system to remain highly
available under the partitionable conditions, whereas
making consistency a priority means that under certain
conditions the system will not be available.
Both options require the client developer to be aware
of what the system is offering. If the system emphasizes
consistency, the developer has to deal with the fact that
the system may not be available to take, for example, a
write. If this write fails because of system unavailability,
then the developer will have to deal with what to do with
the data to be written. If the system emphasizes availability, it may always accept the write, but under certain
conditions a read will not reflect the result of a recently
completed write. The developer then has to decide
whether the client requires access to the absolute latest
update all the time. There is a range of applications that
can handle slightly stale data, and they are served well
under this model.
In principle the consistency property of transaction
systems as defined in the ACID properties (atomicity,
consistency, isolation, durability) is a different kind of
consistency guarantee. In ACID, consistency relates to the
guarantee that when a transaction is finished the database
is in a consistent state; for example, when transferring
money from one account to another the total amount
held in both accounts should not change. In ACID-based
systems, this kind of consistency is often the responsibility of the developer writing the transaction but can be
assisted by the database managing integrity constraints.
performance and high availability. Although replication
brings us closer to our goals, it cannot achieve them in a
perfectly transparent manner; under a number of conditions the customers of these services will be confronted
with the consequences of using replication techniques
inside the services.
One of the ways in which this manifests itself is in
the type of data consistency that is provided, particularly
when many widespread distributed systems provide an
eventual consistency model in the context of data replication. When designing these large-scale systems at Amazon, we use a set of guiding principles and abstractions
related to large-scale data replication and focus on the
trade-offs between high availability and data consistency.
In this article I present some of the relevant background
that has informed our approach to delivering reliable
distributed systems that need to operate on a global
scale. An earlier version of this text appeared as a posting on the All Things Distributed weblog and was greatly
improved with the help of its readers.
HISTORICAL PERSPECTIVE
In an ideal world there would be only one consistency
model: when an update is made all observers would see
that update. The first time this surfaced as difficult to
achieve was in the database systems of the late ’70s. The
best “period piece” on this topic is “Notes on Distributed
Databases” by Bruce Lindsay et al.
5 It lays out the fundamental principles for database replication and discusses
a number of techniques that deal with achieving consistency. Many of these techniques try to achieve distribution
transparency—that is, to the user of the system it appears
as if there is only one system instead of a number of
collaborating systems. Many systems during this time
took the approach that it was better to fail the complete
system than to break this transparency.
2
In the mid-’90s, with the rise of larger Internet systems, these practices were revisited. At that time people
began to consider the idea that availability was perhaps
the most important property of these systems, but they
were struggling with what it should be traded off against.
Eric Brewer, systems professor at the University of California, Berkeley, and at that time head of Inktomi, brought
CONSIS TENC Y—CLIENT AND SERVER
There are two ways of looking at consistency. One is from
