初识分布式系统:CAP定理与BASE理论

初步学习分布式系统,理解CAP定理与BASE理论。

初识分布式系统:CAP定理与BASE理论

传统单机事务模型难以应对分布式事务的处理需求,需要分布式系统。分布式系统的节点分布在网络中,难以像传统的集中式事务处理系统那样实现严格的ACID特性。

1 CAP定理

1.1 背景

2000年7月,加州大学伯克利分校Eric Brewer教授在ACM PODC (Principles of Distributed Computing)会议上提出了CAP猜想。

2年后,麻省理工学院的Seth Gilbert和Nancy Lynch从理论上证明了CAP猜想的可行性,从此CAP定理成为分布式计算领域的公认定理。

1.2 定理

CAP定理:一个分布式系统不可能同时满足一致性(Consistency)、可用性(Availiability)与分区容错性(Partition torlence)这三个基本需求,最多智能同时满足其中两项。

1.2.1 一致性(Consistency)

一致性指的是多副本之间的一致性。分布式系统场景下,一个副本更新后,其他副本如果没有及时更新,那从其他副本上读取到的数据仍然是老数据,即,副本之间的数据出现不一致。

所有节点在同一时间具有相同的数据。

1.2.2 可用性(Availibity)

可用性指的是系统提供的服务必须一直处于可用状态,即,对用户请求总是在有限的时间内返回结果。

每个请求不关成功或是失败都有响应。

1.2.3 分区容错性(Partition torlence)

分区容错性指的是分布式系统遇到任何网络分区故障时,仍然能够对外提供满足一致性和可用性的服务,除非整个网络环境都发生了故障。

系统中任意信息的丢失或失败不影响系统的继续运作。

注:

  • 分布式系统中,不同节点分布在不同的子网络,可能出现子网络之间网络断连,但子网络内部正常,使得分布式系统被分割为若干孤立区域。
  • 组成一个分布式系统的每个节点的加入和退出,都可以看成时一个特殊的网络分区。

1.3 应用

根据CAP定理,分布式系统在应用中必须作出取舍,只能满足最多两个性质,意味着必须选择放弃一个性质。

放弃性质 说明 应用
CA:放弃分区容错性(-P) 单点集群系统,放弃分区容错性意味着放弃系统的可扩展性。实现分区容错性,简单的方法是将所有的数据(至少是事务相关的数据)放在一个分布式节点上,这样网络分区问题时,每个子网络都有依赖数据的可用副本。 RDBMS
CP:放弃可用性(-A) 一旦分布式系统遭遇网络分区或其他故障,受影响的服务需要等待一定时间才能恢复对外服务,在这段时间内不可用。满足一致性,分区容忍性的系统,通常性能不是特别高。 MongoDB, HBase, Redis
AP:放弃一致性(-C) 放弃分布式系统的强一致性,保证分布式系统的最终一致性。引入时间窗口的概念,隔一段时间在不同节点之间复制数据副本。 CouchDB, Cassandra, DynamoDB, Riak

具体地,

  • CA:放弃分区容错性
    • RDBMS:关系型数据库管理系统(Relational Database Management System),不具备可扩展性。
  • CP:放弃可用性
    • MongoDB:NoSQL,面向文档(document-oriented);
    • HBase:Hadoop Database,面向列(column-oriented);
    • Redis:Remote Dictionary Server,键值存储;
  • AP:放弃一致性
    • CouchDB:面向文档;
    • Cassandra:面向列;
    • DynamoDB:面向文档;
    • Riak:键值存储;

2 BASE理论

BASE名字取自缩写:

  • Basically Available
  • Soft state
  • Eventually consistent

2.1 背景

BASE理论由eBay架构师Dan Prichett在文章BASE: An Acid Alternative中首次提出,是对CAP中一致性和可用性权衡的结果。

2.2 理论

BASE理论的核心思想是:即使无法做到强一致性(Strong consistency),但每个应用都可以根据自身的业务特点,采用适当的方式来使系统达到最终一致性(Eventual consistency)。

牺牲强一致性来获得可用性。

2.2.1 基本可用(Basically Available)

分布式系统在出现不可预知故障时,允许损失部分可用性。

如:

  • 响应时间上的损失:出现故障时,响应时间一定程度增加;
  • 功能上的损失:购物节高峰时,部分用户被引导到一个降级页面。

2.2.2 软状态(Soft state)

允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

2.2.3 最终一致性(Eventually consistent)

系统中所有的数据副本,经过一段时间同步后,最终能达到一个一致的状态。

不需要实时一致,达到一致所需的时间延迟,取决于网络延迟、系统负载和数据复制方案设计等因素。

实际工程实践中,最终一致性存在五类变种:

  1. 因果一致性(Causal consistency):进程A修改数据后通知进程B,进程B读取的数据应该是新值。
  2. 读己之所写(Read your writes):进程A修改后再读取,得到的应该是新值。
  3. 会话一致性(Session consistency);系统保证再同一个有效的会话中实现读己之所写。
  4. 单调读一致性(Monotonic read consistency):进程读到新值后,后续不应该反而读出旧值。
  5. 单调写一致性(Monotonic write consistency):同一个进程的写操作应该顺序执行。