I’ve spent a fair amount of time recently discussing how distributed systems fail and
strategies for preventing those failures, and the lack of a shared vocabulary poses a
significant barrier to high-bandwidth communication.
Given some murky personal plans to write more in this area for the next bit,
I’ve written up the vocabulary I’ve found most effective. Hopefully this will
be useful in its own right, but at worst I’ll use it to avoid repeating boilerplate
definitions going forward!
Any discussion about distributed systems starts with a discusison of the
which argues you can only have two of these there properties:
consistency (C) equivalent to having a single up-to-date copy of the data;
high availability (A) of that data (for updates); and
tolerance to network partitions (P).
It’s useful to note that the original authors themselves have since emphasized
that “‘2 of 3’ is missleading”, particularly because (1) production systems make
numerous distinct choices between consistency and availability (not one overall choice),
and (2) “all three properties are more continuous than binary.”
One of the most useful explorations of the continuous nature of consistency and availability
is Harvest, Yield and Scalable Tolerant Systems.
Yield is is the probability of completing a request (e.g. what you typically measure
when you talk about availability),
Harvest is the fraction of data in the response relative to the amount that should
be available in an ideal case.
Using this vocabulary, we can talk about availability tradeoffs in a more nuanced way,
for example always continuing to return results from your search engine but sometimes
not including all results if a node is unavailable, which is described as “harvest degradation.”
It also introduces the concept of orthogonal mechanisms, advocating to remove all
run-time interfaces between systems, instead relying on compile-time interfaces,
such that they operate independently. A real-world example could be building a static cache
of your most common content at compile time, and periodically rebuilding and shipping it,
but not attempting to update the cache in real-time. (Which is actually how this blog works,
with every instance having its own complete snapshot of data that it periodically fetches.)
BASE is diametrically opposed to ACID.
Where ACID is pessimistic and forces consistency at the end of every operation,
BASE is optimistic and accepts that the database consistency will be in a state of flux.
The letters in BASE correspond to:
Basically Available - provide CAP’s Availability by prioritizing Yield over Harvest
Soft state - state is evolving over time due to state changes, there is not a guaranteed correct version at a point in time
Eventually consistency - if changes stop, state will eventually be consistent
Many NoSQL databases follow this model, such as Cassandra, Datomic, Dynamo, Riak, and many more.
Strong consistency - after an update completes, all further operations correctly use the new value
Weak conssistency - operations after an update completes may not correctly use the new value
Eventual consistency - if no new updates are made to an object, at some point in future it will return correct value
Inconsistency window - the period between an update and the system guaranteeing the correct value will be returned
Casual consistency - once an updated version is communicated to a process, it is guaranteed to not use older versions
Monotonic read consistency - similar to casual consistency, but from perspective of receiving process: once a process has seen a version, it will never use previous versions
Monotonic write consistency - writes within a process are serialized
Read-your-writes consistency - reads after a write return the updated version
Session consistency - reads after writes are always correct within a given session
Read level, write level and replica level are the number of nodes in a distributed storage system
involved in the reading, writing and replication of a piece of data.
The Dynamo paper describes this approach
in some detail, and it’s used heavily by both Cassandra and MongoDB as well (among many others)
Conflict resolution mechanisms for distributed systems: