CAP定理的含义

分布式系统（distributed system）正变得越来越重要，大型网站几乎都是分布式的。

分布式系统的最大难点，就是各个节点的状态如何同步。CAP 定理是这方面的基本定理，也是理解分布式系统的起点。

分布式系统的三个指标

三个指标不可能同时做到，结论就叫做 CAP 定理

  • Consistency
  • Availability
  • Partition tolerance
Partition tolerance 分区容错

大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。

client <-> G1 client <-> G2 G1 <-> G2

G1 和 G2 是两台跨区的服务器。G1 向 G2 发送一条消息，G2 可能无法收到。系统设计的时候，必须考虑到这种情况。

一般来说，分区容错无法避免，因此可以认为 CAP 的 P 总是成立。CAP 定理告诉我们，剩下的 C 和 A 无法同时做到。

Consistency 一致性

写操作之后的读操作，必须返回该值。 client 发送请求到 G1 将v0改成v1，再读取时必须返回v1， 但是可能client 请求时到达 G2 读取时，发现返回的还是v0。 这样就不满足一致性了。

为了让 G2 也能变为 v1，就要在 G1 写操作的时候，让 G1 向 G2 发送一条消息，要求 G2 也改成 v1。

Availability 可用性

只要收到用户的请求，服务器就必须给出回应。

用户可以选择向 G1 或 G2 发起读操作。不管是哪台服务器，只要收到请求，就必须告诉用户，到底是 v0 还是 v1，否则就不满足可用性。

Consistency 和 Availability 的矛盾

一致性和可用性，为什么不可能同时成立？答案很简单，因为可能通信失败（即出现分区容错）。

如果保证 G2 的一致性，那么 G1 必须在写操作时，锁定 G2 的读操作和写操作。只有数据同步后，才能重新开放读写。锁定期间，G2 不能读写，没有可用性不。

如果保证 G2 的可用性，那么势必不能锁定 G2，所以一致性不成立。

综上所述，G2 无法同时做到一致性和可用性。系统设计时只能选择一个目标。如果追求一致性，那么无法保证所有节点的可用性；如果追求所有节点的可用性，那就没法做到一致性。

在什么场合，可用性高于一致性？

举例来说，发布一张网页到 CDN，多个服务器有这张网页的副本。后来发现一个错误，需要更新网页，这时只能每个服务器都更新一遍。

一般来说，网页的更新不是特别强调一致性。短时期内，一些用户拿到老版本，另一些用户拿到新版本，问题不会特别大。当然，所有人最终都会看到新版本。所以，这个场合就是可用性高于一致性。

分布式和集群有什么区别
  1. 从概念上就可以看出两者最主要的区别就是分布式是将一种业务拆分成多个子业务部署在多台服务器上，进而对外提供服务；而集群就是将多台服务器组合在一起提供同一种服务；
  2. 集群强调在多台服务器位置集中，并且容易统一管理；而分布式没有具体要求，不论放置在哪个位置，只要通过网络连接起来就行；
  3. 集群是一种物理形态，即多台服务器在一起提供一种服务；而分布式是一种工作方式，即一个程序或业务分解到多台服务器分别完成；

总之，两者最明显的区别还是集群是多台服务器做相同类型的任务，分布式是多台服务器协同做一种任务。

CP模型延伸

拜占庭将军问题
  • 分布式系统中，各节点可能存在故障通信等问题，同时还可能存在恶意攻击等问题，需要在此基础上解决节点的共识问题；
  • 共识问题解决方法：
    • 基于口信消息
    • 基于签名消息
  • 算法类型：
    • 存在恶意节点行为（区块链），采用拜占庭容错算法，如BFT/PBFT/Pow
    • 无恶意节点，消息伪造等情况，采用非拜占庭容错(故障容错 - CFT）算法，如Paxos、Raft算法、ZAB协议
二阶段提交

代表有XA、TCC、Raft、Paxos

  • 二阶段提交过程
    • 投票阶段
    • 提交阶段
  • 二阶段提交最早用于数据库分布式事务（代表协议XA，比如MYSQL就支持XA分布式事务)
  • 二阶段提交的问题
    • 节点提交请求节点（投票阶段），需要预留资源（资源锁定）
    • 针对资源预留，数据库是独立的系统，无法弹性的调整锁的粒度，如果锁得范围过大，会影响并发度
    • 问题替代方案 - TCC 利用业务确认和取消的幂等性，确保事务执行成功
  • Raft、Paxos这类强一致性分布式算法，也采用二阶段提交协议思想，只是需要大部分节点确认就执行事务，而ACID要求全部节点确认才执行事务。
  • 三阶段提交，是基于考虑到协调者故障，节点参与者资源长时间锁定问题，加入节点询问和超时机制，但带来了更多的节点消息通信，使得系统更加复杂，较少使用。
TCC事务补偿

  • TCC（Try-Confirm-Cancel）

    • Try
      • 各节点尝试执行的操作
    • Confirm
      • 各节点确认执行的操作
    • Cancel
      • 不满足，就执行取消回滚，达到一致性

  • TCC的本质是补偿事务，也是基于二阶段提交思想，程序应用扮演了协调者的角色。可以将TCC理解为编程模型，即业务层面上的协议，即确认和取消操作都应该是幂等的，因为当确认或取消失败时候，应用程序需要满足补偿重试达到一致；

  • 少用TCC：TCC不是依赖数据库来实现分布式事务的一致性，而是在业务层面上实现分布式事务，好处是对数据库压力减少，带来的问题就是对代码的侵入性增加，提升了代码的复杂度。因此，从代码简洁和维护性上，如果要确保分布式事务的强一致性，优先考虑支持分布式事务的数据库，比如MYSQL XA，当数据库无法满足业务要求时候（比如性能开销），再来考虑TCC。

  • 幂等性：同一操作对同一系统，所产生的影响均与一次执行的影响一致，不会因为多次导致副作用的产生，主要是基于Token、索引这类唯一标识，标记同一操作，消除多次执行的副作用。

  • 失败重试：幂等性需要将提交相关信息保存到持久存储上，即使故障、超时，也需要在故障恢复、超时后，不断重试以实现自己的承诺。

ACID强一致性

ACID是强一致性，即CP优先考虑，可用性方必然受到损失。如果一个节点出现，分布式事务是必然失败的。但绝大多数场景，对一致性要求没有那么高。

AP模型延伸

追求可用性，短时不一致，达到最终一致性。

分布式设计考虑

如系统过载，一方面考虑有损服务，另一方面调用资源，提升整体吞吐

  • 流量错峰（买票服务不同地区出售时间错峰）
  • 异步处理（排队处理用户买票请求）
  • 服务降级（查询类请求采用缓存提供非实时数据）
  • 过载保护（限流/熔断，直接拒绝掉一部分，或移除已满队列中部分请求，达到系统整体可用）
  • 故障隔离（出现故障，做到故障隔离，避免影响其他服务）
  • 弹性扩容（基于Metric和Monitor实现系统态势感知，做到弹性伸缩）
最终一致性

系统所有数据经历一段时间后，最终会达到一个一致的状态

  • 最终一致的数据，以什么数据为准：
    • 以最新写入的数据为准（KV存储）
    • 以第一次写入的数据为准（不希望存储数据被更改）
  • 如何实现最终一致性：
    • 读时修复，读数据的时候，检查分布式各节点数据是否一致，不一致则通知系统修复（读需要做数据比对，考虑开销，算法效率）
    • 写时修复(数据存储+失败重传)，写数据的时候，检查分布式各节点数据是否一致，不一致则通知系统同步修复（不需要同其他节点做数据比对，仅在有差异时候才修复）
    • 异步修复，定期检测数据是否一致，最终达到一致（常用）

参考