Parallel and distributed processing of big data streams and scheduling algorithms

Abstract

Worldwide streams of data are expanding continuously, resulting in an accelerating need to efficiently and timely handle these large amounts of data that arrive continuously. In-memory computing is used to meet performance related requirements like latency and throughput that are extremely important in Data Stream Processing (DSP) applications. Several different technologies have emerged specifically to address the challenges of processing high-volume, real-time data, exploiting on-the-fly computations. Distributed Stream Processing Systems (DSPSs) assign applications' processing tasks to the available resources and route streaming data between them. Efficient scheduling of processing tasks can reduce application latencies and eliminate network congestions. However, the available in-built scheduling techniques of DSPSs are far from optimal. In this thesis, we need to solve the task scheduling problem which focuses on which tasks to be allocated on which resources, and controls the order of job execution. An overview of the available DSPSs is presented and a classification of the existing scheduling policies is provided. In this way, useful information about the matters to consider when designing an effective scheduling policy is revealed. Then, a general formulation of the task scheduling problem is presented and a matrix-based, linear scheme is provided. Differently from existing research efforts, that rarely consider memory utilization in their analysis, the derived scheme is performed in a memory-efficient and well-balanced manner. It takes advantage of pipelines to efficiently handle applications, where there is need for heavy communication (all-to-all) between tasks, assigned to pairs of components. The scheme proposed in this thesis is static. However, when it comes to streams of data, the input load usually fluctuates drastically over time. Dynamic schemes use run-time adaptations and task re-scheduling to handle possible changes in the cluster but this usually results in significant downtime and performance degradation. Rather than re-configuring online the tasks' allocation, the proposed scheme handles queue waiting times efficiently and tries to maintain a stable and robust configuration by balancing load between the cluster's nodes. Of course, an adaptive version this approach would increase its performance, so this extension is left for future work. For concreteness, this approach is illustrated based on Apache Storm semantics. The performance evaluation depicts the importance of constraining the required buffer space and achieving load balance to improve the system's performance and overcome the challenges of running DSP applications. The proposed scheme was compared to two state-of-the-art strategies; the default Storm scheduler and R-Storm. It was found to outperform both the other strategies in terms of throughput, achieving an average of 25%-45% improvement under various scenarios, mainly as a result of reduced buffering (≈45% less memory). At the end of this work, the contribution of real-time data processing in an application field is presented. The field of agriculture has to face difficult challenges due to numerous technological transformations used for increasing productivity and products quality. In precision agriculture, a key component is the use of IoT and various items like sensors, control systems, robotics and autonomous vehicles that produce high velocity data streams. Current advances in IoT and cloud computing have led to the development of new applications that have great potential in precision agriculture. However, several challenges arise as open research fields and future directions are revealed.

Συνεχόμενες ροές δεδομένων σε όλο τον κόσμο αναπτύσσονται διαρκώς, δημιουργώντας επιτακτική ανάγκη να διαχειριστούμε αυτόν τον μεγάλο όγκο δεδομένων που καταφθάνει συνεχώς, έγκαιρα και αποτελεσματικά. Μοντέλα υπολογιστικής μνήμης χρησιμοποιούνται, προκειμένου να επιτευχθούν απαιτήσεις απόδοσης όπως η χρονοκαθυστέρηση και η ρυθμαπόδοση, που είναι εξαιρετικά σημαντικές για κάθε εφαρμογή επεξεργασίας ροών δεδομένων. Πληθώρα διαφορετικών τεχνολογιών έχει προκύψει, ειδικά για να αντιμετωπίσει τις προκλήσεις της επεξεργασίας υψηλού όγκου δεδομένων σε πραγματικό χρόνο, εκμεταλλευόμενη υπολογισμούς on-the-fly. Κατανεμημένα συστήματα επεξεργασίας ροών δεδομένων αναθέτουν τις επιμέρους εργασίες μιας εφαρμογής στους διαθέσιμους πόρους και δρομολογούν ροές δεδομένων μέσα από αυτές. Η αποτελεσματική δρομολόγηση των εργασιών μπορεί να μειώσει τις χρονοκαθυστερήσεις μιας εφαρμογής και να περιορίσει τη συμφόρηση στο δίκτυο. Ωστόσο, οι τεχνικές δρομολόγησης που είναι ενσωματωμένες στα διαθέσιμα επεξεργασίας ροών δεν είναι οι βέλτιστες δυνατές. Στην παρούσα διατριβή, γίνεται προσπάθεια επίλυσης του προβλήματος της χρονοδρομολόγησης των εργασιών σε συστήματα επεξεργασίας ροών δεδομένων. Το πρόβλημα αυτό εστιάζει στο ποιες εργασίες πρέπει να τοποθετηθούν, σε ποιους διαθέσιμους πόρους και ελέγχει τη σειρά της εκτέλεσής τους. Αρχικά, γίνεται μια επισκόπηση των διαθέσιμων συστημάτων επεξεργασίας ροών δεδομένων και μια κατηγοριοποίηση των διαθέσιμων τεχνικών δρομολόγησης από μελέτη σχετικής βιβλιογραφίας. Με αυτόν τον τρόπο, προέκυψαν οι παράγοντες που πρέπει να λαμβάνονται υπόψη, όταν σχεδιάζεται μια αποτελεσματική τεχνική δρομολόγησης. Έπειτα, γίνεται μοντελοποίηση του προβλήματος και παρουσιάζεται ένα γραμμικό σχήμα βασισμένο σε μετασχηματισμούς πινάκων. Σε αντίθεση με τις υπάρχουσες προτάσεις της βιβλιογραφίας που σπάνια λαμβάνουν υπόψη την κατανάλωση μνήμης στην ανάλυσή τους, το σχήμα που προτείνεται εδώ εκτελείται με έναν τρόπο που διαχειρίζεται αποτελεσματικά τη μνήμη και είναι ισορροπημένο ως προς τον φόρτο. Το σχήμα αυτό, εκμεταλλεύεται την τεχνική της διασωλήνωσης, προκειμένου να διαχειριστεί αποτελεσματικά εφαρμογές, όπου υπάρχει ανάγκη για πλήρη επικοινωνία μεταξύ των εργασιών διαφορετικών τελεστών της εφαρμογής. Το σχήμα της παρούσας μελέτη είναι στατικό. Ωστόσο, στην περίπτωση των ροών δεδομένων, ο φόρτος εισόδου μεταβάλλεται δραστικά με την πάροδο του χρόνου. Τα δυναμικά σχήματα προσαρμόζονται και πραγματοποιούν κατάλληλες μεταβολές στη δρομολόγηση των εργασιών κατά τη διάρκεια εκτέλεσης μιας εφαρμογής, προκειμένου να διαχειριστούν αποτελεσματικά τις αλλαγές στο cluster. Κάτι τέτοιο, όμως, οδηγεί σε σημαντικές καθυστερήσεις και μείωση της απόδοσης του συστήματος. Το προτεινόμενο σχήμα αντί να προσαρμόζει εκ νέου κατά τη διάρκεια της εκτέλεσης, την ανάθεση των επιμέρους εργασιών μιας εφαρμογής, χειρίζεται με έναν αποτελεσματικό τρόπο τις ουρές αναμονής και προσπαθεί να διατηρήσει μια σταθερή και ισχυρή ρύθμιση, ισορροπώντας τον φόρτο μεταξύ των κόμβων του cluster. Σαφώς, μια δυναμική έκδοση της παρούσας προσέγγισης θα βελτίωνε την απόδοσή της, γι’ αυτό και η επέκταση αυτή, είναι μία από τις προτάσεις για μελλοντική έρευνα. Για λόγους ευκρίνειας, η παρούσα προσέγγιση γίνεται με βάση τη σημασιολογία του συστήματος Apache Storm. Η αποτίμηση της αποδοτικότητας του σχήματος υποδεικνύει την σημασία του περιορισμού της απαιτούμενης ενδιάμεσης μνήμης και της εξισορρόπησης φόρτου στη βελτίωση της απόδοσης του συστήματος και στην αντιμετώπιση των προκλήσεων της εκτέλεσης εφαρμογών που επεξεργάζονται ροές δεδομένων. Κατά την εκτέλεση των πειραμάτων, πραγματοποιήθηκε σύγκριση του προτεινόμενου σχήματος με τον προκαθορισμένο δρομολογητή του Apache Storm, καθώς και με τον δρομολογητή R-Storm που προέκυψε από τη βιβλιογραφική ανασκόπηση. Το παρόν σχήμα ξεπέρασε σε επίπεδο ρυθμαπόδοσης και τα δύο σχήματα, παρέχοντας βελτίωση της τάξης του 25%-45% υπό διαφορετικά σενάρια, κυρίως χάρη στη μείωση χρήσης της ενδιάμεσης μνήμης (≈45% λιγότερη μνήμη). Στο τέλος της παρούσας διατριβής, παρουσιάζεται η συνεισφορά της επεξεργασίας δεδομένων σε πραγματικό χρόνο σε ένα πεδίο εφαρμογής. Η χρήση συσκευών ΙοΤ και εργαλείων όπως τα αυτόνομα οχήματα, οι ασύρματοι αισθητήρες και οι ρομποτικές κατασκευές, που παράγουν συνεχώς ροές δεδομένων υψηλής ταχύτητας, αποτελούν κλειδί στην εφαρμογή πρακτικών γεωργίας ακριβείας. Ο πρωτογενής τομέας καλείται σήμερα να αντιμετωπίσει ιδιαίτερες προκλήσεις χάρη στην πληθώρα των τεχνολογικών μετασχηματισμών που πραγματοποιούνται, ώστε να αυξηθεί η παραγωγικότητα και η ποιότητα των παραγόμενων προϊόντων με σεβασμό στο περιβάλλον. Νέες εφαρμογές με μεγάλες δυνατότητες έχουν αρχίσει να αναπτύσσονται, προσπαθώντας να εκμεταλλευτούν την πρόοδο του Διαδικτύου των Πραγμάτων και της υπολογιστικής νέφους. Ωστόσο, οι προκλήσεις είναι πολλές και φανερώνουν νέα ανοιχτά πεδία έρευνας και μελλοντικές τάσεις.