1. Justin Sheehy
  2. riak


riak / www / cap.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<meta name="author" content="Basho Technologies" />
	<meta name="description" content="riak - a decentralized key value store - basho technologies" />
	<meta name="keywords" content="riak nosql decentralized distributed key value store" />
    <meta http-equiv="content-type" content="text/html;charset=utf-8" />
	<link rel="stylesheet" href="css/style-1c.css" type="text/css" />
	<title>Riak - Consistency, Availability, and Partition-Tolerance</title>
	<div id="content">
		<h1><span class="hr"></span><a href="/">riak</a></h1>
		<ul id="top">
			<li><a href="/">Home</a></li>
			<li><a href="http://bitbucket.org/justin/riak/">Source Code</a></li>
                        <li><a href="edoc/index.html">API Docs</a></li>
			<li><a href="faq.html">FAQ</a></li>
			<li><a href="contact.html">Contact</a></li>
		<div id="intro">
			<p>Consistency, Availability, and Partition-Tolerance</p>
		<div id="left">
			<h3>All Hail Consistency!</h3>
			<p>Many traditional databases go to extreme (and expensive) measures to ensure strong consistency.  One way of thinking about strong consistency is that no two parts of a networked system with strong consistency will ever successfully report a response to a given query at a given moment unless they would provide exactly the same response.  That sounds good, right?  Well, it would be good... except that insistence on having it all the time comes at a great cost.</p>

<h3>Everything has a price.</h3>
<p>At the PODC conference in 2000, Eric Brewer gave a talk on Robust Distributed Systems.  As part of a general attempt to clean up approaches to real-world distributed systems problems, he proposed the "CAP Theorem": that of the three desired properties of <strong>C</strong>onsistency, <strong>A</strong>vailability, and <strong>P</strong>artition-tolerance, you could only count on having any two of them in any shared-data system.  This meant that there would be no way for traditional strong-consistency databases to ever guarantee availability and partition-tolerance.  Two years later, Seth Gilbert and Nancy Lynch formalized Brewer's CAP Theorem and proved it to be correct.</p>

<p>(Note that "availability" here means not only read-availability, but also write-availability.  If you have some read-only slave serving requests but cannot write new data, your application is not truly available by any reasonable measure.)</p>

<h3>What choice do we have?</h3>
<p>Any networked system involving more than one host on the internet must be partition-tolerant, as it would be foolish to assume that <a href="http://en.wikipedia.org/wiki/Fallacies_of_Distributed_Computing">the network is reliable</a>.  So, at any given moment, for any given operation, an application system ought to be able to choose which of consistency or avilability it is wiling to bend.</p>

<h3>"Bend", you say?</h3>
<p>If your development stack makes a choice, at some low level such as the database implementation, about the relative priority of consistency and availability... then you're stuck.  That one choice will apply to every single aspect of your application, causing you to (e.g.) give up availability in favor of consistency even when your business would be better served otherwise.</p>

<p>However, if that choice is made available to the application programmer, complexity can properly move up the stack.  This allows you to treat consistency, availability, and partition-tolerance as what they truly are: business needs that may vary in relative priority for different aspects of an application and at different times.</p>

<p>The reason we talk about "bending" those constraints is because we remember that our only limitation is that we cannot fully guarantee that we have all three at a given moment, assuming arbitrary components can fail.  In moments when all is working as expected, we can often achieve all three.  In the other moments, when a failure of some kind is occurring, we can decide how to relax one of these constraints in order to retain the others.</p>

<p>A model of convergence, or <strong>eventual consistency</strong>, can be achieved by allowing brief period of inconsistency in the face of failures.  When allowed in the context of a system that will attempt to remediate these small inconsistencies as soon as possible, this strategy can allow for much greater availability properties at a minimal observable effect in consistency to the user.</p>

<h3>Bend or you will break.</h3>
<p>If even that degree of relaxed inconsistency seems too much, realize that the only moment of inconsistency in such a system are those times when a stricter system would be entirely unavailable.  The decision here is, in moments of great stress, should your system allow brief inconsistencies or instead be entirely unavailable?  The answer to that question will not always be the same, which is why allowing it to be tuned at the application level is essential.</p>

			<br />
		<div id="right">
		<div id="footer">

<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
<script type="text/javascript">
try {
var pageTracker = _gat._getTracker("UA-10051263-1");
} catch(err) {}</script>