三省吾身：我真的懂 CAP 吗

想写这个是源于微信交流群里面的一个讨论。在讨论分布式系统的时候，有群友明确地如下说：

CAP 是可以兼顾的啊！

这把我惊起了一身冷汗，赶紧去查了一下是不是分布式系统理论界又有新的论文来推翻了之前的 CAP 定理了。后来深入讨论以后，才发现是他对 CAP 的理解有误。

CAP 理论是分布式领域的基础，所以大家的讨论和研究很多。学界和工业界也想出来好多办法来折中处理不可兼得时候的情形，例如著名的 BASE 。但是诸如上面的 CAP 可以兼顾”的话是绝对不应该出现的。如果能证明这点并且能写出学术文章的话，那是肯定能发 PODC 并且成为学术大牛的。而现阶段的研究没有一个往着打破 CAP 定理的方向走，这说明 CAP 定理挺牢固的，只是因为 BASE 的存在而产生好像兼顾了的误解。那么，为了帮助大家更好的理解 CAP 及其应用呢，借此机会，我来试着写篇文章讨论一下这方面的内容，并且争取能通过实践将其表达的更加清楚。

CAP 定理到底是什么

以下定义摘自维基百科：

在理论计算机科学中，CAP 定理（CAP theorem），又被称作布鲁尔定理（Brewer's theorem），它指出对于一个分布式计算系统来说，不可能同时满足以下三点：

• 一致性（Consistency） （等同于所有节点访问同一份最新的数据副本）
• 可用性（Availability）（每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）
• 分区容错性（Partition tolerance）（以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在 C 和 A 之间做出选择。）

也就是著名的 CAP 三选二。因为这个定理有实际的理论支撑、并被学术界广泛认可，所以大家一定要记住，CAP 全有的情形是不存在的。实际上，因为定理在中文的翻译下容易让人产生误解，所以很多人会以为，只要在分布式情形下，就算什么也不做，系统都可以保证至少有两个属性，或者我们可以任意选择其中两种属性。但是，其实，就算不发生分区情形，想在分布式系统内部实现 CA，也是很难、很复杂的。比如，以前的 Servlet 都是将用户的 Session 存在服务器上的，这个时候如果要将单机服务器扩展到集群情形，那怎么保证用户的 Session 在每台机器上都是一致的呢？这个时候，要么需要应用自己去做额外的同步协调工作，要么只能想办法让用户的请求只打到同一台机器上。因为这种问题的存在，为了实现服务的扩展性，所以现在都是将服务做成无状态的。用户的 Session 之类的管理丢给分布式缓存（redis、memcache）等来处理，由已经实现了对 CA 的支持的分布式 KV 组件来帮忙处理这些让人难受的问题。

不对等的三点

实际上，CAP 这三种属性，并非对等的，三选二的翻译也不对。一个在网络分区未发生时能保障 CA 的系统，在发生网络分区的时候，必须在一致性和可用性之间做出抉择。也就是说，当网络分区发生的时候，我们必须选择是保 C 还是保 A。当集群因为网络分区分为两个部分的时候，由于互相之间无法通信，所以一边的更新无法同步到另一边，这时候如果客户端仍然能访问集群，则访问到不同部分的客户端之间获取的数据不一致，我们失去了 C，获得 AP；而此时如果集群不接受访问请求，等待分区结束之后解决两部分之间的冲突，实现一致性之后再允许访问，我们失去了 A，保有了 CP。

这就意味着，CAP 三种属性并非对等的。当 P 发生的时候，它就是一个既定的事实。我们没有办法不选 P，只选 CA。只要有 P 发生了，它就是必选项，另一项我们只能选 C 或者 A。而 P 没有发生的时候，我们才能追求 CA。

所以，我建议在理解 CAP 的时候，不要理解为三选二，而是按照正规的定义那样去记忆：

对于一个分布式系统来说，它最多只能满足 CAP 中的两点。

折中方案：BASE

BASE 这个定义主要是让人更容易记忆才凑到一起的。你看它是四个字母，其实讲的是三个属性, 而每个属性其实包含着两个单词：

• Basically Available: 基本可用
• Soft State: 软状态
• Eventually Consistency: 最终一致性

认为 CAP 可以兼顾的同学，很可能是因为对 BASE 方案有所了解才下出这样的结论。但是作为程序员的我们来说，方案可以折中，定义严格不能变。

BASE 讲的是什么呢？实际上，业务上来说，并非所有的系统都要求有很高的服务能力的。比如，对于银行来讲，他们追求的是强一致性。如果在 P 发生的时候选了 A，那么假设数据库集群分区为两个部分，有两个人分别在两个不同地方从同一个账户取钱。这时候，请求有可能是打到两个不同的分区的。如果两个人各自取钱额度没有超过账户余额的话，他们都能取出钱。但是因为两部分分区无法通信，所以取出来的钱的和可能是超过账户余额的。这种事情如果发生的话，银行追钱追账是一件很难受的事情，所以他们很有可能不乐意在这个时候提供服务，或者说，他们决定只让集群中拥有较多机器的部分继续服务，另一部分不接受任何请求，等待网络分区结束以后再恢复服务。采用这种方案的话，银行的数据库系统提供的就是 BA 方案。他们没有利用整个集群的能力，而是只利用了其中的一部分。

既然如此，那为什么是“基本可用(Basically Available)”，而不是“部分可用(Partially Available)”呢？这点留到后面讲如何实现 CA 的时候再说。

软状态则与上述选择不一样，它在发生分区的时候，允许集群的不同部分都能被访问到。这个时候集群的不同部分可能会有不同的状态。如果业务上认为这种不一致是能够容忍的，那么软状态的存在就没有问题。例如，公众号文章的点击数，如果访问到不同的服务器，每个用户看到的点击数可能是不一样的。但是因为这个并不是重要的业务问题，所以就算暂时看到不一致，对用户来说也不是阻碍。

而在网络分区结束之后，如果集群能够自动解决两个不同部分之间的冲突，让集群达成一致性状态，那么我们可以说这个集群实现了最终一致性（Eventually Consistency）。这个时候，集群就又到达了拥有CA属性的状态。

CA，只要我选，集群就给？

我必须强调一下，只有真正理解如何让一个集群在没有网络分区的情形下能达到 CA 状态，我们才能理解好 CAP 理论。此时不得不吐槽一下，中文翻译中的三选二蛮害人的。真的不是你想选哪两个，你就有哪两个的。

实际上，如果对于单节点的系统来说，一致性问题是不存在的(这个说起来有点武断，因为并发可能导致同一变量被不同线程读出不同状态。这里我们不做太细粒度的解读，假设没有发生这种状况就好了)。服务的状态只在一个地方发生变化和读取，客户端读取到的状态都是一致的。我们天然就有 C。

但是这个时候没有 A。因为我们只有一个节点，假如访问量增大的时候，那么可能会使得服务变得特别繁忙，许多请求没法得到响应。这时候可用性很差，而且万一机器发生故障，那么我们所有的数据就都可能没有了。而这对现代系统是灾难性的。所以我们希望能有多台机器来处理问题。一来可以处理更多的请求，二来则可以避免单点故障。那么，到了多台机器上的时候，C 就成为问题了。机器可以增加很多台，但是机器上面的应用状态怎么办呢？这个时候我们当然不应该讲做无状态服务的事情了，虽然我们确实可以将这些交给数据库、KV 存储去做，但是本文讨论的就是当有状态的时候，怎么样在多台机器上复制和持久化这种状态。所以，抛开辅助的分布式组件，我们要怎么样复制，才能在获得A的同时，仍然保有 C 呢？

我们来看一下保有 CA 的几种模式

主动-被动复制模式

在不同的位置持有副本，但是只允许对于其中一个位置的状态做修改。

这种模式相对来说最简单、最容易理解。我们的服务可以有 N 个副本，这些副本都能接受读取请求。但是只允许其中一个副本接受更新请求，并由它负责将这个请求广播到其他副本，以达成集群状态的更新。这个副本被我们称作为主动副本，其他副本则为被动副本，负责接收请求，并且持久化状态。实现这种模式的时候，集群需要实现以下几种功能：

1. 集群成员服务，允许发现和枚举所有副本位置;
2. 集群单例机制，保证始终只有一个主动副本在运行；
3. 主动副本，接收来自客户端的更新请求，然后将其广播到所有的被动副本，并在复制成功之后，应答客户端；
4. 数个被动副本，负责持久化状态的更新，并帮助彼此从消息丢失中恢复。

这其中，集群成员服务可以通过注册中心来解决，我们需要着重解决的问题则在于：

1. 如何保证集群中始终只有一个主动副本？
2. 主动副本失败(断电、断网、崩溃、机器故障)之后，如何进行失败 切换？
3. 怎么样才算是复制成功？
4. 被动副本状态滞后的时候，怎么办？
5. 发生分区的时候，怎样选 C 或 A？

这些问题大家可以自行思考一下。然后限于篇幅，我们下一篇用具体代码来讲主动-被动模式的时候再讲回答这些问题。在这里为了回答一下上面关于基本可用（Basically Available）留下来的一个问题，为什么是基本可以用，不是部分可用呢？因为在部分可用的时候，它不一定是可用的。例如上面的问题 3，怎么样才算是复制成功？

当主动副本接收到更新请求的时候，它会接受请求，并将其广播到被动副本，并在得到肯定回复的时候，应答客户端。那么，我们要考虑的是，要等到多少个被动副本应答之后，才算复制成功了？要求更多的副本应答，能显著减少数据丢失的可能性，并保障系统的一致性；要求更少的副本应答，能显著减少副本响应缓慢带来的延迟，提高可用性。但是这个数目是确定的，假设其为 N。也就是说，必须要有 N 个副本应答之后，系统才能接受更新成功。否则主动副本会一直等待集群确认，直到超时。基本可用也就是要表达这个意思：你的可用分区必须至少要有 N 个副本，才能达成对更新的确认。少于 N 个的话，要么想办法减少 N 的值，要么想办法添加新的副本进去。否则，系统连基本可用都无法保障。

实际上，raft 共识算法的实现，就有点类似上述的主动-被动复制模式。这个我们后续写文章具体细讲。

主动-被动复制模式的优点在于，当系统运行良好的时候，这种模式的性能会非常好，因为主动副本不需要执行协调任务；所有的读请求都能在不需要额外通信的情况下得到响应；写入请求只需要多数副本确认即可。

而当系统有失败发生的时候，它将有两种不同情形的性能退化。如果被动副本节点失败重启，那么为了跟上最新的状态，它将占用较多的流量来请求大部分更新；如果主动副本节点失败的话，就会有一段时间内没有任何主动副本在运行。此时集群需要花费时间来确认节点已经失效，并且需要在集群中选出新的主动副本，来协调整体的更新。而在这段时间内，系统的表现是不可用的。

多主复制模式

在不同的位置上保持服务的多个副本，每处都可以接受修改，并将所有修改在各个副本之间传播。

可以通过多种方法来实现多主复制模式，他们之间的不同则在于发生网络分区的时候，如何处理更新请求。我们这里主要说一下基于共识的复制。

基于共识的复制是最具一致性的方式，它通过对每个更新都确立共识的方式实现，代价则是网络分区的时候，不能处理任何请求（保有 CP）。

这里我必须又吐槽一下不负责任的翻译带来理解上的偏差。共识, Consensus。在计算机科学里面，对共识的定义如下：

给定一个拥有 N 个节点的集群，以及一组提议 P1 到 Pm, 每一个非失败的节点最终会选定单个提议 Px，并且不会撤回此提议，最终所有非失败的节点会选定相同的 Px，这时候我们称集群内部达成了共识。

多主复制模式意味着每一个副本都能接收到更新请求，并能在集群内部对该请求提起共识请求。任何流入的更新都以编号的形式写入到一个虚拟的账本(复制日志)中，并且每个节点都要对哪个更新在哪一行取得共识，这样每个副本都能根据这个账本达到当前状态。这样就在集群内部实现了一致性。而这里的共识操作，我们可以使用 Raft 算法来达成。

Raft 是共识算法，而不是一致性算法。并不是你使用了 Raft 以后，你的集群就能保障一致性。你需要将共识应用到正确的地方，在我们这里，就是对每项更新请求的位置达成共识。Scala 生态中有一个叫 ckite 的库，实现了 raft 算法。下面直接列一下使用 ckite 实现一个简单的键值存储的例子（具体的解读 raft 请等待下一篇）：

 1class KVStore extends StateMachine {
 2  private var map = mutable.Map[String, String]()
 3  private var lastIndex: Long = 0
 4
 5  def applyWrite: PartialFunction[(Long, WriteCommand[_]), String] = {
 6    case (index, Put(key: String, value: String)) ⇒
 7      map.put(key, value)
 8      lastIndex = index
 9      value
10  }
11
12  def applyRead: PartialFunction[ReadCommand[_], Option[String]] = {
13    case Get(key) ⇒ map.get(key)
14  }
15
16  def getLastAppliedIndex: Long = lastIndex
17
18  def restoreSnapshot(byteBuffer: ByteBuffer): Unit = {
19    map = Serializer.deserialize[mutable.Map[String, String]](byteBuffer.array())
20  }
21
22  def takeSnapshot(): ByteBuffer =
23    ByteBuffer.wrap(Serializer.serialize(map))
24
25}

要使用的时候，利用 ckite，将其实例化就好：

 1object KVStoreBootstrap extends App {
 2  val ckite =
 3    CKiteBuilder()
 4      .stateMachine(new KVStore())
 5      .rpc(FinagleThriftRpc)
 6      .storage(MapDBStorage())
 7      .build
 8  ckite.start()
 9
10  HttpServer(ckite).start()
11}

如此，在应用中使用它，则只需要如下执行就好了：

1val consistentRead: Future[Option[String]] = ckite.read(Get(key))
2val possibleStaleRead: Future[Option[String]] = ckite.readLocal(Get(key))
3val write: Future[String] = ckite.write(Put(key, value))

看，实现一个强一致性的基于共识的复制的 KV 存储，多么的简单？只要你会了 Scala，上面的代码一目了然，强大又效率。所以，还等什么呢，还不赶紧来学 Scala？

还是那句话，关于 raft 共识算法和上述代码的解读，我们下篇再讲。

值得学习的《反应式设计模式》

上述的基于共识的复制是解决方案的一种，多主复制模式其实还有如下两种方案：

• 具有冲突检测与处理方案的复制: 在网络分区的时候，接受可能会发生冲突的更新请求。而这些冲突可以在分区结束之后解决。只是可能会要丢弃部分已经被确认过的更新。
• 限定数据模型，使用无冲突的可复制数据结构。这样的并发更新天生就是无冲突的，只需要在集群中进行复制即可。

另外还有主动-主动复制模式，它的策略是在不同的地方持有服务的多份副本，并在所有副本上执行所有的修改操作。这样，每个副本都会执行相同的更新操作，它们之间的状态是保持一致的。只是我们需要一个协调者来负责将更新请求发送给每一个副本。

上述模式相关的更详细的内容都可以在《反应式设计模式》一书内找到。而我相信只要你仔细学习过以后，对于 CAP 有更深的理解，而不是仅仅只能说出三选二。该书点击“阅读原文”就可以直接购买了。

结束语

这个世界上本来没有 CAP 的困扰的，有的只是单机程序。后来访问的人数多了，就有了分布式程序，也就有了 CA 的需求。而 P 是天然存在的，它的发生不可避免。在 P 产生的时候，就要根据业务需求来选择 C 或者 A。选 C 的话，可以让拥有大部分节点的分区接受访问，保持服务的基本可用；选 A 的话，则允许系统存在软状态，最终通过冲突的解决或者更新的复制，达到最终一致性。

CAP 相关的，就这么简单，你搞懂了吗？