Abstract
MapReduce is a parallel programming model, which is extensively used to process join operations for large-scale dataset. However, traditional MapReduce-based join is not efficient when handling skewed data, because it can lead to partitioning skew, which further results in longer response time of the whole join process. Additionally, some newly proposed methods usually involve large amounts of intermediate results over the network in the shuffle phase of Mapreduce-based join, which may consume a lot of time and cause performance degradation. Here a novel algorithm called SALA is proposed, which employs volume/locality-aware partitioning instead of hash partitioning for data distribution. Compared with other existing join algorithms, SALA has three typical advantages: (1) makes sure that the data is distributed to reducers evenly when the input datasets are skewed, (2) reduces the amount of intermediate results transferred across the network by utilizing data locality, and (3) does not make any modification of the MapReduce framework. The extensive experimental results show that SALA not only achieves better load balance but reduces network overhead, and therefore speeds up the whole join process significantly in the presence of data skew.
Supported by the Natural Science Foundation of China under Grant No. 61303004 and 61202012, and the Natural Science Foundation of Fujian Province under Grant No.2013J05099.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahmad, F., Lee, S., Thottethodi, M., Vijaykumar, T.N.: Mapreduce with communication overlap (marco). J. Parallel Distrib. Comput. 73(5), 608–620 (2013)
Atta, F., Viglas, S.D., Niazi, S.: Sand join - a skew handling join algorithm for google’s mapreduce framework. In: 2011 IEEE 14th International Multitopic Conference (INMIC), pp. 170–175, December 2011
Blanas, S., Patel, J.M., Ercegovac, V., Rao, J., Shekita, E.J., Tian, Y.: A comparison of join algorithms for log processing in mapreduce. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6–10, 2010, pp. 975–986 (2010)
Bruno, N., Kwon, Y.C., Wu, M.-C.: Advanced join strategies for large-scale distributed computation. PVLDB 7(13), 1484–1495 (2014)
Dhawalia, P., Kailasam, S., Janakiram, D.: Chisel: a resource savvy approach for handling skew in mapreduce applications. In 2013 IEEE Sixth International Conference on Cloud Computing, Santa Clara, CA, USA, June 28 – July 3, 2013, pp. 652–660 (2013)
Ibrahim, S., Jin, H., Lu, L., Wu, S., He, B., Qi, L.: LEEN: locality/fairness-aware key partitioning for mapreduce in the cloud. In: Proceedings of the Cloud Computing, Second International Conference, CloudCom 2010, November 30 – December 3, 2010, Indianapolis, Indiana, USA, pp. 17–24 (2010)
Kwon, Y.C., Balazinska, M., Howe, B., Rolia, J.A.: Skewtune in action: Mitigating skew in mapreduce applications. PVLDB 5(12), 1934–1937 (2012)
Kwon, Y.C., Ren, K., Balazinska, M., Howe, B.: Managing skew in hadoop. IEEE Data Eng. Bull. 36(1), 24–33 (2013)
Lynden, S.J., Tanimura, Y., Kojima, I., Matono, A.: Dynamic data redistribution for mapreduce joins. In: IEEE 3rd International Conference on Cloud Computing Technology and Science, CloudCom 2011, Athens, Greece, November 29 – December 1, 2011, pp. 717–723 (2011)
Yu, X., Kostamaa, P.: Efficient outer join data skew handling in parallel DBMS. PVLDB 2(2), 1390–1396 (2009)
Xu, Y., Kostamaa, P., Zhou, X., Chen, L.: Handling data skew in parallel joins in shared-nothing systems. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10–12, 2008, pp. 1043–1052 (2008)
Xu, Y., Zou, P., Qu, W., Li, Z., Li, K., Cui, X.: Sampling-based partitioning in mapreduce for skewed data. In: ChinaGrid Annual Conference (ChinaGrid), 2012 Seventh, pp. 1–8, September 2012
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Lin, Z., Cai, M., Huang, Z., Lai, Y. (2015). SALA: A Skew-Avoiding and Locality-Aware Algorithm for MapReduce-Based Join. In: Dong, X., Yu, X., Li, J., Sun, Y. (eds) Web-Age Information Management. WAIM 2015. Lecture Notes in Computer Science(), vol 9098. Springer, Cham. https://doi.org/10.1007/978-3-319-21042-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-21042-1_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21041-4
Online ISBN: 978-3-319-21042-1
eBook Packages: Computer ScienceComputer Science (R0)