Game theory models for MapReduce : joint admission control and capacity allocation

Nowadays many companies have at their disposal large amounts of raw, unstructured data. With the term Big Data we refer to the analysis of huge datasets, allowing the extraction of information of utmost importance for business purposes. Among the enabling technologies, a central place is held by the MapReduce framework, in particular its open source implementation, Apache Hadoop. For cost effectiveness considerations, a common approach entails sharing server clusters among multiple user classes. Such a common infrastructure should provide every user with a fair share of computational resources, ensuring that Service Level Agreements (SLAs) are met and avoiding wastes. In this work we consider mathematical programming problems that model the optimal allocation of computational resources in a cluster, in order to develop new capacity allocation techniques, allowing for better performance in shared datacenters. Our goal is the reduction of power consumption, while respecting the deadlines stated in the SLAs and avoiding penalties associated with job rejections. At the core of this approach there is the development of a distributed algorithm, based on Game Theory models and techniques, and enabling run-time capacity allocation, hence the need to split the original problem of resource allocation in MapReduce environments into two classes of problems, one for the central Resource Manager and the other for each Application Master. Further improvements could be gained taking into account also the issue of data locality, which can greatly impact performance in the execution of MapReduce jobs.

Oggi molte aziende hanno a disposizione grandi quantità di dati molto spesso non strutturati. Con il termine Big Data si fa riferimento all’analisi di grandi moli di dati, permettendo l’estrazione di informazioni di massima importanza per gli obiettivi aziendali. Tra le tecnologie abilitanti, il framework MapReduce occupa un ruolo centrale, in particolare con la sua implementazione open source, Apache Hadoop. Per ragioni economiche, una prassi comune prevede la condivisione di cluster di server tra più classi di utenti. Tale infrastruttura comune dovrebbe fornire ad ogni utente una giusta quota di risorse di calcolo, garantendo che i contratti di Service Level Agreements (SLAs) siano soddisfatti ed evitando sprechi, come l’utilizzo inefficiente delle risorse. In questo lavoro di tesi si propongono problemi di programmazione matematica per modellare l’allocazione ottimale delle risorse computazionali in un cluster, al fine di sviluppare nuove tecniche di allocazione delle risorse, consentendo una migliore performance in datacenter condivisi. L’obiettivo è la riduzione del consumo di energia, rispettando i termini indicati negli SLAs ed evitando penali associate ad obiettivi di prestazioni non raggiunti. Al centro di questo approccio si pone lo sviluppo di un algoritmo distribuito, basato su modelli e tecniche di Teoria dei Giochi, che consenta l’allocazione della capacità di calcolo a run-time. Da qui sorge la necessità di suddividere il problema originale di allocazione delle risorse in ambiente MapReduce in due classi di problemi, uno per il Resource Manager centrale e l’altra per ogni Application Master. Ulteriori lavori futuri faranno rifermiento ad estensioni possibili tenendo conto anche della data locality, che può influire notevolmente sulle prestazioni nell’esecuzione dei job MapReduce.