2000年7月，加州大学伯克利分校的Eric Brewer教授在ACM PODC会议上提出CAP猜想。2年后，麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了CAP。之后，CAP理论正式成为分布式计算领域的公认定理。

无论你是一个系统架构师，还是一个普通开发，当你开发或者设计一个分布式系统的时候，CAP理论是无论如何也绕不过去的。本文就来介绍一下到底什么是CAP理论，如何证明CAP理论，以及CAP的权衡问题。

CAP理论概述

  • CAP理论：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。

    1. 一致性（Consistency）（C）：

      在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）

    2. 可用性（Availability）（A）：

      在集群中一部分节点故障后，在一定时间内，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性）

    3. 分区容错性（Partition tolerance）（P）：

      以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在 C 和 A 之间做出选择。

  • CAP理论中的CA和数据库事务中ACID的CA并完全是同一回事儿。

    • 两者之中的C都是都是一致性(Consistency)。
    • CAP中的A指的是可用性（Availability），而ACID中的A指的是原子性（Atomicity)，切勿混为一谈。

事务的特性：ACID

  • 事务是由一系列对系统中数据进行访问与更新的操作所组成的一个程序的执行逻辑单元。

    • 宏观概念：指不可分割的一个逻辑执行单元
    • 狭义概念：数据库事务

  • Automaticy 原子性:全部执行成功或者不成功，没有中间状态

  • Consistency 一致性:不能破坏数据库数据的完整性和一致性

  • Durability 持久性:事务一旦提交，数据库对应数据的状态变更就是永久性的。

  • Isolation 隔离性：并发的事务是相互隔离的。不能干扰

    隔离级别 脏读 可重复读 幻读
    未授权读取 存在 不可以 存在
    授权读取 不存在 不可以 存在
    可重复读取 不存在 可以 存在
    串行化 不存在 可以 不存在

  • 四种不同的事务处理级别：

    • 未授权读取：读未提交，允许脏读

    • 授权读取：读已提交

    • 重复读：事务过程中多次读取同一数据是一致的，该操作禁止不可重复读和脏读，可能出现幻读

    • 串行化： 最严格的事务隔离级别。事务串行执行，不能并行执行

  • 两个重点概念：

    1. 脏读：读到事务提交之前的值，因为读取到的未提交事务有可能回滚
    2. 幻读：同样的事务操作，前后可能读取同一数据出现不一致

CAP

  • Consistency 最终一致性： 多个副本保持一致
  • Availability 可用性：系统提供的服务必须一直处于可用，对于用户的每一个操作请求总是能在有限时间内返回结果
  • Partition tolerance 分区容错性：分布式系统在遇到任何网络分区故障时，仍然需要能够保证对外提供满足一致性和可用性的服务

  • 放弃P ： 最简单的极端做法，就是放置在一个节点上。 放弃P也就意味着放弃了系统的可扩展性

  • 放弃A： 一旦系统遇到网络分区或者其他故障时，服务需要等待一段时间，在等待时间内就无法正常对外提供服务，即服务不可用

  • 放弃C： 事实上，放弃一致性是指放弃数据的强一致性，而保留最终一致性，具体多久达到数据同步取决于存储系统的设计

BASE

  • Basically Available 基本可用:
    • 相应时间的损失,功能上的损失
  • Soft state 软状态:
    • 允许存在不同节点同步数据时出现延迟，且出现数据同步延迟时存在的中间状态也不会影响系统的整体性能。
  • Eventually consistent 最终一致性:
    • 系统中所有数据副本，在经过一段时间后，都可以达到同步：要求最终达到一致，而不是实时一致

Quorum NRW

  • quorum机制是分布式场景中常用的，用来保证数据安全，并且在分布式环境中实现最终一致性的投票算法
    • N: 复制的节点数，即一份数据被保存的份数。
    • R: 成功读操作的最小节点数，即每次读取成功需要的份数。
    • W: 成功写操作的最小节点数 ，即每次写成功需要的份数。

Write to all copies with latest version no, wait synchronously for W success
Read from all copies, wait for first R responses, pick the highest version number

  • 条件：W + R > N 保证一定能读取到最新的数据

  • 结论：这三个因素决定了可用性，一致性和分区容错性。只需W + R > N，就可以保证强一致性。

  • N一经固定，那么可以得到保证强一致性的情况下

    • W = 1, R = N,对写操作要求高性能高可用。
    • R = 1, W = N , 对读操作要求高性能高可用，比如类似cache之类业务。
    • W = Q, R = Q where Q = N / 2 + 1 一般应用适用，读写性能之间取得平衡。如N=3,W=2,R=2

分布式事务

  • 前提： 分布式系统中，每个节点都能知道自己的事务操作是否成功， 但是没法知道系统中的其他节点的事务是否成功。这就有可能会造成分布式系统中的各节点的状态出现不一致。

  • 因此当一个事务需要跨越服务器节点，并且要保证事务的ACID特性时，就必须引入一个 “协调者”的 角色。那么其他的各个进行事务操作的节点就都叫做“参与者”

  • 典型的两种分布式事务的提交模式：

    • 2PC：Two-Phase Commit

      • 阶段一：提交事务请求
      • 阶段二：执行事务请求

    • 3PC：Three-Phase Commit

      • 阶段一：CanCommit
      • 阶段二：PreCommit
      • 阶段三：DoCommit

定理：任何分布式存储系统只可同时满足二点，没法三者兼顾。

  • 忠告：架构师不要将精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍
  • 原因总的来说就是：数据存在的节点越多，分区容错性（P）越高，但要复制更新的数据就越多，一致性（C）就越难保证。为了保证一致性，更新所有节点数据所需要的时间就越长，可用性（A）就会降低。
  • MySQL：满足 CA
  • ZooKeeper：满足 CP