A study on the query response time minimization in distributed (spatiotemporal) data stores

Abstract

Data centers have become a critical component in enterprise systems as web services and cloud computing continue their massive growth. Meeting hard application constraints (e.g., temporal) under these circumstances puts an enormous strain on the capabilities and limits of enterprise systems, especially in coping with the immense rate of queries in the persistence layer. To cope with these ever-growing application requirements, the data management layer must decouple itself from the many, heavy disk IOs and add a faster persistence layer in between. This approach is implemented with in-memory storage mechanisms which maintain data views in the form of key-value pairs and respond to queries in near-real time even under heavy loads.However, IMKVS suffer inherently (as any distributed system) from the problem of the uneven load distribution among the underlying nodes. The high heterogeneity combining with the distribution of objects through random identifiers, and the fact that these systems do not take into consideration uneven request workloads (e.g., existence of nodes that hold popular objects), can lead to imbalances. As a consequence, overloaded nodes become hotspots in the system and this has a detrimental effect in the systems’ performance in terms of response time.During my Ph.D., the overarching objective of this thesis was to improve the performance of distributed data stores in terms of queries' execution response times by investigating three different perspectives: performance evaluation of spatiotemporal datastores, effective dynamic load balancing and data compression. Initially, we set to investigate the performance of distributed storage systems. Thus, we investigated the field of spatiotemporal data management and analysis, which is a growing area of research supporting multiple application domains. Part of this thesis was set to identify the most efficient data store system in terms of response times, comparing two of the most representative of the two categories (NoSQL and relational), MongoDB and PostgreSQL for a particular class of requirements, i.e., those that the response time in complex spatiotemporal queries is of high importance. The evaluation is based upon real business scenarios.The performance of distributed data stores can greatly be improved by a more effective object placement. Thus, regarding dynamic load balancing, our proposal is to define the actual contributing factors to the load balancing problem and to provide a novel object placement protocol for distributed storage systems that migrates objects between nodes in run time with the goal to minimize very high (based on a threshold identified empirically) response times. The proposed placement protocol constitutes a hybrid solution which combines consistent hashing and directory services. In addition, we approached the problem of data placement, in terms of data compression. Data compression involves the development of a compact representation of information. Therefore, as part of this Ph.D. dissertation, a number of compression algorithms are proposed which are able to reduce the size of the data, while minimizing the loss and at the same time preserving the quality of the information. In other words, compression is investigated as a means to improve performance.The results showed that the proposed object placement protocol achieves to balance the load on a Redis Cluster and the average response time is also becomes uniform across the nodes, leading to an improved performance. In addition, data compression was presented as an alternative to the load balancing problem. A number of compression algorithms are proposed which are able to reduce the size of the data, while minimizing the loss and at the same time preserving the quality of the information. The relationship and the impact of trajectory compression were investigated experimentally by employing trajectory classification and similarity measure techniques. Finally, regarding the most efficient spatiotemporal distributed storage system, the results demonstrated the he superiority of PostgreSQL in almost all cases with the exception of the polygon intersection queries.

Τα κέντρα δεδομένων, αποτελούν ένα κύριο συστατικό στα επιχειρησιακά συστήματα, καθώς οι διαδικτυακές υπηρεσίες και το υπολογιστικό νέφος συνεχίζουν να αναπτύσσονται ραγδαία. Ως εκ τούτου, οι αυξανόμενες απαιτήσεις των χρηστών οδηγούν στα όρια τις δυνατότητες των επιχειρησιακών συστημάτων, που καλούνται να αντιμετωπίσουν ένα τεράστιο αριθμό ερωτημάτων αλλά και σκληρούς χρονικούς περιορισμούς, όσον αφορά την απόκριση του συστήματος. Για να αντιμετωπιστούν αυτές οι ολοένα αυξανόμενες απαιτήσεις των εφαρμογών, το data management layer πρέπει να αποσυνδεθεί από τις πολλές και βαριές εντολές εισόδου-εξόδου από τον δίσκο και να εισάγει ένα γρηγορότερο στρώμα ενδιάμεσα. Η προσέγγιση αυτή μπορεί να υλοποιηθεί με μηχανισμούς αποθήκευσης στη μνήμη (in-memory storage mechanisms), που διατηρούν τα δεδομένα στη μνήμη με τη μορφή ζευγών κλειδιού-τιμής και έχουν τη δυνατότητα να αποκρίνονται στα ερωτήματα των πελατών σε πραγματικό χρόνο ακόμη και κάτω από τεράστια υπολογιστικά φορτία. Ωστόσο τα in-memory KVS (IMKVS), όπως και κάθε κατανεμημένο σύστημα πάσχουν από το πρόβλημα της άνισης κατανομής του φόρτου μεταξύ των κόμβων του συστήματος. Η υψηλή ετερογένεια σε συνδυασμό με την κατανομή των αντικειμένων μέσω τυχαίων αναγνωριστικών, και το γεγονός ότι αυτά τα συστήματα δεν λαμβάνουν υπόψη τους άνισους φόρτους ερωτημάτων αλλά δίνουν περισσότερη βάση στον αριθμό των αντικειμένων που βρίσκονται σε κάθε κόμβο του συστήματος, οδηγεί σε ανισορροπίες (άνιση κατανομή του φόρτου). Ως εκ τούτου, οι υπερφορτωμένοι κόμβοι γίνονται hotspots και αυτό έχει επιζήμια αποτελέσματα όσον αφορά τις επιδόσεις του συστήματος από την άποψη του χρόνου απόκρισης.Στα πλαίσια του διδακτορικού μου έργου, ο βασικός στόχος ήταν η βελτίωση της απόδοσης των κατανεμημένων συστημάτων αποθήκευσης όσον αφορά τους χρόνους απόκρισης εκτέλεσης ερωτημάτων, διερευνώντας το πρόβλημα από τρείς διαφορετικές οπτικές: αξιολόγηση απόδοσης χωροχρονικών συστημάτων αποθήκευσης δεδομένων, αποτελεσματική εξισορρόπηση φορτίου σε πραγματικό χρόνο και συμπίεση δεδομένων.Αρχικά, ξεκινήσαμε να διερευνούμε την απόδοση των κατανεμημένων συστημάτων αποθήκευσης. Έτσι, διερευνήσαμε τον τομέα που αφορά τη διαχείριση και ανάλυση χωροχρονικών δεδομένων, ο οποίος αποτελεί μια αναπτυσσόμενη περιοχή έρευνας που υποστηρίζει πολλαπλούς τομείς εφαρμογών. Μέρος της διδακτορικής μου διατριβής αποτέλεσε ο προσδιορισμός του πιο αποτελεσματικού συστήματος αποθήκευσης δεδομένων υπό την έννοια του χρόνου απόκρισης, συγκρίνοντας δυο συστήματα που ανήκουν στις δυο πιο αντιπροσωπευτικές κατηγορίες (NoSQL και σχεσιακές βάσεις δεδομένων). Συγκεκριμένα, τα συστήματα MongoDB και PostgreSQL εξετάστηκαν σε μια συγκεκριμένη κατηγορία απαιτήσεων, αυτές δηλαδή για τις οποίες ο χρόνος απόκρισης που αφορά σύνθετα χωροχρονικά ερωτήματα είναι υψηλής σημασίας. Η αξιολόγηση των συστημάτων βασίστηκε σε πραγματικά επιχειρηματικά σενάρια.Η απόδοση των κατανεμημένων συτημάτων αποθήκευσης μπορεί να βελτιωθεί σημαντικά με μια πιο αποτελεσματική τοποθέτηση των αντικειμένων στους κομβους του συστήματος. Έτσι, όσον αφορά τη δυναμική εξισορρόπηση φόρτου,στοχεύσαμε στην αναγνώριση και πιστοποίηση των παραγόντων που συμβάλλουν στο πρόβλημα της εξισορρόπησης του φόρτου και στη συνέχεια δημιουργήσαμε ένα νέο πρωτόκολλο τοποθέτησης αντικειμένων για κατανεμημένα συστήματα αποθήκευσης το οποίο μετακινεί αντικείμενα μεταξύ των κόμβων του συστήματος, σε πραγματικό χρόνο εκτέλεσης, με στόχο να ελαχιστοποιηθεί ο αρκετά υψηλός χρόνος απόκρισης (με βάση ένα κατώτατο όριο που προσδιορίστηκε εμπειρικά). Το πρωτόκολλο τοποθέτησης αποτελεί μια υβριδική λύση που συνδυάζει την τυχαία τοποθέτηση και έναν αποκεντρωμένο κατάλογο εξαιρέσεων. Τέλος, προσεγγίσαμε το πρόβλημα της τοποθέτησης δεδομένων από τη σκοπιά της συμπίεσης. Ως μέρος της παρούσας διδακτορικής διατριβής, προτείναμε αλγορίθμους συμπίεσης που μπορούν να μειώσουν το μέγεθος των δεδομένων, ελαχιστοποιώντας την απώλεια πληροφοριών, διατηρώντας ταυτόχρονα την ποιότητα των πληροφοριών. Με άλλα λόγια, διερευνήσαμε τη συμπίεση ως μέσο για τη βελτίωση της απόδοσης του συστήματος.Τα αποτελέσματα έδειξαν ότι το πρωτόκολλο τοποθέτησης αντικειμένων που προτείναμε και δημιουργήσαμε, επιτυγχάνει την εξισορρόπηση του φόρτου σε ένα κατανεμημένο σύστημα, συγκεκριμένα σε ενα Redis Cluster, και ο μέσος χρόνος απόκρισης γίνεται ομοιόμορφος στους κόμβους του συστήματος, οδηγώντας έτσι στην βελτίωση της απόδοσης. Επιπλέον, η συμπίεση δεδομένων που παρουσιάζεται ως εναλλακτική λύση στο πρόβλημα της εξισορρόπησης του φόρτου, κατάφερε να μειώσει το μέγεθος των δεδομένων μέσω των προτεινόμενων αλγορίθμων, ελαχιστοποιώντας την απώλεια και ταυτόχρονα διατηρώντας την ποιότητα των πληροφοριών. Η σχέση και η επίδραση της συμπίεσης διερευνήθηκαν πειραματικά χρησιμοποιώντας τεχνικές ταξινόμησης και μέτρησης ομοιότητας. Τέλος, σχετικά με τον προσδιορισμό του πιο αποτελεσματικού συστήματος αποθήκευσης χωροχρονικών δεδομένων, τα αποτελέσματα έδειξαν πως η PostgreSQL παρουσιάσε τα καλυτερα αποτελέσματα σε όλες σχεδόν τις περιπτώσεις σε σύγκριση με τη MongoDB, με εξαίρεση τα ερωτήματα διασταύρωσης πολυγώνου.