Colored Petri net model for evaluating the performance of MapReduce applications

During the last two decades, data analysis became a critical task in companies, often dealing with an exponential growing amount of data. As single machines or in-house distributed data analysis solutions become insufficient to deal with the complexity of information and the heterogeneity of tasks to perform on them, a flexible, reliable and scalable distributed computing solution is required. Hadoop has been for many years the de-facto standard in this field, implementing the MapReduce computational model and allowing other higher layer application to efficiently elaborate from Gigabytes to even Petabytes of data, operating on a cluster of commodity hardware. YARN, the recent evolution of Hadoop, decouples multi-tenancy and resource allocation from the application layer, allowing new computational paradigms (other than MapReduce) to emerge and provide an alternative to projects built on top of Hadoop. Tez is a framework built on top of YARN with the goal to allow developers to build applications organizing their workflows as a direct acyclic graph, moving from the Map-Reduce paradigm to the Map-Reduce-Reduce one. In the literature one may find several attempts to predict the duration of single MapReduce applications and just a few about a workload of such applications running concurrently. In any case, at the best of our knowledge and at the time of writing, all the previous works deal with the limited complexity of the previous two-phased MapReduce paradigm and the simple FIFO scheduler. In this thesis, a Colored Petri Net (CPN) model is designed to simulate a cluster running one or multiple Tez applications with the Capacity Scheduler as the underlying scheduling policy for resource allocation. The goal is to obtain an estimation of each DAG execution time in a multi-user environment.

Durante l'ultimo ventennio, l'analisi dei dati è diventato un elemento critico nelle aziende, spesso portate a confrontarsi con una crescita esponenziale delle informazioni in loro possesso. Nel momento in cui soluzioni ad hoc di data analysis divengono insufficenti per trattare la complessità delle informazioni e l'eterogeneità dei task definiti per le suddette analisi, sorge la necessità per una soluzione flessibile, affidabile e soprattutto scalabile. Hadoop per molti anni è stato lo standard de-facto in questo campo, implementando il modello computazionale MapReduce e permettendo ad applicazioni di più alto livello l'efficente elaborazione di quantità di dati che vanno dai Gigabyte fino a diversi Petabyte di dati, operando su cluster di hardware commerciale. YARN, la recente evoluzione di Hadoop, disaccoppia l'allocazione di risorse dal livello applicativo, permettendo a paradigmi diversi da MapReduce di emergere e fornire un'alternativa ai progetti costruiti per operare su Hadoop. Tez è un framework basato su YARN con l'obiettivo di permettere allo sviluppatore di scrivere applicazioni organizzando il workflow come un grafo aciclico diretto, spostandosi dal paradigma Map-Reduce a quello Map-Reduce-Reduce. Nella letteratura è possibile trovare diversi tentativi di predire la durata di singole applicazioni MapReduce e solo pochi riguardanti un workload di applicazioni concorrenti. In ogni caso, al meglio della nostra conoscenza, al momento le precedenti ricerche trattano la complessità limitata del paradigma MapReduce e il semplice scheduler FIFO. In questa tesi si è realizzato un modello basato su reti di petri colorate (CPN) per la simulazione di un cluster in cui vengano eseguite una o più applicazioni Tez con il Capacity Scheduler come politica di assegnamento delle risorse. L'obiettivo è la stima del tempo di esecuzione di ogni DAG in presenza di più classi di utenti.