Parallel and distributed processing of big data streams and scheduling algorithms
Authors: Τανταλάκη Νικολέτα 
Published: September 2021

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