第5期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·923· 实分布的清晰认知，抽样数据虽然不能保证真 题。目前，大数据处理主流框架中对抗数据偏斜 实地反映全体数据的分布特征，但基于其结果来 的能力都普遍较弱Bsm。普适性的分布式并行计 近似估计数据的整体分布也可以实现较好的结 算框架中通常假设数据在计算过程中是均匀分布 果。在此基础上，本文提出了一种改进分局均衡 的，这跟现实数据的分布特征背向而驰。严重的 策略来缓解现有分布式并行计算框架中的数据偏 数据偏斜程度会使集群计算系统的计算能力直线 斜问题。 下降，引发资源利用率低和任务执行过慢等问题。 22面向分布式处理的抗数据倾斜分片机制 鉴于此，本文提出了一种密钥重分配和分裂分区 随着大数据时代的到来，信息爆炸使得数据 算法(SKRSP)来解决分区倾斜，该算法同时考虑 的规模和复杂度都在增长，大数据并行计算中数 了中间数据的分区平衡和shuffle算子后的分区 据偏斜问题也日趋严重，成为一个亟需解决的问 平衡。SKRSP策略的整体架构如图4所示。 中间数据分布预测 分片策略生成及应用 ①采样 ②分布预测 采样任务0 ③分片策略生成 分片0 采样数据 e。。 基于hash的 采样任务1 key分配策略 N 分片0 分片1 KRHP 是否 排序 采样任务m-1 KSHP 分片m-1 带权重的key 分片1 分片边界数据 年年卡中年卡年年年专年年年专华年出 ④ 分片策略应用 ma即任务0 reduce任务0 分片m1 分片0 segement 0 reduce分片O segement 1 map任务1 k2 reduce任务1 分片1 egement 1 执行shuf印le-op reduce分片1 的RDD map任务m-】 中间数据 segement 0 reduce任务m-l1 分片m-1 egement广 reduce分片m-1 图4 SKRSP整体架构 Fig.4 General introduction to SKRSP SKRSP整体框架包含了两个主要部分：中间 策略。对于这些属于排序类的应用程序，提出了 数据分布预测、分片策略的生成与应用。 KSRP算法来确定加权边界。最终的key重新分 l)为了避免reduce任务之间的数据偏斜，需 配策略可以通过其他KRHP算法获得。具体来 要在shuffle阶段之前估计中间数据的key分布。 说，采样中间数据key的分布是系统用于决策分 因此，必须在常规作业之前输人地图任务时启动 区策略的依据。一方面，如果操作结果无需排序， 先前的示例作业。本文在不同的分区上并行实现 基于hash的key cluster分片方法将被采用；另一 了基于步骤的拒绝采样算法。所有的样本和对应方面，如果操作结果是需要进行排序，基于range 的采样率都是从不同的map splits中收集的，它们 的key cluster分片策略将被采用。因此，就得到 构成了通过采样率计算每个k©y的权重的输入。在 了不同的分片策略。在shuf的e写数据的阶段，在 此基础上，可以估计中间数据的一般ky分布。 上一个步骤中获得的分片策略会指导每个<key 2)分片策略的生成与应用。本系统根据Spark value>对其进行分区计算，从而获得其reduce端 作业的具体应用场景，采用不同的方法生成分配 的分区D号。该D号就是每个map任务计算后实分布的清晰认知[34] ，抽样数据虽然不能保证真 实地反映全体数据的分布特征，但基于其结果来 近似估计数据的整体分布也可以实现较好的结 果。在此基础上，本文提出了一种改进分局均衡 策略来缓解现有分布式并行计算框架中的数据偏 斜问题。 2.2 面向分布式处理的抗数据倾斜分片机制 随着大数据时代的到来，信息爆炸使得数据 的规模和复杂度都在增长，大数据并行计算中数 据偏斜问题也日趋严重，成为一个亟需解决的问 题。目前，大数据处理主流框架中对抗数据偏斜 的能力都普遍较弱 [35-37]。普适性的分布式并行计 算框架中通常假设数据在计算过程中是均匀分布 的，这跟现实数据的分布特征背向而驰。严重的 数据偏斜程度会使集群计算系统的计算能力直线 下降，引发资源利用率低和任务执行过慢等问题。 鉴于此，本文提出了一种密钥重分配和分裂分区 算法（SKRSP）来解决分区倾斜，该算法同时考虑 了中间数据的分区平衡和 shuffle 算子后的分区 平衡。SKRSP 策略的整体架构如图 4 所示。 分片 0 分片 0 分片 1 分片 1 分片 m−1 分片 m−1 分片 0 分片 1 分片 m−1 reduce 分片 0 reduce 分片 1 reduce 分片 m−1 执行 shuffle-op 的 RDD 中间数据分布预测 分片策略生成及应用 基于 hash 的 key 分配策略 带权重的 key 分片边界数据 采样任务 0 采样任务 1 采样任务 m−1 采样数据 1 采样 2 分布预测 3 分片策略生成 4 分片策略应用 map 任务 0 map 任务 1 map 任务 m−1 reduce 任务 0 reduce 任务 1 reduce 任务 m−1 segement 0 segement 1 segement r−1 segement 0 segement r−1 中间数据 KRHP KSHP N Y 是否 排序 <k, v> ··· ··· ··· ··· ··· ··· ··· ··· ··· 图 4 SKRSP 整体架构 Fig. 4 General introduction to SKRSP SKRSP 整体框架包含了两个主要部分：中间 数据分布预测、分片策略的生成与应用。 1）为了避免 reduce 任务之间的数据偏斜，需 要在 shuffle 阶段之前估计中间数据的 key 分布。 因此，必须在常规作业之前输入地图任务时启动 先前的示例作业。本文在不同的分区上并行实现 了基于步骤的拒绝采样算法。所有的样本和对应 的采样率都是从不同的 map splits 中收集的，它们 构成了通过采样率计算每个 key 的权重的输入。在 此基础上，可以估计中间数据的一般 key 分布。 2）分片策略的生成与应用。本系统根据 Spark 作业的具体应用场景，采用不同的方法生成分配 策略。对于这些属于排序类的应用程序，提出了 KSRP 算法来确定加权边界。最终的 key 重新分 配策略可以通过其他 KRHP 算法获得。具体来 说，采样中间数据 key 的分布是系统用于决策分 区策略的依据。一方面，如果操作结果无需排序， 基于 hash 的 key cluster 分片方法将被采用；另一 方面，如果操作结果是需要进行排序，基于 range 的 key cluster 分片策略将被采用。因此，就得到 了不同的分片策略。在 shuffle 写数据的阶段，在 上一个步骤中获得的分片策略会指导每个<key, value>对其进行分区计算，从而获得其 reduce 端 的分区 ID 号。该 ID 号就是每个 map 任务计算后 第 5 期 曹嵘晖，等：面向机器学习的分布式并行计算关键技术及应用 ·923·