MapReduce rationality verification based on object Petri net

doi:10.21629/JSEE.2019.05.05

Journal of Systems Engineering and Electronics ›› 2019, Vol. 30 ›› Issue (5): 861-874.doi: 10.21629/JSEE.2019.05.05

• Electronics Technology • Previous Articles Next Articles

MapReduce rationality verification based on object Petri net

Zeliu DING^1,^2,*(), Deke GUO³(), Xi CHEN⁴(), Jin CHEN¹()

¹ School of Electronics Engineering, Navy University of Engineering, Wuhan 430033, China
² Research Center of Evaluation and Demonstration, Academy of Military Sciences, Beijing 100091, China
³ College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
⁴ School of Computer Science, McGill University, Montreal H3A 2A7, Canada

Received:2017-09-15 Online:2019-10-08 Published:2019-10-09
Contact: Zeliu DING E-mail:dingzeliu@gmail.com;guodeke@gmail.com;Chenxiwarm@gmail.com;198607@163.com
About author:DING Zeliu was born in 1983. He is a Ph.D. and an assistant research fellow in Academy of Military Sciences. His research interests are data center networks, cloud computing and complex information systems. E-mail: dingzeliu@gmail.com|GUO Deke was born in 1980. He is a Ph.D. and a professor in National University of Defense Technology. His research interests are P2P, data center networks, cloud computing and mobile computing. E-mail: guodeke@gmail.com|CHEN Xi was born in 1986. She is a Ph.D. in McGill University. Her research interests are cyberphysical systems and cloud computing. E-mail: Chenxiwarm@gmail.com|CHEN Jin was born in 1986. He is a lecturer in Naval University of Engineering. His research interests are underwater communication and picture processing. E-mail: chenjin 198607@163.com
Supported by:
the Natural Science Foundation of Hubei Province, China(2016CFB287);This work was supported by the Natural Science Foundation of Hubei Province, China (2016CFB287)

Abstract

Abstract:

As a powerful distributed data processing mechanism, MapReduce supports abundant parallel applications that process massive data on computer clusters. To process the massive data efficiently and correctly, a rational design for the MapReduce procedure is desired. An irrational MapReduce procedure can cause great waste of computing resources and even paralyze the exe-cution system. With the wide application of MapReduce, the unavoidable drawback of irrational MapReduce procedures becomes increasingly serious. To solve this problem, a method for verifying the rationality of a MapReduce procedure before executing it on a computer cluster is proposed. This method constructs the rationality criteria for MapReduce, and then studies an automatic approach for modelling MapReduce with an executable model object Petri net (OPN). Finally, the approaches for automatically identifying the rationality criteria by analyzing the consequence of model execution is developed. The results from extensive case studies demonstrate that the proposed method is feasible and effective.

Key words: MapReduce, rationality verification, cloud computing framework

Zeliu DING, Deke GUO, Xi CHEN, Jin CHEN. MapReduce rationality verification based on object Petri net[J]. Journal of Systems Engineering and Electronics, 2019, 30(5): 861-874.

Figures/Tables 11

Fig 1

Fig 2

Table 1

Fig 3

Table 2

Table 3

Assignments of Case 2"

$AS$	From	To	Keys	$\|\rm Keys\|$
${\rm Assign}_{1}$	${\rm Map}_{1}$	${\rm Reduce}_{1}$	$v1, v2, v3, v4, v5$	5
${\rm Assign}_{2}$	${\rm Map}_{1}$	${\rm Reduce}_{2}$	$v6, v7, v8, v9, v10$	5
${\rm Assign}_{3}$	${\rm Map}_{2}$	${\rm Reduce}_{1}$	$v1, v2, v3, v4, v5 $	5
${\rm Assign}_{4}$	${\rm Map}_{2}$	${\rm Reduce}_{2}$	$v6, v7, v8, v9, v10 $	5
${\rm Assign}_{5}$	${\rm Map}_{3}$	${\rm Reduce}_{1}$	$v1, v2, v3, v4, v5 $	5
${\rm Assign}_{6}$	${\rm Map}_{3}$	${\rm Reduce}_{2}$	$v6, v7, v8, v9, v10 $	5
${\rm Assign}_{7}$	${\rm Reduce}_{1}$	${\rm Map}_{4}$	$v1, v2, v3, v4, v5 $	5
${\rm Assign}_{8}$	${\rm Reduce}_{2}$	${\rm Map}_{5}$	$v6, v7, v8, v9, v10$	5
${\rm Assign}_{9}$	${\rm Map}_{4}$	${\rm Reduce}_{3}$	$(v1, v2), (v1, v3), (v3, v4), $ $(v3, v5) $	4
${\rm Assign}_{10}$	${\rm Map}_{4}$	${\rm Reduce}_{4}$	$(v3, v6), (v4, v6), (v4, v8), $ $(v6, v7) $	4
${\rm Assign}_{11}$	${\rm Map}_{5}$	${\rm Reduce}_{4}$	$(v3, v6), (v4, v6), (v4, v8), $ $(v6, v7) $	4
${\rm Assign}_{12}$	${\rm Map}_{5}$	${\rm Reduce}_{5}$	$(v7, v8), (v8, v9), (v8, v10), $ $(v7, v10) $	4
${\rm Assign}_{13}$	${\rm Reduce}_{3}$	${\rm Map}_{6}$	$(v1, v2), (v1, v3), (v3, v4), $ $(v3, v5) $	4
${\rm Assign}_{14}$	${\rm Reduce}_{4}$	${\rm Map}_{7}$	$(v3, v6), (v4, v6), (v4, v8), $ $(v6, v7) $	4
${\rm Assign}_{15}$	${\rm Reduce}_{5}$	${\rm Map}_{8}$	$(v7, v8), (v8, v9), (v8, v10), $ $(v7, v10) $	4
${\rm Assign}_{16}$	${\rm Map}_{6}$	${\rm Reduce}_{6} $	$v1, v2, v3, v4, v5 $	5
${\rm Assign}_{17}$	${\rm Map}_{7}$	${\rm Reduce}_{6} $	$v1, v2, v3, v4, v5 $	5
${\rm Assign}_{18}$	${\rm Map}_{7}$	${\rm Reduce}_{7} $	$v6, v7, v8, v9, v10 $	5
${\rm Assign}_{19}$	${\rm Map}_{8}$	${\rm Reduce}_{7} $	$v6, v7, v8, v9, v10 $	5
${\rm Assign}_{20}$	${\rm Reduce}_{6}$	${\rm Map}_{9} $	$v1, v2, v3, v4, v5 $	5
${\rm Assign}_{21}$	${\rm Reduce}_{7}$	${\rm Map}_{10}$	$v6, v7, v8, v9, v10 $	5
${\rm Assign}_{22}$	${\rm Map}_{9}$	${\rm Reduce}_{8}$	$(v1, v2), (v1, v3), (v3, v4), $ $(v3, v5) $	4
${\rm Assign}_{23}$	${\rm Map}_{9}$	${\rm Reduce}_{9}$	$(v3, v6), (v4, v6), (v4, v8), $ $(v6, v7) $	4
${\rm Assign}_{24}$	${\rm Map}_{9}$	${\rm Reduce}_{10}$	$(v7, v8), (v8, v9), (v8, v10), $ $(v7, v10) $	4
${\rm Assign}_{25}$	${\rm Map}_{10}$	${\rm Reduce}_{8}$	$(v1, v2), (v1, v3), (v3, v4), $$(v3, v5) $	4
${\rm Assign}_{26}$	${\rm Map}_{10}$	${\rm Reduce}_{9}$	$(v3, v6), (v4, v6), (v4, v8), $$(v6, v7) $	4
${\rm Assign}_{27}$	${\rm Map}_{10}$	${\rm Reduce}_{10}$	$(v7, v8), (v8, v9), (v8, v10), $$(v7, v10) $	4

Table 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

References 24

1	DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters. Proc. of the 6th USENIX Conference on Operating System Design and Implementation, 2004, 137- 150.
2	CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable:a distributed storage system for structured data. Proc. of the 7th USENIX Conference on Operating Systems Design and Implementation, 2006, 205- 218.
3	ISARD M, BUDIU M, YU Y, et al. Dryad:distributed dataparallel programs from sequential building blocks. Proc. of the 21st ACM Symposium on Operating Systems Principles, 2007, 59- 72.
4	Open source software for creating private and public clouds. http://www.openstack.org. Apache hadoop. http://hadoop.apache.org.
5	LIN J. The curse of Zipf and limits to parallelization: a look at the stragglers problem in MapReduce. Proc. of the 7th ACM Workshop on Large-Scale Distributed Systems for Information Retrieval, 2009: 57-62.
6	WU D, XIA Y, SUN X S, et al. Masking failures from application performance in data center networks with shareable backup. Proc. of the International Conference on Communication Architectures, Protocols&Apps, 2018: 176-190.
7	CHEN L, LINGYS J, CHEN K, et al. AuTO: scaling deep reinforcement learning for datacenter-scale automatic traffic optimization. Proc. of the International Conference on Communication Architectures, Protocols&Apps, 2018: 191-205.
8	MOTAMENI H, MOVAGHAR A, SHIRAZI B, et al. Analysis software with an object-oriented Petri net model. World Applied Sciences Journal, 2008, 3 (4): 565- 576.
9	HONG J, BAE D. Software modeling and analysis using a hierarchical object-oriented Petri net. Information Sciences, 2000, 130 (1/4): 133- 164.
10	SANDHOLM T, LAI K. MapReduce optimization using regulated dynamic prioritization. Proc. of the International Conference on Measurement and Modeling of Computer Systems, 2009: 299-310.
11	RANGER C, RAGHURAMAN R, PENMETSA A, et al. Evaluating MapReduce for multi-core and multiprocessor systems. Proc. of the 13th IEEE International Symposium on High-Performance Computer Architecture, 2007: 13-24.
12	LAMMEL R. Google's MapReduce programming model revisited. Elsevier Science of Computer Programming, 2008, 70 (1): 1- 30. doi: 10.1016/j.scico.2007.07.001
13	ZAHARIA M, KONWINSKI A, JOSEPH A D, et al. Improving MapReduce performance in heterogeneous environments. Proc. of the 8th USENIX Conference on Operating Systems Design and Implementation, 2008: 29-42.
14	KAVULYA S, TAN J, GANDHI R, et al. An analysis of traces from a production MapReduce cluster. Pittsburgh, USA: Parallel Data Laboratory at Carnegie Mellon University, 2009.
15	REN X, ANANTHANARAYANAN G, WIERMAN A, et al. Hopper: decentralized speculation-aware cluster scheduling at scale. Proc. of the International Conference on Communication Architectures, Protocols&Apps, 2015: 379-392.
16	WEI W, DU J, YU T, et al. SecureMR:a service integrity assurance framework for MapReduce. Proc. of the IEEE Annual Computer Security Applications Conference, 2009, 73- 82.
17	ZHU Y, KANG N, CAO J. Packet-level telemetry in large datacenter networks. Proc. of the International Conference on Communication Architectures, Protocols&Apps, 2015: 479-491.
18	YANG H, DASDAN A, HSIAO R L, et al. Map-ReduceMerge: simplified relational data processing on large clusters. Proc. of the International Conference on Management of Data, 2007: 1029-1040.
19	KRUIJF M, SANKARALINGAM K. MapReduce for the Cell B.E. architecture. IBM Journal of Research and Development, 2009, 53(5): 747-758.
20	DEAN J, GHEMAWAT S. MapReduce:a flexible data processing tool. Communications of the ACM, 2010, 53 (1): 72- 77.
21	HUANG B, ZHOU M, ZHANG P, et al. Speedup techniques for multi-objective integer programs in designing optimal and structurally simple supervisors of AMS. IEEE Trans. on Systems, Man and Cybernetics: Systems, 2018, 48(1): 77-88.
22	HUANG B, ZHOU M C, HUANG Y S, et al. Supervisor synthesis for FMS based on critical activity places. IEEE Trans. on Systems, Man and Cybernetics:Systems, 2017, 49 (5): 1- 10.
23	COHEN J. Graph twiddling in a MapReduce world. IEEE Computing in Science and Engineering, 2009, 2 (4): 29- 41.
24	WEISSTEIN E. Floyd-Warshall algorithm. http://mathworld.wolfram.com/Floyd-WarshallAlgorithm.html.

Suitability	OPN	Standard Petri Net	OPNET	FSA
Elements correspondence	Yes	Yes	No	No
Hierarchical structure	Yes	No	Yes	No
Process modelling	Yes	Yes	No	Yes
Visual modelling	Yes	Yes	Yes	Yes

MapReduce rationality verification based on object Petri net

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 11

References 24

Related Articles 0

Recommended Articles

Metrics

Comments