Resource allocation and quality management in geo-distributed workflows

Abstract

As the amount of data being stored in geographically distributed data centers is growing and the need to analyze them in a fast manner remains, the option to aggregate them in a central location before processing them becomes significantly inefficient. Therefore, the need to analyze data closer to where they are produced arises. Numerous research efforts have been made to determine the optimal placement of such analysis, usually depicted as a Directed Acyclic Graph (DAG) consisting of multiple steps, to minimize various performance objectives. Additionally, the emergence of Internet of Things and edge computing paradigm where multiple sensors produce massive amounts of data that need to be analyzed in real-time using near-by devices, rather than the cloud, incurs extra challenges such as severe hardware and network heterogeneity, privacy and security constraints. Even after an optimized resource allocation plan is devised, the latency may still be high due to the amount of data being analyzed. Thus, there is a need for development of techniques that reduce this size while also account for the quality-of-result, through measuring the different dimensions of data quality, such as completeness. This thesis aims to address these challenges. First, a multi-objective resource allocation solution for geo-distributed analytics is proposed. The developed techniques take into consideration the heterogeneity of the network links, achieving an average 44.31% reduction of the total running time and at the same time a 50.12% reduction of traffic compared to the state-of- the-art solution. Moreover, a prototype on Apache Spark showcases the performance gains in a real-world scenario. Next, techniques for an edge computing environment that consider the heterogeneity of edge devices and network links, and privacy constraints while incorporating data quality verification tasks, are proposed. Evaluation of the proposed techniques through simulations shows improvements in terms of an objective function that considers latency and extent of quality checks, up to 2.56X compared to state-of-the-art solutions. In addition, the proposed solution reduces latency by up to 8X in 86.9% of cases compared to the default Apache Storm scheduler. Moreover, an empirical study on the performance and scalability benefits that big data frameworks can bring to data quality assessment is conducted. Additionally, the problem of jointly optimizing multiple DAGs is tackled though employing a technique that decides on task placements that efficiently utilize edge devices and finds optimal trade-offs between quality reduction and latency. Evaluation results in Apache Storm show reductions of latency up to 6X with an average speedup of 2.76X compared to the advanced Resource-Aware scheduler. The techniques are also transferred to a data replication problem that further optimizes the applications’ latency, by up to an order of magnitude. Finally, a vision for next-generation, edge-enabled, big data analytics solutions is provided, where the remaining open issues as well as the new challenges posed by the deployment of even more data-intensive applications such as deep learning, are highlighted and a road-map for addressing them is presented, capitalizing also on the results and outcome of this thesis.

Καθώς ο όγκος των δεδομένων που αποθηκεύονται σε γεω-κατανεμημένα κέντρα δεδομένων αυξάνεται και η ανάγκη για γρήγορη ανάλυσή τους παραμένει, η επιλογή να συγκεντρωθούν σε μια κεντρική τοποθεσία πριν από την επεξεργασία τους καθίσταται σημαντικά αναποτελεσματική. Ως εκ τούτου, προκύπτει η ανάγκη ανάλυσης των δεδομένων πιο κοντά στις πηγές τους. Έχουν γίνει πολυάριθμες ερευνητικές προσπάθειες για τον προσδιορισμό της βέλτιστης ανάθεσης μιας τέτοιας ανάλυσης, που συνήθως απεικονίζεται ως Κατευθυνόμενο Άκυκλο Γράφημα που αποτελείται από πολλαπλές εργασίες, με σκοπό τη βελτιστοποίηση μετρικών. Επιπρόσθετα, η εμφάνιση του Διαδικτύου των Πραγμάτων και του edge computing όπου πολλαπλοί αισθητήρες παράγουν τεράστιες ποσότητες δεδομένων που πρέπει να αναλυθούν σε πραγματικό χρόνο σε κοντινές συσκευές, αντί για το cloud, επιφέρει πρόσθετες προκλήσεις, όπως ετερογένεια υλικού και δικτύου, και περιορισμούς ασφαλείας. Ακόμη και μετά την εύρεση ενός βελτιστοποιημένου πλάνου ανάθεσης εργασιών, ο χρόνος εκτέλεσης μπορεί να παραμένει υψηλός λόγω του όγκου των δεδομένων που αναλύονται. Επομένως, υπάρχει ανάγκη για ανάπτυξη τεχνικών που μειώνουν αυτό το μέγεθος, ενώ παράλληλα λαμβάνουν υπόψη την ποιότητα του αποτελέσματος, μέσω της μέτρησης των διαφορετικών διαστάσεων της ποιότητας των δεδομένων, όπως η πληρότητα. Η παρούσα διατριβή στοχεύει να αντιμετωπίσει αυτές τις προκλήσεις. Αρχικά, προτείνεται μια δι-κτιρτηριακή λύση ανάθεσης εργασιών σε γεω-κατανεμημένους πόρους. Οι τεχνικές που αναπτύχθηκαν λαμβάνουν υπόψη την ετερογένεια των συνδέσεων δικτύου, επιτυγχάνοντας κατά μέσο όρο 44.31% μείωση στο συνολικό χρόνο εκτέλεσης και ταυτόχρονα 50.12% μείωση της κίνησης δεδομένων σε σύγκριση με μία προηγμένη λύση. Επιπρόσθετα, ένα πρωτότυπο στο Apache Spark αποδεικνύει τις αποτελεσματικότητα σε ένα πραγματικό περιβάλλον. Στην συνέχεια, προτείνονται τεχνικές για ένα edge περιβάλλον που λαμβάνουν υπόψη την ετερογένεια των συσκευών και των συνδέσεων δικτύου και τους περιορισμούς ιδιωτικότητας των δεδομένων ενώ εισάγουν και εργασίες επαλήθευσης ποιότητας των δεδομένων. Η αξιολόγηση των προτεινόμενων τεχνικών μέσω προσομοιώσεων δείχνει βελτιώσεις όσον αφορά μια μετρική που λαμβάνει υπόψη τον χρόνο εκτέλεσης και τον έλεγχο ποιότητας, έως και 2.56 φορές σε σύγκριση με λύσεις τελευταίας τεχνολογίας. Επιπλέον, η προτεινόμενη λύση μειώνει τον χρόνο εκτέλεσης έως και 8 φορές στο 86.9% των περιπτώσεων σε σύγκριση με τον βασικό δρομολογητή του Apache Storm. Επιπλέον, υλοποιήθηκε μια εμπειρική μελέτη σχετικά με τα οφέλη απόδοσης και επεκτασιμότητας που μπορούν να επιφέρουν τα συστήματα ανάλυσης μεγάλων δεδομένων στην αξιολόγηση της ποιότητας. Επιπλέον, το πρόβλημα της ταυτόχρονης βελτιστοποίησης πολλαπλών ροών αντιμετωπίζεται με την υλοποίηση τεχνικών που αποφασίζουν για την ανάθεση εργασιών σε edge συσκευές και αντισταθμίζουν την μείωση ποιότητας με τον χρόνο εκτέλεσης. Τα αποτελέσματα της αξιολόγησης στο Apache Storm δείχνουν μειώσεις του χρόνου εκτέλεσης έως και 6 φορές με μέση επιτάχυνση 2.76 φορές σε σύγκριση με τον προηγμένο δρομολογητή Resource-Aware. Οι τεχνικές μεταφέρονται επίσης σε ένα πρόβλημα μετακίνησης δεδομένων εισόδου που βελτιστοποιεί περαιτέρω τον χρόνο εκτέλεσης των εφαρμογών, έως και μια τάξη μεγέθους. Τέλος, παρουσιάζεται ένα όραμα για το μέλλον των τεχνικών ανάλυσης μεγάλων δεδομένων σε edge συσκευές, όπου επισημαίνονται τα εναπομείναντα άλυτα προβλήματα καθώς και οι νέες προκλήσεις που επιφέρει η ανάπτυξη ακόμη πιο υπολογιστικά απαιτητικών εφαρμογών, όπως η βαθιά μάθηση, και προτείνεται ένας τρόπος για την αντιμετώπισή τους αξιοποιώντας επίσης τα αποτελέσματα της συγκεκριμένης διατριβής.