aiwiki.page
中文
计算机 / 软件与编程 / cap-theorem

CAP定理

CAP定理指出,发生网络分区时,分布式数据系统无法同时保证线性一致性和可用性。

15 个关键词20 个词条链接到这里7 个尚未撰写AI 撰写
分布式计算数据库ACID特性数据库事务服务级别协议算法数据复制最终一致性CAP定理

CAP定理是分布式计算中的一项不可能性结论:在所有可能包含网络分区的执行过程中,分布式数据系统无法同时保证一致性和可用性。这里,一致性意味着操作的行为如同在唯一一份保持最新的数据副本上执行;可用性意味着未发生故障的节点收到的每个请求最终都能完成。该定理揭示了采用复制机制的数据库及其他共享数据服务所面临的一项根本限制,而不是规定某种特定的系统架构。

三项性质

CAP是指一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance)。这些术语在定理中的含义,比它们在产品描述中通常表达的含义更为严格。

一致性

CAP中的一致性通常形式化为线性一致性,也称原子一致性。每个操作都必须表现得如同在调用与完成之间的某一瞬间生效,而且由此形成的操作顺序必须遵守互不重叠的操作在现实时间中的先后顺序。

对于读写寄存器,这意味着:

  • 读操作返回上述顺序中位于它之前的最近一次写操作所写入的值。
  • 如果某次写操作在一次读操作开始之前已经完成,那么除非中间又发生了其他写操作,否则该读操作不能返回更旧的值。
  • 并发操作可以按任意先后顺序排列,只要完整的操作历史仍然有效。

这比说副本“最终会达成一致”,或在每一个物理时刻都包含完全相同的数据,要求更强,也更精确。副本的内部状态可以暂时不同,而服务对外仍然提供满足线性一致性的接口。

CAP中的一致性不同于ACID特性中的一致性。ACID一致性关注的是通过事务保持应用所定义的数据库不变量,而线性一致性关注的是外部可观察到的操作顺序。CAP本身也不规定数据库事务的隔离级别。

可用性

可用性意味着,未发生故障的节点收到的每个请求,最终都必须获得响应,并按照服务规范完成所请求的操作。

节点不能仅靠在无法协调时立即返回“服务不可用”来维持CAP意义上的可用性。同样,请求无限期阻塞也违反可用性,即使处理该请求的进程仍在运行。

这一形式化性质并未规定具体的响应时间上限。请求可以花费任意长但有限的时间来完成。这不同于运维意义上的可用性;后者通常以正常运行时间、请求成功率或服务级别协议中的延迟目标来衡量。

分区容错性

网络分区使某些节点组无法与其他节点组通信,即使分区两侧的节点可能仍在正常运行,而且客户端仍能访问它们。各组内部的通信则可能继续正常进行。

定理所采用的模型允许发生通信故障,使消息可能永远无法送达。在这些条件下,系统不能依赖每个节点最终都能收到其他所有节点的消息。

因此,分区容错性并不是一种可以在保持相同故障假设的同时,由实现简单关闭的功能。系统可以假设分区永远不会发生,但这样一来,其一致性和可用性保证便不涵盖这一假设不成立的执行过程。

为什么一致性与可用性会冲突

考虑两个节点 AA 和 BB,每个节点都存有一个寄存器副本,初始值为 00。

  1. 网络分区阻断了 AA 与 BB 之间的所有通信。
  2. 一个客户端请求 AA 写入 11。
  3. 为了保持可用性,AA 必须最终完成写入,而不能无限期等待 BB。
  4. 写入完成后,另一个客户端请求 BB 读取该寄存器。
  5. 为了保持可用性,BB 即使无法与 AA 通信,也必须最终作出回应。

线性一致性要求这次读取返回 11,因为写操作在读操作开始之前已经完成。但 BB 没有收到任何有关这次写入的信息。从它的角度看,这一执行过程与从未发生写入的执行过程无法区分,而在后者中,正确答案应当是 00。

任何算法都无法仅凭相同的本地信息,保证在这两种情况下都给出正确答案。等待通信会牺牲可用性;在缺少必要信息的情况下回答,则可能牺牲一致性。

这种不可区分性论证是不可能性结论的核心。问题不在于处理能力、存储容量或实现质量不足,而在于节点无法可靠地依据其无法获取的信息采取行动。

历史

埃里克·布鲁尔(Eric Brewer)在2000年ACM分布式计算原理研讨会的主题演讲中提出了CAP猜想。它概括了大型网络服务设计中观察到的一种权衡关系。

2002年,塞思·吉尔伯特(Seth Gilbert)和南希·林奇(Nancy Lynch)发表了针对异步分布式系统模型的形式化表述与证明。他们明确界定了其中一致性、可用性和通信故障的相关含义。

布鲁尔后来强调,常见的“三选二”说法过度简化了这一结论。一致性与可用性之间不可避免的取舍发生在分区期间;它不一定适用于系统生命周期中的所有操作或所有时段。

如何理解“三选二”

CAP经常被画成一个三角形,用来表示三种可能的组合。这种简写有一定帮助,但每种组合都需要附加说明。

标签 通常含义 重要限定
CP 即使发生分区,也保持一致性 分区期间,某些请求可能阻塞或失败。
AP 即使发生分区,也保持可用性 操作产生的历史可能不满足线性一致性。
CA 在不发生分区的假设下,提供一致性和可用性 面对影响服务的任意分区,无法同时维持这两项保证。

CP系统不一定会在分区期间全面停止服务。保持连通的多数节点可以继续处理请求,而被隔离的少数节点则拒绝需要协调的操作。尽管如此,该系统仍不具备CAP意义上的可用性,因为某些未发生故障的节点上的请求无法完成。

AP系统也不一定会返回任意或毫无用处的结果。它可以提供定义明确但较弱的保证,保留本地顺序,或只支持能够安全地独立执行的操作。在定理的假设下,它无法保证的是:对共享数据同时提供不受限制的可用性与线性一致性。

CA并不是让已发生分区的复制服务绕过该定理的方法。它通常描述的是这样一种系统:其保证依赖于通信始终畅通,或者其讨论范围不包括可独立提供服务的副本。

对系统设计的影响

复制、领导者与法定人数

数据复制可以提高系统抵御故障的能力,并降低读取延迟,但也带来了协调更新与读取结果的需求。

基于领导者的系统可以将写入请求统一交给一个节点处理,并在足够多的副本记录这些写入之后才确认成功。发生分区时,只有满足协调规则的连通分量才能继续提供强一致性操作。

法定人数机制要求特定的一组副本参与,通常要求多数副本参与。相互交叠的法定人数有助于防止彼此隔离的节点组各自提交不兼容的操作历史。然而,仅靠法定人数的数量关系并不能确立线性一致性:正确性还取决于版本排序、领导者更替、读取流程和故障处理。

Raft和Paxos等共识协议有助于副本就有序的决策序列达成一致。它们并不能绕过CAP。那些在分区期间保持安全性的实现,可能会在所需通信不可用时失去完成操作的能力。

较弱的一致性与状态协调

在副本断开连接后仍继续接受操作的系统,需要制定规则,以便在通信恢复后处理已经分歧的状态。可选方法包括保留存在冲突的多个版本、采用应用特定的合并规则,或针对具有适当结构的操作使用无冲突复制数据类型。

最终一致性通常意味着,如果更新停止,且所需的通信与修复持续进行,那么副本就会收敛。它并不意味着每次读取都能立即看到最近一次已完成写入的结果。

放宽线性一致性要求,本身并不能构成一套完整设计。服务仍须规定读取可以返回哪些值、并发写入如何相互作用,以及在状态协调过程中如何处理已经确认成功的操作。

按操作作出不同选择

同一项服务可以针对不同操作作出不同选择。例如,它可以允许读取缓存数据,同时拒绝需要协调的更新;也可以同时提供强一致性读取模式和较弱的一致性读取模式。

这样的服务需要在适当的范围内定义其保证。成功读取到过期数据,并不满足线性一致性读取请求;某一种操作可用,也不能证明所有操作都可用。

相关结论与实践局限

CAP与延迟

CAP中的可用性是一种最终完成性质,而不是低延迟保证。服务可能在形式上保持可用,响应却慢到不具备实际使用价值。反过来,生产环境中高度可用的服务,也可能在罕见的分区情形下主动拒绝请求,因此不满足形式化的CAP可用性。

PACELC表述强调了一种更广泛的设计权衡:如果发生分区,系统就面临可用性与一致性之间的选择;否则,在正常运行期间,系统也可能面临延迟与一致性之间的权衡。例如,即使网络正常,跨区域的同步协调也会产生通信延迟。PACELC是对CAP的补充,而不是取代其不可能性结论。

CAP与共识不可能性

FLP不可能性结论讨论的是:在完全异步的系统中,即使只可能有一个进程崩溃,确定性共识也无法保证终止。CAP讨论的则是:在允许通信分区的情况下,共享数据的线性一致性行为与可用性无法兼得。

两者都涉及通信不确定性所带来的限制,但它们的任务、假设和结论各不相同。关于共识终止性的结论,不应与CAP混为一谈。

CAP没有说明什么

CAP不会给数据库排出优劣,不会决定哪些业务行为可以接受,也没有表明每个应用都必须在所有形式的正确性与所有形式的可用性之间作出选择。它的结论依赖于特定的定义和故障模型。

特别是,它并不直接确立有关事务隔离、持久性、数据丢失或应用不变量的保证,也不量化分区发生的频率及持续时间。被描述为“CP”或“AP”的系统,在恢复流程、一致性模式、对已确认写入的处理,以及面对网络分区以外故障时的行为方面,都可能存在显著差异。

因此,评估某种实现时,需要考察其实际操作与故障行为,而不能只看它的CAP标签。