Here's an abstract and summary of the provided transcript:
Abstract:
This post details the comprehensive redesign of the Marginalia Search index to leverage modern hardware, particularly NVMe SSDs, for enhanced query performance. The core changes involve migrating from memory-mapped B-trees to a new deterministic block-based skip list structure, specifically optimized for random access patterns inherent in search engine operations. The author explores the unintuitive performance characteristics of NVMe SSDs, demonstrating that larger read block sizes (e.g., 128 KB) can yield disproportionately faster transfer rates with minimal latency increase, significantly improving lookup and execution times. The article also discusses the implementation of io_uring for concurrent reads of position data, highlighting its benefits for throughput alongside challenges in managing queue depth and latency jitter. The redesign has led to substantial performance gains and is now deployed in production, with key findings emphasizing the importance of data locality, read-merging, and careful tuning for optimal NVMe SSD utilization.
Summarizing "Faster Index I/O with NVMe SSDs"
Problem & Motivation (Introduction):
The Marginalia Search index was redesigned to improve query performance within a tight 100-250ms budget, despite recent growth from 350 million to 800 million documents.
Upcoming support for additional languages is expected to further increase index size, necessitating efficiency improvements.
The existing index structure, using memory-mapped B-trees, had performance limitations, especially with increasing scale.
Original Index Structure (Indexing at a glance):
Conceptually, the index consists of an inverted_index (mapping terms to document IDs and positions) and positions (storing term positions within documents).
The inverted_index was implemented as a memory-mapped B-tree, a known problematic approach for databases due to issues like page cache thrashing.
Linux Read Modes (Aside: Read Modes):
Buffered Reads: Go through the system's page cache, potentially avoiding disk reads; can read more data than requested. Generally preferred but can suffer from readahead and cache thrashing with random access.
Direct Reads (O_DIRECT): Bypass the system cache, copying data directly to the buffer. Require reads at specific block-size multiples (e.g., 512B or 4096B) and can be finicky. Often faster for cache misses and offer more consistent latencies in database-like scenarios.
RWF_DONTCACHE (upcoming) is presented as a promising middle-ground.
Redesigning the B-Trees (Redesigning The B-Trees):
Initial attempt to re-implement B-trees with direct-mode reads was not performant due to block-size limitations creating "dead air" from block alignment requirements.
This led to the development of a Deterministic Block-Based Skip List as the new data structure.
New Data Structure: Deterministic Block Skip Lists:
Concept: Similar to B-trees but optimized for sorted list intersection, easier to implement, and conceptually a directed acyclic graph.
Design Rules for NVMe Optimization:
First node in a list can be anywhere in a block; subsequent nodes must start at a block boundary.
Nodes must not straddle block boundaries.
These rules allow for dense, direct-mode friendly reads and handle truncated blocks for varied list sizes.
Forward Pointers: Deterministic locations, allowing efficient traversal by storing only the largest value in the destination node. Follow a linear then quadratic scheme for varying jump sizes, ensuring efficient navigation.
NVMe SSD Performance (NVMe SSDs):
Key Insight: For isolated single reads, NVMe SSDs exhibit sublogarithmic read time as a function of block size. Reading much larger blocks (e.g., 1MB) takes only slightly longer than reading very small blocks (e.g., 512B).
Implication: Choosing a small block size (e.g., 4KB) drastically underutilizes the SSD's read performance.
Optimal Block Size: 128 KB appears to be the point of diminishing returns, offering significant performance gains over smaller sizes.
Larger blocks also improve buffer pool performance and allow for more forward pointers, reducing node traversals.
Compression of document lists became less critical due to high read speeds, shifting bottleneck to result ranking and position data retrieval.
Read Latency and io_uring (Read latency):
io_uring was adopted for retrieving position data (many small reads) and provides 5-20x speedup over synchronous reads.
Challenges: Can lead to "thundering herd" issues and clobbering the SSD controller, causing latency jitter (pauses of dozens of milliseconds).
Mitigation: Breaking out position data retrieval into a limited number of separate threads and careful tuning to balance throughput and latency.
Data Locality (Data Locality):
Optimization: Rearranging position data to cluster by document, reducing spread and allowing more relevant data per read.
Effectiveness: Works well with buffered reads and POSIX_FADV_RANDOM, outperforming O_DIRECT in production due to kernel read merging.
Conclusions and Future Work (Conclusions):
Maximizing NVMe SSD performance requires benchmarking and scrutinizing old assumptions; it's more about data locality, read-merging, and queue depth than limiting bytes read.
Benchmarking disk I/O is complex due to multiple layers of caching.
io_uring can be powerful but requires careful use and tuning to avoid negative performance impacts ("foot gun").
The new changes are merged and deployed, with 128 KB block sizes in production (64 KB to 256 KB also perform comparably).
Future optimizations may include better compression for position data or reviving bloom filter intersection for approximate position matching to reduce I/O.
The design is configurable to run well on various hardware, including SATA SSDs.