Deterministic, elastic and real - time processing in the big data era

Abstract

In recent years we observe a large increase in the amount of data thatneeds to be analyzed and processed in real-time in a variety ofapplication domains, ranging from traffic monitoring to healthcareinfrastructures and financial processing. In order to processefficiently such high volume of data, novel distributed big dataframeworks such as Apache Storm and Apache Spark have been proposed.Such systems offer scalable and low latency data processing bydistributing the computation between multiple concurrently runningcomponents. However, there exist several important research challengesthat need to be addressed in order to use them in their fullpotential. These challenges include, but are not limited to, providingdeterminism guarantees for the processed tuples, determining thenumber of processing components that should be utilized, handling thedata skewness and efficiently scheduling multiple concurrently runningapplications with real-time response requirements. The purpose of thisthesis is to propose practical methods to address these issues.The first part of the thesis improves big data frameworks by tacklingthe problem of coping with the demands of determinism and meetinglatency constraints. In order to deterministically process thestreaming data, we need mechanisms that synchronize the order in whichtuples are processed by the operators. On the other hand, achievingreal-time response in such a system requires to efficiently handle thetradeoff between determinism and low latency performance. Consideringthe challenges and trade-offs implied by real-time constraints, in thecontext of this thesis a set of systems and methodologies are proposedthat enable the end-users and the system administrators to dynamicallyrelax the determinism guarantees when needed, in order to satisfy thelatency constraints.The second part of the thesis focuses on the problem of schedulingjobs with real-time response time requirements on big data frameworksthat use the MapReduce programming paradigm and also on buildingaccurate prediction models for estimating the execution time of theapplications. The problems are particularly challenging due to theheterogeneity of the execution environment, the load imbalance causedby skewed data blocks, the real-time response demands imposed by theapplications as well as the limited number of available profilingruns. A set of scheduling algorithms and a novel profiling frameworkthat exploits the similarity of the applications' execution plans areproposed for addressing the aforementioned problems. Finally, in thethird part of the thesis, we contribute to the problem of efficientresource management in distributed stream processing systems. Wepropose and develop a novel elasticity mechanism that enables topro-actively determine the degree of parallelism of the big dataframeworks' components and we also consider the applicability ofwell-known load balancing algorithms to further improve the system'sthroughput.Throughout the thesis, our methodologies have been evaluated onreal-world datasets and scenarios. Our experimental results have shownthat our proposed algorithms systematically outperform the competingapproaches and that they constitute practical approaches which can beemployed in widely utilized distributed stream processing systems,like Apache Storm and Apache Spark.

Τα τελευταία χρόνια παρατηρούμε μία ραγδαία αύξηση του πλήθους τωνδεδομένων τα οποία είναι απαραίτητο να αναλυθούν σε πραγματικό χρόνοαπό διαφορετικού είδους εφαρμογές, οι οποίες περιλαμβάνουν, εφαρμογέςανάλυσης της κυκλοφοριακής συμφόρησης, ιατροφαρμακευτικής περίθαλψηςκαθώς και χρηματοοικονομικές εφαρμογές. Προκείμενου να γίνει μεαποδοτικό τρόπο η επεξεργασία τόσου μεγάλου όγκου δεδομένων, έχουνπροταθεί πρωτότυπα κατανεμημένα συστήματα επεξεργασίας μεγάλου όγκουδεδομένων όπως το Apache Storm και το Apache Spark. Αυτά τα συστήματαείναι κλιμακωτά και παρέχουν χαμηλό χρόνο απόκρισης με το νακατανέμουν την επεξεργασία των δεδομένων σε πολλαπλούς και παράλληλαεκτελέσιμους υπολογιστικούς πόρους. Παρόλα αυτά, υπάρχουν αρκετές καισημαντικές ερευνητικές προκλήσεις που πρέπει να διευθετηθούνπροκειμένου να χρησιμοποιηθούν με τις πλήρεις δυνατότητές τους. Αυτέςοι προκλήσεις περιλαμβάνουν - αλλά δεν περιορίζονται μόνο σε αυτές -την παροχή της ντετερμινιστικής επεξεργασίας των δεδομένων, τονκαθορισμό των υπολογιστικών πόρων που πρέπει να χρησιμοποιηθούν, τηδιαχείριση της ασυμμετρίας που παρουσιάζεται στα δεδομένα που πρέπεινα επεξεργαστούν παράλληλα καθώς και τον αποτελεσματικόχρονοπρογραμματισμό των πολλαπλών εφαρμογών που εκτελούνται πάνω απότο σύστημα όταν οι εφαρμογές έχουν απαιτήσεις απόκρισης πραγματικούχρόνου. Ο σκοπός αυτής της διδακτορικής διατριβής είναι η πρότασηπρακτικών μεθόδων για την αντιμετώπιση αυτών των προβλημάτων.Το πρώτο μέρος της διδακτορικής διατριβής περιλαμβάνει προτάσεις γιατη βελτίωση της απόδοσης των συστημάτων επεξεργασίας μεγάλου όγκουδεδομένων μέσω της αντιμετώπισης του προβλήματος της παροχήςντετερμιστικής επεξεργασίας των δεδομένων και ταυτόχρονα τηνικανοποίηση απαιτήσεων απόκρισης πραγματικού χρόνου. Προκειμένου ταδεδομένα να επεξεργαστούν ντετερμινιστικά, είναι απαραίτητη η χρήσημηχανισμών που καθορίζουν τη σειρά με την οποία τα δεδομέναεπεξεργάζονται από τους υπολογιστικούς πόρους. Αφ'ετέρου, ηικανοποίηση περιορισμών πραγματικού χρόνου σε τέτοια συστήματα απαιτείτην αποτελεσματική διαχείριση του αντισταθμίσματος (trade-off) μεταξύτης ντετερμινιστικής επεξεργασίας και του μικρού χρόνου απόκρισης.Εξετάζοντας αυτές τις προκλήσεις και το αντιστάθμισμα πουδημιουργείται λόγω των περιορισμών πραγματικού χρόνου, ένα σύνολο απόσυστήματα και μεθοδολογίες προτείνονται στα πλαίσια του διδακτορικούπροκειμένου να επιτραπεί στους χρήστες των εφαρμογών και τουςδιαχειριστές των συστημάτων να χαλαρώνουν δυναμικά τους περιορισμούςτου ντετερμινισμού οταν είναι απαραίτητο, ώστε να ικανοποιηθούν οιπεριορισμοί στο χρόνο απόκρισης των εφαρμογών.Το δεύτερο μέρος της διατριβής επικεντρώνεται στο πρόβλημα τουχρονοπρογραμματισμού εφαρμογών με απαιτήσεις πραγματικού χρόνου σεσυστήματα επεξεργασίας δεδομένων μεγάλης κλίμακας δεδομένων πουχρησιμοποιούν το MapReduce προγραμματιστικό μοντέλο, και επιπροσθέτωςστο πρόβλημα της δημιουργίας υψηλής ακρίβειας μοντέλων πρόβλεψης τουχρόνου εκτέλεσης των εφαρμογών. Η δυσκολία των προβλημάτων έγκειταιστο ότι οι εφαρμογές πολλές φορές εκτελούνται σε ετερογενήπεριβάλλοντα, στην ανομοιομορφία των δεδομένων που επεξεργάζονται οιυπολογιστικοί πόροι λόγου της ασυμμετρίας (skewness) των δεδομένων,στις απαιτήσεις πραγματικού χρόνου που έχουν οι εφαρμογές καθώς και τοπεριορισμένο πλήθος διαθέσιμων εκτελέσεων για τη δημιουργία μοντέλωνπρόβλεψης υψηλής ακρίβειας. Προκειμένου να αντιμετωπιστούν ταπροαναφερθέντα προβλήματα προτείνονται ένα σύνολο από αλγορίθμουςχρονοπρογραμματισμού καθώς και ένα πρωτότυπο σύστημα δημιουργίαςπροφιλ εφαρμογών . Τέλος, το τρίτο μέρος της διδακτορικής διατριβήςσυνεισφέρει στο πρόβλημα της αποτελεσματικής διαχείρισης των πόρων σεκατανεμημένα συστήματα ροών δεδομένων. Προτείνεται ένας πρωτότυποςμηχανισμός ελαστικότητας (elasticity) ο οποίος επιτρέπει των καθορισμόεκ των προτέρων του βαθμού του παραλληλισμού των επεξεργαστικών πόρωντου συστήματος, καθώς επίσης εξετάζεται και η χρήση γνωστών αλγορίθμωνδιαμοιρασμού του φόρτου εργασίας μεταξύ των υπολογιστικών πόρωνπροκειμένου να βελτιώσουμε περαιτέρω το διαμετακομιστικό ρυθμό(throughput) του συστήματος.Καθ' όλη την διατριβή, οι μεθοδολογίες που αναπτύχθηκαν έχουναξιολογηθεί σε πραγματικά δεδομένα και σενάρια. Τα πειραματικάαποτελέσματα έδειξαν ότι οι προτεινόμενοι αλγόριθμοι ξεπερνούνσυστηματικά τις υπάρχουσες προσεγγίσεις και ότι αποτελούν πρακτικέςτεχνικές που μπορούν να χρησιμοποιηθούν σε δημοφιλή κατανεμημένασυστήματα επεξεργασίας ροών δεδομένων, όπως το Apache Storm και τοApache Spark.