CAP Notes

08 Nov 2014 by fleuria

上周意识到知乎答错了一个问题之后，回家扫了几篇 CAP 相关的文章，重写了答案，也记录了一些笔记。CAP 很容易被误解或者模棱两可，一旦理解之后可以认为它不难，即使不理解也并不妨碍依赖它作为设计系统的指导原则，但是不能否认，CAP 理论直面了分布式系统的固有困难，可能还是写一篇 blog 总结一下对理解更加有益。单纯看网上的文章很容易走歪，我也仍不能保证这篇 blog 中没有理解错误的地方，欢迎指正、交流。

Defination

“Data consistency, system availability, and tolerance to network partition—only two can be achieved at any given time. ” ，即一个系统在一个特定时刻最多只能保证两条性质，进一步可以理解为：在 P 发生时，A 和 C 只能选一个；当系统没有出现 P 时，不需要做 C 与 A 的权衡。

C、A、P 各自的定义是：

  • Consistency: 关心单个数据多个副本的一致，需要注意与 ACID 的 “C” 有很大不同；属于 safety 约束，“anything bad won’t happen”；
  • Availability: 写入、读取请求最终一定可以得到结果；属于 liveness 约束，“something good eventually happen”；
  • Partition: 网络分区，原因可能是网线烧了，也可能是交换机挂掉导致网络不可连接，也可能因为垃圾收集、高延时操作导致网络连接超时，甚至垃圾收集可以算是首要的 Partition 原因。

“Choose Two of Three”

CAP 被误解最多的地方似乎就在这里。似乎很多人把 CAP 理论理解为 “一个系统只能在 CAP 中选两个”，因而出现了一些分类：比如 MySQL 是 CA 系统，Zookeeper 是 CP 系统，Mongodb 是 AP 系统等等。这种分类法在业内有它的意义，可以直观地向大家 advise 我们的系统权衡了什么。可是就像 Brewer 在十年后说的，“怎样牺牲 P” 的意义并不明朗。不妨考虑几个问题：

  • 牺牲不牺牲 P，这由得我们么？即使在一个 99.99% 可靠的网络环境下，万一 发生了 P，是不是依然需要在 C 和 A 里做选择？
  • 如果说单机的 MySQL 是 CA 系统，牺牲了 P，可是发生 P 的时候，A 又从何保证？
  • 如果说 Mongodb 是 AP 系统，那么配置为 writeConcern.MAJORITY 之后，它是什么？

等等。无论如何，回到这个定义：“在 P 发生时，A 和 C 只能选一个，上面的困惑其实都没有必要存在。

首先，CAP 只关心单个数据多个副本的一致性，如果系统中不存在数据副本，那么就不适合用 CAP 去描述它；其次，单个系统通常允许不同的配置，去做不同的 C、A 权衡。

ACID vs CAP, Serializability vs Lineraizability

“Consistency” 是一个被滥用的术语，CAP 中的 “Consistency” 与 ACID 的 “Consistency” 就是一个典型的不同语境不同含义。CAP 中的 C 只关心单个数据在多个副本上的 “一致性”，更接近多核 CPU 缓存关心的 “Coherence”；而 ACID 中的 C 关心一个事务前后数据总是满足不变性条件，更接近数据的 “Intergrity”。

CAP 理论只关心单个数据的多副本的一致性，而数据库事务要保证多个数据的一致性，这更多是靠着 ACID 的 “Isolation” 性质。理想的 Isolation 是将数据库事务串行执行，即 Serializability。这相当于多核编程环境中的上锁：进入一个临界区，其中的多个数据读写，受锁保护。而多个事务执行的顺序并不需要强求，谁先抢到锁，谁就执行，实际上是随机的。而且事务执行完毕的结果，并不需要立即对其它事务可见，允许事务使用 Snapshot 的方式实现。

在多核编程上下文中，也有一个术语可以对应 CAP 中的 C，那就是 Linearizability：关心单个对象的单个操作的实时顺序。保证 Linearizability 的环境下一旦一个对象被写入，可以被后续的读操作读到；一旦一个对象被读到，后续的读操作不会读到更老的版本。脑洞一下不难联想到，这也正是内存栅栏所面对的问题：保证数据修改对其它核的可见性。 CAP 语境下的一些一致性模型，也可以在内存一致性模型的相关文献中找到参考。

然而不管 Serializability 还是 Lineraizability 都需要昂贵的 Coordiation 工作。在现实世界的系统中，数据库事务一般不会默认开启强的 Serializability ，我们需要考量自己的业务，使用尽可能低的隔离级别，以提高事务的吞吐；多核 CPU 也不会开启强的 Lineraizability，我们需要在合适的地方插内存栅栏，或者严格遵循内存模型确保修改的可见性。

分布式环境下，需要同时面对多核编程和数据库事务两个领域的固有困难，这并不容易。

Eventual Consistency, Compensation

“最终一致性” 也是个常见的 advisement。异步地复制副本，多个副本的内容会最终达成一致，允许在发生 Partition 时存在数据的不一致。它的好处显而易见：低延时，所有操作在最近的节点完成即可，对于 geo-replicated 系统，延时将大大降低；实现简单，不再将各种宕机视为 “corner case”，不需要编写复杂的 Coordination 逻辑（比如 master 选举）；而且数据不一致的概率一般并不大；牺牲的 Durability 在很大程度上也可以靠 quorum 方法得到缓解，比如同步写入 W 个副本再返回，没有 W-1 个节点挂就行。

但 “最终一致性” 是一个很弱的形容词，它并没有对数据冲突的处理提供任何有用的帮助。最终一致性只约束各副本的内容最终一致，最后选哪个副本都能满足 “最终一致性”；甚至极端一点，一台总是返回 42 的烂系统也是最终一致的。在业务系统上，开发者必须直面不一致数据的修复（Compensation）工作。强一致环境下省心各种不变量的福利，也就不再存在；开发者必须时刻在意着系统中所有的不变量，一旦破坏一个，就会导致难于调试的 bug。这与多线程编程所面临的困难很相似。

不同的业务场景，一般会采用不同的方法进行数据修复：

  • Last Write Win
  • 使用 CRDT 数据结构，满足交换律的操作可以安全地 merge
  • 依据业务的不变量，自己制定数据的修复规则
  • 不更新数据，也就不存在冲突就不存在数据修复的问题，使用新建代替更新

实际中的数据修复可能会很 tricky，实现者需要权衡它的好处、不一致的代价和不一致的概率。对于一些应用，不一致的概率和不一致的代价都足够小，甚至都不需要考虑不一致数据的修复，比如 Justin Bieber 的关注数，不准也没关系。

Real World CAP

之前没有想到的是，CAP 在指导日常的业务系统时也非常有用：

ATM 机： Brewer 在文章中提到了 ATM 机的例子，直觉上 ATM 机属于金融系统，高一致性应该优先，然而实际上，ATM 机宁愿牺牲 C，因为机器所在的环境一般并不稳定，更可用的机器可以引来更高的流水，对银行更为有利。而 ATM 机的转入业务是满足交换律的，网络断开时收到的转入，到网络恢复时同步即可；而转出业务，可以在网络断开时设置一个限额，比如 200 块，当客户的余额不足 200 块时，理论上客户可以在另一台 ATM 机器上把钱先取走，然后再取 200 块，这以来银行会损失 200 块，但银行可以在网络恢复时发现这笔欺诈，走法律途径解决问题。同样，现实中的金融系统也是更多依赖着后验的审计，而不是每笔钱都事先严格审批。

卖票、电商秒杀：12306 在优化卖火车票时，可以在数据库前面放一个 mq 存买票请求，而 mq 与数据库操作可能发生异常，为了避免 “买票成功” 的用户最后拿不到票，产品上的补救是用户下单时不显示 “买票成功” 而是 “排队中”，确保写入数据库之后再 “买票成功”，相当于把牺牲 A 转移给了用户，用户需要自己时不时去检查一下排队有没有成功，或者耐心等待系统发送的提醒邮件；至于普通电商秒杀的话，进 mq 就直接 “下单成功” 就行了，大不了事后赔一件。

缓存：在系统中使用缓存时，也就相当于将数据库中的数据存储了一份副本在缓存里。如果写缓存与数据库写入之间发生异常，也就相当于发生了 P 但牺牲了 C。相比精细地 Expire 缓存，约定缓存内容不可变，使用唯一的 cache key 总是新建缓存数据来避免缓存更新，更容易保证缓存的一致性。同样，CDN 是一个典型的 AP 系统，多个节点之间副本的不一致绝对可以接受，因此 Asset Pipeline 等前端发布方案在上线前端代码时，总是生成一个唯一的文件名，这也是出于副本一致性问题的需求。

SOA：大型系统一般会拆分为多个子系统，而不同的子系统会选择不同的权衡。比如用户对阅读网页的一致性要求不高，但对网页装载的时间延时敏感，可以牺牲显示网页内容的一致性；但下单买商品需要强一致，这时可以牺牲 A，甚至进一步把牺牲 A 转移给用户。

References

  • CAP Faq：http://henryr.github.io/cap-faq/
  • CAP Twelve Years Later: http://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed
  • Eventual Consistency, Revisited: http://www.allthingsdistributed.com/2008/12/eventually_consistent.html
  • Linearizability vs Serializability: http://www.bailis.org/blog/linearizability-versus-serializability/
  • Eventual Consistency Today:Limitations, Extensions, and Beyond: https://www.cs.berkeley.edu/~alig/papers/eventual-consistency-limitations-extensions.pdf
  • CAP 笔记: http://www.douban.com/note/438220510/