Page 147 - 《软件学报》2026年第1期

144 软件学报 2026 年第 37 卷第 1 期

账户模型的状态实现方式中尤为突出, 主要原因是现实中少数热门账户往往会发起系统中大部分交易, 当热门账
户集中于同一分片时, 会导致分片的工作负载严重不均. 我们基于以太坊数据采用静态分配方法, 进行多轮次的交
易分配以评估分片的负载分布. 图 3 展示了在 8 分片下, 每轮注入 50 000 条以太坊交易的结果. 该方法会在分片之
间产生极度不均衡的交易分布.

12 000
热分片
8
10 000
7
6 8 000
分片号 5 4

6 000
3
2
4 000
1
注入交易轮次
2 000
图 3 哈希分配下分片工作负载分布

为解决上述问题, 大量研究提出了动态分配方法. 相较于静态分配方法, 该方法通过分析状态之间的关联性和
交易模式, 定期调整状态分配策略, 能够更加灵活地应对交易模式的变化, 有效降低系统的跨分片交易比例, 并且
优化分片负载均衡, 进一步提升系统的整体性能. 动态分配的具体实现包括基于图论的分配方法、基于机器学习
的分配方法以及交易级的状态调度方法. 表 1 对状态分配的各类方法的优缺点进行了总结. 此外, 动态分配过程中
涉及状态存储位置的调整, 需要状态管理机制来实现状态数据的高效管理与定位. 因此, 本节还将介绍动态分配环
境下的主流状态数据管理方法.

表 1 状态分配方法总结对比

分类 状态特征分析 动态适应性 优点 缺点
哈希分配 否 差 实现简单且分配高效 分配固定, 缺乏灵活性
图分配 是 中等 基于历史数据识别状态特征, 实施图划分 周期性分配, 无法应对系统突然波动
状态调度 是 强 实时调度状态, 应对系统波动能力强 存在一定的调度决策计算开销
机器学习 是 强 可预测未来交易行为, 分配准确率高 训练成本高, 算法效果依赖输入数据的质量

2.1.1 基于图论的分配方法
一些研究 [15,40–45] 将状态分配转化为图模型上的子图划分问题 [46–48] . 在划分过程中, 通过减少不同子图之间的
边数量和平衡子图权重, 实现降低系统跨分片交易比例以及平衡分片工作负载的目的. 基于图论的分配方法通常
在分片配置时期执行, 系统将使用上一纪元的历史交易构建区块链状态关系图, 执行相应的子图划分算法, 从而为
下一纪元生成状态分配策略. 区块链状态关系图构建方法主要包括以下两种.
(1) 账户为节点 (如图 4 所示): 该构建方法适用于采用账户模型的区块链全分片系统. 具体来说, 系统利用收
集到的历史交易数据, 构建无向状态关系图 G(V, E). 在该图中, V 表示账户 (节点) 集合, E 表示交易 (边) 集合. 当
两个账户 v i 和 v j 之间存在交易时, 它们之间就会有一条对应的边 e ij . 边权重 w(e ij ) 表示两个账户之间的交易数量.
节点权重 w(v i ) 表示与该账户相关的交易总数. 基于状态关系图 G(V, E), 系统执行子图划分算法进行状态分配.
[15] [45] [46]
BrokerChain 和 X-Shard 采用 METIS 算法将图 G 划分为 K 个不重叠的子图, 每一个子图对应一个分片.
CLPA [42] 、TxAllo [43] 和 Estuary [44] 则使用了社区检测算法 [49,50] , 通过识别图 G 中联系密切的节点, 将其作为社区划
分子图. 这种方法确保了频繁交互的账户能够被聚集在同一分片中, 从而有效地减少跨分片交易. 此外, 图分配方
法在划分过程中通过限制各子图的节点权重 w(v i ) 之和, 以平衡分片间工作负载. 以 BrokerChain 为例, 在系统中