Indexing on Non-Volatile Memory: Techniques, Lessons Learned and Outlook (SpringerBriefs in Computer Science)

✍ Scribed by Kaisong Huang, Tianzheng Wang

• Publisher: Springer
• Year: 2023
• Tongue: English
• Leaves: 92
• Category: Library

✦ Synopsis

This book focuses on online transaction processing indexes designed for scalable, byte-addressable non-volatile memory (NVM) and provides a systematic review and summary of the fundamental principles and techniques as well as an outlook on the future of this research area.

In this book, the authors divide the development of NVM indexes into three “eras”― pre-Optane, Optane and post-Optane―based on when the first major scalable NVM device (Optane) became commercially available and when it was announced to be discontinued. The book will analyze the reasons for the slow adoption of NVM and give an outlook for indexing techniques in the post-Optane era.

The book assumes only basic undergraduate-level understanding on indexing (e.g., B+-trees, hash tables) and database systems in general. It is otherwise self-contained with the necessary background information, including an introduction to NVM hardware and software/programming issues, a detailed description of different indexes in highly concurrent systems for non-experts and new researchers to get started in this area.

✦ Table of Contents

Preface
Contents
Chapter 1 Introduction
1.1 The Non-Volatile Memory Vision
1.2 Database Indexing on NVM
References
Chapter 2 NVM Hardware and Software
2.1 Non-Volatile Memory Hardware Landscape
2.1.1 Maturing and In-Production NVM Devices
Phase Change Memory (PCM)
3D XPoint (Optane PMem)
Non-Volatile DIMMs
2.1.2 Work-In-Progress NVM Candidates
Memristor
STT-RAM
Nano-RAM
2.2 System Architecture
2.2.1 NVM in the Storage Hierarchy
2.2.2 Role of NVM
Generic DRAM-NVM Architecture
DRAM as a Transparent Cache
Hybrid Modes
2.3 Programming Model
Hardware Support
Software Support
References
Chapter 3 A Primer on Database Indexing
3.1 Overview
3.2 Range Indexes
3.2.1 B+-trees
3.2.2 Radix Trees (Tries)
3.3 Hash Tables
3.3.1 Static Hashing
3.3.2 Dynamic Hashing
Extendible Hashing
3.3.2.1 Linear Hashing
3.4 Index Concurrency Control
References
Chapter 4 Range Indexes on Non-Volatile Memory
4.1 Introduction
4.2 Pre-Optane NVM Range Indexes
4.2.1 Write-Atomic B+-tree (wB+-Tree)
Tree Structure
Unsorted Nodes
Indirection
4.2.2 NV-Tree
Tree Structure
Selective Consistency
4.2.3 Fingerprinting B+-tree (FPTree)
Tree Structure
Fingerprinting
Selective Concurrency
4.2.4 BzTree
Tree Structure
Lock-Free Index Operations
4.3 Optane-Era NVM Range Indexes
4.3.1 LB+-Tree
Tree Structure
Entry Moving
Logless Node Split
Distributed Headers
4.3.2 ROART
Tree Structure
Leaf Compaction
Reducing Persistence Overhead
Delayed Check Memory Management (DCMM)
4.3.3 PACTree
Tree Structure
Asynchronous SMOs
NUMA-Aware NVM Management
4.3.4 DPTree
Tree Structure
Flush-Optimized Persistent Logging
Coarse-Grained Versioning
Crash-Consistent In-Place Merge
4.4 Chapter Notes
References
Chapter 5 Hash Tables on Non-Volatile Memory
5.1 Introduction
5.2 Level Hashing
Hash Table Structure
Reducing Data Movement during Insert
In-Place Resizing
Concurrency Control
5.3 Cacheline-Conscious Extendible Hashing
Hash Table Structure
Consistency
Concurrency Control
5.4 Dash
Hash Table Structure
Fingerprinting
Load Balancing
Concurrency and Recovery
5.5 Chapter Notes
References
Chapter 6 Summary
6.1 Overview
6.2 Index Structure and Layout
6.3 Concurrency
6.4 NVM Management
References
Chapter 7 Lessons Learned and Outlook
7.1 A Cautionary Tale of Optane PMem
7.1.1 Total Cost of Acquisition
7.1.2 Performance Per Dollar
7.1.3 Non-Technical Factors
7.2 Lessons Learned
7.3 Outlook
7.3.1 NVM Indexing Techniques for DRAM Indexing
7.3.2 Leveraging NVDIMMs
7.3.3 Future NVM and Far Memory Technologies
References