分类: 分布式系统

超越不可能

相信所有研究过分布式系统的同学都对大名鼎鼎的FLP不可能性有所耳闻,简单来说,FLP不可能性证明了“在可能有哪怕一个进程故障的异步系统模型中,共识问题无法被解决”。但矛盾的是,现在正当红的很多分布式系统,都依赖于底层的共识算法,比如Multi-Paxos、Raft等,难道是FLP错了么?共识问题已经被解决了?还是说我们用的分布式系统都是有问题的?

想要理解这个问题,其实是要搞清楚一件事情:FLP不可能性真正意味着什么?

注:如无特殊说明,本文中的进程故障模型均为crash-stop,通信链路模型为perfect link。

Consensus


首先回顾一下分布式系统中的共识(Consensus)问题是什么。共识问题指在分布式系统中,一个或多个进程提议了一个值应当是什么后,使系统中所有进程对这个值达成一致意见。

一个能够正确的解决共识问题的算法必须满足下面的三个性质:

  • 终止性(Liveness):所有正确进程最后都能完成决定。
  • 协定性(Safety):所有正确进程决定相同的值。
  • 完整性(Integrity):如果正确的进程都提议同一个值,那么所有正确进程最终决定该值。

同步/异步模型


明确了问题,还要看解决问题所用的系统模型是什么样的。

在分布式系统中,最重要的两个系统模型无非就是同步模型和异步模型了。同步模型和异步模型的区别在于对时间的假设,同步模型中消息的传递、进程处理消息所需要的时间都有明确的上界和下界,并且每个进程的本地时间和实际时间的偏移也在一个已知的范围中。而异步模型中没有关于时间的任何假设,是一个没有“时间”概念的模型。

同步模型是理论研究中非常理想的模型,显然的,我们可以在同步模型中用非常简单的方法解决共识问题(各种材料中都会提到,略过),但是在实践中,同步模型是不切实际的,在真实的系统中依靠时间往往是不靠谱的。

这也是为什么我们要研究异步模型的原因:异步模型中的算法是移植性最好的。

在异步模型中正确的算法,在更强的模型中也一定正确,因此,在真实系统中也是正确的。与之相反的是,在同步模型中正确的算法,在更弱的模型中就不一定了,比如3PC算法,在同步模型中解决了2PC的阻塞问题,但是在实践中罕有应用,原因就在这里。

FLP不可能性


在FLP提出之前,有很多研究工作试图在异步模型中解决共识问题,而FLP不可能性的提出,终结了这种尝试。

为了理解FLP不可能性,我们需要主要看一下论文中提出的两个引理:

  • Initial Bivalency Lemma (Lemma 2): Any algorithm that solves the 1-crash consensus has an initial bivalent configuration
  • Bivalency Preservation Lemma (Lemma 3): Given any bivalent config \(\gamma\) and any event \(e\) applicable, There exists a reachable config \(\delta\) where \(e\) is applicable, and \(e(\delta)\) is bivalent (\(\delta=\gamma\) possible)

简单解释一下引理中涉及的几点定义:FLP论文中把共识问题抽象为所有节点要对一个value最终是0还是1达成共识,config指所有节点的状态和网络中的所有消息;bivalent config指最终共识结果可能为0也可能为1的config;event指的是一个节点收到一条网络消息后执行的动作,只有节点收到网络消息后对应的event才是applicable的。

有了这两条引理再看FLP的证明:我们从bivalent config开始(Lemma 2),反复应用Lemma 3,则整体总是处在bivalent的状态,违背了Liveness的要求

FLP不可能性提出后,人们不再尝试寻找异步模型中共识问题完全正确的解法,而是对于提出的共识算法,分析其在异步模型中能够解决的部分。

Failure Detectors


从直观上理解,FLP的证明核心在于:在异步模型中,无法准确的区分一个进程究竟是故障了还是运行的非常非常慢。

那么如果我们能够一定程度的判断出进程故障,是不是就可以解决共识问题了呢?在《Unreliable Failure Detectors for Reliable Distributed Systems》这篇论文中就提出在异步模型中通过使用Failure Detector来解决共识问题。

论文首先给出了Failure Detector的两个属性:

Completeness:

  • Strong: Eventually every process that crashes is permanently suspected by every correct process.
  • Weak: Eventually every process that crashes is permanently suspected by some correct process.

Accuracy:

  • Strong: No process is suspected before it crashes.
  • Weak: Some correct process is never suspected.
  • Eventual strong: There is a time after which correct processes are not suspected by any correct process.
  • Eventual weak: There is a time after which some correct process is never suspected by any correct process.

然后按照这两个属性的不同,定义了8类属性不同的Failure Detector:

Eight classes of failure detectors defined in terms of accuracy and completeness

论文中最为重要的一点的是证明了在异步模型中,Eventuallly Weak Failure Detector是能够解决共识问题所需要的最弱的Failure Detector

当然,FLP是不可突破的,所以Eventuallly Weak Failure Detector在异步模型中是不可实现的,那你可能要问了,研究这个些个模型还有什么用?毕竟互联网是异步模型啊!实际上,这是一个概率问题,在异步模型中共识达成之前的这段时间里,系统也不一定是那么的“异步”,某种实现的Failure Detector(比如论文中举例的实现方法)有极大概率是可以满足Eventuallly Weak Accuracy的要求的,同理,要依赖更强的Accuracy则意味着更低的成功概率。如果实现的Failure Detector在运行中运气不好没有满足算法需要的Accuracy属性,共识问题不可解,但只会影响到算法的Liveness。

在异步模型中,既然Eventuallly Weak Failure Detector足以解决共识问题,那么还有没有其他问题需要依赖更强属性的Failure Detector才能解呢?答案是有的,比如拜占庭将军问题,就必须要有Perfect Failure Detector的帮助才可以解决。

换言之,通过对这些不同强度的Failure Detector的分析,我们能够定义出一些比异步模型更强的模型:

Problem solvability in different distributed computing models

如上图,在异步模型的基础上增加不同的Failure Detector,能够更加准确的定义特定问题可以被解决的模型,填补了同步模型到异步模型之间的灰色地带。除此之外,还有一些其他的研究工作也做了类似的模型定义,例如半同步模型,实际上和这篇论文背后的想法是相通的。

工程实践


现在工程实现中常用的共识算法,都是Paxos及其变种,我们已经知道了FLP算法结论是不可突破的,回顾Paxos算法,在异步模型中,由于活锁的存在,Paxos算法并没有完全解决共识问题(Liveness不满足)。

但是这并不妨碍Paxos算法在各种分布式系统中大行其道,原因就在于上面提到的分析,即使在异步模型中,在达成共识之前,系统并没有那么“异步”,我们仍有极大的概率是可以达成共识的。

这体现了理论研究和工程实践之间的一个“鸿沟”,理论研究中的不可能结论,是在追求100%可解的基础上得出的,在工程实践中,我们可以用一个99.99%的概率可解的算法(剩下的0.01%的场景下由于Liveness不满足,需要更长的时间),也足够好了。

参考资料


[1] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process[R]. Massachusetts Inst of Tech Cambridge lab for Computer Science, 1982.

[2] Guerraoui R, Schiper A. Consensus: the big misunderstanding [distributed fault tolerant systems][C]//Proceedings of the Sixth IEEE Computer Society Workshop on Future Trends of Distributed Computing Systems. IEEE, 1997: 183-188.

[3] Chandra T D, Toueg S. Unreliable failure detectors for reliable distributed systems[J]. Journal of the ACM (JACM), 1996, 43(2): 225-267.

[4] Impossibility of Consensus