1. 写在前面
承接上一篇博客:也谈分布式系统中的网络模型和故障模型,本篇博客仍然想探讨一些分布式系统的理论知识。
大家应该都听说过分布式系统理论中的FLP不可能性和CAP不可能三角,那么FLP
和CAP
之间是什么关系呢?等价还是包含?
本篇博客,就想来谈谈FLP
和CAP
之间的关系。
2. 理论回顾
本节先分别回顾一下FLP
和CAP
这两个理论。
2.1 FLP不可能性
Impossibility of Distributed Consensus with One Faulty Process这篇论文对FLP
不可能性的描述如下:
No completely asynchronous consensus protocol can tolerate even a single unannounced process death.
翻译成大白话就是说:在一个异步的网络环境中,即使只有一个进程出现故障,也无法实现任何安全的共识算法。
在这篇论文中,作者也进行了一些假设:
- 节点故障只限定于
crash failure
,不考虑Byzantine failure
(“do not consider Byzantine failures”) - 消息通道是可靠的,消息只可能被延迟,但不会丢失也不会出现错误,且只会被传递一次 (“the message system is reliable—it delivers all messages correctly and exactly once”)
总的来说,这些假设是比较强的假设。因为在如此强的假设下都无法实现安全的共识算法,那么在一些较弱的假设下就更无法实现。因此,FLP
不可能性的适用性更广。
但论文中也指出,如果我们将假设进一步加强:假设网络模型是同步的,那么是可能实现安全的共识算法的。
By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
也就是说,很多拜占庭条件下的共识算法都是在同步网络的假设下进行设计的。之所以同步网络下能实现共识算法,是因为同步网络使得“检测故障节点”成为了可能。
回顾我们在上一篇博客:也谈分布式系统中的网络模型和故障模型中讨论的各种故障模型,FLP
不可能性属于最里面的第二层,如下如所示:
2.2 CAP不可能三角
根据维基百科上的定义, CAP
不可能三角是指:
It is impossible for a distributed data store to simultaneously provide more than two out of the following three guarantees: consistency, availability, and partition tolerance.
翻译成大白话是说:在分布式数据存储模型中,一致性、可用性和分区容错性,只能三者取其二。
CAP
相关的假设如下:
- 故障模型为
Omission failure
,如上图最里面的第三层,即消息的传递无限晚,但有可能恢复(典型表现为网络分区) - 网络可能出现故障,消息可能会丢失(因为需要考虑分区容错性)
这里有必要对Omission failure
故障模型进行解释。实际上,我们已经在上一篇博客:也谈分布式系统中的网络模型和故障模型中的3.1小节解释了网络分区故障和Omission failure
的关系,即:网络分区故障实际上是Omission failure
的一个特例。这里,我们再进行一番解释,以使读者能更好地理解。
- 网络分区故障描述了这样一类故障:网络连接出现了中断,一个网络被分割成了若干个子网络。但是这种分割(网络中断)是暂时的,后期可能会恢复。否则,如果网络一旦断开就永久断开,那么子网络之间就没有任何联系。在每个子网络中分别部署服务就好了,也就不存在一致性和可用性的问题了。
Omission failure
描述了这样一类故障:对于某个特定消息而言,节点A可能永远无法接收到节点B的消息;但对于其他消息,节点A是可能收到消息的。前者表明可能出现了网络故障,后者表明该故障是可自动恢复的。
由此可见,网络分区其实是Omission failure
的一种特例。
3. FLP和CAP的关系
先说结论:“FLP不可能性”和“CAP不可能三角”是两个不等价的理论。
以下借鉴博客History of the Impossibles – CAP and FLP中的内容,介绍FLP
和CAP
的不同。
Properties | FLP | CAP |
---|---|---|
Problem scope | Distributed consensus | Replicated storage |
Failure model | Crash failure | Omission failure |
Formalization | Rigorous | Gilbert & Lynch approximation |
Solutions | Synchronous network model | Crash failure |
3.1 Problem scope
FLP
讨论的分布式共识(distributed consensus
)的问题。分布式共识可实现的功能包括:
- leader election
- replicated state machine
- distributed commit
而CAP关注的是复制存储(replicated storage
)的问题,replicated storage
可以看作是replicated state machine
的一个特例。
可以看出,复制存储是分布式共识的子问题。也即,FLP
关注的问题更加通用,CAP
问题是FLP
问题的子集。
此外,
CAP
中的复制存储问题只讨论了这样一类问题:同一份数据在不同节点上进行存储(主从复制即是这样一类问题);- 而
FLP
中的分布式共识问题除了CAP
中的问题外,还讨论了这样一类问题:多个任务(数据)被调度到不同节点上并行执行(存储),不同节点上的任务和状态可能是不同的(2PC
协议即包含了这样一类问题)。
由此也可见,FLP
中讨论的问题更加复杂。一些方案可能无法解决FLP
中的问题,但可能能够解决CAP
中的问题,如3.2节中的在Crash failure
模型假设下的方案。
3.2 Failure model
正如前面已经讨论过的,FLP
中故障模型的假设更强,因而其得出的“不可能性”结论也适用于CAP
场景(Crash failure
)中;但CAP
得出的“不可能三角”结论就不一定适用于FLP
场景中 (Omission failure
)。
结合我们在3.1节中的比较,容易得到以下结论:
- 在
Omission failure
故障模型中,既不可能达成分布式共识,也无法实现同时满足CAP
的分布式存储 - 在
Crash failure
故障模型中,虽然无法达成分布式共识,也可能实现同时满足CAP
的分布式存储。Quora中的一个回答即给出了这样一种方案设计。
3.3 Formalization
“FLP不可能性”是进行了严格的理论验证的,但“CAP不可能三角”的证明却没那么严格。具体来说,CAP
不可能三角的提出者(Brewer)和后来的证明者(Gilbert和Lynch),他们对于CAP
理论的阐述是不太一致的。也即,证明者所证明的对象,实际上不是提出者一开始提出来的对象。
3.4 Solutions
由于“FLP不可能性”和“CAP不可能三角”分别从理论上论证了,两个问题都是无法完美解决的。
一个很自然的想法是,能够通过增强一下假设,使得该问题得以解决。
- 通过将网络模型增强为同步网络,分布式共识就得以实现。正如2.1节所说,很多解决拜占庭问题的共识算法就是这么做的
- 通过将故障模型加强为
crash failure
,复制存储也就得以实现,正如3.2节所说。
参考链接
- History of the Impossibles – CAP and FLP
- Distributed Systems: Are the FLP impossibility result and Brewer’s CAP theorem basically equivalent?
- Network partition
- 有人了解过FLP impossibility吗?
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985)
- Gilbert and Lynch. Brewer’s conjecture and the feasibility of consistent, available, fault-tolerant web services.
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/6391.html