C.A.P.定理

All lectures for ZH purposes
第 1 级 , 课程 885
可用

4.1 关于 Brewera 的一致性

首先,Eric Brewer 不是,也从未声称自己是数据库专家。他属于分布式系统社区,他在“分布式计算原理”会议上发表了著名的演讲,其中出现了 CAP“定理”。(顺便说一下,十年后的 2010 年,他再次在同一个会议上作了受邀演讲,在这次演讲中,他特别给出了一些分布式系统的例子,其发展考虑到了“定理”的 CAP。)在这方面对数据库领域中使用的术语有自己的解释。

特别地,术语“立即一致性”是指在用户收到系统关于某个数据更新操作成功完成的通知后,该操作的结果立即对所有观察者可见。

最终一致性是指如果在足够长的时间内没有新的数据更新操作进入系统,那么可以预期,之前所有数据更新操作的结果最终会扩散到系统的所有节点,所有的副本数据都是consistent(显然,这应该理解为“所有副本都将具有相同的状态”)。

有了这种一致性的感觉,Brewer 的“定理”可以认为是非常容易理解和显而易见的:在任何具有共享数据的分布式系统中,只能同时确保网络的一致性、可用性和分区容忍度中的任意两个属性。在这方面,Brewer 甚至将 ACID 属性集与他提出的 BASE 属性集(基本可用、软状态、最终一致性——大多数情况下的可用性;不稳定状态;最终一致性)进行了对比。但在我看来,这种反对是没有道理的,因为在第一种情况下,我们谈论的是交易的逻辑特征,而在第二种情况下,我们谈论的是分布式系统的物理属性。

4.2 “定理”的证明

许多人认为布鲁尔的“定理”已经被正式证明。实际上,Seth Gilbert 和 Nancy Lynch 的论文介绍了一些(几乎)正式的定义,在这些定义中,“定理”真正成为定理并得到证明。但是,让我们看看分布式系统的这三个属性是如何确定的,其中,根据布鲁尔“定理”,只能同时支持两个属性。

一致性称为原子性,或线性化一致性(atomic, or linearizable consistency),它是系统的一个属性,系统的所有个体数据对象都是原子性的(linearizable)。反过来,原子对象是具有多个操作的对象,这样操作的调用和响应数据的接收就好像立即发生一样,即 在上一个操作完全完成之前,对象不接受下一个操作的调用。接收操作的顺序必须是这样的,如果读类型操作在执行了一些写类型操作之后到达,那么读操作必须返回由这个或一些稍后的写操作写入的值。

如果必须回答非故障节点收到的每个请求,则分布式系统始终可用。系统对网络分区的弹性被建模为在丢失从一个节点发送到另一个节点的任意数量的消息时系统的生存能力的保持。

基于这些定义,Hilbert 和 Lynch 制定了以下定理(异步网络模型中没有时钟,节点应该仅根据接收到的消息和本地计算来做出决策):

在异步网络模型中,不可能实现保证所有有效执行(包括丢失消息的那些)的可用性和原子一致性属性的读/写数据对象。

这个定理真的很简单,用“反证法”的方法形式化地证明了。文章接着得出结论:

在异步网络模型中,不可能实现一个读/写数据对象来保证所有有效执行的可访问性属性和有效执行的原子一致性,其中消息不会丢失。

此外,对于部分同步的网络模型证明了主要定理的真实性,其中每个节点都有一个时钟,显示的时间以相同的速率增加,但不同步,即 可以在同一真实时刻显示不同的时间。结果表明,对于这种情况,不会得出类似的结果,因此,对于部分同步网络,组织具有“良好”属性的分布式系统的可能性更大。

是的,在某种意义上(不一定与 Brewer 的意图相同)Gilbert 和 Lynch 可以被认为已经证明了在单个分布式系统中不可能同时确保网络的原子一致性、可用性和分区容忍性等属性。但这与一般的数据库事务和特定的 ACID 事务有什么关系呢?

4.3 ACID 交易

以下是朱利安·布朗 (Julian Browne) 在他关于讨论 CAP 的“定理”的笔记中所写的内容:

在他们的证明中,Hilbert 和 Lynch 使用术语原子性而不是一致性,从技术角度来看这更有意义,因为严格来说,ACID 意义上的一致性指的是数据库事务的理想属性,意味着没有数据会如果他们违反了一些预先设定的限制,就会变得持久。但是如果我们假设分布式系统的一个预先设定的限制是禁止同一个数据元素存在多个不同的值,那么,在我看来,一致性抽象中的这个缺陷可以被考虑无关紧要(此外,如果布鲁尔使用术语原子性,那么就会出现 AAP 定理,其名称非常不方便发音)。

这篇写得不是很认真,但很诚实。而且,事实上,原子一致性的要求不应该与 ACID 意义上的事务一致性的要求混在一起。如果您愿意,数据库完整性约束是合乎逻辑的业务需求。它们来自应用程序域逻辑。原子一致性的要求是一种非常不同的类型。这是一种实现要求,属于数据库行业传统上所说的物理一致性(例如,在执行任何索引更改操作时,对应的 B+ 树的所有块都必须包含有效值并由有效引用链接).

以下是数据库社区的代表 Daniel Abadi 和 Alexander Thomson 在他们的笔记中非常认真地写下的内容:

...对可扩展事务系统可用性的要求变得越来越重要,这通常通过复制和在其中一个节点发生故障时自动重定向请求来满足。因此,应用程序开发人员期望 ACID 系统的一致性保证(最初包括对用户定义的不变量的本地支持)将得到扩展以确保强一致性(同一数据的所有副本在任何给定时间都将是相同的副本,即在这种情况下的一致性隐含在 CAP/PACELC 的意义上。

换句话说,Brewer 一致性与 ACID 意义上的一致性无关,但在专注于通过数据复制提供高可用性的系统中,需要保持强副本一致性。这不是 ACID 属性,而是大规模并行 DBMS 的一项技术(物理)特性,可促进应用程序开发。

根据 Michael Stonebreaker 的说法,构建高质量现代 DBMS 的关键是技术妥协的正确选择。在选择特定的工程解决方案时,必须考虑许多因素——未来用户的要求、各种故障情况的可能性等,而不是教条地受任何一般理论指导方针(包括 CAP“定理”)的指导。

Stonebreaker 认为,在事务性并行数据库系统领域,为了支持高可用性和网络分区容错而放弃 Brewer 的一致性是一个糟糕的权衡,因为 (a) 副本一致性是系统非常有用的特性;(b) 事务性大规模并行 DBMS 不需要具有大量节点的集群,因此不太可能出现网络分裂情况;(c) 系统很容易变得不可用,不是因为网络分区,而是因为经常出现软件错误等原因。

因此,经常引用布鲁尔“定理”的 NoSQL 阵营(阅读 NoACID)代表的高度活跃与构建支持 ACID 事务的大规模并行事务 DBMS 的理论上的不可能性无关,但与简化系统的事实有关不仅支持 ACID 事务,还支持副本一致性,创建起来更容易、更快。由于它们的组织简单,它们能够非常快速地处理数据,对于某些应用程序而言,这比数据库技术固有的所有便利性更重要。

让我们看看数据库社区如何应对这一挑战。

评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION