Solid-state storage and work sharing for efficient scaleup data analytics

Abstract

Today, managing, storing and analyzing data continuously in order to gain additional insight is becoming commonplace. Data analytics engines have been traditionally optimized for read-only queries assuming that the main data reside on mechanical disks. The need for 24x7 operations in global markets and the rise of online and other quickly-reacting businesses make data freshness an additional design goal. Moreover, the increased requirements in information quality make semantic databases a key (often represented as graphs using the RDF data representation model). Last but not least, the performance requirements combined with the increasing amount of stored and managed data call for high-performance yet space-efficient access methods in order to support the desired concurrency and throughput. Innovative data management algorithms and careful use of the underlying hardware platform help us to address the aforementioned requirements. The volume of generated, stored and queried data is increasing exponentially, and new workloads often are comprised of time-generated data. At the same time the hardware is evolving with dramatic changes both in processing units and storage devices, where solid-state storage is becoming ubiquitous. In this thesis, we build workload-aware data access methods for data analytics - tailored for emerging time-generated workloads - which use solid-state storage, either (i) as an additional level in the memory hierarchy to enable real-time updates in data analytics, or (ii) as standalone storage for applications involving support for knowledge-based data, and support for efficiently indexing archival and time-generated data. Building workload-aware and hardware-aware data management systems allows to increase their performance and to augment their functionality. The advancements in storage have led to a variety of storage devices with different characteristics (e.g., monetary cost, access times, durability, endurance, read performance vs. write performance), and the suitability of a method to an application depends on how it balances the different characteristics of the storage medium it uses. The data access methods proposed in this thesis - MaSM and BF-Tree - balance the benefits of solid-state storage and of traditional hard disks, and are suitable for time-generated data or datasets with similar organization, which include social, monitoring and archival applications. The study of work sharing in the context of data analytics paves the way to integrating shared database operators starting from shared scans to several data analytics engines, and the workload-aware physical data organization proposed for knowledge-based datasets - RDF-tuple - enables integration of diverse data sources into the same systems.

Σήμερα, η συνεχής διαχείριση, αποθήκευση και ανάλυση δεδομένων με σκοπό την εξαγωγή πρόσθετης γνώσης και πληροφορίας έχει καταστεί κοινή πρακτική. Οι μηχανές ανάλυσης δεδομένων έχουν παραδοσιακά βελτιστοποιηθεί για ερωτήματα μόνο ανάγνωσης, με την παραδοχή ότι τα κύρια δεδομένα αποθηκεύονται σε μηχανικούς δίσκους. Η ανάγκη για αδιάλειπτη λειτουργία (24x7) στις παγκόσμιες αγορές, καθώς και η ανάπτυξη διαδικτυακών και άλλων επιχειρήσεων που απαιτούν άμεση ανταπόκριση, καθιστούν τη φρεσκάδα των δεδομένων (data freshness) έναν επιπλέον στόχο σχεδιασμού. Επιπλέον, οι αυξανόμενες απαιτήσεις ως προς την ποιότητα της πληροφορίας καθιστούν τις σημασιολογικές βάσεις δεδομένων ιδιαίτερα σημαντικές, οι οποίες συχνά αναπαρίστανται ως γράφοι με τη χρήση του μοντέλου αναπαράστασης δεδομένων RDF. Τέλος, οι απαιτήσεις υψηλής απόδοσης σε συνδυασμό με τη διαρκώς αυξανόμενη ποσότητα αποθηκευμένων και διαχειριζόμενων δεδομένων επιβάλλουν την ανάπτυξη αποδοτικών μεθόδων πρόσβασης στα δεδομένα, οι οποίες να προσφέρουν υψηλή απόδοση και ταυτόχρονα οικονομία χώρου, ώστε να υποστηρίζουν τον επιθυμητό βαθμό ταυτόχρονης πρόσβασης και ρυθμό επεξεργασίας. Καινοτόμοι αλγόριθμοι διαχείρισης δεδομένων, σε συνδυασμό με την προσεκτική αξιοποίηση της υποκείμενης υπολογιστικής υποδομής, συμβάλλουν στην αντιμετώπιση των παραπάνω απαιτήσεων. Ο όγκος των δεδομένων που παράγονται, αποθηκεύονται και αναζητούνται αυξάνεται εκθετικά, ενώ οι νέοι φόρτοι εργασίας αποτελούνται συχνά από δεδομένα που παράγονται συνεχώς στον χρόνο. Παράλληλα, το υλικό εξελίσσεται ραγδαία, τόσο ως προς τις μονάδες επεξεργασίας όσο και ως προς τις συσκευές αποθήκευσης, με τα μέσα αποθήκευσης στερεάς κατάστασης (solid-state storage) να καθίστανται πλέον πανταχού παρόντα. Στην παρούσα διατριβή αναπτύσσουμε μεθόδους πρόσβασης δεδομένων προσαρμοσμένες στα χαρακτηριστικά του εκάστοτε φόρτου εργασίας για εφαρμογές ανάλυσης δεδομένων, ειδικά σχεδιασμένες για αναδυόμενους φόρτους εργασίας που βασίζονται σε δεδομένα με τιμές σχετιζόμενες με το χρόνο δημιουργίας τους. Οι μέθοδοι αυτές αξιοποιούν αποθήκευση στερεάς κατάστασης είτε (i) ως ένα επιπλέον επίπεδο στην ιεραρχία μνήμης, προκειμένου να καταστήσουν δυνατές τις ενημερώσεις σε πραγματικό χρόνο σε συστήματα ανάλυσης δεδομένων, είτε (ii) ως αυτόνομο αποθηκευτικό μέσο για εφαρμογές που υποστηρίζουν δεδομένα γνώσης, καθώς και για την αποδοτική ευρετηρίαση αρχειακών και χρονικά παραγόμενων δεδομένων. Η ανάπτυξη συστημάτων διαχείρισης δεδομένων που λαμβάνουν υπόψη τόσο τον φόρτο εργασίας όσο και τα χαρακτηριστικά του υλικού επιτρέπει τη βελτίωση της απόδοσής τους και την επέκταση της λειτουργικότητάς τους. Οι εξελίξεις στις τεχνολογίες αποθήκευσης έχουν οδηγήσει στην εμφάνιση ποικίλων συσκευών με διαφορετικά χαρακτηριστικά, όπως το οικονομικό κόστος, οι χρόνοι πρόσβασης, η αξιοπιστία, η ανθεκτικότητα, καθώς και η σχετική απόδοση σε αναγνώσεις και εγγραφές. Η καταλληλότητα μιας μεθόδου για μια συγκεκριμένη εφαρμογή εξαρτάται από τον τρόπο με τον οποίο εξισορροπεί τα διαφορετικά χαρακτηριστικά του αποθηκευτικού μέσου που χρησιμοποιεί. Οι μέθοδοι πρόσβασης στα δεδομένα που προτείνονται στην παρούσα διατριβή — οι MaSM και BF-Tree — αξιοποιούν ισορροπημένα τα πλεονεκτήματα τόσο των μέσων αποθήκευσης στερεάς κατάστασης όσο και των παραδοσιακών σκληρών δίσκων. Είναι ιδιαίτερα κατάλληλες για δεδομένα που συναντώνται σε εφαρμογές κοινωνικών δικτύων, συστημάτων παρακολούθησης και αρχειακών συστημάτων. Η μελέτη του διαμοιρασμού εργασίας (work sharing) στο πλαίσιο της ανάλυσης δεδομένων ανοίγει τον δρόμο για την ενσωμάτωση κοινόχρηστων τελεστών βάσεων δεδομένων — ξεκινώντας από κοινόχρηστες σαρώσεις δεδομένων (shared scans) — σε διάφορες μηχανές ανάλυσης δεδομένων. Παράλληλα, η προσαρμοσμένη στον φόρτο εργασίας φυσική οργάνωση δεδομένων που προτείνεται για σύνολα δεδομένων γνώσης, με την ονομασία RDF-tuple, καθιστά δυνατή την ενοποίηση ετερογενών πηγών δεδομένων μέσα στο ίδιο πληροφοριακό σύστημα.

De nos jours, la gestion, le stockage et l’analyse de données en continu, afin d’obtenir des informations supplémentaires, devient courant. Les systèmes d’analyse de données ont été traditionnellement optimisés pour des requêtes en lecture seule en supposant que les données principales résidaient sur des disques mécaniques. Le besoin d’opérer 24 heures sur 24, 7 jours sur 7 dans le contexte de marchés globaux et suite à l’accroissement des activités commerciales en ligne ont fait de la "fraîcheur des données" un objectif supplémentaire. En outre, les exigences accrues en matière de qualité de l’information rendent les bases de données sémantiques clés (souvent représentées comme des graphes utilisant le modèle de représentation de données RDF). Finalement, les contraintes de performances combinées avec l’augmentation du volume des données stockées et gérées nécessitent des méthodes d’accès performantes mais efficaces en termes de stockage afin de garantir le niveau de concurrence et de débit souhaité. Des algorithmes de gestion de données innovants et l’utilisation attentive de la plateforme matérielle sous jacente nous aident à répondre aux exigences citées. Le volume des données générées, stockées et demandées augmente exponentiellement et les nouvelles charges de travail contiennent souvent des données temporelles. En même temps, le matériel informatique évolue avec des changements drastiques autant dans les unités de traitement que dans le stockage où les lecteurs à état solide deviennent omniprésents. Dans cette thèse, nous construisons des méthodes d’accès s’adaptant aux charges de travail d’analyse de données. Elles sont faites sur mesure pour les données temporelles qui utilisent le stockage à l’état solide soit (i) comme un niveau supplémentaire dans la hiérarchie de stockage permettant des mises à jour en temps réel des analyses de données ou (ii) comme stockage indépendant pour des applications nécessitant le support de données basées sur la connaissance et le soutient pour l’indexation efficace de données d’archive. Les systèmes de gestion de données utilisant la connaissance de la charge de travail et de la plateforme matérielle sous jacente peuvent augmenter leurs performances et fonctionnalités. L’avance dans le domaine des périphériques de stockage a mené au développement d’une variété de caractéristiques différentes (par exemple: coûts monétaires, temps d’accès, durabilité, endurance, performance de lecture contre écriture, etc.). L’efficacité d’une méthode d’accès pour une application donnée dépend de comment ces caractéristiques sont conciliées. Les méthodes d’accès proposées dans cette thèse, MaSM et BF Tree, équilibrent les gains du stockage à l’état solide avec le stockage sur disques durs traditionnels et sont appropriées pour les données temporelles ou avec une structure similaire. Ceci comprend les applications sociales, de contrôle ou d’archivage. L’étude du partage du travail dans le contexte des analyses de données ouvre la voie à l’intégration d’opérateurs de bases de données partagés à partir de scans communs à plusieurs systèmes d’analyse de données et avec l’organisation physique des données basée sur les charges de travail et les ensembles de données liées à des connaissances (RDF tuple) permettent l’intégration de plusieurs sources de données dans un même système.