常见的分布式协议与算法【转】 (4)

谣言传播 (Rumor mongering):指的是当一个节点有了新数据后,这个节点变成活跃状态,并周期性地联系其他节点向其发送新数据,直到所有的节点都存储了该新数据。由于谣言传播非常具有传染性,它适合动态变化的分布式系统

img

Quorum NWR算法

Quorum NWR 中有三个要素,N、W、R。

N 表示副本数,又叫做复制因子(Replication Factor)。也就是说,N 表示集群中同一份 数据有多少个副本,就像下图的样子:

image-20200705173603964

在这个三节点的集群中,DATA-1 有 2 个副本,DATA-2 有 3 个副 本,DATA-3 有 1 个副本。也就是说,副本数可以不等于节点数,不同的数据可以有不同 的副本数。

W,又称写一致性级别(Write Consistency Level),表示成功完成 W 个副本更新。

R,又称读一致性级别(Read Consistency Level),表示读取一个数据对象时需要读 R 个副本。

通过 Quorum NWR,你可以自定义一致性级别,通过临时调整写入或者查询的方式,当 W + R > N 时,就可以实现强一致性了。

所以假如要读取节点B,我们再假设W(2) + R(2) > N(3)这个公式,也就是当写两个节点,读的时候也同时读取两个节点,那么读取数据的时候肯定是读取返回给客户端肯定是最新的那份数据。

关于 NWR 需要你注意的是,N、W、R 值的不同组合,会产生不同的一致性效 果,具体来说,有这么两种效果:

当 W + R > N 的时候,对于客户端来讲,整个系统能保证强一致性,一定能返回更新后的那份数据。
当 W + R < N 的时候,对于客户端来讲,整个系统只能保证最终一致性,可能会返回旧数据。

PBFT算法

PBFT 算法非常实用,是一种能在实际场景中落地的拜占庭容错算法。

我们从一个例子入手,看看PBFT 算法的具体实现:

假设苏秦再一次带队抗秦,这一天,苏秦和 4 个国家的 4 位将军赵、魏、韩、楚商量军机 要事,结果刚商量完没多久苏秦就接到了情报,情报上写道:联军中可能存在一个叛徒。这 时,苏秦要如何下发作战指令,保证忠将们正确、一致地执行下发的作战指令,而不是被叛 徒干扰呢?

需要注意的是,所有的消息都是签名消息,也就是说,消息发送者的身份和消息内容都是 无法伪造和篡改的(比如,楚无法伪造一个假装来自赵的消息)。

首先,苏秦联系赵,向赵发送包含作战指令“进攻”的请求(就像下图的样子)。

image-20200705175931531

当赵接收到苏秦的请求之后,会执行三阶段协议(Three-phase protocol)。

赵将进入预准备(Pre-prepare)阶段,构造包含作战指令的预准备消息,并广播给其他 将军(魏、韩、楚)。

image-20200705194136691

因为魏、韩、楚,收到消息后,不能确认自己接收到指令和其他人接收到的指令是相同的。所以需要进入下一个阶段。

接收到预准备消息之后,魏、韩、楚将进入准备(Prepare)阶段,并分别广播包含作战 指令的准备消息给其他将军。

比如,魏广播准备消息给赵、韩、楚(如图所示)。为了 方便演示,我们假设叛徒楚想通过不发送消息,来干扰共识协商(你能看到,图中的楚 是没有发送消息的)。

image-20200705194247539

因为魏不能确认赵、韩、楚是否收到了 2f(这里的 2f 包括自己,其中 f 为叛徒数,在我的演示中是 1) 个一致的包含作战指令的准备消 息。所以需要进入下一个阶段Commit。

进入提交阶段后,各将军分别广播提交消息给其他将军,也就是告诉其他将军,我已经 准备好了,可以执行指令了。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzdyzz.html