Κατανεμημένοι Αλγόριθμοι Ερωτημάτων Ένωσης με Εφαρμογές στην Ανάλυση Δεδομένων Δικτυακής Κίνησης - Σαρλής, Δημήτριος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Υπολογιστικών Συστημάτων., 2014)
Τα τελευταία χρόνια έχει παρατηρηθεί ραγδαία αύξηση της κίνησης στο Internet, γεγονός που είναι περισσότερο εμφανές σε κόμβους ουδέτερης διασύνδεσης (IXPs) από τους οποίους διέρχονται πλέον έως και petabytes δεδομένων καθημερινά. Υπάρχει ανάγκη, λοιπόν, για επεξεργασία αυτού του τεράστιου όγκου δεδομένων με αποδοτικές τεχνικές, για να εξαχθούν στατιστικά για την κίνηση που διέρχεται από αυτούς τους κόμβους. Στην παρούσα διπλωματική ασχολούμαστε με τη σχεδίαση και υλοποίηση ενός συστήματος ανάλυσης δεδομένων δικτυακής κίνησης τύπου sFlow που θα χρησιμοποιεί τεχνικές κατανεμημένης επεξεργασίας, όπως το MapReduce σε αντίθεση με τις παραδοσιακές τεχνικές που χρησιμοποιούνται μέχρι τώρα. Το σύστημα αυτό θα είναι σε θέση να αντιμετωπίσει τη γενικότερη περίπτωση log processing όπου έχουμε ένα βασικό σύνολο δεδομένων και θέλουμε να εξάγουμε πληροφορία από αυτό σε συνδυασμό με εξωτερικές πηγές επιπλέον πληροφορίας. Για το σκοπό αυτό εξετάζουμε αποδοτικές τεχνικές με τις οποίες μπορεί να γίνει η συνένωση των πληροφοριών, όπως είναι η τεχνική του map join. Συνδυάζουμε αυτή τη μέθοδο με εξειδικευμένες συναρτήσεις στο Hive για να πετύχουμε καλύτερη απόδοση. Ακόμη, προτείνουμε έναν έξυπνο τρόπο για pre-partitioning των δεδομένων με τη χρήση ενός K-d tree, ώστε να μπορεί να γίνει γρήγορα η εκτέλεση ερωτημάτων που αφορούν περιορισμένο τμήμα των δεδομένων (με χρήση διάφορων φίλτρων). Στη συνέχεια εξετάζουμε την επίδραση διαφορετικών συστημάτων εκτέλεσης MapReduce στα ίδια ερωτήματα και συγκρίνουμε τα χαρακτηριστικά τους. Τέλος, παρουσιάζουμε τη δυνατότητα κλιμάκωσης του συστήματος που υλοποιήσαμε, καθώς αυξάνει ο αριθμός των διαθέσιμων κόμβων αλλά και το μέγεθος του συνόλου δεδομένων. Σε κάθε περίπτωση η δική μας μέθοδος παρουσιάζει μία βελτίωση έως και 70% στο χρόνο εκτέλεσης σε σύγκριση με μία απλή βασική υλοποίηση.