解决了什么

分片区块链是一种通过将节点分组（即分片）来并行处理不相交的交易，从而显著提高吞吐量的区块链技术。

分片技术

分片机制基础

然而，现有的分片区块链并没有很好地满足多样化的【交易】的延迟要求。

交易往往要求区块链的延迟率非常低。

论文指出，有三大挑战阻碍了分片区块链成为实时交易处理系统，分别是静态区块大小、先来先服务的交易打包策略以及负载不平衡。

三类等待延迟

由静态块大小引起的等待延迟
- 大多数区块链在其配置文件中设置了一个限制每个区块所能包含的最大$Tx$数量的固定值。
  - 例如：FISCO BCOS 限制一个区块最多容纳 1000交易；fabric限制最多容纳 500交易
- 这样的【静态块】大小没有考虑到事务数量限制和系统吞吐量之间的平衡。
  - 较大的块大小增加了吞吐量，但同时也增加了块形成时间
  - 较小的块使得整个区块链的共识区块数量增加，但共识能力有限，吞吐量会减少
- 如果分片系统使用【完全动态块】大小，
  - 在每一轮中，每个分片具有不同的块大小（即具有不同的交易数量）。因为最终需要汇总所有的分片到主链，小的分片块会等待大的分片块的形成，这也可能会导致后续的交易延迟。（木桶效应，一轮的时间是性能最慢的那一个）
先到先服务的交易打包策略导致的等待延迟
- 大多数区块链使用“先来先服务”的策略进行交易打包，先到的交易先加入区块中
- 未考虑到紧急事务的需求：到达较早的非紧急Txs先被打包，而到达较晚的紧急Txs只能等待。
- 冲突事务的同块处理：如果将大量相互冲突的Txs (即读写集相交的Txs) 打包成一个块，这会增加块的总执行时间。（参考：操作系统-读者写者问题）
  - 传统方案——Txs只能串行执行，没有充分利用多核处理器提供的并行性。
负载不均衡
- 大多数区块链采用静态交易分配方式（即每个分片处理哪类交易是固定好的）
  - 有些分片没有足够的Tx来处理。相反，一些分片拥有大量的待处理Tx，这增加了一些Tx的等待延迟

如何解决的

三个创新点

一种平衡吞吐量和超时次数的分片间动态块大小协商方法，可以为每一轮确定一个全局最优的块大小。
一种基于DAG（有向无环图）的事务打包方法，用于减少超时打包的次数和提高并行度，使得每轮中的每个分片都能打包一批并行度最高的最紧急的Tx。
基于最小成本流的分片重配置方法：解决负载不平衡问题。

架构图

论文框架图

领导者（蓝色结点）负责出块，内部分片运行PBFT共识，然后分片结果的哈希收集汇总到一个Main chain中
每个分片的事务处理能力等于分片中最弱节点的事务处理能力
为每个事务（交易）增加一系列特征值
- 时间类
  - 到达时间$a_i$
  - 最晚延迟处理时间$el_i$：若为0，认为这个事务不紧急，若>0，则必须在该时间内处理完毕
  - 预计处理时间$pt_i$
- 冲突类
  - 读取数据集合：$\rho(TX_i)$
  - 写入数据集合：$\omega(TX_i)$
  - 两个事务（i j）是否冲突$C_{ij}$
    - $\mathrm{C}_{ij}=\begin{cases}1\mathrm{~if~}\rho(\mathrm{Tx}_{i})\cap\omega(\mathrm{Tx}_{j})\neq\emptyset\\1\mathrm{~if~}\omega(\mathrm{Tx}_{i})\cap\rho(\mathrm{Tx}_{j})\neq\emptyset\\1\mathrm{~if~}\omega(\mathrm{Tx}_{i})\cap\omega(\mathrm{Tx}_{j})\neq\emptyset\\0&\mathrm{otherwise}&&\end{cases}$
    - 冲突即 读写有交集 或者 需要同时写入

事务响应时间

论文框架图|500

$\mathrm{tcl}_i=\mathrm{tqd}_i+\mathrm{sbgd}_j^k+\mathrm{scd}_k+\mathrm{fbgd}_j^k+\mathrm{fcd}$

tqd：Tx从进入事务池到被打包的等待时间
sdgb：分片块内完成Txs的执行所需要的时间。
sdk：分片内节点在sBlockjk上达成共识所需的时间。
fdgd：主链收集所有分片块的等待时间。
fcd：主链内节点对最终区块达成共识所需的时间。

交易过程

交易过程|800

选举领导者，来自不同分片的领导节点 根据各自分片的事务处理能力和 待处理Tx在各自分片中的状态 协商全局最优块大小。
在每个分片中，领导节点根据全局最优分块大小，从其Txpool中打包一批并行度最大的最紧急Tx，然后将这批Tx广播给同一分片内的其他节点。
并行的执行交易
内部分片达成共识
分片将交易结果哈希上传至主链，主链达成共识

动态块大小协商方法

传统方案
- 静态块：过于静态，
  - 较大的块大小增加了吞吐量，但同时也增加了块形成时间
  - 较小的块使得整个区块链的共识区块数量增加，但共识能力有限，吞吐量会减少
- 动态块：过于动态，每个分片不一样
  - 最后结束快的分片需要等待结束慢的分片，希望同时结束，便于协调和性能分配。

动态块大小协商

图b中：TCT表示交易可能经历的最长共识时间；MGT为最终块（main chain）的最小生成时间

二维片大小

每个区块被视为宽度为STPC（分片事务处理能力），长度为BPT (批处理时间)的 二维矩阵。

当前分片块可以包含的交易事务为：

$0<\sum_{ {\mathrm{Tx}_{i}\in\mathrm{sBlock}_{j}^{k} } }\mathrm{pt}_{i}\leq\mathrm{STPC}_{k}\cdot\mathrm{BPT}$

pt为处理这个交易所需的时间

分片事务处理能力定义为这个分片 最弱结点的并行处理数量（因为需要共识，所以是最弱结点的）

$\mathrm{STPC}_{k}=\min_{ {\mathrm{node}_{i}^{k}\in\mathrm{shard}_{k} } }\mathrm{CPU}_{i}$

批处理时间BPT

【交易事务流程】交易事务提交->分片内执行->分片内共识->分片间共识（结束）

定值TCT：表示事务可能经历的最长共识时间，即TCT为分片内最大共识时间 （因为不确定分配到哪个分片） 与分片间最大共识时间之和。$\mathrm{TCT}=\max_{\mathrm{shard}_{k}\in\mathrm{Shards} }\mathrm{scd}_{k}+\mathrm{fcd}$

我们限制了一个事务的处理结束时间必须在$el_i$内，其中开始时间点在$at_i$
$el_i = 0$表示该事务没有截止时间要求

一个事务的最大剩余时间$rt_i$

$\mathrm{rt}_i=\begin{cases}&\mathrm{el}_i-(\mathrm{currentTime}-\mathrm{at}_i)&\quad\mathrm{if~el}_i\neq0\\&\mathrm{unlimited}&\quad\mathrm{otherwise}&\end{cases}$

剩余时间rt|450

如果一个事务最大剩余时间小于一个TCT，那么肯定排在第一位（最优先）

$\mathrm{index}_{i}=\begin{cases}&u&\mathrm{if~rt}_{i}=\mathrm{unlimited}\\&0&\mathrm{if~rt}_{i}<=\mathrm{TCT}\\&\lceil\frac{\mathrm{rt}_{i}-\mathrm{TCT} }{\mathrm{interval} }\rceil&\mathrm{otherwise}&&\end{cases}$

图示的interval即100ms

APT：表示这一区间的事务的总处理时间（不含等待时间）

BPT：批处理时间，处理完成后才进行共识

二维数组

深入理解TCTBPG

BPT表2

（橙色表）展示了在不同BPT选择下，将超过其截止时间的交易数量（延迟交易的事务数量）。
- 例如，当BPT=200时，要求，至少批处理（开始执行事务）200ms后才进行共识轮。违反截止时间的交易数量为20（即range0.Txs、range1.Txs和range2.Txs的数量之和）。因为这几个区段要求200ms内完成执行，但是如果BPT=200，那么就可能轮不到他们。
- 目标：超过其截止时间的交易数量（延迟交易的事务数量）尽可能少
（橙色表紫色数字）另外，一些非紧急的区块，也有可能在 被分配在下一轮 进行打包出块。其最晚时间是MGT=TCT（一次执行、共识）+MBGP(一轮的时间)

注意：这个表不一定呈现单增趋势，因为可能有一部分区段是没有交易的

最佳BPT

每个结点的BPT

每个分片的BPT是不一样的（因为处理的Tx类型不完全相同）。各个分片的最佳BPT就是让violations（延迟响应的事务数量）尽可能少，同时BPT（一次性批处理时间）尽可能大（以提高吞吐量）。比如这里分片1的最佳BPT=200，分片2=300

因为仍然属于同一个区块链系统，所以不同分片的BGP应该设置的相同（否则，其他分片需要更长的等待，等待某一个分片BPT处理完）

$\mathrm{GOBPT}=\underset{ {\mathrm{BPT}_{t}\in\mathrm{BPTs} } }{\operatorname*{\operatorname*{\operatorname*{\arg\min} } } }\{\sum_{ {\mathrm{shard}_{k}\in\mathrm{Shards} } }\text{violations}_{t}^{k}-\alpha\mathrm{BPT}_{t}\}$

violations：就是延迟响应的事务数量
这个公式的意思就是：全局延迟响应的事务数量的总和↓ - BPT乘以一个系数↑ 最小
这个最优化方程使得 violations（延迟响应的事务数量）尽可能少，同时BPT尽可能大

基于DAG的事务打包方法：用于提高并行性

DAG：有向无环图

需要考虑以下两个目标。

( 1 )最紧急的Txs应该先打包，以尽量减少违反截止时间的次数。
( 2 )每一批打包的Txs可以充分利用并行性

基于Dag和优先关系表的截止期和冲突管理方法：处理谁最紧急

图的构成
- 紧急事务排在前面
- 两个冲突的事务相互链接
优先关系表：橙色表，每个区块链节点的Txpool都配备了DAG和优先关系表。
交易事务池：绿色表。
- 共享变量：需要访问/写入的变量

DAG冲突管理

从TX1开始逐个按顺序绘制DAG图
TX2的共享变量是唯一的（没有和TX1冲突），可以与其他事务并行
TX3的共享变量和TX1、TX2冲突，那么比较优先级
- TX1无响应时间要求，TX3也无响应时间要求，所以按照先来先服务的思想，TX1优先
- TX2需要在剩下的1.5s内响应，TX2更紧急
TX4与TX2 TX3冲突
- TX4响应剩余时间2.5，优先级介于TX2和TX3之间，插入
最终，最上层的是最紧急的事务，需要优先服务。

考虑截止期和并行性的事务打包方法：调度如何并行

DAG例子

二维数组集装箱调度

每一行代表区块链节点处理器中的一个线程

目标：如何装满一个尽可能满的箱子。

紧迫打包
- 最迫切的（DAG图最上端的事务）会被最先装入
打包过程：
- 使用$(RT, thread_i)$表示放置最优先交易的候选位置。例如，交易1（处理时间=2）被放入线程2，因为线程2当前的累积处理时间（APT） 最小。（即哪个线程空缺越多，就往哪个线程添加内容）
- - 其中PRT是上一轮的RT，RT代表当前所有线程中累计处理时间最少的时间（选择一个大于PRT的APT可以确保我们不会回退到处理更早或更慢的交易，从而保持交易处理的连续性和效率）
- 选择一个最优先且最紧急且不冲突的事务加入，比如TX1加入线程2，形成a图。
  - 注意：不能加入TX7\8\12\13因为会造成冲突，需要等待前面的事务执行完，所以最紧急且不冲突古的是1
  - 此时RT=2,PRT=1（图没画），然后可以加入TX4，形成b图
- 此时卡住了，因为不能继续加入了（继续加入会发生冲突），那么计算(图c)
```
    这里就是为什么要用双指针的原因，因为有时候会卡住。
```

基于最小费用流的负载均衡配置

负载不均衡
- 大多数区块链采用静态交易分配方式（即每个分片处理哪类交易是固定好的）
  - 有些分片没有足够的Tx来处理。相反，一些分片拥有大量的待处理Tx，这增加了一些Tx的等待延迟
核心思想：
- 将具有强大事务处理能力的节点调度到负载较重的分片上
- 计算结点之间的不平衡程度

调度谁

计算每个分片的浪费时间$WPT$

$\mathrm{WPT}_i^k=\mathrm{GOBPT}_i-\max_{j\in[1,\mathrm{STPC}_k^e]}\mathrm{APT}_j$

二维数组

计算剩余交易池处理时间

有些交易超时了。计算处理这些未打包的交易的平均时间

$\mathrm{RMPT}_{i}^{k}=\frac{\sum_{ {\mathrm{Tx}_{j}\in\mathrm{rTxs}_{i}^{k} } }\mathrm{pt}_{j} }{\mathrm{STPC}_{k}^{e} }$

每个分片的浪费时间越大，说明该分片能力越强；计算剩余交易池处理时间越小，该分片能力越强

计算不平衡程度，IBD越小，分片能力越强
$\mathrm{IBD}_{k}^{e}=\sum_{ {\mathrm{fBlock}_{i}\in\mathrm{UFB}_{e} } }\sum_{ {\mathrm{SBlock}_{i}^{k}\in\mathrm{fBlock}_{i} } }(\mathrm{RMPT}_{i}^{k}-\mathrm{WPT}_{i}^{k})$
标准化压缩IBD，将所有分片的IBD平衡到[-1,1]之间。如果IBD小于0，那么处理能力过剩；大于0，则处理能力不足

我们只需要交换【处理能力过剩中最强的】&【处理能力不足中最弱的】就可以尽可能保持平衡。

如何调度

最优化算法

定义网络模型：

节点（供应和需求）：
- 供应节点：处理能力过剩的分片，可以“供应”节点给其他分片。
- 需求节点：处理能力不足的分片，需要“需求”其他分片的节点。
边（调度决策）：
- 边代表将一个节点从一个分片移动到另一个分片的调度决策。
容量限制：
- 每个分片在每个周期内最多只能接收或发送一个节点。

计算效益：

增益函数（Gik）：
- 代表将节点i调度到分片k的增益。增益是基于IBD（Imbalance Degree）和节点处理能力差异的函数。
- $PI_{ik}$：代表表示节点 𝑖被调度到分片 𝑘 后，分片 𝑘的平均处理能力与之前的比率。如果>1说明处理能力增强；<1说明处理能力变弱
- $\mathrm{G}_{ik}=\begin{cases}\mathrm{IBD}_{k}^{e}(1-\frac{1}{\mathrm{PI}_{ik} })&\mathrm{if~PI}_{ik}\neq1\mathrm{~and~}\mathrm{IBD}_{k}^{e}>0\\\mathrm{IBD}_{k}^{e}\cdot(\mathrm{PI}_{ik}-1)&\mathrm{if~PI}_{ik}\neq1\mathrm{~and~}\mathrm{IBD}_{k}^{e}\leqslant0\\\mathrm{P}&\mathrm{if~}\mathrm{PI}_{ik}=1\mathrm{~and~}k=o\\-\mathrm{Q}&\mathrm{if~}\mathrm{PI}_{ik}=1\mathrm{~and~}k\neq o&&\end{cases}$
- 如果$PI_{ik}\neq1$ 且 𝐼𝐵𝐷>0（处理能力不足的分片）。这表示通过调度节点 𝑖 到分片 𝑘，我们期望减少分片 𝑘 的IBD。
- 如果$PI_{ik}\neq1$ 且 𝐼𝐵𝐷<0（处理能力过剩的分片）。这表示通过调度节点 𝑖 到分片 𝑘，我们期望减少分片 𝑘 的IBD。
- 若调度前后分片的处理能力没有变化
  - 如果没有进行调度（源=目的），正常现象，为了进一步减少调度引起的开销，设置固定值P进行鼓励
  - 如果调度了反而没有变化，那么不如不调度，乘法。
效益最大化：
- 目标是最大化总增益，即最小化负载不平衡。

实验

成功吞吐量：区块链系统每秒成功处理的交易数量。

截止时间满足率：在预期延迟内成功处理的延迟敏感交易的百分比。

平均交易确认延迟：区块链系统成功处理的所有交易的平均延迟。

对比

[[区块链/河口：一种基于状态拆分的低跨分片区块链分片协议]]

关于区块链分片吞吐量优化

河口：针对结点状态进行优化
- 多账户（多状态）的思想，账户之间可以合并/细分
本文：针对区块交易进行优化
- 考虑区块交易的并行性、优先级和区块中交易大小
两者都考虑了分片的负载优化：即平衡各个分片的交易事务数量/处理能力

关于负载均衡

同样提出了负载平衡的思想。其是基于 推荐系统 的算法改编

考虑的是结点处理该分片交易的数量。将数量多的作为主结点，进行合并或者细分

COPRAS算法过程|450

其优势在于：全局性的调整，调整后的结果基本是最优的
其劣势在于：过于全局化，调整的性能开销相对更大

本文：基于最优化算法设计了一个调整增益函数
考虑的是结点处理该分片交易的性能。将性能最好和最坏进行交换

其优势在于：限制每个分片只调整一个结点，相对开销更小
其劣势在于：只调整一个结点，做不到全局化最优
- 但是有 动态块大小协商方法 进行补充

为什么选这篇

分片区块链是一种通过将节点分组（即分片）来并行处理不相交的交易，从而显著提高吞吐量的区块链技术。然而，现有的分片区块链并没有很好地满足多样化的交易的延迟要求。（交易往往要求区块链的延迟率非常低。）
论文指出，有三大挑战阻碍了分片区块链成为实时交易处理系统，分别是静态区块大小、先来先服务的交易打包策略以及负载不平衡。因此需要对区块链分片系统进行实时化。

解决了什么

论文主要目的是把区块链转为实时交易系统，尽可能减少时间延迟。下文Tx指的是交易。
1. 由静态块大小引起的等待延迟：静态块大小（即每个区块容纳的交易量固定）没有考虑到事务数量限制和系统吞吐量之间的平衡。较大块增加吞吐量，但也增加了块形成时间。小块使得整个区块链的共识区块数量增加，但共识能力有限吞吐量会减少；如果分片系统使用【完全动态块】大小，即在每一轮中，每个分片具有不同的块大小。因为最终需要汇总所有的分片到主链，小的分片块会等待大的分片块的形成，这也可能会导致后续的交易延迟
2. 先到先服务的交易打包策略导致的等待延迟：大多数区块链使用“先来先服务”的策略进行交易打包，先到的交易先加入区块中。未考虑到紧急事务需求，到达较早的非紧急Txs先被打包，而到达较晚的紧急Txs只能等待。同时，针对冲突事务的同块处理，如果将大量相互冲突的Txs (即读写集相交的Txs) 打包成一个块，这会增加块的总执行时间。（参考：操作系统-读者写者问题）
3.负载不均衡：大多数区块链采用静态交易分配方式（即每个分片处理哪类交易是固定好的）有些分片没有足够的Tx来处理。相反，一些分片拥有大量的待处理Tx，这增加了一些Tx的等待延迟

如何解决的
1.一种平衡吞吐量和超时次数的分片间动态块大小协商方法，可以为每一轮确定一个全局最优的块大小。首先，为每个交易设定一个最晚处理时间rt，通过遍历每个结点在不同BGP（批处理时间）下的可能超时数量，共同商定一个全局最佳批处理时间，使得整个系统超时交易数量最小。
2.一种基于DAG（有向无环图）的事务打包方法：用于减少超时打包的次数和提高并行度，使得每轮中的每个分片都能打包一批并行度最高的最紧急的Tx。有向无环图中，最上层会被最优先执行，图的每条边代表“有冲突”信息的交易，有向无环图实现了“横轴并行”、“纵轴串行”的特性，能够达到最紧急、最不容易冲突的交易流程。
3.基于最小成本流的分片重配置方法：解决负载不平衡问题。核心目标是把处理能力弱的分片中最强的结点和处理能力强的分片中最弱的结点交换，通过一个最优化方法，计算每个结点前后置换后的结点处理效率增益，算出一个近似全局最优调度，使得每个分片处理的交易能力近乎相当。
实验
成功吞吐量：区块链系统每秒成功处理的交易数量。
截止时间满足率：在预期延迟内成功处理的延迟敏感交易的百分比。
平均交易确认延迟：区块链系统成功处理的所有交易的平均延迟。
读后思考
文章的创新点非常足，通过构建了一个交易时间限制的场景，引出了第一和第二两个创新点。我认为第二个创新点非常值得寻味，有向无环图是在区块链中最近比较火热的一个数据结构，文章巧妙的把这个数据结构前后相连、左右不相接的特性引入到区块链交易的“并行化”处理中，实现了“横轴并行”、“纵轴串行”，达到最紧急、最不容易冲突的交易流程。可以在此基础上继续修改，仍然是利用有向无环图的特性，与区块链交易其他特性结合在一起。比如这篇文章是说的“最紧急的交易处在纵轴最上端”，那么也可以设想“信誉最高的处在纵轴最上端”，结合安全进行创意移植。