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/