Journal of East China Normal University(Natural Science) >
Sorting algorithm analysis of distributed data based on Map/Reduce
Received date: 2016-06-27
Online published: 2016-11-29
Distributed system has been widely applied in recent years to tackle the storage and calculation of big data. Sorting of large-scale dataset in the distributed system has become the fundamental problem to affect a varieties of application performances which is not only concerning about the selection of sorting algorithm at each node, but also about the development of distributed algorithms to coordinate at each node. This paper summarizes the common distributed sorting algorithms which are applied in the distributed system. Analysis has been conducted to the implementation process, cost model and applicable field of each algorithm. And the analysis results have been verified by experiments. This work can help developers choose and optimize the big data sorting
algorithm in distributed environments.
Key words: distributed system; sorting algorithm; cost model
YU Sheng-jun , GONG Xue-qing , ZHU jun , QIAN Wei-ning . Sorting algorithm analysis of distributed data based on Map/Reduce[J]. Journal of East China Normal University(Natural Science), 2016 , 2016(5) : 121 -130 . DOI: 10.3969/j.issn.1000-5641.2016.05.014
[ 1 ] KNUTH D E. The Art of Computer Programming: Sorting and Searching [M]. 2nd ed. Indianapolis: Addison-Wesley Professional, 1998.
[ 2 ] BORTHAKUR D. The hadoop distributed file system: Architecture and design [J]. Hadoop Project Website, 2007, 11: 1-10.
[ 3 ] DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.
[ 4 ] CHRIS NYBERG, MEHUL SHAH. Sort Benchmark Home Page [EB/OL]. (2015) [2016-04-20]. http://sortbenchmark.org/.
[ 5 ] BORTHAKUR D, GRAY J, SARMA J S, et al. Apache Hadoop goes realtime at Facebook [C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. ACM, 2011: 1071-1080.
[ 6 ] MANE S B, SAWANT Y, KAZI S, et al. Real time sentiment analysis of twitter data using hadoop [J]. International Journal of Computer Science and Information Technolo, 2014, 5(3): 3098-3100.
[ 7 ] O’MALLEY O, MURTHY A C. Winning a 60 second dash with a yellow elephant [J]. Proceedings of Sort Benchmark, 2009, 1810(9): 1-9.
[ 8 ] WANG J, WU Y, CAI H, et al. Fuxi Sort [EB/OL]. (2015) [2016-04-20]. http://sortbenchmark.org/Fux-iSort2015.pdf.
[ 9 ] GRIFFITHS N. Nmon performance: A free tool to analyze AIX and Linux performance [EB/OL]. (2003-11-04)[2016-04-20]. http://www.ibm.com/developerworks/aix/library/au-analyze aix/.
/
〈 |
|
〉 |