Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (3): 647-653.DOI: 10.11772/j.issn.1001-9081.2017.03.647

Previous Articles     Next Articles

Partitioning and mapping algorithm for in-memory computing framework based on iterative filling

BIAN Chen, YU Jiong, XIU Weirong, YING Changtian, QIAN Yurong   

  1. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China
  • Received:2016-09-26 Revised:2016-10-17 Online:2017-03-10 Published:2017-03-22
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61262088, 61462079, 61363083, 61562086), the Educational Research Program of Xinjiang Uygur Autonomous Region(XJEDU2016S106).

基于迭代填充的内存计算框架分区映射算法

卞琛, 于炯, 修位蓉, 英昌甜, 钱育蓉   

  1. 新疆大学 信息科学与工程学院, 乌鲁木齐 830046
  • 通讯作者: 卞琛
  • 作者简介:卞琛(1981-),男,江苏南京人,副教授,博士研究生,CCF会员,主要研究方向:网络计算、分布式系统;于炯(1964-),男,北京人,教授,博士,CCF高级会员,主要研究方向:网格计算、高性能计算;修位蓉(1979-),女,重庆人,讲师,硕士,主要研究方向:数据挖掘、分布式应用;英昌甜(1989-),女,新疆乌鲁木齐人,博士研究生,主要研究方向:大数据存储、内存计算;钱育蓉(1979-),女,新疆乌鲁木齐人,副教授,博士,CCF会员,主要研究方向:云计算、图形图像处理。
  • 基金资助:
    国家自然科学基金资助项目(61262088,61462079,61363083,61562086);新疆维吾尔自治区高校科研计划项目(XJEDU2016S106)。

Abstract: Focusing on the issue that the only one Hash/Range partitioning strategy in Spark usually results in unbalanced data load at Reduce phase and increases job duration sharply, an Iterative Filling data Partitioning and Mapping algorithm (IFPM) which include several innovative approaches was proposed. First of all, according to the analysis of job execute scheme of Spark, the job efficiency model and partition mapping model were established, the definitions of job execute timespan and allocation incline degree were given. Moreover, the Extendible Partitioning Algorithm (EPA) and Iterative Mapping Algorithm (IMA) were proposed, which reserved partial data into extend region by one-to-many partition function at Map phase. Data in extended region would be mapped by extra iterative allocation until the approximate data distribution was obtained, and the adaptive mapping function was executed by awareness of calculated data size at Reduce phase to revise the unbalanced data load in original region allocation. Experimental results demonstrate that for any distribution of the data, IFPM promotes the rationality of data load allocation from Map phase to Reduce phase and optimize the job efficiency of in-memory computing framework.

Key words: in-memory computing, load balance, extendible partitioning, iterative mapping

摘要: 针对内存计算框架Spark在作业Shuffle阶段一次分区产生的数据倾斜问题,提出一种内存计算框架的迭代填充分区映射算法(IFPM)。首先,分析Spark作业的执行机制,建立作业效率模型和分区映射模型,给出作业执行时间和分配倾斜度的定义,证明这些定义与作业执行效率的因果逻辑关系;然后,根据模型和定义求解,设计扩展式数据分区算法(EPA)和迭代式分区映射算法(IMA),在Map端建立一对多分区函数,并通过分区函数将部分数据填入扩展区内,在数据分布局部感知后再执行扩展区迭代式的多轮数据分配,根据Reduce端已分配数据量建立适应性的扩展区映射规则,对原生区的数据倾斜进行逐步修正,以此保障数据分配的均衡性。实验结果表明,在不同源数据分布条件下,算法均提高了作业Shuffle过程分区映射合理性,缩减了宽依赖Stage的同步时间,提高了作业执行效率。

关键词: 内存计算, 数据均衡, 扩展式分区, 迭代式映射

CLC Number: