nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Modeling Big Data Processing Programs

verfasst von : João Batista de Souza Neto, Anamaria Martins Moreira, Genoveva Vargas-Solar, Martin A. Musicante

Erschienen in: Formal Methods: Foundations and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We propose a new model for data processing programs. Our model generalizes the data flow programming style implemented by systems such as Apache Spark, DryadLINQ, Apache Beam and Apache Flink. The model uses directed acyclic graphs (DAGs) to represent the main aspects of data flow-based systems, namely, operations over data (filtering, aggregation, join) and program execution, defined by data dependence between operations. We use Monoid Algebra to model operations over distributed, partitioned datasets and Petri Nets to represent the data flow. This approach allows the data processing program specification to be agnostic of the target Big Data processing system. As a first application of the model, we used it to formalize mutation operators for the application of mutation testing in Big Data processing programs. The testing tool TRANSMUT-Spark implement these operators.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Calculational Proofs in Relational Graphical Linear Algebra

Nächstes Kapitel Optimization of Timed Scenarios

TRANSMUT-Spark is publicly available at https://github.com/jbsneto-ppgsc-ufrn/transmut-spark.

Ammann, P., Offutt, J.: Introduction to Software Testing, 2nd edn. Cambridge University Press, New York (2017)

Bajaber, F., Elshawi, R., Batarfi, O., Altalhi, A., Barnawi, A., Sakr, S.: Big Data 2.0 processing systems: taxonomy and open challenges. J. Grid Comput. 14(3), 379–405 (2016). https://doi.org/10.1007/s10723-016-9371-1CrossRef

Beam, A.: Apache Beam: an advanced unified programming model (2016). https://beam.apache.org/

Brookes, S.D., Hoare, C.A.R., Roscoe, A.W.: A theory of communicating sequential processes. J. ACM 31(3), 560–599 (1984). https://doi.org/10.1145/828.833MathSciNetCrossRefMATH

Carbone, P., Ewen, S., Haridi, S., Katsifodimos, A., Markl, V., Tzoumas, K.: Apache flink: stream and batch processing in a single engine. IEEE Data Eng. Bull. 38(4), 28–38 (2015)

Chen, Y.-F., Hong, C.-D., Lengál, O., Mu, S.-C., Sinha, N., Wang, B.-Y.: An executable sequential specification for Spark aggregation. In: El Abbadi, A., Garbinato, B. (eds.) NETYS 2017. LNCS, vol. 10299, pp. 421–438. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59647-1_31CrossRef

Chlyah, S., Gesbert, N., Genevès, P., Layaïda, N.: An Algebra with a Fixpoint Operator for Distributed Data Collections, March 2019. https://hal.inria.fr/hal-02066649

Fegaras, L.: An algebra for distributed Big Data analytics. J. Funct. Program. 27, e27 (2017). https://doi.org/10.1017/S0956796817000193MathSciNetCrossRefMATH

Fegaras, L.: Compile-time query optimization for Big Data analytics. Open J. Big Data (OJBD) 5(1), 35–61 (2019). https://www.ronpub.com/ojbd/OJBD2019v5i1n02Fegaras.html

10.

Hadoop: Apache Hadoop Documentation (2019). https://hadoop.apache.org/docs/r2.7.3/

11.

Hidders, J., Kwasnikowska, N., Sroka, J., Tyszkiewicz, J., Van den Bussche, J.: Petri Net + nested relational calculus = dataflow. In: Meersman, R., Tari, Z. (eds.) OTM 2005. LNCS, vol. 3760, pp. 220–237. Springer, Heidelberg (2005). https://doi.org/10.1007/11575771_16CrossRef

12.

Hidders, J., Kwasnikowska, N., Sroka, J., Tyszkiewicz, J., Van den Bussche, J.: DFL: a dataflow language based on Petri Nets and nested relational calculus. Inf. Syst. 33(3), 261–284 (2008)CrossRef

13.

Jensen, K., Kristensen, L.M., Wells, L.: Coloured Petri Nets and CPN tools for modelling and validation of concurrent systems. Int. J. Softw. Tools Technol. Transf. 9(3), 213–254 (2007). https://doi.org/10.1007/s10009-007-0038-xCrossRef

14.

Kavi, K.M., Buckles, B.P., Bhat, N.: A formal definition of data flow graph models. IEEE Trans. Comput. C-35(11), 940–948 (1986). https://doi.org/10.1109/TC.1986.1676696

15.

Lee, E., Messerschmitt, D.: Pipeline interleaved programmable DSP’s: synchronous data flow programming. IEEE Trans. Acoust. Speech Signal Process. 35(9), 1334–1345 (1987)CrossRef

16.

Marconi, F., Quattrocchi, G., Baresi, L., Bersani, M.M., Rossi, M.: On the timed analysis of Big-Data applications. In: Dutle, A., Muñoz, C., Narkawicz, A. (eds.) NFM 2018. LNCS, vol. 10811, pp. 315–332. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77935-5_22CrossRef

17.

Murata, T.: Petri Nets: properties, analysis and applications. Proc. IEEE 77(4), 541–580 (1989). https://doi.org/10.1109/5.24143CrossRef

18.

Ono, K., Hirai, Y., Tanabe, Y., Noda, N., Hagiya, M.: Using Coq in specification and program extraction of Hadoop MapReduce applications. In: Barthe, G., Pardo, A., Schneider, G. (eds.) SEFM 2011. LNCS, vol. 7041, pp. 350–365. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24690-6_24CrossRef

19.

Petri, C.A.: Kommunikation mit Automaten. Ph.D. thesis, Universität Hamburg (1962). (in German)

20.

Souza Neto, J.B.: Transformation mutation for Spark programs testing. Ph.D. thesis, Federal University of Rio Grande do Norte (UFRN), Natal/RN, Brazil (2020). (in Portuguese)

21.

Souza Neto, J.B., Martins Moreira, A., Vargas-Solar, G., Musicante, M.A.: Mutation operators for large scale data processing programs in Spark. In: Dustdar, S., Yu, E., Salinesi, C., Rieu, D., Pant, V. (eds.) CAiSE 2020. LNCS, vol. 12127, pp. 482–497. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-49435-3_30CrossRef

22.

Yang, F., Su, W., Zhu, H., Li, Q.: Formalizing MapReduce with CSP. In: 2010 17th IEEE International Conference and Workshops on Engineering of Computer Based Systems, pp. 358–367 (2010)

23.

Yu, Y., et al.: DryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language. In: Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI 2008, pp. 1–14. USENIX Association, Berkeley, CA, USA (2008). http://dl.acm.org/citation.cfm?id=1855741.1855742

24.

Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: cluster computing with working sets. In: Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud 2010, p. 10. USENIX Association, Berkeley, CA, USA (2010). http://dl.acm.org/citation.cfm?id=1863103.1863113

Titel: Modeling Big Data Processing Programs
verfasst von: João Batista de Souza Neto
Anamaria Martins Moreira
Genoveva Vargas-Solar
Martin A. Musicante
Verlag: Springer International Publishing
Buch: Formal Methods: Foundations and Applications
Print ISBN: 978-3-030-63881-8

Electronic ISBN: 978-3-030-63882-5

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-63882-5_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"