一、背景

这种高压变压器的主要特点是:

• 利用一个明确的链路拓扑结构管理模板,数据流在这一方向流动

• 减少消息复杂性,在高客户负载的情况下增加吞吐量

• 无第三方服务支持的自载复制配置管理membership，使reconfiguration更加流畅

• 任何副本都可以处理读取请求,并实现线性读取,不需要任何额外的通信,因此读取请求可以平衡地载入每个副本

通过链上结构,复制品可以高效地依赖pipeline模式进行数据传递，这一点在ChainReplication中已经得到了证实。

通过pipeline交流模式，ChainPaxos可以压缩广播消息到点到点数据传输,有效减少信息的复杂性,提高系统的吞吐量。然而链式的消息传递的流程会随副本数量的增加而线性延长，因此,在低客户负荷的情况下,延迟并不是一个优势。

在同步系统中,ChainReplication可以依赖链尾复制品以线性读取,并且当链尾复制品崩溃时,它可以选择它的前身来读取请求。

ChainReplication的同步流程如上图，客户端将写请求发往leader，leader处理后将该请求按照副本链进行传递，当链尾副本处理完后可以直接响应客户端，然后将ack反向转到垃圾回收(无用的信息清洗)的链头。

而在异步的系统中，实现线性阅读往往需要额外的成本,最常见的方法是将读取操作应用为帕克斯实体,系统还需要就读操作的位置达成协议,因此 需要 增加 通讯 费用 。此外，若在利用第三方服务进行副本成员管理（如Zookeeper）的情况下，通过单节点提供线性读取,网络分离时可能出现问题,因为主要服务机构不能自然地感知成员的变化。

这是一个分布式系统的一个例子R1、R2、R3三个副本，利用Zookeeper进行成员管理。在某一时刻，由R3为了提供阅读服务,突然出现了网络分区,R3它是孤立的,但它仍然可以向客户提供服务,即使动物园主确实如此reconfiguration,如果限制不够,读取请求可能继续输入R3去旧数据吧,因为每次阅读请求之前我们都不能一次去动物园监护员看看成员是否改变了,这太贵了

ChainPaxos可以实现任意复制的线性读取,不需要额外的信息交流,但以较长的延误为代价。

二、算法实现

流程概况

首先, ChainPaxos过程在下图所示:

在上图中，构成了Rep1 -> Rep2 -> Rep3的副本链，其中Rep1是链首，也就是ChainPaxos中的leader，客户端的写请求会被直接发向（或转发至）leader进行处理。当Rep1收到客户端的写字请求后,它将进入下一个链接节点Rep2发送accept信息以及accept-ACK信息；当Rep2收到信后,他将自己带走accept信息、Rep1的accept信息、自己的accept-ACK信息、Rep1的accept-ACK将信息传递到下一个副本Rep3，依次类推；当链尾处理完信息后，直接将所有的accept-ACK给链路的一次发货。 此外,accept-ACK在消息传递过程中,复制品在达到分数时第一次向客户作出回应。

看起来很复杂,但实际上很简单,MultiPaxos可以理解为多组的简化版本。在逻辑上，每个副本都是一个小组的提案者,其他副本是收件人,但是它不使用像 SDPaxos那样的多个实例域,相反, 我们共享一个例子领域.因为这个建议只能来自链路,消息的流也是固定的,也就是说,即使每个组都与一个实例域相符,他们的实例域的顺序顺序也是一致的。物理上(例如域设置和消息流),多组的共识被压缩在一起;在逻辑上,我们可以把它看作是单独的,只是信息的意义更丰富。

在pipeline在发送信息时,每个副本都会有自己的accept消息和accept-ACK数据流中添加的消息是发送自己的“群”到副本后部的accept邮件2是先送回一份副本的accept消息做出应答。

在发送消息时,消息accept以及accept-ACK你积累越多, 它就越流入一本书里.R1的消息ack当它累积到 quorum (包括自己) 时,副本可以提交命令并响应客户端(如上面所示)Rep2），很明显，R1后面副本收到的ack达到 quorum更容易,因此可以直接提交(无需对客户重复答复),当消息流到链路末端时会积累ack连接到链子, 这样链子可以提交和回收.

在上面的图中,实际上有些误导,这里我们正在扩大星团的大小,假设有Rep1、Rep2、Rep3、Rep4、Rep5五个副本，副本链为Rep1 -> Rep2 -> Rep3 -> Rep4 -> Rep5，其中Rep3、Rep4、Rep5这些三份文件是在转发信时提交的,Rep1在收到 chain 末端的最后答复后提交,但Rep2并无法在这一轮的消息流动中提交。因此，在正向的消息传递中，应包含已经提交的命令的语义，Rep2然后,这个命令可以在发送 chain 的下一轮开始的消息中提交(类似于在草案 appendEntries 中 committedIdx )。

主流程实现细节

下面的图表描述了该副本的状况:

第一个组用于成员管理,chain所有复制链中的复制(顺序阵列),self为自己的标识符，c_nextok没有标记的链中的副本的下一个副本(签名为reconfiguration这位代表即将被解雇。_sleader领导的标识符,marked要标记的一套副本(用于使用reconfiguration这位代表即将被解雇。

第二组用于帕克斯过程,np_leader这是我看过的最大规模的选票。inst例如序列,每个实例的属性有: n_a对 与 这个 例子 有关 的 投票,val为提议值，
n_acpts接受订单的副本数目,decided为该instance是否committed的标志位。

第三组是临时存储请求,submitted临时客户端的相应命令没有收到提交响应,pending暂存leader收到的来自客户端或其它副本转发的未被submit（处理）（注意submit和commit是不一样的）的命令对应的请求。

第四组用于保持某些需求的状态,max_ack代表最大接收器响应的实例索引(事实上,被承诺的Idxofraft),max_acpt代表了最大被理解的实例指数(实际上是下一个Idx草案),amLeader指示副本是否是一个领导者(而不是链)。

下面的图表显示了正常的信息流伪造代码:

任意副本都可以接收客户端发来的请求，并将其转发至leader（Alg2 第1行），然后leader会将其保存至pending(第2章,第5页) 当领导处理请求时,首先增加最大值_acpt然后开始将信息从它本身向正确的方向移动(Alg 2,行11),即:accept消息流的处理。

首领首先接受他自己送来的accept消息(第2段13行):

• 第十四行:确定选票是否有效,并忽略你见过的最大选票以下的请求

• 15行：如果见到了更大的ballot，则需要更新副本见过最大的ballot以及新主等信息（类似raft的stepdown）

• 第16至17行:无冲突地表决和记录accept该实例的副本数（n_acpts+ 1）

• 行18-19:如果有冲突,请更新accept该实例的副本数（此时可能产生membership的变化，随之该副本在链中的位置可能发生变化，也可能重复接收了该信息，所以要在inst[n_i].n_acpts(复制品的位置在链条中保持不变)及_acpts+ 1（membership发生了变化）中选择最大的那个）

• 20-21行：membership变动所需，若命令为membership的移除，则为要移除的副本打上标签

• 行22-23:如果已达到法定数额,则可以执行命令

• 第24行:先发承诺的进度,先列在副本数目中n如果超过3(是奇数),(1 , n/2]之间的副本无法在一轮消息流动内提交，需要leader发起下一次消息流动后才可以提交，指的就是这里（类似于raft中appendEntries中的committedIdx）

• 行25:将消息移动到链中的下一个复制节点

链尾在处理完消息后，会向leader发送一个应答，leader感知到该应答后会推进commit的进度（Alg2 第27行）。

• n_acpts指明先前的副本对后续的副本的反应,如副本发现 n_acpts当你达到法定人数时,你可以直接承诺
• m_ack所有提交的实例的全部响应意味着复制可以安全地一次性提交_ack所有以前未提交的命令(如附件中 committedIdx和草案中的Entries)都可以这样做,因为ChainPaxos不允许未排序的提交

故障处理以及reconfiguration

每一个副本A都会定期发送keep-alive向其链的第一份副本发送消息B，如果B如果你在一定时间内没有收到消息,你可能会怀疑一份副本A失败发生并试图删除它(请求领导)RemoveNode(A)我们认为,链子需要定期发送keep-alive消息被发送到链条的尾部,当尾部怀疑领导不正常时,它也开始了选举过程(准备阶段)。

当一个RemoveNode(A)操作被副本Bcommit（decided）后，B副本就可以更新chain和marked等待信息(Alg 3-2426)。

在异步的系统中，复制可能被误解为失败(可能只是网络拥挤),但ChainPaxos没有考虑到这些,ChainPaxos受到缓慢节点的影响,复制品是否真的失败,只要它被怀疑，那么它一定慢，这阻碍了整个链路的信息的流动,先移除了再说。若该节点是正常的，它可以稍后添加。

此外，如果一个副本在一定时间内没有接收到消息流，则会怀疑leader故障，自己尝试选主（Prepare），因此leader在空闲时应该每隔一段时间发起一次no-op的消息流（说白了就是heartbeat）。

以下图示了一些辅助函数的伪码:

注意上面第11行ACCEPT消息有笔误，参数leader和n_i的位置反了

复制品从链子里搬出主要由两个阶段组成,第一阶段是标记阶段，当一个副本收到RemoveNode当命令执行时,首先将节点标记删除并从信息流中排除(此时chain没有删除节点,只是添加到marked然后将其上节点改为下节点(作为未标记节点)以确保信息可以贯穿整个链路;第二阶段是移除阶段，当该RemoveNode当命令提交时,复制品将从链上物理上删除(此时chain和marked中都移除该节点）。

首先看看Alg3中的相应的第一个行MARKFORREMOVAL相应的函数是标记阶段：

• 行2:将添加一个要移除的节点marked

• 行3:如果要删除的节点是当前节点的下一个节点,则需要特殊处理(4-6行)

• 4行：将待移除节点先从逻辑上移出链，也就是将该节点的下一个节点换成下一个没有被标记的节点，使链可以正常流通，也保证了待移除节点后续不会再为提案投票

• 5-6行：存在待移除节点还有数据没能流向下一个节点的可能，因此该节点需要将还未提交（同时也就是还未垃圾回收）的提案往新的下游节点再发一次

标记记录要移除的节点的集合,这些节点是逻辑上被移除的(消息不会向它们发送)

由于数据的流向是固定的,顶部必须比底部有更多的建议。 假设链 existsA -> B -> C -> D，此时我们要移除C，但存在提案集合S由于C故障没有发往D为了尽可能确保数据的完整性,B未提交的建议将转交D(即在行 5-6 中完成)因为B一定知道所有C知道的提案（B在C..但是根据假代码的模式,它可能导致D一个洞出现了, 就是一系列的建议.S'由于C故障没有发往D，但B现已提交部分或全部S'中的提案，此时即使B如果再转播,可能有鱼漏到网里

第二个是Alg3中的24-26行,这与移除阶段事实上,当命令提交时,节点的物理移除将被移除,而复制品不再能够感知节点的移除。

然后通过其他辅助功能:

Alg3 第7行的FORWARD，用于数据的流转：

• 8-9行：若当前副本为链尾（也就是下一个副本是leader（链首）），就会向leader发送一个应答，通过n_i表达当前n_i没有,例已获得答复的全部副本,领导可以提交

• 线10-11:其他节点被指向下一个节点

Al3行12UPDATELEADERINFO,用来在复制后改变主人的状态,不用说太多(类似下级的原稿)。

阿爾3線22號DECIDE承诺和采取行动,达成 quorum 建议:

• 23行：表示该提案已被decide（commit）

• 行24-26:如果递交的订单是RemoveNode该命令将被删除,直到节点完全被删除

• 行27-31:如果递交的订单是AddNode该命令将添加的节点添加到链上并更新当前节点的下一个未标记的节点。如果当前节点的下一个节点是添加的节点,它将被发送到它的状态(通常用于闪光和存储中的复制的状态信息(包括示例序列等))

• 33行:通过关闭等执行用户状态机状态转换的命令

• 行34:完成应用程序的命令在pending中移除

Al3行35DECIDEANDGCUPTO,促进提交的进度(同时处于链路中(1 , n/2]原先在该回合提交的地点未提交的建议的副本:

• 行36-39:为n_i在提交建议前直接提交和申请操作

• 40行：更新max_ack，用于下游副本的DECIDEANDGCUPTO

选举

选举过程比较简单,如果一封信怀疑领导失败,可以转发给另一封信Prepare请求来拉票选举。需要注意的是，新ballot的选择要足够大，为下一个未感知的实例的索引即可，同时要注明副本标识，以防ballot重复。

当副本怀疑领导失败时,它将被叫TRYBECOMELEADER,开办选举(第4行第一行):

• 行2:生成选票

• 行3:将所有副本发送到链上Prepare请求

需要注意，Prepare请求中的max_ack+1用于尝试通过Prepare就未提交的建议达成协商一致意见(回收)

当副本接收到Prepare留言后(Alg 4 4行):

• 第五行:评判投票是否比前任领袖大

• 降级

• 行7:副本获得候选人自己的最大数额_ack+1后收到的建议(恢复部分建议)

• 8行：给候选人响应

收到候选人的答复(行4)后:

• 第十一条:评判投票是否比前任领袖大

• 12行:记录投票数目

• 第13行:如表决达到分数,继续第14至17行

• 行14:领导签名位置真

• 15-17行：对投票人发来的未committed但accepted的实例进行恢复，对每个实例选取ballot最大的值进行恢复

新增副本

新增的副本A将发送AddNode(A)给leader，当A加入该组后,它成为链路的结局,并要求承诺AddNode(A)节点将快照和部分状态转移到背景,A消息可以本地处理。

线性读

为了实现线性读取,我们首先需要保证读结果可以作为一种状态的反应,最简单的方法是把操作读作建议,可以commit，虽然执行读取操作不会引起状态变化,但我们可以清楚地知道读取操作在操作序列中在哪里。然而,这种方法的成本更大,阅读操作也需要通过paxos达成协议,在阅读密集型系统中效率较低。

换种说法，线性读取需要符合接收读取请求的远程复印状态的目标值,而ChainPaxos可以确保,当新的信息准备通过链路流动时,所有副本都处于相同的状态。因此，当复制品收到读取操作时,ChainPaxos将读取操作上传到复制不能检测的第一个实例(如果当前的复制检测到最近的实例,则下文是i,然后接收的读取操作被上传到i+1),在读取操作时加载的实例收到对应ack然后可以提交读取操作并对客户端作出响应。

在论文中,信息通过链路过后,整个链路中的副本的状态应该是相同的,因为最大_ack但是,链子的后半部分状态可能需要更新超过前半部分,因为链子的后半部分的拷贝不会在下一个消息中等待最大值_ack它可以直接提交,但感觉有点问题

然而,当客户端负载低时,这个模式有一定读取延迟。因为在提交下一个副本时需要执行读取操作,换句话说,虽然阅读操作不会产生额外的通讯成本,依靠接下来的新闻流,这就是为什么 ChainPaxos读取操作可能最早被延迟的原因。但为了别的副本不能怀疑领导人的错,leader会每隔一段时间发起一次no-op因此,消息流,读取操作可以在有限的时间里执行。 每个间隔设置一个领导t毫秒发送一次no-op在最坏情况下,即当客户端负载低时,消息流需要2t不能以毫秒(第一次)响应no-op流只能accept或commit在第二个消息流中上传的实例不会收到ack（即max_ack),然后进行读取操作。

三、总结

ChainPaxos使用链上结构,通过pipeline该模式传送信息, 信息复杂度低, 客户可以在高负荷情况下提供高吞吐量, 内部会员管理, 实现负荷平衡线性读取.

本文由 在线网速测试 整理编辑，转载请注明出处，原文链接：https://www.wangsu123.cn/news/31515.html。