journal article·2018-11-10Open access

DynDL: Scheduling Data-Locality-Aware Tasks with Dynamic Data Transfer Cost for Multicore-Server-Based Big Data Clusters

Jiahui Jin, Qi An, Wei Zhou, Jiakai Tang, Runqun Xiong

Applied Sciences· Volume 8· Issue 11

Abstract

Network bandwidth is a scarce resource in big data environments, so data locality is a fundamental problem for data-parallel frameworks such as Hadoop and Spark. This problem is exacerbated in multicore server-based clusters, where multiple tasks running on the same server compete for the server’s network bandwidth. Existing approaches solve this problem by scheduling computational tasks near the input data and considering the server’s free time, data placements, and data transfer costs. However, such approaches usually set identical values for data transfer costs, even though a multicore server’s data transfer cost increases with the number of data-remote tasks. Eventually, this hampers data-processing time, by minimizing it ineffectively. As a solution, we propose DynDL (Dynamic Data Locality), a novel data-locality-aware task-scheduling model that handles dynamic data transfer costs for multicore servers. DynDL offers greater flexibility than existing approaches by using a set of non-decreasing functions to evaluate dynamic data transfer costs. We also propose online and offline algorithms (based on DynDL) that minimize data-processing time and adaptively adjust data locality. Although DynDL is NP-complete (nondeterministic polynomial-complete), we prove that the offline algorithm runs in quadratic time and generates optimal results for DynDL’s specific uses. Using a series of simulations and real-world executions, we show that our algorithms are 30% better than algorithms that do not consider dynamic data transfer costs in terms of data-processing time. Moreover, they can adaptively adjust data localities based on the server’s free time, data placement, and network bandwidth, and schedule tens of thousands of tasks within subseconds or seconds.
Source: crossref · Quality: baseline

Research context

OpenAlex topics: Cloud Computing and Resource Management · Distributed and Parallel Computing Systems · Parallel Computing and Optimization Techniques

SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.

Affiliations

School of Computer Science and Engineering, Southeast University, Nanjing 211189, China

School of Cyber Science and Engineering, Southeast University, Nanjing 211189, China

References (50)

Show source-provided references
1. Dean, J., and Ghemawat, S. (2004, January 6–8). MapReduce: Simplified Data Processing on Large Clusters. Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI’04), San Francisco, CA, USA.
2. (2018, October 01). Apache Hadoop. Available online: http://hadoop.apache.org/.
3. Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., and Stoica, I. (2010, January 22–25). Spark: Cluster Computing with Working Sets. Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud’10), Boston, MA, USA.
4. Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., and Czajkowski, G. (2010, January 6–10). Pregel: A system for large-scale graph processing. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’10), Indianapolis, IN, USA.10.1145/1807167.1807184 ↗
5. Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., and Isard, M. (2016, January 2–4). TensorFlow: A System for Large-Scale Machine Learning. Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI’16), Savannah, GA, USA.
6. Zhang, H., Cho, B., Seyfe, E., Ching, A., and Freedman, M.J. (2018, January 23–26). Riffle: Optimized shuffle service for large-scale data analytics. Proceedings of the Thirteenth EuroSys Conference (EuroSys’18), Porto, Portugal.10.1145/3190508.3190534 ↗
7. Morin, C., and Muller, G. (2010, January 13–16). Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling. Proceedings of the 5th European Conference on Computer Systems (EuroSys’10), Paris, France.
8. Isard, M., Prabhakaran, V., Currey, J., Wieder, U., Talwar, K., and Goldberg, A.V. (2009, January 11–14). Quincy: fair scheduling for distributed computing clusters. Proceedings of the 22nd ACM Symposium on Operating Systems Principles (SOSP’09), Big Sky, Montana, USA.10.1145/1629575.1629601 ↗
9. Keeton, K., and Roscoe, T. (2016, January 2–4). Firmament: Fast, Centralized Cluster Scheduling at Scale. Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI’16), Savannah, GA, USA.
10. Wang, W., Zhu, K., Ying, L., Tan, J., and Zhang, L. (2013, January 14–19). Map task scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality. Proceedings of the 2013 IEEE Conference on Computer Communications (INFOCOM’13), Turin, Italy.10.1109/INFCOM.2013.6566957 ↗
11. Xie, Q., Yekkehkhany, A., and Lu, Y. (2016, January 10–14). Scheduling with multi-level data locality: Throughput and heavy-traffic optimality. Proceedings of the 35th Annual IEEE International Conference on Computer Communications (INFOCOM’16), San Francisco, CA, USA.10.1109/INFOCOM.2016.7524416 ↗
12. Tan, J., Meng, X., and Zhang, L. (2013, January 14–19). Coupling task progress for MapReduce resource-aware scheduling. Proceedings of the 2013 IEEE Conference on Computer Communications (INFOCOM’13), Turin, Italy.10.1109/INFCOM.2013.6566958 ↗
13. auf der Heide, F.M., and Phillips, C.A. (2010, January 13–15). Assigning tasks for efficiency in Hadoop: extended abstract. Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’10), New York, NY, USA.
14. Jin, J., Luo, J., Song, A., Dong, F., and Xiong, R. (2011, January 23–26). BAR: An Efficient Data Locality Driven Task Scheduling Algorithm for Cloud Computing. Proceedings of the 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid’11), Newport Beach, CA, USA.10.1109/CCGrid.2011.55 ↗
15. Pandas: Robust Locality-Aware Scheduling with Stochastic Delay Optimality10.1109/TNET.2016.2606900 ↗
16. Xie, D., Li, F., Yao, B., Li, G., Zhou, L., and Guo, M. (July, January 26). Simba: Efficient In-Memory Spatial Analytics. Proceedings of the 2016 International Conference on Management of Data (SIGMOD’16), San Francisco, CA, USA.10.1145/2882903.2915237 ↗
17. Armbrust, M., Xin, R.S., Lian, C., Huai, Y., Liu, D., Bradley, J.K., Meng, X., Kaftan, T., Franklin, M.J., and Ghodsi, A. (June, January 31). Spark SQL: Relational Data Processing in Spark. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD’15), Victoria, Australia.10.1145/2723372.2742797 ↗
18. Tigani, J., and Naidu, S. (2014). Google BigQuery Analytics, John Wiley & Sons.
19. GLPP: A Game-Based Location Privacy-Preserving Framework in Account Linked Mixed Location-Based Services10.1155/2018/9148768 ↗
20. Centrality in heterogeneous social networks for lurkers detection: An approach based on hypergraphs10.1002/cpe.4188 ↗
21. Benchmarking big data architectures for social networks data processing using public cloud platforms10.1016/j.future.2018.05.068 ↗
22. Bao, Y., Peng, Y., Wu, C., and Li, Z. (arXiv, 2018). Online Job Scheduling in Distributed Machine Learning Clusters, arXiv.10.1109/INFOCOM.2018.8486422 ↗
23. Classification Framework of MapReduce Scheduling Algorithms10.1145/2693315 ↗
24. Zaharia, M., Konwinski, A., Joseph, A.D., Katz, R.H., and Stoica, I. (2008, January 8–10). Improving MapReduce Performance in Heterogeneous Environments. Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI’08), San Diego, CA, USA.
25. Xu, H., and Lau, W.C. (2015, January 2–5). Task-Cloning Algorithms in a MapReduce Cluster with Competitive Performance Bounds. Proceedings of the 35th IEEE International Conference on Distributed Computing Systems (ICDCS’15), Vienna, Austria.10.1109/ICDCS.2015.42 ↗
26. Pham, X., and Huh, E. (2016, January 5–7). Towards task scheduling in a cloud-fog computing system. Proceedings of the 18th Asia-Pacific Network Operations and Management Symposium (APNOMS’16), Kanazawa, Japan.
27. Energy-Aware Scheduling of MapReduce Jobs for Big Data Applications10.1109/TPDS.2014.2358556 ↗
28. Kaur, K., Kumar, N., Garg, S., and Rodrigues, J.J.P.C. (2018, January 20–24). EnLoc: Data Locality-Aware Energy-Efficient Scheduling Scheme for Cloud Data Centers. Proceedings of the 2018 IEEE International Conference on Communications (ICC2018), Kansas City, MO, USA.10.1109/ICC.2018.8422225 ↗
29. Cost-Effective Resource Provisioning for MapReduce in a Cloud10.1109/TPDS.2014.2320498 ↗
30. Sandholm, T., and Lai, K. (2009, January 15–19). MapReduce optimization using regulated dynamic prioritization. Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’09), Seattle, WA, USA.10.1145/1555349.1555384 ↗
31. A Data-Emergency-Aware Scheduling Scheme for Internet of Things in Smart Cities10.1109/TII.2017.2763971 ↗
32. A data-aware scheduling strategy for workflow execution in clouds10.1002/cpe.4229 ↗
33. Zhu, Y., Jiang, Y., Wu, W., Ding, L., Teredesai, A., Li, D., and Lee, W. (May, January 27). Minimizing makespan and total completion time in MapReduce-like systems. Proceedings of the 2014 IEEE Conference on Computer Communications (INFOCOM’14), Toronto, ON, Canada.10.1109/INFOCOM.2014.6848159 ↗
34. Takefusa, A., Tatebe, O., Matsuoka, S., and Morita, Y. (2003, January 22–24). Performance Analysis of Scheduling and Replication Algorithms on Grid Datafarm Architecture for High-Energy Physics Applications. Proceedings of the 12th International Symposium on High-Performance Distributed Computing (HPDC’03), Seattle, WA, USA.
35. Tatebe, O., Morita, Y., Matsuoka, S., Soda, N., and Sekiguchi, S. (2002, January 22–24). Grid Datafarm Architecture for Petascale Data Intensive Computing. Proceedings of the 2nd IEEE International Symposium on Cluster Computing and the Grid (CCGrid’02), Berlin, Germany.
36. Decoupling Computation and Data Scheduling in Distributed Data-Intensive Applications
37. Raicu, I., Foster, I.T., Zhao, Y., Little, P., Moretti, C.M., Chaudhary, A., and Thain, D. (2009, January 11–13). The quest for scalable support of data-intensive workloads in distributed systems. Proceedings of the 18th ACM International Symposium on High Performance Distributed Computing (HPDC’09), Garching, Germany.10.1145/1551609.1551642 ↗
38. Raicu, I., Zhao, Y., Dumitrescu, C., Foster, I.T., and Wilde, M. (2007, January 10–16). Falkon: A Fast and Light-weight tasK executiON framework. Proceedings of the ACM/IEEE Conference on High Performance Networking and Computing (SC’07), Reno, NV, USA.10.1145/1362622.1362680 ↗
39. (2018, October 01). Max-Min Fairness—Wikipedia. Available online: http://en.wikipedia.org/wiki/Max-min fairness.
40. Dynamic Resource Allocation for MapReduce with Partitioning Skew10.1109/TC.2016.2532860 ↗
41. Wang, B., Jiang, J., and Yang, G. (May, January 26). ActCap: Accelerating MapReduce on heterogeneous clusters with capability-aware data placement. Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM’15), Hong Kong, China.10.1109/INFOCOM.2015.7218509 ↗
42. Yu, X., and Hong, B. (2015, January 25–29). Grouping Blocks for MapReduce Co-Locality. Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium (IPDPS ’15), Hyderabad, India.10.1109/IPDPS.2015.16 ↗
43. Dependency-Aware Data Locality for MapReduce10.1109/TCC.2015.2511765 ↗
44. Locality-aware and load-balanced static task scheduling for MapReduce10.1016/j.future.2018.06.035 ↗
45. Choi, D., Jeon, M., Kim, N., and Lee, B. (2018). An Enhanced Data-Locality-Aware Task Scheduling Algorithm for Hadoop Applications. IEEE Syst. J., 1–12.10.1109/JSYST.2017.2764481 ↗
46. Beaumont, O., Lambert, T., Marchal, L., and Thomas, B. (2018, January 21–25). Data-Locality Aware Dynamic Schedulers for Independent Tasks with Replicated Inputs. Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW’18), Vancouver, BC, Canada.10.1109/IPDPSW.2018.00187 ↗
47. An improved algorithm for optimizing MapReduce based on locality and overlapping10.26599/TST.2018.9010115 ↗
48. Semi-matchings for bipartite graphs and load balancing10.1016/j.jalgor.2005.01.003 ↗
49. Bounds for certain multiprocessing anomalies10.1002/j.1538-7305.1966.tb01709.x ↗
50. Xie, Q., and Lu, Y. (May, January 26). Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality. Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM’15), Hong Kong, China.10.1109/INFOCOM.2015.7218468 ↗