Βέλτιστη εξισορρόπηση φόρτου σε κατανεμημένες NoSQL βάσεις δεδομένων
| dc.contributor.advisor | Τσακαλίδης, Αθανάσιος | |
| dc.contributor.author | Κενδέα, Μάριος | |
| dc.contributor.committee | Τσακαλίδης, Αθανάσιος | |
| dc.contributor.other | Kendea, Marios | |
| dc.date.accessioned | 2017-02-13T07:37:24Z | |
| dc.date.available | 2017-02-13T07:37:24Z | |
| dc.date.copyright | 2016-09-26 | |
| dc.degree | Μεταπτυχιακή Εργασία | el |
| dc.description.abstract | Οι πάροχοι υπηρεσιών νέφους υπολογιστών αποθηκεύουν για τους χρήστες και τις εφαρμογές τους όλο και αυξανόμενο μέγεθος δεδομένων. Αυτά τα δεδομένα μπορεί να είναι πολυδιάστατα, δεδομένα τοποθεσιών και άλλα που πιθανών να ακολουθούν άγνωστες κατανομές. Οι εφαρμογές που χρησιμοποιούν αυτά τα δεδομένα, και τα αποθηκεύουν σε κατανεμημένες NoSQL βάσεις δεδομένων, πρέπει να έχουν κάποιο τύπο δεικτοδότησης τόσο σε επίπεδο υπολογιστικού κόμβου αλλά και σε επίπεδο αρχιτεκτονικής για την δεικτοδότηση των ίδιων των υπολογιστικών κόμβων. Σε συνδυασμό αυτά πρέπει να επιτυγχάνουν εξισορρόπηση φόρτου (load balancing) ώστε τα ερωτήματα εύρους μεγάλης κλίμακας (Large-Scale Range Queries), τα οποία εκτελούνται να έχουν καλή απόδοση. Στην παρούσα εργασία παρουσιάζονται οι αρχιτεκτονικές των ευρετηρίων ΗΒ+-tree για δεικτοδότηση πολυδιάστατων δεδομένων και NSM-tree για δεικτοδότηση δεδομένων τοποθεσιών και εκτέλεση ερωτημάτων εύρους σε αυτές. Το HB+-tree (HBase B+-tree) είναι ένα βασισμένο στο Hadoop (κατανεμημένο σύστημα) κατανεμημένο Β+-δέντρο το οποίο ορίζει ένα ευρετήριο στους υπολογιστικούς κόμβους της HBase (κατανεμημένη βάση δεδομένων). Στην συνέχεια παρουσιάζεται μια πειραματική αξιολόγηση για την εκτέλεση ερωτημάτων δύο βασικών ειδών κατανεμημένων βάσεων και πως το HB+-δέντρο μπορεί να επηρεάσει θετικά στην απόδοση κατά την εκτέλεση ερωτημάτων στη μια από αυτές. Η μία βάση είναι η στήλο-προσανατολισμένη HBase και η άλλη είναι η βάση δεδομένων για γράφους Neo4j. Επίσης, με τα αποτελέσματα της συγκεκριμένης σύγκρισης προκύπτουν λύσεις σε προβλήματα εξισορρόπησης φόρτου στην εκτέλεση ερωτημάτων όταν μπορεί να εφαρμοστεί ο μηχανισμός προώθησης ερωτημάτων στην ανάλογη βάση δεδομένων. Τέλος, παρουσιάζεται με χρήση της αλγοριθμικής τεχνικής «μπάλες σε κάδους» ένας σχεδιασμός ευρετηρίου για την βέλτιστη εξισορρόπηση φόρτου κλειδιών στους διατεθειμένους υπολογιστικούς πόρους. Η επίτευξη βέλτιστου load balancing στα κλειδιά και κατά συνέπεια και στον όγκο των δεδομένων αποτελεί το «θεμέλιο» δημιουργίας ενός αποδοτικού κατανεμημένου ευρετηρίου (Distributed Overlay or Infrastructure) με τη χρήση του οποίου θα επιτυγχάνεται η βέλτιστη εκτέλεση ερωτημάτων εύρους. Το Overlay αυτό ονομάζεται HB3-tree (HBase Balls in Bins – tree). | el |
| dc.description.translatedabstract | Cloud providers store on databases for their users an increasing large amount of data. These data are most of the time multi-dimensional, location data and other that probably have a non-uniform distribution. Applications that use this data, and store them in distributed NoSQL databases, must have some type of indexing both inside cluster nodes but also at the level of indexing the set of cluster nodes. All these come together and result to have load balancing on data resulting the Large-Scale Range Queries performance to be optimal. The context of this thesis includes the architecture of ΗΒ+-tree overlay and index that index multidimensional data and also includes the NSM-tree indexing of location data. The experimental evaluation is presented. The HB+-tree (HBase B+-tree) is a Hadoop-based (distributed middleware) distributed B+-tree, which index HBase nodes. Next, an experimental evaluation for benchmarking the queries execution times on two distributed NoSql Databases and how the HB+-tree overlay and index can affect the performance of those queries. The first one is the column-oriented HBase and the other is the graph database Neo4j. Τhe results of this comparison can give solutions for load balancing problems in cases of executing queries when the query forwarding mechanism can be applied. At the end, a new novel indexing on both compute nodes and data is presented. The method uses the algorithmic technic «balls in bins» an architecture solution for optimal load balancing the keys inside the resources. Achieving optimal load balancing on keys and thus to the volume of data will be the "foundation" of creating an efficient distributed index (Distributed Overlay or Infrastructure). The Overlay is called HB3-tree (HBase Balls in Bins - tree) that will achieve optimal performance on range queries. | el |
| dc.identifier.uri | http://hdl.handle.net/10889/10105 | |
| dc.language.iso | gr | el |
| dc.rights | 0 | el |
| dc.subject | Εξισορρόπηση φόρτου | el |
| dc.subject | Ευρετήρια | el |
| dc.subject | Κατανεμημένα συστήματα | el |
| dc.subject | Βάσεις δεδομένων NoSql | el |
| dc.subject | Δομές δεδομένων | el |
| dc.subject | Ερωτήματα εύρους | el |
| dc.subject.alternative | Load balancing | el |
| dc.subject.alternative | Indexing methods | el |
| dc.subject.alternative | Distributed systems | el |
| dc.subject.alternative | NoSql databases | el |
| dc.subject.alternative | Hadoop | el |
| dc.subject.alternative | HBase | el |
| dc.subject.alternative | MapReduce | el |
| dc.subject.alternative | HB+-tree | el |
| dc.subject.alternative | NSM-Tree | el |
| dc.subject.alternative | HB3+-tree | el |
| dc.subject.alternative | Data structures | el |
| dc.subject.alternative | Range queries | el |
| dc.subject.ddc | 005.75 | el |
| dc.title | Βέλτιστη εξισορρόπηση φόρτου σε κατανεμημένες NoSQL βάσεις δεδομένων | el |
| dc.title.alternative | Optimal load balancing in distributed NoSQL databases | el |
| dc.type | Thesis | el |