Προσαρμοστικοί Αλγόριθμοι Εξισορρόπησης Φόρτου Σε Κατανεμημένα Περιβάλλοντα (δίκτυα Ομοτίμων Και Υπολογιστικά Νέφη)

Abstract

Το αντικείμενο της παρούσας διδακτορικής διατριβής είναι η μελέτη τεχνικών εξισορρόπησης φόρτου σε κατανεμημένα συστήματα διαχείρισης δεδομένων. Στο πρώτο μέρος της εργασίας παρουσιάζεται ένας προσαρμοστικός επιγραμμικός (online) αλγόριθμος με σκοπό την εξισορρόπηση φόρτου εργασίας σε κατανεμημένες δομές δεδομένων που υποστηρίζουν την δρομολόγηση ερωτημάτων εύρους τιμών. Ο προτεινόμενος αλγόριθμος αντιμετωπίζει προβλήματα άνισων κατανομών φόρτου εργασίας που προκύπτουν όταν οι εξυπηρετητές διαμοιράζουν αντικείμενα διαφορετικής δημοτικότητας. Ο αλγόριθμος υλοποιήθηκε και εφαρμόστηκε σε έναν skip-γράφο, ένα δομημένο δίκτυο ομότιμων κόμβων ικανό να δρομολογεί ερωτήματα εύρους τιμών. Ο αλγόριθμος συγκρίθηκε πειραματικά και θεωρητικά κάτω από διαφορετικές και ρεαλιστικές συνθήκες κίνησης με άλλους παρόμοιους αλγόριθμους. Η πειραματική και θεωρητική ανάλυση αποδεικνύει ότι ο προτεινόμενος αλγόριθμος είναι πιο γρήγορος και καταναλώνει λιγότερους δικτυακούς πόρους κατά την διαδικασία της εξισορρόπησης. Στο δεύτερο μέρος της εργασίας παρουσιάζεται μια κατανεμημένη αρχιτεκτονική δεικτοδότησης, αποθήκευσης και επερώτησης διαφορετικού τύπου δεδομένων μεγάλου όγκου. Σχεδιάζουμε και υλοποιούμε ένα κλιμακώσιμο σύστημα στο οποίο τόσο τα περιεχόμενα όσο και τα ευρετήρια αυτών δημιουργούνται και διαμοιράζονται πλήρως παράλληλα. Ο φόρτος εργασίας κατά την δημιουργία και εξυπηρέτηση τόσο των περιεχομένων όσο και του ευρετηρίου εξισορροπείται μεταξύ των κόμβων του συστήματος συνδυάζοντας καινοτόμες τεχνικές παράλληλης ανάλυσης δεδομένων με κατανεμημένες, αραιές NoSQL βάσεις δεδομένων. Το πρωτότυπό μας σύστημα δοκιμάστηκε κάτω από μεγάλο φόρτο ερωτημάτων και η μέση απόκρισή του κρατήθηκε σε τάξη millisecond.