cap理论 证明

要真正理解 CAP 理论必须要读懂它的形式化描述。 形式化描述中最重要的莫过于对 Consistency, Availability, Partition-tolerance 的准确定义。 
Consistency (一致性) 实际上等同于系统领域的 before-or-after atomicity 这个术语，或者等同于 linearizable (可串行化) 这个术语。具体来说，系统中对一个数据的读和写虽然包含多个子步骤并且会持续一段时间才能执行完，但是在调用者看来，读操作和写操作都必须是单个的即时完成的操作，不存在重叠。对一个写操作，如果系统返回了成功，那么之后到达的读请求都必须读到这个新的数据；如果系统返回失败，那么所有的读，无论是之后发起的，还是和写同时发起的，都不能读到这个数据。 
要说清楚 Availability 和 Partition-tolerance 必须要定义好系统的故障模型。在形式化证明中，系统包含多个节点，每个节点可以接收读和写的请求，返回成功或失败，对读还要返回一个数据。和调用者之间的连接是不会中断的，系统的节点也不会失效，唯一的故障就是报文的丢失。 Partition-tolerance 指系统中会任意的丢失报文(这和“最终会有一个报文会到达”是相对的)。 Availability 是指所有的读和写都必须要能终止。 
注： “Availability 是指所有的读和写都必须要能终止” 这句话听上去很奇怪，为什么不是“Availability 是指所有的写和读都必须成功”？ 要回答这个问题，我们可以仔细思考下“什么是成功”。“成功”必须要相对于某个参照而言，这里的参照就是 Consistency。 

CAP 理论说在一个系统中对某个数据不存在一个算法同时满足 Consistency, Availability, Partition-tolerance 。 注意，这里边最重要和最容易被人忽视的是限定词“对某个数据不存在一个算法”。这就是说在一个系统中，可以对某些数据做到 CP, 对另一些数据做到 AP，就算是对同一个数据，调用者可以指定不同的算法，某些算法可以做到 CP，某些算法可以做到 AP。 

要做到 CP， 系统可以把这个数据只放在一个节点上，其他节点收到请求后向这个节点读或写数据，并返回结果。很显然，串行化是保证的。但是如果报文可以任意丢失的话，接受请求的节点就可能永远不返回结果。 

要做到 CA， 一个现实的例子就是单点的数据库。你可能会疑惑“数据库也不是 100% 可用的呀？” 要回答这个疑惑，注意上面说的故障模型和 availability 的定义就可以了。 

要做到 AP， 系统只要每次对写都返回成功，对读都返回固定的某个值就可以了。 

如果我们到这里就觉得已近掌握好 CAP 理论了，那么就相当于刚把橘子剥开，就把它扔了。 

CAP 理论更重要的一个结果是， 在 Partial Synchronous System (半同步系统) 中，一个弱化的 CAP 是能达到的: 

* 对所有的数据访问，总返回一个结果 
* 如果期间没有报文丢失，那么返回一个满足 consistency 要求的结果。 

这里的半同步系统指每个节点存在一个时钟，这些时钟不需要同步，但是按照相同的速率流逝。更通俗的来说，就是一个能够实现超时机制的系统。 

举个例子，系统可以把这个数据只放在一个节点上，其他节点收到请求后向这个节点读或写数据，并设置一个定时器，如果超时前得到结果，那么返回这个结果，否则返回失败。 

更进一步的，也是最重要的，实现一个满足最终一致性 (Eventually Consistency) 和 AP 的系统是可行的。 现实中的一个例子是 Cassandra 系统。