Brewer 的 CAP 理论

Brewer 在 2000 年基于他在伯克利大学的工作以及对 Inktomi 的观察上提出了 CAP 理论(牛人就是观察出的理论啊!),这之前(1997 年SOSP Cluster-Based Scalable Network Services 和1999年 Cluster-Based Scalable Network Services)他和他的同事也提出了应该在高扩展性系统做出取舍权衡,所以在 2000 年提出的这个理论也不是一个特别意外新颖的观点,和许多著名的理论相同,他们都是建立大量工作和牛人基础之上的。

CAP 理论谈到了在分布式系统中应该注重的三个核心需求:可用性(Availablity)、一致性(Consistency)和分区容忍(Partition tolerance)。这个理论在两年后被 MIT 的 Seth Gilbert and Nancy Lynch 形式化地证明了。我们先分别来看看这三个需求:

  1. Consistency 一致性:Consistency 是数据库中 ACID 中的 C。Gilbert 和 Lynch 在证明 CAP 理论时使用‘automic(原子性)’来代替 Consistency (这可能是因为数据库中更喜欢使用原子性,而分布式系统更愿意使用一致性),但表示的意思都是一个服务/请求被完全执行或者完全不执行。以网购为例,当一件衬衣只有一件时,客户A 和 客户B 将这件衬衣加入购物车并购买时,只允许一个客户完成购买。
  2. Availablity 可用性:Availablity 就是说:服务总是可用的。
  3. Partition tolerance 分区容忍:在不考虑扩展性等问题,我们应用只在一个机器上运行的时候,我们服务器就是一个先来先服务的原子性处理机,能够保证一致性,当将数据连同逻辑结构分散到不同的节点,考虑到当不同节点发生通信故障(还有比如另一个节点响应的时间超过了接受节点的阈值时间等)时,导致了从宏观上看服务方被分割为一个个可能的分区。应用对其容忍的程度叫做分区容忍,这里的分区可以理解为单个服务器。Gilbert 和 Lynch 这样解释 Partition tolerance:

No set of failures less than total network failure is allowed to cause the system to respond incorrectly

译:只有全局网络瘫痪才能导致错误响应

下面谈谈 CAP 的重要性,可用性不用说非常重要。关于扩展性,有两点:第一点是在某个应用实施时很大程度上是商业决定,可能在技术上并不合适,未来会遇到扩展性的问题;第二点关于数据集群的存储有两种实现:数据库集群和非数据库集群。数据库涉及到乐观锁、分片等关键技术,非数据库则要考虑如果不用数据库来寻址和扩展。但两者都会涉及到 CAP 问题,具体实现中,设计者往往需要牺牲可用性 Availablity、一致性 Consistency 和分区容忍 Partition tolerance三者之一。

最后一部分谈谈图形化证明 CAP 理论:首先看一个简单的例子,在网络节点 N1 和 N2 上运行应用程序并共享值V0,如下图:

如图一所示当A 修改值V0 为V1 时,首先节点N1  V0 变为 V1 ,接着如图二将 V1 值传播给节点 N2 进行修改,理想情况下应该如图三修改后的值 V1 再返回给前端 B。

在实际情况中网络等原因会导致第二个过程中网络节点中值没有被正确的更新,导致每个节点返回的值是不同的,即发生了一致性问题。

这个问题可能在两个节点的时候并不是什么大问题,当这个集群由成千上万的网络节点组成时,这个问题就非常严重了。

节点与节点之间的操作在要满足原子性即一致性要求下,必须当所有节点的数据完全更新时,才能够确认数据更新完毕,否则应该回滚到之前的原始值。而从网络的观点来看,如果消息的传递是异步的话,节点之间永远不知道对方是否真的更新了自己所发送的数据。这样 CAP 理论就告诉我们如果我们既想要高可用性,又能够容忍分区(集群),我们也就必须能够容忍有些节点V 的值是 V0 ,有些节点 V 的值是 V0 。

如下图 α1 和 α分表代表对值 V 的两个操作‘写’和‘读’,在本地服务器中这种一致性很好控制,通过数据库的锁机制保证 α操作必须在 α完成之后即可。可是在分布式环境中,只有控制了 α2  操作在这些异步的更新消息之后才能够保证读的一致性。

从上面 CAP 提供的信息来看,只有在C、A、P三者之间做一个取舍才能够更适合我们的服务的需求:

  • 牺牲分区容忍:将所有的数据都放在一个服务器上
  • 牺牲可用性:使用强一致性锁,在所有节点数据更新完毕后才确认更新完成
  • 牺牲一致性:允许不同节点有不同的值,这时候锁的机制不是那么强了,数据异步的更新消息在节点间传递的时候,任意节点还是可以提供数据的读,当然读出的值也就不同了。

 

Reference:

  1. http://www.julianbrowne.com/article/viewer/brewers-cap-theorem

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据