IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 区块链 -> 通过划分法优化共识算法-“Scaling Replicated State Machines with Compartmentalization”详解 -> 正文阅读

[区块链]通过划分法优化共识算法-“Scaling Replicated State Machines with Compartmentalization”详解

通过划分法优化共识算法-“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+1accept消息给acceptor,接收f+1个来自acceptor
accepted消息,并发送f+1learn消息给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的的网格(其中rw都要大于f),任意列为write quorum,行为read quorum。通过网格中任意行和列都一定相交的特点,保证即使在r + w < n的情况下,任意的read quorum以及write quorum间都有交集。结构如下图所示:

这里感觉有点问题,r × wrw应该是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都需要完整应用所有的命令。

  区块链 最新文章
盘点具备盈利潜力的几大加密板块,以及潜在
阅读笔记|让区块空间成为商品,打造Web3云
区块链1.0-比特币的数据结构
Team Finance被黑分析|黑客自建Token“瞒天
区块链≠绿色?波卡或成 Web3“生态环保”标
期货从入门到高深之手动交易系列D1课
以太坊基础---区块验证
进入以太坊合并的五个数字
经典同态加密算法Paillier解读 - 原理、实现
IPFS/Filecoin学习知识科普(四)
上一篇文章      下一篇文章      查看所有文章
加:2022-09-04 01:17:05  更:2022-09-04 01:18:03 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年6日历 -2024/6/17 5:45:11-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码