分布式一致性算法

  • pqdong 

   区域链的技术核心,便是共识算法的应用,在分布式系统中,一致性是一个重要的指标。区域链可以看做是一个分布式系统在加密货币领域的应用,共识算法是每个区域链网络的关键要素,他们负责维护这些分布式系统的完整性和安全性。第一个被创建出的加密货币共识算法是工作量证明(PoW),它由中本聪设计并在比特币上实现,用于实现拜占庭容错。

   拜占庭将军问题是在N个将军指挥的军队中有N/2以上的将军行动一致才能取得胜利,然而将军中存在叛徒,通过什么样的算法才能实现行动一致那。从计算机理论上来讲,我们可以建设有M个叛徒将军,已经证明当N<=3M时是不可解的。那么当满足N<=3M时有什么比较好的算法能完成这一问题哪。

在区域链共识算法提出之前,理论上有两种解决方法,分别可以描述为口头协议和书面协议,其中口头协议是指每个消息都能被正确的传递,而且不传递消息会被检测出来,并且接受者知道消息来源。这种口头协议的缺点在于不知道上一个消息的源头来自哪里。书面协议能够使用签名技术,且不可以篡改,可以通过检验签名可靠性,这种方法虽然可以溯源,但是却因为签名机制的原因,难以拜托中心节点的中心化机构。而且网络中的延迟也为此种方法可行性带来了困扰。

在工程实践上,cap理论指出:在分布系统中不可能同时满足一致性,可用性,和分区容错性。在强一致性的算法中,主从复制模式,主等待从的过程其实就是一个牺牲了可用性的过程。Paxos算法也是基于消息传递且具有高度容错特性的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一。Paxos算法分为两个阶段。具体如下:

阶段一:

(a) Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求。

(b) 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案。

阶段二:

(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意:V就是收到的响应中编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案。

Poaxs算法虽然完美,但是实现起来复杂,因此工业界大多(zookeeper)使用zab算法,它分为两个过程,第一个过程,可以crash的leader需要持久化自己的状态信息,然后向follow发送消息,只需要半数以上的follow追随即可,相比poaxs没有复杂的多个阶段的提议,意见只由leader提出。而且leader在向follow发消息时使用的是类似两阶段提交的策略,只要半数同意即可确定。另一个阶段就是leader的选举,leader的选举采用的是poaxs算法,最大的问题就是新老交互的问题 。

而中本聪提出的去中心化的区域链算法,通过工作量证明,即议案的提出由最先完成工作的人提出,其余未完成工作的人必须跟随并且同意此提案,与上边的分布式一致性算法相比我们可以看出区域链去中化算法的优点,但是此算法也存在着明显的缺点就是需要大量的工作计算,甚至重复计算,从而浪费了大量的计算资源,电力资源等等。

发表评论

电子邮件地址不会被公开。 必填项已用*标注