Data structuring techniques for non-volatile memories

Abstract

Non-Volatile Memories (NVMs) have revolutionize data storage replacing traditional magnetic HDDs in both consumer and enterprise computer systems. Flash based Solid State Drives (SSDs) have become the storage medium of choice for many applications thanks to their high throughput/low latency, shock resistance and low power consumption. Lately, the advent of 3DXPoint with even better properties introduced a new breakthrough for storage systems. Data indexing has been significantly influenced by these advances. Indexes are special purpose data structures, designed to provide fast access to large data collections. They have been extensively studied in DBMSes assuming HDDs as the underlying storage. However, treating SSDs as simply another category of block devices ignoring their inherent idiosyncrasies (e.g. erase-before-write, wear-out, asymmetric read/write speed) and their assets (e.g. their ability to process more than one I/O requests in parallel) may lead to poor performance.In this dissertation we survey the most important flash-aware indexes and we present new indexing techniques for the NVM based storage. Briefly, in the first part of our research we study flash aware spatial indexes, while in the second we follow a different roadmap exploiting both flash and 3DXPoint technologies. Thus, we introduce GFFM and LB-Grid two variants of Grid File for flash SSDs. GFFM utilizes a buffering strategy that exploits batch writes, while LB-Grid uses logging to reduce small random writes at the buckets' level. We present flash efficient algorithms for range, kNN and group point queries for both LB-Grid and GFFM. We also discuss our contribution in the development of flash efficient bulk-loading, bulk-insertion and querying algorithms for the XBR+-tree. In the sequel, we examine hybrid storage configurations that comprise flash and 3DXPoint SSDs. We propose the H-Grid, a spatial index structure that utilizes flash SSDs as mass storage tier and 3DXPoint ones as performance tier. We examine R-tree efficiency on a 3DXPoint SSD as well, and we present the sHR-tree an initial, yet illuminating effort to develop a hybrid index based on R-tree. Finally, we assay the latest advances in the SSDs' architecture, the programming models and upcoming NVM technologies and we discuss the future trends and new lines of research related to this field.

Οι μη-πτητικές μνήμες έχουν συνεισφέρει σημαντικά στην εξέλιξη των συστημάτων αποθήκευσης. Oι δίσκοι στερεάς κατάστασης τεχνολογίας flash έχουν αντικαταστήσει τους παραδοσιακούς μαγνητικούς δίσκους σε μια μεγάλη γκάμα εφαρμογών, καθώς προσφέρουν υψηλές επιδόσεις, χαμηλή κατανάλωση, οικονομία χώρου και μεγάλη αντοχή σε καταπονήσεις. Μια νέα τεχνολογία μη-πτητικών μνημών με ακόμη καλύτερες ιδιότητες, η 3DXPoint, φιλοδοξεί να αποτελέσει εφαλτήριο για ακόμη μεγαλύτερες επιδόσεις. Η πρόοδος που έχει συντελεστεί τα τελευταία χρόνια στα συστήματα αποθήκευσης έχει επηρεάσει σημαντικά την ευρετηρίαση δεδομένων. Οι δείκτες είναι ειδικές δομές δεδομένων που αποσκοπούν στο να παρέχουν γρήγορη πρόσβαση σε μεγάλες συλλογές δεδομένων και έχουν μελετηθεί εκτενώς για την περίπτωση που ένας μαγνητικός δίσκος χρησιμοποιείται ως αποθηκευτικό μέσο. Ωστόσο, η απευθείας χρήση δομών που έχουν σχεδιαστεί για τους μαγνητικούς δίσκους σε συστήματα αποθήκευσης που χρησιμοποιούν μη πτητικές μνήμες δεν παρέχει ικανοποιητικά αποτελέσματα. Οι δίσκοι στερεάς κατάστασης συγκεντρώνουν ένα αριθμό από ιδιαιτερότητες, που μπορεί να οδηγήσουν σε χαμηλή απόδοση. Συνοπτικά, οι ταχύτητες ανάγνωσης, εγγραφής, διαγραφής δεδομένων διαφέρουν, η εγγραφή νέων δεδομένων απαιτεί την πρότερη διαγραφή τυχόν υπαρχόντων, ενώ μεγάλος αριθμός εργασιών εγγραφής/διαγραφής προκαλεί φθορά της μνήμης. Από την άλλη, η αποδοτική εκμετάλλευση του εσωτερικού παραλληλισμού που διαθέτουν οι δίσκοι στερεάς κατάστασης είναι άρρηκτα συνδεδεμένη με υψηλές αποδόσεις. Στα πλαίσια αυτής της διατριβής μελετήσαμε εκτενώς την βιβλιογραφία και παρουσιάσαμε μια κριτική καταγραφή των σημαντικότερων δομών ευρετηρίασης μονοδιάστατων και πολυδιάστατων δεδομένων που έχουν αναπτυχθεί για τους δίσκους στερεάς κατάστασης. Σχεδιάσαμε και αναπτύξαμε τα GFFM και LB-Grid, δύο δομές ευρετηρίασης χωρικών δεδομένων που στηρίζονται στο Grid File. Το GFFM αξιοποιεί μαζικές εγγραφές και αναγνώσεις, ενώ το LB-Grid χρησιμοποιεί μια τεχνική logging για να μειώσει των αριθμό των τυχαίων εγγραφών. Ταυτόχρονα, αναπτύξαμε αλγορίθμους ερωτημάτων που εκμεταλλεύονται τα χαρακτηριστικά των δίσκων στερεάς κατάστασης. Συμμετείχαμε στην σχεδίαση τεχνικών μαζικού χτισίματος, μαζικής εισαγωγής νέων δεδομένων και μαζικής επεξεργασίας ερωτημάτων για το XBR+-tree. Μελετήσαμε το πρόβλημα της ευρετηρίασης χωρικών δεδομένων σε υβριδικά συστήματα αποθήκευσης που αποτελούνται από δίσκους στερεάς κατάστασης τεχνολογίας flash και 3DXPoint. Αναπτύξαμε το H-Grid και το sHR-tree, δύο υβριδικούς δείκτες, που εκμεταλλεύονται τις ιδιότητες των δύο τεχνολογιών μη-πτητικών μνημών. Τέλος, με βάση τις πιο πρόσφατες εξελίξεις στις τεχνολογίες των μη πτητικών μνημών και των δίσκων στερεάς κατάστασης αναδείξαμε νέες ερευνητικές ευκαιρίες στο χώρο της ευρετηρίασης δεδομένων.