Using symbolic execution to improve the runtime management of spark applications

The need to crunch a steadily growing amount of data generated by the modern applications is driving an increasing demand of flexible computing power, often satisfied by cloud computing solutions. Cloud computing revolutionized the way computer infrastructures are abstracted and used by exploiting virtualization and providing an easy access to resources through the Internet. Big data is a research field that deals with ways to analyze and extract information from data sets containing structured and unstructured data whose size is so large that makes the processing of data with traditional databases and applications very difficult or practically impossible. The processing of these data therefore requires the use of distributed frameworks specialized for the parallel execution of programs, such as Apache Hadoop [5] and Apache Spark. These specialized frameworks are used to transform the applications in atomic parts that can be executed in a distributed cluster of physical or virtual machines. Hadoop uses the Map-Reduce programming model that was firstly introduced by Google and consists of two distinct phases: Map and Reduce. The former processes and transforms a block of data to produce key-value pairs (tuples) as intermediate outputs, the latter aggregates these tuples into a final output. A more advanced solution is represented by Apache Spark, that allows for faster executions by avoiding or limiting the use of the persistent storage and it provides a more sophisticated programming model based on parallel execution plans (PEPs) which are represented as directed acyclic graph (DAG) of phases. Big data applications pose new challenges in satisfying requirements on the Quality of Service (QoS) provided to end users. In the context of traditional applications (e.g. web) this problem has often been faced using self-adaptive systems that control runtime KPIs (Key Performance Indicators) against changes in the application context and workload. Compared to traditional applications, where a single execution lasts ten to hundreds of milliseconds, big data applications might require minutes or hours to process large datasets, thus QoS must consider the execution of single runs. Therefore, in this domain the QoS is often defined by means of deadlines, that are the maximum allowed duration of as single application execution. The execution time of big-data applications depends on many factors such as the amount of computing resources available (cpu’s, memory, storage) and the concurrent execution of other applications on the same cluster. Therefore, in the literature one can find several approaches that focus on resource allocation or scheduling techniques in order to reduce deadline violations by using different techniques such as integer linear programming, machine learning and control theory. All of these approaches use the knowledge of the PEP to reason, predict or estimate the application execution time and work under the assumption that the application PEP does not change under different input datasets or application parameters. Unfortunately, this is true only if the application code does not contain any conditional branch whose outcome depends on user input values or the result of previous calculations involving input data. Otherwise, different application PEPs could be needed to describe all the possible execution flows generated by the combinations of all the different branch outcomes in the application code. Without considering all these PEPs the analysis of the application could be significantly unprecise. xSpark, developed at Politecnico di Milano, is an extension of the Apache Spark framework that offers fine-grained dynamic resource allocation using lightweight containers and control-theoretical planners. It allows users to set application deadlines (which is not possible using Spark) and uses the knowledge of the application PEP, retrieved during a profiling phase, to dynamically allocate resources to the application. xSpark does not consider loops or conditional branches in the application code and assumes that the PEP is unique. xSparkSEEPEP, the solution described in this thesis, extends xSpark capability to safely run multi-PEP applications, by exploiting symbolic execution. At each decisional branch outcome in the application, xSparkSEEPEP determines which PEPs are still valid and prunes the PEPs tree, removing the invalid PEPs, thus leaving only the valid ones in the PEPs tree. A heuristic is used to select the PEP to execute among the valid ones, in order to minimize the risk of missing the deadline while maximizing the CPU usage efficiency. xSparkSEEPEP is the result of the integration of SEEPEP, a tool exploiting symbolic execution to discover all possible application PEPs produced by different inputs and parameters, with a modified version of xSpark. We tested xSparkSEEPEP with two applications, Promocalls and Louvain, that uses GraphX, a Spark library specialized for graph processing. The evaluation shows that SEEPEP is able to effectively extract all the PEPs generated by Spark applications and that xSparkSEEPEP effectively and efficiently controls the allocation of resources during the execution of PromoCalls and Louvain, keeping the execution times within considered deadlines with significantly smaller errors and consuming a lower amount of resources than the original version of xSpark. Since the current solution focuses on controlling a single application, a future work could be directed at extending xSparkSEEPEP to control multiple concurrent applications.

Il bisogno di elaboraree una quantità sempre crescente di dati generati dalle moderne applicazioni sta guidando una crescente domanda di potenza di calcolo flessibile, spesso soddisfatta dalle soluzioni di cloud computing. Il cloud computing ha rivoluzionato il modo in cui le nfrastrutture informatiche vengono astratte e utilizzate sfruttando la virtualizzazione e fornendo un facile accesso alle risorse attraverso Internet. I big data sono un campo di ricerca che si occupa dei modi per analizzare ed estrarre informazioni da set di dati contenenti dati strutturati e non strutturati, la cui dimensione è così grande che ne rende molto difficile o praticamente impossibile l’elaborazione con database e applicazioni tradizionali. L’elaborazione di questi dati richiede quindi l’uso di framework distribuiti specializzati per l’esecuzione parallela di programmi, come Apache Hadoop e Apache Spark. Questi framework specializzati sono utilizzati per trasformare le applicazioni in parti atomiche che possono essere eseguite in un cluster distribuiti di macchine fisiche o virtuali. Hadoop utilizza il modello di programmazione Map-Reduce che è stato inizialmente introdotto da Google e si compone di due fasi distinte: Map e Reduce. Il primo processa e trasforma un blocco di dati per produrre coppie chiave-valore (tuple) come output intermedi, quest’ultimo aggrega queste tuple in un output finale. Una soluzione più avanzata è rappresentata da Apache Spark, che consente esecuzioni più rapide evitando o limitando l’utilizzo dell’archiviazione persistente e fornisce un modello di programmazione più sofisticato basato su piani di esecuzione paralleli (PEPs) che sono rappresentati come un grafico aciclico orientato (DAG) delle fasi. Le applicazioni di big data pongono nuove sfide nel soddisfare i requisiti sulla Qualità del Servizio (QoS) fornita agli utenti finali. Nel contesto delle applicazioni tradizionali (ad esempio le applicazioni web), questo problema è stato spesso affrontato utilizzando sistemi autoadattativi che controllano KPIs (Key Performance Indicators) a runtime rispetto ai cambiamenti nel contesto dell’applicazione e nel carico di lavoro. Rispetto alle applicazioni tradizionali, dove una singola esecuzione dura da decine a centinaia di millisecondi, le applicazioni di big data potrebbero richiedere minuti o ore per elaborare grandi dataset, quindi il QoS deve considerare l’esecuzione di singole esecuzioni. Pertanto, in questo dominio il QoS viene spesso definito attraverso deadline, che sono la durata massima consentita della singola esecuzione dell’applicazione. Il tempo di esecuzione delle applicazioni Big Data dipende da molti fattori come la quantità di risorse di calcolo disponibili (CPU, memoria, storage) e l’esecuzione simultanea di altre applicazioni nello stesso cluster. Pertanto, in letteratura si possono trovare diversi approcci che si concentrano sull’assegnazione delle risorse o sulle tecniche di schedulazione al fine di ridurre le violazioni delle scadenze utilizzando diverse tecniche come la programmazione lineare intera, l’apprendimento automatico e la teoria del controllo. Tutti questi approcci utilizzano la conoscenza del PEP per ragionare, prevedere o stimare il tempo di esecuzione dell’applicazione e lavorare partendo dal presupposto che il PEP dell’applicazione non cambi a seconda dei diversi dataset di input o parametri dell’applicazione. Sfortunatamente, questo è vero solo se il codice dell’applicazione non contiene alcun branch condizionale il cui risultato dipende dai valori di input dell’utente o dal risultato di calcoli precedenti che coinvolgono dati di input. In caso contrario, potrebbero essere necessari diversi PEPs delle applicazioni per descrivere tutti i possibili flussi di esecuzione generati dalle combinazioni di tutti i diversi risultati che derivano dal codice dell’applicazione. Senza considerare tutti questi PEPs, l’analisi dell’applicazione potrebbe essere notevolmente imprecisa. xSpark, sviluppato al Politecnico di Milano, è un’estensione del framework Apache Spark che offre un’allocazione dinamica delle risorse a grana fine utilizzando contenitori leggeri e pianificatori teorici del controllo. Consente agli utenti di impostare le deadline delle applicazioni (cosa non possibile utilizzando Spark) e utilizza la conoscenza del PEP dell’applicazione, recuperato durante una fase di profilazione, per allocare dinamicamente le risorse all’applicazione. xSpark non considera loop o branch condizionali nel codice dell’applicazione e presuppone che il PEP sia univoco. xSparkSEEPEP, la soluzione descritta in questa tesi, estende la capacità di xSpark di eseguire in sicurezza applicazioni multi-PEP, sfruttando l’esecuzione simbolica. Ad ogni risultato di un branch decisionale nell’applicazione, xSparkSEEPEP determina quali PEPs sono ancora validi e pota l’albero dei PEPs, rimuovendo i PEPs non più validi, lasciando così solo quelli validi nell’albero dei PEPs. Una euristica viene utilizzata per selezionare il PEP da eseguire tra quelli validi, al fine di ridurre al minimo il rischio di oltrepassare la deadline, massimizzando l’efficienza di utilizzo della CPU. xSparkSEEPEP è il risultato dell’integrazione di SEEPEP, uno strumento che sfrutta l’esecuzione simbolica per scoprire tutti i possibili PEP delle applicazioni prodotte da diversi input e parametri, con una versione modificata di xSpark. Abbiamo testato xSparkSEEPEP con due applicazioni, Promocalls e Louvain, che utilizza GraphX, una libreria Spark specializzata per l’elaborazione di grafi. La valutazione mostra che SEEPEP è in grado di estrarre efficacemente tutti i PEPs generati dalle applicazioni Spark e che xSparkSEEPEP controlla in modo efficace ed efficiente l’allocazione delle risorse durante l’esecuzione di PromoCalls e Louvain, mantenendo i tempi di esecuzione entro scadenze prefissate con errori significativamente minori e consumando una quantità di risorse inferiore rispetto alla versione originale di xSpark. Poiché la soluzione attuale si concentra sul controllo di una singola applicazione, un lavoro futuro potrebbe essere diretto all’estensione di xSparkSEEPEP per controllare più applicazioni concorrenti.