Μοντελοποίηση εφαρμογών και τελεστών μεγάλων δεδομένων σε περιβάλλοντα υπολογιστικών νεφών

Abstract

The Big Data revolution has created new requirements for the design of applications and operators that are able to handle the volume of the data sources. The adoption of distributed architectures and the increasing popularity of the Cloud paradigm has complexed their structure, making the problem of modeling their behavior increasingly difficulty. Moreover, the wide variety of the existing datasets have complicated the problem of selecting the appropriate inputs for a given operator, since the examination of the data utility for a given workflow is a largely manual process that requires exhaustive execution for the entirety of the available datasets. This thesis attempts to model the behavior of an arbitrary Big Data operator from two different viewpoints.First, we wish to model the operator’s performance when deployed under different resource configurations. To this end, we present an adaptive performance modeling methodology that relies on recursively partitioning the configuration space in disjoint regions, distributing a predefined number of samples to each region based on different region characteristics (i.e., size, modeling error) and deploying the given operator for the selected samples. The performance is, then, approximated for the entire space using a combination of linear models for each subregion. Intuitively, this approach attempts to compromise the contradicting aspects of exploring the configuration space and exploiting the obtained knowledge through focusing on areas with higher approximation error.Second and in order to accelerate data analysis, we wish to model the operator’s output when deployed over different datasets. Based on the observation that similar datasets tend to affect the operators that are applied to them similarly, we propose a content-based methodology that models the output of a provided operator for all datasets. Our approach measures the similarity between the different datasets in the light of some fundamental properties commonly used in data analysis tasks, i.e., the statistical distribution, the dataset size and the tuple ordering. These similarities are, next, projected to a low dimensional metric space that is utilized as an input domain by Neural Networks in order to approximate the operator’s output for all datasets, given the actual operator output for a mere subset of them. Our evaluation, conducted using several real-world operators applied for real and synthetic datasets, indicated that the introduced methodologies manage to accurately model the operator’s behavior from both angles. The adoption of a divide-and-conquer approach that equally respects space exploration and knowledge exploitation for the performance modeling part, proved to be the main reason that our scheme outperforms other state-of-the-art methodologies. On the same time, the construction of a low dimensional dataset metric space for the second part, proved to be particularly informative in order to allow Machine Learning models to approximate operator output for a wide variety of operators with diverse characteristics.

Η επανάσταση των Μεγάλων Δεδομένων έχει δημιουργήσει νέες απαιτήσεις για το σχεδιασμό εφαρμογών και τελεστών έτσι ώστε να μπορούν να διαχειρίζονται τον τεράστιο όγκο δεδομένων. Η υιοθέτηση κατανεμημένων τεχνικών και η ολοένα αυξανόμενη δημοτικότητα των Υπολογιστικών Νεφών έχουν συντελέσει στην αύξηση της πολυπλοκότητας της αρχιτεκτονικής των τελεστών Μεγάλων Δεδομένων, κάνοντας το πρόβλημα της μοντελοποίησης της συμπεριφοράς τους ολοένα και πιο δύσκολο. Παράλληλα, η μεγάλη ποικιλομορφία των διαφορετικών πηγών δεδομένων έχει περιπλέξει το πρόβλημα της επιλογής των κατάλληλων εισόδων για έναν τελεστή, καθώς η εξέταση της χρησιμότητας των δεδομένων εισόδου για αυτόν είναι μια μη αυτοματοποιημένη διαδικασία που στηρίζεται στην εξαντλητική εκτέλεση του τελεστή για το σύνολο των διαθέσιμων δεδομένων. Η διατριβή αυτή προσπαθεί να μοντελοποιήσει τη συμπεριφορά ενός δοθέντος τελεστή Μεγάλων Δεδομένων, υπό το πρίσμα δύο διαφορετικών κατευθύνσεων.Πρώτον, η διατριβή αυτή ασχολείται με το πρόβλημα της μοντελοποίησης της απόδοσης ενός τελεστή όταν αυτός εγκαθίσταται με διαφορετικές παραμέτρους. Για το σκοπό αυτό, παρουσιάζεται μια προσαρμοστική μεθοδολογία μοντελοποίησης της απόδοσης μιας εφαρμογής, που στηρίζεται: (α) στην αναδρομική διαμέριση του χώρου παραμέτρων, (β) στην κατανομή ενός προαποφασισμένου αριθμού δειγμάτων σε κάθε υποπεριοχή σύμφωνα με διαφορετικά χαρακτηριστικά της (π.χ., το μέγεθός της, το σφάλμα μοντελοποίησης, κλπ) και (γ) στην φυσική εγκατάσταση της εφαρμογής για τα επιλεχθέντα σύνολα παραμέτρων. Η απόδοση προσεγγίζεται για ολόκληρο το χώρο χρησιμοποιώντας ένα συνδυασμό γραμμικών μοντέλων που εφαρμόζεται σε κάθε υποπεριοχή. Διαισθητικά, η προσέγγιση αυτή προσπαθεί να συμβιβάσει τις αντίρροπες κατευθύνσεις της εξερεύνησης του χώρου παραμέτρων και της εκμετάλλευσης της αποκτηθείσας γνώσης (μέσω των δειγμάτων που έχουν επιλεγεί προηγούμενα) διαμέσου της συγκέντρωσης σε περιοχές με υψηλό σφάλμα προσέγγισης.Δεύτερον και με σκοπό την επιτάχυνση της ανάλυσης των δεδομένων, η διατριβή αυτή προτείνει μια μεθοδολογία για τη μοντελοποίηση της εξόδου ενός τελεστή όταν αυτός εφαρμόζεται σε διαφορετικά σύνολα δεδομένων εισόδου. Με βάση την παρατήρηση ότι όμοια σύνολα δεδομένων τείνουν να επηρεάζουν έναν τελεστή με παρόμοιο τρόπο, προτείνεται μια βασισμένη στο περιεχόμενο μεθοδολογία που μοντελοποιεί την έξοδο ενός τελεστή για όλα τα δεδομένα εισόδου. Η προσέγγιση αυτή ποσοτικοποιεί την ομοιότητα μεταξύ των διαφορετικών συνόλων δεδομένων υπό το πρίσμα τριών θεμελιωδών ιδιοτήτων: (α) τη στατιστική κατανομή τους, (β) το μέγεθος τους και (γ) τη σειρά εμφάνισης των πλειάδων τους. Η ομοιότητα μεταξύ των διαφορετικών συνόλων προβάλλεται, εν συνεχεία, σε ένα μετρικό χώρο χαμηλής διάστασης και χρησιμοποιείται σαν σύνολο ορισμού από ένα Νευρωνικό Δίκτυο που έχει ως σκοπό την προσέγγιση της εξόδου του τελεστή για όλα τα σύνολα, δοθέντων την πραγματικών τιμών εξόδου για ένα μικρό υποσύνολο τους.Η πειραματική αξιολόγηση, που πραγματοποιήθηκε χρησιμοποιώντας μεγάλη πληθώρα πραγματικών τελεστών που εκτελούνται τόσο για πραγματικά όσο και συνθετικά δεδομένα εισόδου, έδειξε ότι οι προτεινόμενες μεθοδολογίες μπορούν μοντελοποιήσουν με υψηλή ακρίβεια τη συμπεριφορά ενός τελεστή Μεγάλων Δεδομένων και από τις δυο εξεταζόμενες σκοπιές. Η υιοθέτηση της τεχνικής “διαίρει και βασίλευε” που σέβεται εξίσου την εξερεύνηση του χώρου παραμέτρων και την εκμετάλλευση της παραγόμενης γνώσης σχετικά με τη μοντελοποίησης της απόδοσης, είναι ο κύριος λόγος που εξηγεί την υψηλότερη ακρίβεια που πετυχαίνει η προταθείσα μεθοδολογία, εν συγκρίσει με άλλες, παρεμφερείς μεθοδολογίες μοντελοποίησης απόδοσης. Παράλληλα, ο μετρικός χώρος χαμηλής διάστασης, που κατασκευάζεται σχετικά με το δεύτερο κομμάτι της διατριβής, περιέχει αρκετή πληροφορία για να επιτρέψει μοντέλα Μηχανικής Μάθησης να προσεγγίσουν την έξοδο ενός μεγάλου αριθμού τελεστών με διαφορετικά χαρακτηριστικά.