On Distributed Information Composition in Big Data Systems
On Distributed Information Composition in Big Data Systems
复制标题
DOI：
10.1109/escience.2019.00025
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Haifa AlQuwaiee;Songlin He;C. Wu;Qiang Tang;Xuewen Shen
中科院分区：
文献类型：
--
作者：
Haifa AlQuwaiee;Songlin He;C. Wu;Qiang Tang;Xuewen Shen
以Hadoop为例的现代大数据计算系统采用基于分布式存储的并行处理。由并行任务（例如科学工作流中的计算模块或MapReduce框架中的reducer）产生的结果通常存储在跨多个数据节点的分布式文件系统中。然而，大多数现有系统不提供如许多大数据应用所需的组成这种分布式信息的机制。我们构建了分析成本模型，并制定了一个分布式信息组合问题在大数据系统中，简称为DIC-BDS，聚合多个数据集存储为数据块在Hadoop分布式文件系统（HDFS）使用特定复杂性的组合运算符产生一个最终输出。我们严格证明了DIC-BDS是NP完全的，并提出了两个启发式算法：固定窗口分布式组合方案（FDCS）和动态窗口分布式组合方案与延迟（DDCS-D）。我们在Google云中使用各种通常认为复杂度的合成运算符进行了广泛的实验，包括O（n）、O（n log n）和O（n^2）。实验结果表明，所提出的解决方案的性能优于现有的方法。具体来说，FDCS优于所有其他算法相比，复杂度为O（n）或O（n log n）的复合操作，而DDCS-D实现了最小的总复合时间与复杂度为O（n^2）的复合操作。这些算法为现有工作流和大数据系统中的有效信息聚合提供了额外的数据处理级别。
Modern big data computing systems exemplified by Hadoop employ parallel processing based on distributed storage. The results produced by parallel tasks such as computing modules in scientific workflows or reducers in the MapReduce framework are typically stored in a distributed file system across multiple data nodes. However, most existing systems do not provide a mechanism to compose such distributed information, as required by many big data applications. We construct analytical cost models and formulate a Distributed Information Composition problem in Big Data Systems, referred to as DIC-BDS, to aggregate multiple datasets stored as data blocks in Hadoop Distributed File System (HDFS) using a composition operator of specific complexity to produce one final output. We rigorously prove that DIC-BDS is NP-complete, and propose two heuristic algorithms: Fixed-window Distributed Composition Scheme (FDCS) and Dynamic-window Distributed Composition Scheme with Delay (DDCS-D). We conduct extensive experiments in Google clouds with various composition operators of commonly considered degrees of complexity including O(n), O(n log n), and O(n^2). Experimental results illustrate the performance superiority of the proposed solutions over existing methods. Specifically, FDCS outperforms all other algorithms in comparison with a composition operator of complexity O(n) or O(n log n), while DDCS-D achieves the minimum total composition time with a composition operator of complexity O(n^2). These algorithms provide an additional level of data processing for efficient information aggregation in existing workflow and big data systems.