Βελτιστοποίηση ερωτημάτων σε κατανεμημένα και δυναμικά περιβάλλοντα

Abstract

According to a 2012 IBM annual report, the volume of the data that is produced every day exceeds the 2.5 quintillion bytes. The sources of this data vary from social networks and data sharing sites to sensor networks and mobile phones. The latter phenomenon has given rise to the development of novel infrastructure for storing and processing data, such as clusters, grids and clouds. The development of novel query/worfklow optimization and processing techniques is more than necessary in order to take advantage of the maximum of the potentials of this infrastructure as state-of-the-art algorithms tend to overlook many of the peculiarities of modern infrastructure. Thus, the produced plans are less efficient or even inconsistent with the user requirements. This thesis aims to develop algorithms and techniques for overcoming the limitations of state-of-the-art work. Its main contributions are summarized to the following: (i) A novel provably optimal algorithm has been developed for building query/workflow plans when the SQL operators/user tasks are executed through remote service calls. The goal is to minimize the response time of a query/workflow. The assumptions that were considered and differentiate the proposed algorithm from the state-of-the-art ones are, first, the adoption of pipelined parallelism and, second, the possibility of direct communication between remote services through heterogeneous network links. The motivation for studying this problem was the increasing adoption of services by modern infrastructure. (ii) Two generalizations of the previous algorithm have been also developed that account for multi-way join services. The cases where the proposed algorithms build the minimum response time plans have been also studied. (iii) A new adaptive technique has been introduced for query processing in dynamic environments. Experiments performed both with synthetic and real-world data show that the proposed technique builds more efficient plans incurring less runtime overhead. This work has been motiv! ated by the highly dynamic and unpredictable nature of modern infrastructure and data. (iv) Finally, motivated by the fact that the resources of modern infrastructure are leased, several algorithms have been proposed for query/workflow scheduling over multiple clouds. The latter algorithms aim to schedule queries/workflows considering both an SQL operator's/task's response time and the resource leasing cost. The difference between the proposed algorithms and the state-of-the-art ones is the assumption that clouds express their response time-resource monetary cost characteristics through continuous functions.

Σύμφωνα με την επίσημη έκθεση της IBM για το έτος 2012, ο όγκος των δεδομένων που παράγονται επί καθημερινής βάσης ξεπερνά τα 2.5 πεντάκις εκατομμύρια bytes δεδομένων. Οι πηγές αυτών των δεδομένων ποικίλουν από κοινωνικά δίκτυα και δικτυακούς τόπους διαμοιρασμού ψηφιακών αρχείων μέχρι δίκτυα αισθητήρων για τη συλλογή κλιματολογικών δεδομένων και κινητά τηλέφωνα. Τα ανωτέρω κατέστησαν επιτακτική την ανάπτυξη καινοτόμων υποδομών αποθήκευσης και επεξεργασίας δεδομένων, όπως αυτές της συστάδας, του πλέγματος και του νέφους. Προκειμένου να εκμεταλλευτούμε στο μέγιστο τις δυνατότητες π! ου προσφέρουν οι σύγχρονες υποδομές είναι αναγκαία η ανάπτυξη νέων τεχνικών βελτιστοποίησης και επεξεργασίας ερωτημάτων/εργασιών. Ο λόγος είναι ο εξής: οι αλγόριθμοι της βιβλιογραφίας δεν ελάμβαναν μέχρι στιγμής υπόψη πολλές από τις ιδιαιτερότητες αυτών των υποδομών με αποτέλεσμα τα πλάνα που παραγόταν να είναι λιγότερο αποδοτικά ή να μη συνάδουν με τις απαιτήσεις του εκάστοτε χρήστη. Στόχος της παρούσας διατριβής είναι η ανάπτυξη αλγορίθμων και τεχνικών για την αποδοτική και εναρμονισμένη με τις απαιτήσεις των χρηστών βελτιστοποίηση και εκτέλεση ερωτημάτων στις σύγχρονες υποδομές. Οι σημαντικότερες συνεισφορές της διατριβής συνοψίζονται στα εξής: (i) Αναπτύχθηκε ένας καινοτόμος βέλτιστος αλγόριθμος δημιουργίας πλάνων ερωτημάτων/ροών εργασιών όπου οι τελεστές SQL/εργασίες των χρηστών εκτελούνται μέσω κλήσεων σε απομακρυσμένες υπηρεσίες (services). Στόχος είναι η ελαχιστοποίηση του χρόνου ολοκλήρωσης του ερωτήματος/της ροής εργασίας του χρήστη. Οι παραδοχές που ελήφθησαν υπόψη και διαφοροποιούν τον προταθέντα αλγόριθμο από αυτούς της βιβλιογραφίας είναι, πρώτον, η υιοθέτηση παραλληλισμού σωλήνωσης και, δεύτερον, η απευθείας ανταλλαγή δεδομένων μεταξύ των υπηρεσιών μέσω ετερογενών συνδέσμων δικτύου. Κίνητρο για την ενασχόληση με το συγκεκριμένο πρόβλημα αποτέλεσε ο αυξανόμενος βαθμός χρήσης υπηρεσιών από τις σύγχρονες υποδομές. (ii) Αναπτύχθηκαν γενικεύσεις του ανωτέρω αλγορίθμου για τη δημιουργία πλάνων υπηρεσιών που περιλαμβάνουν υπηρεσίες σύνδεσης πολλαπλών εισόδων (multi-way join) και μελετήθηκαν θεωρητικά οι περιπτώσεις που οι προταθέντες αλγόριθμοι παράγουν πλάνα με τον ελάχιστο χρόνο ολοκλήρωσης. (iii) Εισήχθη μία νέα τεχνική για την προσαρμόσιμη εκτέλεση ερωτημάτων σε δυναμικά περιβάλλοντα. Όπως αποδεικνύεται και πειραματικά, η νέα τεχνική επιτυγχάνει να παράξει αποδοτικότερα πλάνα με μικρότερο φόρτο εκτέλεσης. Κίνητρα για την ανάπτυξη αυτής της τεχνικής υπήρξαν τόσο ο υψηλός βαθμός μεταβλητότητας όσο και η απρόβλεπτη φύση των σύγχρονων υποδομών και δεδομένων. (iv) Τέλος, έχοντας ως κίνητρο το γεγονός ότι οι πόροι των σύγχρονων υποδομών νέφους εκμισθώνονται, προτάθηκαν καινοτόμοι αλγόριθμοι χρονοδρομολόγησης ερωτημάτων/ροών εργασιών σε περιβάλλοντα πολλαπλών νεφών. Οι εν λόγω αλγόριθμοι αναλαμβάνουν να χρονοδρομολογήσουν τα ερωτήματα/ροές εργασιών εισόδου λαμβάνοντας υπόψη τόσο το χρόνο ολοκλήρωσης ενός τελεστή SQL/μίας υποεργασίας χρήστη όσο και το χρηματικό κόστος εκμίσθωσης των πόρων. Η ειδοποιός διαφορά των αλγορίθμων που προτάθηκαν από αυτούς της βιβλιογραφίας είναι η υπόθεση πως τα νέφη εκφράζουν τα χαρακτηριστικά χρόνου ολοκλήρωσης-χρηματικού κόστους εκμίσθωσης πόρων μέσω συνεχών συναρτήσεων.