Αποδοτική επεξεργασία ερωτημάτων κατάταξης στο map / reduce

Abstract

Η παρούσα Διπλωματική εργασία έχει ως στόχο την αποδοτική επεξεργασία ερωτημάτων με κατάταξη (γνωστά και ως Top-K) με τη μέθοδο Map/Reduce. Στις εφαρμογές που διαχειρίζονται τεράστιο όγκο δεδομένων, η εκτέλεση υπολογισμών ή Top-K ερωτημάτων πρέπει να πραγματοποιηθεί με έναν κατανεμημένο τρόπο καθώς και με παράλληλη επεξεργασία ώστε να είναι γρήγορη και αποδοτική. Για να επιτευχθεί αυτό, χρησιμοποιήθηκε το σύστημα Hadoop και το προγραμματιστικό μοντέλο του Map/Reduce σε κατανεμημένα περιβάλλοντα. Τα μεγαλύτερα πλεονεκτήματα του Hadoop για την ανάπτυξη κατανεμημένων εφαρμογών είναι η παράλληλη επεξεργασία των δεδομένων σε ένα σύνολο κόμβων ενός συμπλέγματος καθώς και η δυνατότητα να διαχειρίζεται αστοχίες υλικού, καθώς το σύστημα ανιχνεύει τις διεργασίες που έχουν αποτύχει και τις επαναδρομολογεί σε άλλους κόμβους του συμπλέγματος. Έτσι η αξιοπιστία διασφαλίζεται σε επίπεδο λογισμικού και δεν εξαρτάται από την ποιότητα του υλικού. Η σημαντικότερη αδυναμία όμως του Map/Reduce σε περιπτώσεις ερωτημάτων κατάταξης (Top-K) είναι ότι για να εξάγει το τελικό αποτέλεσμα, είναι αναγκασμένο να διαβάσει όλα τα δεδομένα, κάτι το οποίο όμως δεν είναι καθόλου αποδοτικό. Στην εργασία, μέσα από το πειραματικό μέρος και την εκτέλεση τριών διαφορετικών αλγορίθμων θα αναδειχθούν οι αδυναμίες της προκαθορισμένης λειτουργίας του προγραμματιστικού μοντέλου Map/Reduce σε Top-K ερωτήματα καθώς και η προτεινόμενη λύση και η αποδοτική επεξεργασία τέτοιου τύπου ερωτημάτων. Θα αντιμετωπιστούν δύο από τις κυριότερες αδυναμίες που εμφανίζονται, τόσο αυτή του πρόωρου τερματισμού (EarlyTermination), όσο και η δίκαιη και ισομερής κατανομή του φορτίου των δεδομένων (Load Balancing).