(翻译) CAP 理论 FAQ
CAP 理论 FAQ
0. 关于这个文档
没有其它比CAP理论更引人注意的话题了, 这个FAQ的目的, 是说明对于CAP, 当前哪些是已知的, 并帮助那些刚接触这个理论的人快速了解, 并解决一些错误的观念和常见的误解.
当然, 很可能我的认知是肤浅甚至完全错误的, 欢迎任何评论和纠正.
1. CAP理论的来源是什么?
Eric Brewer 博士在2000年的 Principles of Distributed Computing 会议上作了一个报告, 标题是"Towards Robust Distributed Systems", 在这个报告中, 他提出了CAP 理论 - 那时候这个理论还未被证明 - 描述了在分布式系统中一致性和可用性之间的矛盾.
两年后, 在MIT研究分布式系统的 Seth Gilbert 和 Nancy Lynch 教授在他们的论文“Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services”中证明了CAP理论.
2. CAP理论到底说了什么?
CAP定理(以下简称 CAP)指出, 在异步网络中实现的读写存储, 不可能同时满足以下三个特性:
- 可用性 - 是否对于数据存储的每个请求都会成功执行?
- 一致性 - 对于数据的读写执行, 是否从每个分布式节点所观察到的都是一致的, 或者是可线性化一致的?
- 隔离容忍性 - 分布式系统之间的通信是否允许丢失任意消息?
更通俗地说, CAP定理告诉我们, 无法建立一个既能响应每个请求又能每次都返回预期结果的分布式存储系统. 这是一个不可能的结果, 它告诉我们, 我们在努力尝试的目标实际上是不可实现的. 这很重要, 因为过去几年已经建立和正在建立的许多分布式系统都会受到这个理论的影响. 但它并不意味着我们不能在这些限制下建立有用的系统. 细节是魔鬼, 在你开始"是的, 但是..."之前, 确定自己已经明白什么是CAP理论允许和不允许的.
3. 什么是 ‘读写存储’?
CAP理论特别关注的一种结构, 叫 register, 即嵌入式领域中的寄存器. 寄存器是一种具有两种操作的数据结构:
- set(X) 将寄存器的值设为 X
- get() 返回寄存器中最新的值
一个KV存储可以看成是一组寄存器的集合. 即使寄存器看起来非常简单, 但它体现了分布式系统做的事情本质 - 写入数据和读取数据.
4. 原子一致性(Atomic Consistency), 线性一致性(Linearizable Consistency)是什么含义?
原子一致性(Atomic Consistency), 或者说线性一致性(Linearizable Consistency), 是关于客户端在执行读写操作时返回值的可见度问题, 体现在寄存器上, 就是在被所有的分布式节点访问时, 响应和请求是基于同一个时钟顺序的(注: 这是强一致性, 理想状态的一致性).
例如一个执行由多个客户端的操作组成, 这些操作可能是并发的, 在原子一致性的要求下, 这个执行的结果必须等同于所有操作单次串行(按顺序，一个接一个)执行的结果. 这是一个很强的约束, 与其它的约束是冲突的, 除了其他约束之外, 它还排除了最终一致性(EC, 允许在写入变得可见之前有延迟). 所以在EC下, 可能会出现:
set(10),
set(5),
get() = 10 // 但是读取到的是10
在原子一致性下, 上面的流程是不可能出现的.
原子一致性会确保寄存器的外部访问顺序, 也就是说, 如果A读取了X, 并且A能与B通信, B去读也能读取到一致的结果. 在稍微弱一些的约束下(例如顺序一致性)这个结果可能不一定成立. 下面我们做如下的操作:
B:set(5), A:set(10), A:get() = 10, B:get() = 10
这体现了操作的原子一致性, 但是下面这种情况就不是
B:set(5), A:set(10), A:get() = 10, B:get() = 5
虽然这和下面的序列化操作是一样的
B:set(5), B:get() = 5, A:set(10), A:get() = 10
在第二个例子中, 如果A在读取寄存器后告诉B关于寄存器的值(10), B会错误地认为有另外的操作在 A:get() 和 B:get() 之间把寄存器值改成了5. 如果不允许节点间通信, B 并不知道 A:set, 并且要保持读写的一致, 就像 B:get() 发生在 A:set 之前一样.
Wikipedia 有更多的说明. Maurice Herlihy 1990年的论文原文在这里.
5. 什么是异步(asynchronous)?
异步网络, 就是对节点处理消息或网络送达消息的时间没有限制的网络, 这个定义带来的影响, 就是无法判断一个节点到底是宕机了, 还是它的消息被延迟了.
6. 什么是可用(available)?
一个数据存储的可用, 体现在所有的get和set请求最终都会返回响应. 这个响应不是指返回错误, 因为如果用这个判断的话, 很明显一个系统可以只靠返回错误而保证可用性. 因为可用性对于响应的时效性并没有约束, 所以系统可以花任意长的时间来处理一个请求, 但是必须最终返回响应.
要注意到, 这是同时是一个强约束, 也是一个弱约束. 强约束是指所有的请求都必须正确处理并返回, 弱约束是指处理时间的长度没有限制.
7. 什么是分区隔离(partition)?
分区隔离, 是指分布式系统中一个或多个节点间的通信出现故障, 导致消息丢失(不是延迟, 如果消息最终到达了, 就不属于这种情况).
这个词有时用于描述一个时间区间, 这个时间区间内两组节点之间的消息传递都失败了. 这是一种更严格的失败模型, 可以称这种隔离为完全隔离.
CAP的证明依赖于完全隔离, 在实际应用中, 如果所有的消息都通过一个组件, 如果这个组件失效, 那么这两个节点的所有消息发送都会失败.
8. 为什么 CAP 理论是正确的?
CAP理论的基本思想是, 如果存在分区隔离的情况, 一个客户端向一侧分区写入数据, 那么对另一分区的任何读取都不可能读取到这些写入. 这时候就会面临着一个选择: 是用可能过时的数据来响应读取, 还是等待(可能永远等待)来自另一侧分区的消息而影响可用性? 基于这个构造的场景, 我们描述了一个分布式系统无法同时保持一致性和可用性的情况. CAP理论受到这么多关注的一个原因, 是这个场景是很可能出现的, 当网络设备出现故障时就会发生分区间的完全隔离.
9. 什么时候系统不得不放弃 C 或者 A?
CAP理论仅仅说明在某些情况下一个分布式系统必须放弃A或者C. 这属于比较极端的情况, 而理论并没有说明发生这种极端情况的可能性有多大. C 和 A 都是强约束: 只有操作100%满足时才成立. 只要有一个非一致的读取或失败的写入, 都会使 C 或 A 的保证无效. 但是在极端情况之外是很容易满足 C 和 A 同时成立的.
由于大多数分布式系统都会长时间运行, 在整个生命周期中处理数百万千万的请求, 这期间大概率会遇上某个极端情况, 了解CAP理论, 就可以提前了解在哪个方面会出问题, 并进行准备.
10. 为什么当我说我的系统是CA时, 一些人会不满意?
Brewer的观点, Gilbert的论文, 以及很多其他人的观点, 通常把C, A和P作为等同的特性, 并在其中可以任意选择两个. 然而这是一种误导性的表述, 因为"分区隔离的容忍性"是无法避免的: 分布式系统几乎不可避免地会遇到节点间通信障碍. 所以CAP更适合理解为: 构建一个可能出现分区隔离的系统时, 如何做出权衡. 实际上，这就是分布式系统: 没有100%可靠的网络, 所以(至少在分布式环境中)现实中并不存在CA系统.
所以, 将定理改一下可能更有指导意义: 一个分布式系统出现通信故障时，不可能同时兼顾A和C.
有些系统不会出现分区隔离，例如单节点的数据库服务器, 然而这些系统通常与CAP适用的环境不相关. 如果您将一个分布式数据库描述为"CA"系统, 那么您对分布式系统和CAP理论还存在误解.
11. 如果消息不会丢失呢?
Gilbert的论文中, 一个可能令人惊讶的结论是: 在一个异步网络中, 让一个寄存器保持永远可用是无法实现的, 并且只有当消息不会丢失时才能保持一致性.
这个结论基于异步网络的属性, 其思想是无法判断一个消息是否已经丢失, 所以一个节点无法一边等待一边维持可用性, 这种情况下只要响应了, 结果一致性就被破坏了.
12. 我的网络真的是异步的吗?
可以说, 是的. 不同的网络有不同的特征.
如果
- 您的节点没有时钟(不太可能), 或者它们的时钟可能会偏离(更有可能)
- 系统进程可能会任意延迟消息的传递(由于重试或GC暂停)
那么您的网络就可以被认为是异步的.
Gilbert和Lynch还证明, 在部分同步系统中, 节点共享但时钟不是同步的, 并且每个消息的处理时间都有限制, 因此不可能实现可用的原子性存储.
然而，来自#8的结果在部分同步模型中不成立, 实现始终可用的原子性存储是可能的, 并且当所有消息都不会丢失时可以保证一致性.
原文
Gilbert and Lynch also proved that in a partially-synchronous system, where nodes have shared but not synchronised clocks and there is a bound on the processing time of every message, that it is still impossible to implement available atomic storage.
However, the result from #8 does not hold in the partially-synchronous model; it is possible to implement atomic storage that is available all the time, and consistent when all messages are delivered.
13. FLP 和 CAP 之间有什么联系?
FLP理论(Fischer, Lynch 和 Patterson)是三十年前提出的一个非常有名的"不可能性(Impossibility)"理论, 这个理论确立了共识(一致性, 让所有的节点达成一致)问题: 如果有一个异步网络, 这个网络的节点可能会失效, 那么这种一致性是无法实现的.
FLP理论与CAP理论没有直接关系, 尽管它们在某些方面是相似的: 两者都是对于分布式系统中无法解决的问题的"不可能性"结论. 细节是魔鬼, 下面是FLP与CAP的一些不同之处:
- FLP允许一个节点失败, 这个节点与系统完全隔离, 并且不必响应请求
- 否则, FLP不允许消息丢失, 网络只是异步但是没有消息丢失
- FLP 用于处理共识问题, 这是一个类似的, 但不同于原子性存储的问题
14. C 和 A 是不可调和的吗?
在设计分布式系统时, 可以对一致性或可用性降低标准而实现一个"可用"的系统. 实际上CAP理论的意义在于, 这是不可避免的，任何设计和构建的系统都必须对其中的一项或两项作出妥协. 作为设计者, 则需要弄清楚什么时候并且如何做.
关心一致性的系统会选择降低可用性, 比如ZooKeeper. 其他系统, 例如Amazon的Dynamo, 为了保持高度的可用性, 则选择降低一致性.
如果不能满足CAP理论中的理想状态假设, 就必须重新证明这个不可能性结论.
原文
Once you weaken any of the assumptions made in the statement or proof of CAP, you have to start again when it comes to proving an impossibility result.
15. 一个故障节点是否等效于一个被隔离的节点?
不等效. 一个故障节点通常不需要再响应请求. CAP理论并不允许节点"故障"(这是一个强假设, 因为实际上节点不发生故障是不可能的).
在一个异步网络中当N-1个节点发生故障时, 可以证明原子性存储的不可能性结论. 这个结论会对设计上的权衡造成影响: 是保证写入的节点数量(性能问题), 还是容错能力(可靠性问题)
16. 一个运行很慢的节点是否等效于一个被隔离的节点?
不一样: 消息最终会被传递到一台很慢的节点, 但永远不会被传递到一台被隔离的节点. 实际上, 很难区分消息丢失(节点故障)和节点很慢的情况, 这也是CAP, FLP和其它分布式理论为什么成立的原因.
17. 我是否能绕过或者战胜 CAP 理论?
不能, 您可能设计了一个还未受到明显影响的系统, 这很好.
来源
https://www.the-paper-trail.org/page/cap-faq/, 作者 Henry Robinson
补充
以下的内容不是原文的一部分, 了解这些知识有助于加深对分布式系统的理解
关于时钟一致性
时钟的标准定义是这样的wikipedia
The second is equal to the duration of 9192631770 periods of the radiation corresponding to the transition between the hyperfine levels of the unperturbed ground state of the 133Cs atom.
翻译过来就是: 一秒的时间长度等于铯-133原子基态的两个超精细能级之间跃迁相对应辐射周期的9,192,631,770倍时间长度
- 这个对时间的定义脱离了具体的空间和温度, 是当前对时间最精确的描述
- GPS, 北斗和各国授时中心都是基于铯原子钟时间, 在G频段工作的基站和卫星也会使用原子钟, 出于体积的考虑可能用的是铷原子钟
- 时间是相对的. 原子能级跃迁的辐射频率与重力有关, 重力越大频率越低, 体现在一个海拔为0的观察者眼里, 更高海拔的时钟会走得更快
- 因此严格意义上说, 一致性时钟和全局时脉是不现实的, 你可以对重力的影响做补偿, 但是做不到严格意义的一致.
- 在实际的网络环境还需要考虑到处理器的时钟损耗, 做到极致, 时间同步误差在几十到几百纳秒.
原子一致性是否可行?
严格地说, 不可行.
在实际应用上, 如果将系统限制在一个很小的尺度(几十厘米), 并将允许的误差提高到微秒级别, 这种情况下是可行的. 可以简化为多处理器架构的单机系统.