Δομές ευρετηρίου για cloud computing

Abstract

Η ραγδαία ανάπτυξη της τεχνολογίας των ηλεκτρονικών υπολογιστών τα τελευταία χρόνια έχει οδηγήσει στην αύξηση της ταχύτητας μετάδοσης δεδομένων και των δυνατοτήτων των υπολογιστών. Λόγω των υψηλών ταχυτήτων σύνδεσης έχει ευνοηθεί και αναπτυχθεί η μελέτη και χρήση κατανεμημένων συστημάτων. Παράλληλα η ραγδαία ανάπτυξη του παγκόσμιου ιστού έχει δημιουργήσει την ανάγκη της γρήγορης και αποδοτικής επεξεργασίας πολύ μεγάλου όγκου δεδομένων (το Google επεξεργάζεται καθημερινά περίπου 20 petabytes δεδομένων). Για την απαραίτητη επεξεργασία δεν είναι πλέον δυνατή η χρήση ενός απλού υπολογιστή και πολλές φορές δεν είμαστε σε θέση να αποφασίσουμε εκ των προτέρων την υπολογιστική ισχύ που θα χρειαστούμε. Οι αλλαγές αυτές σε συνδυασμό με τις συνεχώς αυξανόμενες σύγχρονες ανάγκες έχουν οδηγήσει στην ανάπτυξη του cloud computing. To cloud computing μπορεί απλά να περιγράφει ως ένα σύνολο άπειρων δυνατοτήτων (επεξεργαστική ισχύ, χωρητικότητα κλπ) από το οποίο ο κάθε χρήστης χρησιμοποιεί ότι του είναι απαραίτητο για την κάλυψη των αναγκών του. Η ισχύς και η αποδοτικότητα των συστημάτων αυτών σίγουρα είναι ένα θετικό στοιχείο αλλά δεν είναι επαρκής. Καθώς ο όγκος των δεδομένων είναι πολύ μεγάλος είναι επιθυμητή και αναπόφευκτη η δυνατότητα να μπορεί ο χρήστης να θέτει ερωτήματα και να λαμβάνει απάντηση σε σύντομο χρονικό διάστημα. Τέτοια ερωτήματα μπορεί να είναι κατά πόσο κάποιο σημείο υπάρχει στα διαθέσιμα δεδομένα ή ποια είναι τα διαθέσιμα δεδομένα σε κάποιο εύρος τιμών. Σε πολλές εφαρμογές όπως network monitoring και geographical information systems τα δεδομένα έχουν πολλές ιδιότητες (attributes) και ανήκουν σε μεγαλύτερες διαστάσεις. Μια τυπική πλατφόρμα cloud computing αποτελείται από εκατοντάδες ή και χιλιάδες από κόμβους (υπολογιστές χαμηλού κόστους) οι οποίοι είναι ικανοί να αποθηκεύσουν τεράστιο όγκο δεδομένων. Για την διαχείριση τόσο μεγάλου όγκου δεδομένων είμαστε αναγκασμένοι να αναπτύξουμε αποδοτικές δομές ευρετηρίου που θα μας επιτρέπουν την γρήγορη και παράλληλη αναζήτηση και θα απαιτούν όσο το δυνατόν λιγότερο αποθηκευτικό χώρο και υπολογιστική ισχύ. Στα κεφάλαια που ακολουθούν περιγράφεται αναλυτικά το cloud computing καθώς και μια δομή ευρετηρίου που ανταποκρίνεται στις πιο πάνω ανάγκες. Επιπλέον ως αντιμετώπιση του προβλήματος προτείνεται μια αποδοτική δομή ευρετηρίου η οποία κλιμακώνει και μπορεί να χρησιμοποιηθεί σε πραγματικά συστήματα cloud computing. Σύμφωνα με τα πειράματα που έχουν γίνει η δομή αυτή είναι ικανή να ανταποκριθεί σε πολλά point και range queries με ελάχιστη καθυστέρηση. Η προτεινόμενη δομή βασίζεται σε R-Tree και Bloom Filters.