利用布隆滤波二次拆分的数据倾斜处理算法

• 作者: 张强 张学文
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 数据倾斜 布隆滤波 二次拆分 学习自动机 大数据处理 负载变化率
• 年，卷（期）: 2021,（2）
• 所属期刊栏目: 软件与算法
• 页码范围: 475-481
• 页数: 7页
• 分类号: TP391
• 语种: 中文
• DOI: 10.16208/j.issn1000-7024.2021.02.026

摘要

MapReduce进行大数据分布式计算时,数据集倾斜特性将导致子任务间完成时间差异明显,影响计算性能.提出基于布隆滤波二次拆分的处理算法.考虑硬件配置、计算资源等约束,提出基于布隆滤波的改进Hash分区函数,缩小映射操作的选择范围.在Reduce阶段设计学习自动机分区算法,使用均匀分布抽样获取任务类型与规模,以Reducer范围为约束条件搜索Mapper与Reducer的近似最优映射.与不考虑Reducer异构的常规算法相比,所提算法网络开销与负载变化率可降低2.4％和28％以上,负载均衡度则提升7.31％以上,表明所提算法具有更高的计算效率.