Efficient storage indexing of structured and unsructured data

Abstract

Commercial and public organizations currently strive to manage massive amounts of structured and unstructured data in all fields of society. The data collected across different local and online services, such as news websites, social media, mail servers and file systems, is inherently semi-structured or unstructured. Therefore, effective text indexing and search is crucial for data usability and exploration. Moreover, the exploding amount of structured data that needs to be managed and the demanding workloads that include both throughput-oriented batch jobs and latency-sensitive data serving drive the development of horizontally-expandable, distributed storage systems, called scalable datastores. In this thesis, we study the analysis, design, and implementation of storage systems to efficiently store, access, and search both structured and unstructured data.Real-time text search requires to incrementally ingest content updates and make them searchable almost immediately, but also serve search queries at low latency. Recent methods for incremental index maintenance substantially increase search latency with the index fragmented across multiple disk locations. For the support of fast indexing and search over disk-based storage, we introduce a method called Selective Range Flush (SRF). We organize the disk index over blocks, which allow to selectively update only the parts of the index that can be efficiently updated based on SRF. We show that SRF reduces the indexing time, but requires substantial experimental effort to tune specific parameters for performance efficiency. Subsequently, we propose the Unified Range Flush (URF) method, which is conceptually simpler than SRF, achieves similar or better performance with fewer parameters and less tuning, and is amenable to I/O complexity analysis. We implement the two methods in the Zettair open-source search engine, using carefully optimized storage and memory management. Then, we do extensive experiments with three different web datasets of size up to 1TB. Across different open-source systems, we show that our methods offer search latency that matches or reduces up to half the lowest achieved by existing disk-based methods. In comparison to an existing method of comparable search latency on the same system, our methods reduce by a factor of 2.0-2.4 the I/O part of build time, and by 21-24% the total build time.Scalable datastores are required to manage enormous amounts of structured data for online serving and analytics applications. Across different workloads, they weaken the relational and transactional assumptions of traditional databases to achieve horizontal scalability and availability, and meet demanding throughput and latency requirements. Efficiency tradeoffs at each storage server often lead to design decisions that sacrifice query responsiveness for higher insertion throughput. In order to address this limitation, we introduce the Rangetable storage structure and Rangemerge method so that we efficiently manage structured data in granularity of key ranges. We develop both a general prototype framework and a storage system based on Google's LevelDB open-source key-value store. In these two platforms, we implement several representative methods as plugins to experimentally evaluate their performance under common operating conditions. We conclude that our approach incurs range-query latency that is minimal and has low sensitivity to concurrent insertions, while it achieves insertion performance that approximates that of write-optimized methods under modest query load. Our method also reduces down to half the reserved disk space, improves the write throughput proportionally to the available main memory, and naturally exploits the key skewness of the inserted dataset.

Δημόσιοι οργανισμοί και ιδιωτικές επιχειρήσεις αντιμετωπίζουν σήμερα το πρόβλημα της διαχείρισης μεγάλου όγκου δομημένων και αδόμητων δεδομένων. Τα δεδομένα αυτά συχνά συλλέγονται από ένα πλήθος τοπικών υπηρεσιών ή υπηρεσιών του διαδικτύου, όπως τα συστήματα αρχείων, οι ιστοσελίδες ενημέρωσης, τα κοινωνικά δίκτυα και οι διακομιστές ηλεκτρονικού ταχυδρομείου, και είναι εγγενώς ημιδομημένα ή αδόμητα. Για το λόγο αυτό, η αποτελεσματική δεικτοδότηση και αναζήτηση κειμένου είναι μία εξαιρετικά σημαντική υπηρεσία για την αξιοποίηση και χρήση των δεδομένων αυτών. Επιπρόσθετα, το συνεχώς αυξανόμενο μέγεθος των δομημένων δεδομένων που πρέπει να διαχειριστούν, καθώς και ο υψηλός αλλά και ποικιλόμορφος φόρτος εργασίας, έχουν οδηγήσει στην ανάπτυξη οριζόντια-επεκτάσιμων κατανεμημένων συστήματων τα οποία καλούνται κλιμακώσιμα συστήματα αποθήκευσης. Στη διατριβή αυτή μελετούμε την ανάλυση, το σχεδιασμό και την υλοποίηση αποδοτικών συστημάτων αποθήκευσης και αναζήτησης για δομημένα και αδόμητα δεδομένα.Η αναζήτηση κειμένου σε πραγματικό χρόνο προϋποθέτει τη δυνατότητα συνεχούς εισαγωγής νέων ενημερώσεων στο σύστημα και την σχεδόν άμεση διάθεσή τους προς αναζήτηση, όπως επίσης και την εξυπηρέτηση ερωτημάτων αναζήτησης με χαμηλή καθυ\-στέ\-ρηση. Πρόσφατες μέθοδοι για την αυξητική ενημέρωση του ευρετηρίου αναζήτησης κατακερματίζουν το ευρετήριο στο δίσκο, με αποτέλεσμα τη σημαντική αύξηση των χρόνων αναζήτησης. Έχοντας ως στόχο την υποστήριξη γρήγορης δεικτοδότησης και αναζήτησης, προτείνουμε τη μέθοδο Selective Range Flush (SRF). Επιλέγουμε να οργανώσουμε το ευρετήριο στο δίσκο σε μπλοκ, το οποίο επιτρέπει την επιλεκτική ενημέρωση μόνο των τμημάτων του ευρετηρίου που μπορούν να ενημερωθούν αποδοτικά βάσει του αλγορίθμου SRF. Δείχνουμε πως ο SRF πετυχαίνει μείωση του χρόνου δεικτοδότησης, όμως απαιτεί σημαντική πειραματική προσπάθεια για την αποτελεσματική παραμετροποίηση του. Στη συνέχεια προτείνουμε τον αλγόριθμο Unified Range Flush (URF), ο οποίος είναι κατά βάση απλούστερος από τον SRF, πετυχαίνει παρόμοια ή και καλύτερη απόδοση με λιγότερες παραμέτρους και ευκολότερη ρύθμισή τους, ενώ επιτρέπει τη μελέτη της ασυμπτωτικής του πολυπλοκότητας. Αναπτύσσουμε τις δύο προτεινόμενες μεθόδους στη μηχανή αναζήτησης ανοιχτού κώδικα Zettair, χρησιμοποιώντας προσεκτικά υλοποιημένα υποσυστήματα διαχείρισης μνήμης και δίσκου. Έπειτα, εκτελούμε εκτεταμένα πειράματα με τρεις διαφορετικές συλλογές δεδομένων μεγέθους μέχρι 1TB. Μεταξύ διαφορετικών συστημάτων ανοιχτού κώδικα, δείχνουμε ότι οι μέθοδοί μας παρέχουν καθυστέρηση αναζήτησης που είναι παρόμοια ή μειωμένη έως και 50% σε σχέση με τις χαμηλότερες καθυστερήσεις που πετυχαίνουν υπάρχουσες μέθοδοι. Συγκριτικά με μία μέθοδο αντίστοιχης καθυστέρησης αναζήτησης, οι μέθοδοί μας μειώνουν κατά έναν παράγοντα 2.0-2.4 το κομμάτι του χρόνου δεικτοδότησης που αφορά την Ε/Ε, και κατά 21%-24% το συνολικό χρόνο δεικτοδότησης.Τα κλιμακώσιμα συστήματα αποθήκευσης είναι σήμερα απαραίτητα για τη διαχείριση του τεράστιου όγκου δομημένων δεδομένων που απαιτούν οι υπηρεσίες διαδικτύου και οι διάφορες εφαρμογές ανάλυσης δεδομένων. Με σκοπό την επίτευξη οριζόντιας κλιμακωσιμότητας και διαθεσιμότητας, καθώς και την εξυπηρέτηση αιτημάτων με υψηλή ρυθμαπόδοση και χαμηλή καθυστέρηση, τα συστήματα αυτά δεν υιοθετούν το σχεσιακό μοντέλο και τις ACID ιδιότητες που παρέχουν οι παραδοσιακές βάσεις δεδομένων. Έχοντας ως κύριο στόχο την παροχή υψηλής απόδοσης αποθήκευσης εγγραφών, τα συστήματα αυτά συνήθως επιλέγουν να θυσιάσουν την απόδοση ανάγνωσης εγγραφών. Για να αντιμετωπίσουμε τον περιορισμό αυτό προτείνουμε την δομή αποθήκευσης Rangetable και τη μέθοδο Rangemerge, βάσει των οποίων η διαχείριση των εγγραφών γίνεται αποδοτικά ομαδοποιώντας τις σε λεξικογραφικά εύρη. Αναπτύσσουμε τόσο μία γενική πρότυπη πλατφόρμα αποθήκευσης όσο και ένα αποθηκευτικό σύστημα βασισμένο στο LevelDB, ένα ανοιχτού κώδικα σύστημα διαχείρισης κλειδιού-τιμής από τη Google. Υλοποιούμε ένα πλήθος από αντιπροσωπευτικές μεθόδους στα δύο αυτά συστήματα και μελετούμε πειραματικά την απόδοσή τους. Δείχνουμε πως η απόδοση της προσέγγισής μας επιτυγχάνει καθυστέρηση απάντησης σε ερωτήματα εύρους (range-queries) που είναι ελάχιστη και έχει χαμηλή ευαισθησία σε ταυτόχρονες εισαγωγές δεδομένων. Παράλληλα, η απόδοση εγγραφής της μεθόδου μας προσεγγίζει αυτές των μεθόδων που είναι σχεδιασμένες για υψηλή απόδοση εγγραφής όταν ταυτόχρονα εξυπηρετούνται και αιτήματα ανάγνωσης. Τέλος, η μέθοδός μας μειώνει στο μισό το δεσμευμένο αποθηκευτικό χώρο, βελτιώνει την ρυθμαπόδοση εισαγωγής δεδομένων αναλογικά με τη διαθέσιμη μνήμη του συστήματος, ενώ εκμεταλλεύεται την ασυμμετρία της κατανομής των κλειδιών που εισάγονται.