Survey on big data storage framework and algorithm

doi:10.11772/j.issn.1001-9081.2016.09.2465

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (9): 2465-2471.DOI: 10.11772/j.issn.1001-9081.2016.09.2465

Previous Articles Next Articles

Survey on big data storage framework and algorithm

YANG Junjie^1,2, LIAO Zhuofan^1,2, FENG Chaochao³

1. School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha Hunan 410114, China;
2. Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation (Changsha University of Science and Technology), Changsha Hunan 410114, China;
3. School of Computer, National University of Defense Technology, Changsha Hunan 410073, China

Received:2016-03-01 Revised:2016-05-01 Online:2016-09-10 Published:2016-09-08
Supported by:
This work is partially supported by National Natural Science Foundation of China (61402056, 61303066), the Scientific Research Fund of Hunan Provincial Education Department (14C0030).

大数据存储架构和算法研究综述

杨俊杰^1,2, 廖卓凡^1,2, 冯超超³

1. 长沙理工大学计算机与通信工程学院, 长沙 410114;
2. 综合交通运输大数据智能处理湖南省重点实验室(长沙理工大学), 长沙 410114;
3. 国防科技大学计算机学院, 长沙 410073

通讯作者: 廖卓凡
作者简介:杨俊杰(1992-),男,河南洛阳人,硕士研究生,主要研究方向:大数据优化部署;廖卓凡(1981-),女,湖南湘潭人,讲师,博士,CCF会员,主要研究方向:移动互联网、大数据优化部署、无线传感器网络;冯超超(1982-),男,云南昆明人,助理研究员,博士,CCF会员,主要研究方向:高性能微处理器设计。
基金资助:
国家自然科学基金资助项目（61402056，61303066）；湖南省教育厅科研项目（14C0030）。

Abstract

Abstract: With the growing demand of big data computing, the processing speed of the cluster needs to be improved rapidly. However, the processing performance of the existing big data framework can not satisfy the requirement of the computing development gradually. As the framework of the storage is distributed, the placement of data to be processed has become one of the key factors affecting the performance of the cluster. Firstly, the current distributed file system structure was introduced. Then the popular data placement algorithms were summarized and classified according to different optimization goals, such as network load balance, energy saving and fault tolerance. Finally, future challenges and research directions in the area of storage framework and algorithms were presented.

Key words: big data, data placement, distributed file system, MapReduce, Hadoop

摘要： 随着大数据计算需求的增长，集群的处理速度需要得到快速的提升，然而目前大数据处理框架的处理性能已逐渐满足不了这种快速增长的需求。由于集群的存储架构是分布式存储，因此数据的存放在大数据处理过程中成为影响集群的处理性能的因素之一。首先，对当今的分布式文件存储系统的结构进行了介绍；接着，根据不同的优化目标，例如减少网络负载、负载均衡、降低能耗和高容错性等，对近年国内外大数据存储算法的研究进行了总结，分析和对比了已有算法的优点以及存在的问题；最后，对大数据存储架构和优化算法设计的挑战和未来研究方向作了展望。

关键词: 大数据, 数据部署, 分布式文件系统, MapReduce, Hadoop

CLC Number:

TP393

YANG Junjie, LIAO Zhuofan, FENG Chaochao. Survey on big data storage framework and algorithm[J]. Journal of Computer Applications, 2016, 36(9): 2465-2471.

杨俊杰, 廖卓凡, 冯超超. 大数据存储架构和算法研究综述[J]. 计算机应用, 2016, 36(9): 2465-2471.

References

[1] 程学旗,靳小龙,王元卓,等.大数据系统和分析技术综述[J].软件学报,2014,25(9):1889-1908.(CHENG X Q, JIN X L, WANG Y Z, et al. Survey on big data system and analytic technology [J]. Journal of Software, 2014,25(9):1889-1908.)
[2] 王元卓,靳小龙,程学旗.网络大数据:现状与展望[J].计算机学报,2013,36(6):1125-1138.(WANG Y Z,JIN X L,CHENG X Q. Network big data: present and future[J]. Chinese Journal of Computers, 2013, 36(6): 1125-1138.
[3] 孟小峰,慈祥.大数据管理:概念、技术与挑战[J].计算机研究与发展,2013,50(1):146-169.(MENG X F, CI X. Big data management: concepts, techniques and challenges [J]. Journal of Computer Research and Development, 2013, 50(1): 146-169.)
[4] 张滨,陈吉荣,乐嘉锦.大数据管理技术研究综述[J].计算机应用与软件,2014,31(11):1-5.(ZHANG B, CHEN J R, LE J J. Overview on big data management technology research [J]. Computer Applications and Software, 2014, 31(11): 1-5.)
[5] ZICARI R V. Big data: challenges and opportunities [EB/OL]. [2016-01-08]. http://gotocon.com/dl/goto-aar-2012/slides/RobertoV.Zicari_BigDataChallengesAndOpportunities.pdf.
[6] ZHAO Q, XIONG C, ZHAO X, et al. A data placement strategy for data-intensive scientific workflows in cloud [C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Washington, DC: IEEE Computer Society, 2015: 928-934.
[7] YU B, PAN J. Location-aware associated data placement for geo-distributed data-intensive applications [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2015:603-611.
[8] JALAPARTI V, BODIK P, MENACHE I, et al. Network-aware scheduling for data-parallel jobs: plan when you can [C]// SIGCOMM '15: Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York: ACM, 2015: 407-420.
[9] CHEN W, PAIK I, LI Z. Topology-aware optimal data placement algorithm for network traffic optimization [J]. IEEE Transactions on Computers, 2016,65(8):2603-2617.
[10] WANG J, QIU M, GUO B, et al. Phase-reconfigurable shuffle optimization for Hadoop MapReduce [J]. IEEE Transactions on Cloud Computing, 2015(99):1.
[11] YU W, WANG Y, QUE X, et al. Virtual shuffling for efficient data movement in MapReduce [J]. IEEE Transactions on Computers, 2015, 64(2):556-568.
[12] BUYYA R. High Performance Cluster Computing: Architectures and Systems [M]. Upper Saddle River, NJ: Prentice Hall, 1999, 1: 823.
[13] 刘琨,肖琳,赵海燕.Hadoop中云数据负载均衡算法的研究及优化[J].微电子学与计算机,2012,29(9):18-22.(LIU K, XIAO L, ZHAO H Y. Research and optimize of cloud data load balancing in hadoop [J]. Microelectronics & Computer, 2013, 29(9): 18-22.
[14] XIE Q, LU Y. Priority algorithm for near-data scheduling: throughput and heavy-traffic optimality [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2015: 963-972.
[15] LE Y, LIU J, ERGUN F, et al. Online load balancing for MapReduce with skewed data input [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2014: 2004-2012.
[16] CHEN Q, YAO J, XIAO Z. LIBRA: lightweight data skew mitigation in MapReduce [J]. IEEE Transactions on Parallel & Distributed Systems, 2015, 26(9): 2520-2533.
[17] TANG S, LEE B S, HE B. Dynamic job ordering and slot configurations for MapReduce workloads [J]. IEEE Transactions on Services Computing, 2016, 9(1): 4-17.
[18] JOHNSON S M. Optimal two- and three-stage production schedules with setup times included [J]. Naval Research Logistics Quarterly, 1954, 1(1):61-68.
[19] YAO Y, WANG J, SHENG B, et al. Self-adjusting slot configurations for homogeneous and heterogeneous Hadoop clusters [EB/OL]. [2016-01-09]. http://www.cs.umb.edu/~shengbo/paper/tcc15.pdf.
[20] GRANDL R, ANANTHANARAYANAN G, KANDULA S, et al. Multi-resource packing for cluster schedulers [C]// SIGCOMM '14: Proceedings of the 2014 ACM Conference on SIGCOMM. New York: ACM, 2014:455-466.
[21] 魏文娟,王黎明.异构Hadoop集群下的比例数据分配策略[J].计算机应用与软件,2015,32(6):316-319.(WEI W J, WANG L M. Proportional data placement strategy in heterogeneous hadoop clusters [J]. Computer Applications and Software, 2015, 32(6): 316-319.)
[22] WANG B, JIANG J, YANG G. ActCap: accelerating MapReduce on heterogeneous clusters with capability-aware data placement [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2015: 1328-1336.
[23] KOOMEY J. Growth in data center electricity use 2005 to 2010 [EB/OL]. [2015-11-04]. http://cs.bennington.edu/courses/f2013/cs4125.01/koomeydatacenterelectuse2011finalversion.pdf.
[24] HAMILTON J. Cooperative Expendable Micro-slice Servers (CEMS): low cost, low power servers for Internet-scale services [EB/OL]. [2015-11-04]. http://database.cs.wisc.edu/cidr/cidr2009/JamesHamilton_CEMS.pdf.
[25] 廖彬,于炯,张陶,等.基于分布式文件系统HDFS的节能算法[J].计算机学报,2013,36(5):1047-1064.(LIAO B, YU J, ZHANG T, et al. Energy-efficient algorithms for distributed file system HDFS [J].Chinese Journal of Computers, 2013, 36(5): 1047-1064.
[26] CAVDAR D, CHEN L Y, ALAGOZ F. Green MapReduce for heterogeneous data centers [C]// Proceedings of the 2014 IEEE Global Communications Conference. Piscataway, NJ: IEEE, 2014: 1120-1126.
[27] ZENG D, GU L, GUO S. Cost minimization for big data processing in geo-distributed data centers [J]. IEEE Transactions on Emerging Topics in Computing, 2014, 2(3): 314-323.
[28] YOON M S, KAMAL A E. Optimal dataset allocation in distributed heterogeneous clouds [C]// Proceedings of the 2014 IEEE Globecom Workshops. Piscataway, NJ: IEEE, 2014: 75-80.
[29] MASHAYEKHY L, NEJAD M M, GROSU D, et al. Energy-aware scheduling of MapReduce jobs [C]// Proceedings of the 2014 IEEE International Congress on Big Data. Washington, DC: IEEE Computer Society, 2014:32-39.
[30] CHEN K, POWERS J, GUO S, et al. CRESP: towards optimal resource provisioning for MapReduce computing in public clouds [J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(6):1403-1412.
[31] 林彬,李姗姗,廖湘科,等.Seadown:一种异构MapReduce集群中面向SLA的能耗管理方法[J].计算机学报,2013,36(5):977-987.(LIN B, LI S S, LIAO X K, et al. Seadown: SLA-aware size-scaling power management in heterogeneous MapReduce cluster [J]. Chinese Journal of Computers, 2013, 36(5): 977-987.
[32] XU H, LAU W C. Optimization for speculative execution in a MapReduce-like cluster[C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2015: 1071-1079.
[33] ANANTHANARAYANAN G, KANDULA S, GREENBERG A, et al. Reining in the outliers in MapReduce clusters using Mantri [C]// OSDI '10: Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2010:265-278.
[34] CHEN Q, LIU C, XIAO Z. Improving MapReduce performance using smart speculative execution strategy [J]. IEEE Transactions on Computers, 2014, 63(4): 954-967.
[35] FONTUGNE R, MAZEL J, FUKUDA K. Hashdoop: a MapReduce framework for network anomaly detection [C]// Proceedings of the 2014 IEEE Conference on Computer Communications Workshops. Piscataway, NJ: IEEE, 2014: 494-499.
[36] 宋宝燕,王俊陆,王妍.基于范德蒙码的HDFS优化存储策略研究[J].计算机学报,2015,38(9):1825-1837.(SONG B Y, WANG J L, WANG Y. Optimized storage strategy research of HDFS based on Vandermonde code [J]. Chinese Journal of Computers, 2015, 38(9): 1825-1837.

Survey on big data storage framework and algorithm

大数据存储架构和算法研究综述

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZHOU Xiang, ZHAI Junhai, HUANG Yajie, SHEN Ruicai, HOU Yingzhen. Instance selection algorithm for big data based on random forest and voting mechanism [J]. Journal of Computer Applications, 2021, 41(1): 74-80.
[2]	GOU Zi'an, ZHANG Xiao, WU Dongnan, WANG Yanqiu. Log analysis and workload characteristic extraction in distributed storage system [J]. Journal of Computer Applications, 2020, 40(9): 2586-2593.
[3]	CAO Cejun, LIU Ju. Overview of modeling method of emergency organization decision in disaster operations management [J]. Journal of Computer Applications, 2020, 40(7): 2142-2149.
[4]	ZHU Xiaojie, ZHAO Zihao, DU Yi. PiFlow: model driven big data pipeline framework [J]. Journal of Computer Applications, 2020, 40(6): 1638-1647.
[5]	WU Wenli, LIU Guohua, ZHANG Junbao. Complexity analysis of functional query answering on big data [J]. Journal of Computer Applications, 2020, 40(2): 416-419.
[6]	DONG Cong, ZHANG Xiao, CHENG Wendi, SHI Jia. Performance optimization of distributed file system based on new type storage devices [J]. Journal of Computer Applications, 2020, 40(12): 3594-3603.
[7]	LI Ziying, SHI Zhenguo. Scheduling method for big data tasks [J]. Journal of Computer Applications, 2020, 40(10): 2923-2928.
[8]	ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms [J]. Journal of Computer Applications, 2019, 39(7): 1869-1882.
[9]	LI Yunshu, TENG Fei, LI Tianrui. Microoperation-based parameter auto-optimization method of Hadoop [J]. Journal of Computer Applications, 2019, 39(6): 1589-1594.
[10]	MA Jiangang, MA Yinglong. Semantic-driven learning and classification method of judicial documents [J]. Journal of Computer Applications, 2019, 39(6): 1696-1700.
[11]	JI Lina, CHEN Kai, YU Yanwei, SONG Peng, WANG Shuying, WANG Chenrui. Vehicle type mining and application analysis based on urban traffic big data [J]. Journal of Computer Applications, 2019, 39(5): 1343-1350.
[12]	ZHANG Yitian, YU Jiong, LU Liang, LI Ziyang. Task scheduling strategy based on data stream classification in Heron [J]. Journal of Computer Applications, 2019, 39(4): 1106-1116.
[13]	XU Yao, LI Zhuoran, MENG Jinlong, ZHAO Lipo, WEN Jianxin, WANG Guiling. Extraction method of marine lane boundary from exploiting trajectory big data [J]. Journal of Computer Applications, 2019, 39(1): 105-112.
[14]	ZHENG Zhentao, ZHAO Zhuofeng, WANG Guiling, XU Yao. Ship trajectory extraction method for port parking area identification [J]. Journal of Computer Applications, 2019, 39(1): 113-117.
[15]	GUO Fangfang, CHAO Luomeng, ZHU Jianwen. Multi-source data parallel preprocessing method based on similar connection [J]. Journal of Computer Applications, 2019, 39(1): 57-60.