{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T18:12:34Z","timestamp":1774635154280,"version":"3.50.1"},"reference-count":35,"publisher":"National Library of Serbia","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ComSIS","COMPUT SCI INF SYST","COMPUT SCI INFORM SY","COMPUTER SCI INFORM","COMSIS J"],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:p>Data locality is an important concept in big data processing. Most of the existing research optimized data locality from the aspect of task scheduling. However, as the execution container of tasks, the executors started on which nodes can directly affect the locality level achieved by the tasks. This paper tries to improve the data locality by executor allocation for reduce stage in Spark computing environment. Firstly, we calculate the network distance matrix of executors and formulate an optimal executor allocation problem to minimize the total communication distance. Then, when the network distance between executors satisfies the triangular inequality, an approximate algorithm is proposed; and when the network distance between executors does not satisfy the triangular inequality, a greedy algorithm is proposed. Finally, we evaluate the performance of our algorithms in a practical Spark cluster by using several representative micro-benchmarks (Sort and Join) and macro-benchmarks (PageRank and LDA). Experimental results show that the proposed algorithms can decrease the execution time of tasks for lower data communication.<\/jats:p>","DOI":"10.2298\/csis220131065f","type":"journal-article","created":{"date-parts":[[2022,12,23]],"date-time":"2022-12-23T14:49:21Z","timestamp":1671806961000},"page":"491-512","source":"Crossref","is-referenced-by-count":5,"title":["Optimizing data locality by executor allocation in spark computing environment"],"prefix":"10.2298","volume":"20","author":[{"given":"Zhongming","family":"Fu","sequence":"first","affiliation":[{"name":"Computer School, University of South China, and Hunan Provincial Base for Scientific and Technological Innovation Cooperation Hengyang, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mengsi","family":"He","sequence":"additional","affiliation":[{"name":"Computer School, University of South China, and Hunan Provincial Base for Scientific and Technological Innovation Cooperation Hengyang, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuo","family":"Tang","sequence":"additional","affiliation":[{"name":"College of Information Science and Engineering, Hunan University, and National Supercomputing Center Changsha, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Zhang","sequence":"additional","affiliation":[{"name":"Science and Technology on Parallel and Distributed Laboratory (PDL), National University of Defense Technology Changsha, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1078","reference":[{"key":"ref1","unstructured":"\u201dApache Spark\u201d,https:\/\/spark.apache.org\/"},{"key":"ref2","unstructured":"\u201dApache Hadoop\u201d,https:\/\/hadoop.apache.org\/"},{"key":"ref3","unstructured":"\u201dApache Spark\u201d,https:\/\/spark.apache.org\/docs\/3.3.0\/job-scheduling.html\/"},{"key":"ref4","unstructured":"\u201dRatings and classification data.\u201d,http:\/\/webscope.sandbox.yahoo.com"},{"key":"ref5","unstructured":"arxivbulkdata. https:\/\/arxiv.org\/help\/bulk data s3\/"},{"key":"ref6","unstructured":"Wikipedia corpus. https:\/\/www.english-corpora.org\/wiki\/"},{"key":"ref7","unstructured":"Wt10g. http:\/\/ir.dcs.gla.ac.uk\/test collections\/"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"Arslan, E., Shekhar, M., Kosar, T.: Locality and network-aware reduce task scheduling for dataintensive applications. In: Tang, W., Zhao, Y., Zheng, Z. (eds.) Proceedings of the 5th International Workshop on Data-Intensive Computing in the Clouds, DataCloud \u201914, New Orleans, Louisiana, USA, November 16-21, 2014. pp. 17-24. IEEE (2014)","DOI":"10.1109\/DataCloud.2014.10"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"Beaumont, O., Lambert, T., Marchal, L., Thomas, B.: Performance analysis and optimality results for data-locality aware tasks scheduling with replicated inputs. Future Gener. Comput. Syst. 111, 582-598 (2020)","DOI":"10.1016\/j.future.2019.08.024"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"Cheng, L., Wang, Y., Liu, Q., Epema, D.H.J., Liu, C., Mao, Y., Murphy, J.: Network-aware locality scheduling for distributed data operators in data centers. IEEE Trans. Parallel Distributed Syst. 32(6), 1494-1510 (2021)","DOI":"10.1109\/TPDS.2021.3053241"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"Dean, J., Ghemawat, S.: Mapreduce: Simplified data processing on large clusters. Commun. ACM 51(1), 107-113 (Jan 2008)","DOI":"10.1145\/1327452.1327492"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"Fu, Z., He, M., Tang, Z., Zhang, Y.: Optimizing data locality by executor allocation in reduce stage for spark framework. In: Shen, H., Sang, Y., Zhang, Y., Xiao, N., Arabnia, H.R., Fox, G., Gupta, A., Malek, M. (eds.) Parallel and Distributed Computing, Applications and Technologies. pp. 349-357. Springer International Publishing, Cham (2022)","DOI":"10.1007\/978-3-030-96772-7_32"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"Fu, Z., Tang, Z., Yang, L., Liu, C.: An optimal locality-aware task scheduling algorithm based on bipartite graph modelling for spark applications. IEEE Trans. Parallel Distributed Syst. 31(10), 2406-2420 (2020)","DOI":"10.1109\/TPDS.2020.2992073"},{"key":"ref14","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman (1979)"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"Gu, H., Li, X., Lu, Z.: Scheduling spark tasks with data skew and deadline constraints. IEEE Access 9, 2793-2804 (2021)","DOI":"10.1109\/ACCESS.2020.3040719"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"Guo, Z., Fox, G., Zhou, M.: Investigation of data locality in mapreduce. IEEE\/ACM International Symposium on Cluster Cloud & Grid Computing pp. 419-426 (2012)","DOI":"10.1109\/CCGrid.2012.42"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"Lee, S., Jo, J., Kim, Y.: Survey of data locality in apache hadoop. In: Iwashita, M., Shimoda, A., Chertchom, P. (eds.) 2019 IEEE International Conference on Big Data, Cloud Computing, Data Science & Engineering, BCD 2019, Honolulu, HI, USA, May 29-31, 2019. pp. 46-53. IEEE (2019)","DOI":"10.1109\/BCD.2019.8885148"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"Lu, X., Islam, N.S., Wasi-ur-Rahman, M., Jose, J., Subramoni, H., Wang, H., Panda, D.K.: High-performance design of hadoop RPC with RDMA over infiniband. In: 42nd International Conference on Parallel Processing, ICPP 2013, Lyon, France, October 1-4, 2013. pp. 641-650. IEEE Computer Society (2013)","DOI":"10.1109\/ICPP.2013.78"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"Ma, X., Fan, X., Liu, J., Li, D.: Dependency-aware data locality for mapreduce. IEEE Trans. Cloud Comput. 6(3), 667-679 (2018)","DOI":"10.1109\/TCC.2015.2511765"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"Morisawa, Y., Suzuki, M., Kitahara, T.: Flexible executor allocation without latency increase for stream processing in apache spark. In: 2020 IEEE International Conference on Big Data (Big Data). pp. 2198-2206 (2020)","DOI":"10.1109\/BigData50022.2020.9377967"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"Naik, N.S., Negi, A., Bapu, B.R.T., Anitha, R.: A data locality based scheduler to enhance mapreduce performance in heterogeneous environments. Future Gener. Comput. Syst. 90, 423- 434 (2019)","DOI":"10.1016\/j.future.2018.07.043"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"Neciu, L., Pop, F., Apostol, E.S., Truica, C.: Efficient real-time earliest deadline first based scheduling for apache spark. In: Potolea, R., Iancu, B., Slavescu, R.R. (eds.) 20th International Symposium on Parallel and Distributed Computing, ISPDC 2021, Cluj-Napoca, Romania, July 28-30, 2021. pp. 97-104. IEEE (2021)","DOI":"10.1109\/ISPDC52870.2021.9521640"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"Shabeera, T.P., Kumar, S.D.M.: A novel approach for improving data locality of mapreduce applications in cloud environment through intelligent data placement. Int. J. Serv. Technol. Manag. 26(4), 323-340 (2020)","DOI":"10.1504\/IJSTM.2020.10028331"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"Shabeera, T.P., Kumar, S.D.M., Chandran, P.: Curtailing job completion time in mapreduce clouds through improved virtual machine allocation. Comput. Electr. Eng. 58, 190-202 (2017)","DOI":"10.1016\/j.compeleceng.2016.10.009"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"Shang, F., Chen, X., Yan, C.: A strategy for scheduling reduce task based on intermediate data locality of the mapreduce. Clust. Comput. 20(4), 2821-2831 (2017)","DOI":"10.1007\/s10586-017-0972-7"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"Sun, M., Hang, Z., Zhou, X., Lu, K., Li, C.: Hpso: Prefetching based scheduling to improve data locality for mapreduce clusters. In: Conference on Design (2014)","DOI":"10.1007\/978-3-319-11194-0_7"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"Tan, J., Meng, S., Meng, X., Zhang, L.: Improving reducetask data locality for sequential mapreduce jobs. In: 2013 Proceedings IEEE INFOCOM. pp. 1627-1635 (2013)","DOI":"10.1109\/INFCOM.2013.6566959"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"Tang, S., He, B., Yu, C., Li, Y., Li, K.: A survey on spark ecosystem: Big data processing infrastructure, machine learning, and applications. IEEE Trans. Knowl. Data Eng. 34(1), 71- 91 (2022)","DOI":"10.1109\/TKDE.2020.2975652"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"Tang, Z., Ma, W., Li, K., Li, K.: A data skew oriented reduce placement algorithm based on sampling. IEEE Trans. Cloud Comput. 8(4), 1149-1161 (2020)","DOI":"10.1109\/TCC.2016.2607738"},{"key":"ref30","unstructured":"Vavilapalli, V.K., Murthy, A.C., Douglas, C., Agarwal, S., Konar, M., Evans, R., Graves, T., Lowe, J., Shah, H., Seth, S., Saha, B., Curino, C., O\u2019Malley, O., Radia, S., Reed, B., Baldeschwieler, E.: Apache hadoop YARN: yet another resource negotiator. In: Lohman, G.M. (ed.) ACM Symposium on Cloud Computing, SOCC \u201913, Santa Clara, CA, USA, October 1-3, 2013. pp. 5:1-5:16. ACM (2013)"},{"key":"ref31","unstructured":"Xia, T., Wang, L., Geng, Z.: A reduce task scheduler for mapreduce with minimum transmission cost based on sampling evaluation. International Journal of Database Theory & Application (2015)"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"Yan, X., Wong, B., Choy, S.: R3S: rdma-based RDD remote storage for spark. In: Proceedings of the 15th International Workshop on Adaptive and Reflective Middleware, ARM@Middleware 2016, Trento, Italy, December 12-16, 2016. pp. 4:1-4:6. ACM (2016)","DOI":"10.1145\/3008167.3008171"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"Yang, D., Rang, W., Cheng, D., Wang, Y., Tian, J., Tao, D.: Elastic executor provisioning for iterative workloads on apache spark. In: 2019 IEEE International Conference on Big Data (Big Data). pp. 413-422 (2019)","DOI":"10.1109\/BigData47090.2019.9006021"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"Zaharia, M., Borthakur, D., Sarma, J.S., Elmeleegy, K., Shenker, S., Stoica, I.: Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling. In: European Conference on Computer Systems. pp. 265-278 (2010)","DOI":"10.1145\/1755913.1755940"},{"key":"ref35","unstructured":"Zhang, X., Luo, F., Jia, Z., Shen, J.: Prefetching method for hadoop mapreduce environments. Xi\u2019an Dianzi Keji Daxue Xuebao\/Journal of Xidian University 41(2), 191-196 (2014)"}],"container-title":["Computer Science and Information Systems"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T06:35:45Z","timestamp":1721889345000},"score":1,"resource":{"primary":{"URL":"https:\/\/doiserbia.nb.rs\/Article.aspx?ID=1820-02142200065F"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023]]}},"URL":"https:\/\/doi.org\/10.2298\/csis220131065f","relation":{},"ISSN":["1820-0214","2406-1018"],"issn-type":[{"value":"1820-0214","type":"print"},{"value":"2406-1018","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]}}}