找回密码
 立即注册
查看: 252|回复: 0

通过划分法优化共识算法-“Scaling Replicated State Machines ...

[复制链接]
发表于 2022-9-22 11:24 | 显示全部楼层 |阅读模式
Scaling Replicated State Machines with Compartmentalization
一、背景

目前,为了解决状态机复制算法在各种场景或者机制中的瓶颈,相关从业人员设计了大量状态机复制算法的变体。然而,这些变体在解决一个问题的同时往往会引出新的问题(如ChainPaxos为解决无额外通信的线性读,牺牲了读操作的响应时间),或引入更强的约束(Mencius为打破leader的瓶颈,要求更严格的网络环境,不允许消息的乱序)。论文针对这个问题,提出划分技术,打破了从业人员对MultiPaxos不能scale的观点。划分技术通过较为全面的方式,对SMR算法进行优化,而不明显对其它性能产生额外的牺牲。
论文主要对MultiPaxos划分后进行scaling优化,但需要注意的是,划分是一种思路,并不局限于MultiPaxos,可以推广到其它SMR算法,甚至可以应用到其它领域的算法中。
二、前提

首先,我们需要知道为什么从业者认为MultiPaxos不能scale。这里我们假设系统能容忍f个节点的崩溃故障。

  • 为什么增加proposer的数量无法提高系统的性能:在MultiPaxos中,只有leader处理来自客户端的请求,和proposer的数量无直接关联,proposer数量的增加甚至可能会降低leader选举的效率;
  • 为什么增加acceptor的数量无法提高系统的性能:增加acceptor会给leader处理消息产生更大的压力(leader需处理更多来自acceptor的消息),而且根据majority,每个acceptor始终都需要处理至少一半的命令,增加acceptor并不能分担其它acceptor的压力;
  • 为什么增加replica的数量无法提高系统的性能:增加replica会给leader广播消息产生更大的压力(leader需发送给更多副本learn消息),且每个replica都需要提交且应用所有的命令,所以增加replica并不能分担其它replica的压力。
三、实现

论文主要提供了六种划分MultiPaxos的方式,如下图:


1. Proxy Leaders

众所周知,leader是MultiPaxos的瓶颈之一。在正常流程中,对于客户端提交的一个命令,leader至少需要发送f+1个accept消息给acceptor,接收f+1个来自acceptor 的accepted消息,并发送f+1个learn消息给replica,算上来自客户端的消息,一共需要处理3f+4个消息。而acceptor只需要处理2个消息,replica需要处理1或者2个消息(其中一个replica需要对客户端做出响应)。而且leader需要处理来自客户端的所有请求,这样的计算倾斜使leader很容易成为系统的瓶颈。
MultiPaxos采用唯一的leader的一个好处是,leader拥有global view,可以独断地将客户端发来的命令分配到日志的某一槽上,从而高效地对命令进行排序。如果增加leader的数量,MultiPaxos就会退化为最基础的Paxos流程,副本间需要对命令的排序也达成共识(即Prepare阶段,为某一个日志槽预定所有权),退化为两阶段提交,还可能产生冲突。论文认为leader的主要职责可以被分为排序以及广播,既然排序不能scale,那就scale广播,因此引出了proxy leader的概念。



需要有至少f+1个节点承担proxy leader的角色,该角色分担了leader的广播职责,当接收到客户端的请求时,leader只需将该命令分配到一个日志槽上,之后通过轮询等方式将广播的任务分摊到proxy leader上。这样一来,对于一个命令,leader只需要处理两个消息,proxy leader则会均匀地承担3f+4个消息的处理。
很明显,关键路径上leader节点的任务量大大降低,通过增加proxy leader的方式可以将之前leader的广播负载均匀地分摊到多个节点上,因此proxy leader是可以scale的。
2. Acceptor Grids

一般来说,MultiPaxos的Prepare阶段和Accept阶段都需要收到majority(f+1)的acceptor的响应后才能继续进行,即read quorum以及write quorum都为f+1。一般认为,在容忍f个副本故障的系统中增加acceptor的数量并不能提升系统的性能。一是acceptor数量的增加会加剧leader处理消息的压力;二是acceptor数量的增加并不能降低acceptor的压力(在副本数为n的系统中,假设quorum为m(一般m会随着n的增加而等比增加),无论怎么增加acceptor的数量,每个acceptor都至少需要处理m/n的命令)。
假设一个系统的read quorum为r,write quorum为w,我们认为只要满足r + w > n,任意的read quorum和write quorum便有交集,即可保证每一次的读都能读到达成共识的值。当然,我们需要保证w > f以保证数据的一致性。majority为该情况下的一种特例。 然而,这种仅仅以数量或者比例约束quorum的方式,并不能通过增加acceptor的方式提高系统性能。
因此,论文采用flexible quorum的方式,将quorum构建成一个r × w的的网格(其中r和w都要大于f),任意列为write quorum,行为read quorum。通过网格中任意行和列都一定相交的特点,保证即使在r + w < n的情况下,任意的read quorum以及write quorum间都有交集。结构如下图所示:
这里感觉有点问题,r × w中r和w应该是quorum的数量,而不是quorum中节点的数量,为什么还需要大于f?



实际上,r + w > n通过数理逻辑的方式保证任意的read quorum以及write quorum间都有交集,此时quorum并不一定需要指定副本,只要满足数量即可;而Grid的方式则是通过网格结构的特点保证read quorum以及write quorum间有交集,但是每个quorum都是确定的。
基于网格的结构下,我们可以将新增加的acceptor组成write quorum加入网格中,这样,我们在增加acceptor数量的同时只需要增加read quorum,而不需要增加write quorum。由于每个acceptor至少处理w / n的命令,因此在Acceptor Grids的情况下增加acceptor的数量可以降低acceptor的压力,提高系统性能。
3. More Replicas

这个优化比较好理解,当replica应用完命令后,会有一个副本负责对客户端做出响应,因此每个replica响应给客户端的次数平均下来为1 / n。虽然增加replica的数量不能降低每个replica应用命令的数量,但是可以减少每个replica响应客户端的次数。



4. Leaderless Reads

MultiPaxos通过一个有序的日志序列保证操作的有序性,为了实现线性写,每个写操作都会被分配到一个日志槽中。实现线性读的关键是读操作能反映一个状态,最简单的实现方式是也将读操作分配到日志槽中并达成共识。然而,读操作并不会改变状态机的状态,通过对读操作分配日志槽并达成共识的方式开销太大,因此论文提出将write path和read path进行划分。
划分后,写操作的执行与之前一样,但读操作采用Paxos Quorum Reads(PQR)的方式进行。在进行读操作时,客户端首先向一个read quorum发送PreRead消息,acceptor接收到该消息后会将自己已经投过票的最大的日志槽的索引wi响应给客户端,客户端选取最大的wi作为i。然后向任意replica发送Read(x, i)消息,当replica日志槽中第i个命令应用后,对x进行读取并响应给客户端。如下图:



这里的逻辑比较清晰,最开始发送PreRead消息给read quorum是为了获取整个系统中最新的日志槽i,然后便可以将该读操作挂载到该日志槽上,此时该读操作可以反映日志槽i对应的状态而不需要自己占一个槽。因此实现线性读。
此时,增加read quorum的数量(注意不是read quorum中节点的数量),可以在读密集的系统(如:Chubby(写操作小于1%)、Spanner(写操作小于0.3%))中将PreRead消息负载到更多的read quorum中从而分摊压力。
5. Batchers

将命令分批处理是提高系统吞吐量的一个有效手段,客户端发送请求给leader时,leader会对请求进行积攒,当达到一定数量或超时后统一发送给acceptor进行处理,如果batch的大小为10,那么系统整体可以减少十倍的消息数量。如下图:



需要注意,replica需要响应给参与该batch的所有客户端
主链路中leader后的角色都可以享受到这种优化带来的好处(降低每个命令需要处理的消息数),但leader却被赋予了分批的职责,此时加重了leader的负担。
此时leader的职责主要有batching以及给batch排序。如同proxy leader时的思路,论文将这两个职责进行切分,引入Batcher角色,由Batcher对请求进行batching,达到阈值后发送给leader对batch进行排序,其它流程不变。如下图:



显然Batcher之间是并行工作的,所以增加其数量能有效降低其压力。
对于读操作也类似,首先通过Batcher对读请求进行batching,然后统一对batch进行PreRead,这样一个batch中的读请求都会挂载到同一个日志槽上。
6. Unbatchers

由于replica需要响应参与某batch的所有客户端,这就导致如果batch的大小为n,那么replica在响应时就需要一次发送n条消息。这导致replica可能成为瓶颈。
在引入Batch后,replica除了应用命令进行状态转换之外,还需要进行batch响应。论文将这两个职责进行拆分,引入Unbatcher角色。此时relica只需应用命令,将响应发送给unbatcher,然后由unbatcher对客户端进行响应。如下图:



unbatcher的工作是并行的,因此增加其数量可以有效降低其负担。
四、总结

论文采用了划分的方式从不同维度对MultiPaxos的瓶颈进行优化,使其支持scale。同时,优化路线是层层递进的,逐渐消除可能新产生的瓶颈,但这也导致单独讨论其中一种优化意义相对不那么大。
MultiPaxos中leader的瓶颈太过明显,在一般情况下,leader限制了其它角色的能力,仅仅消除leader的瓶颈便可以较好地提升系统的吞吐量。同样的,在没有解决leader瓶颈的前提下,使用其它优化可能并不会有很好的效果。
当然,最终leader和replica还是可能成为瓶颈。因为leader的排序以及replica的状态转移一定会出现在执行的关键路径中,而为了保持排序的独断性,我们无法通过scale的方式对排序进行优化(当然可以增加sequencer的数量,但需要对命令的排序额外达成共识)。同样,为了保证数据的完整性,无法通过增加replica的方式分摊replica状态转移的负担,每个replica都需要完整应用所有的命令。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

×
懒得打字嘛,点击右侧快捷回复 【右侧内容,后台自定义】
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Unity开发者联盟 ( 粤ICP备20003399号 )

GMT+8, 2024-11-24 10:33 , Processed in 0.091956 second(s), 26 queries .

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表