Aparajita: Branchless SIMD Search and Append-Only Nodes for LSM-Tree MemTables

Article activity feed

1. 

   PREreview

   Sep 25, 2026

   This Zenodo record is a permanently preserved version of a Structured PREreview. You can view the complete PREreview at https://prereview.org/reviews/22960770.

   Does the introduction explain the objective of the research presented in the preprint? Yes Justification: The introduction and abstract clearly articulate the research problem, hardware motivation, and explicit objectives of the manuscript: Problem Context: In Log-Structured Merge-tree (LSM-tree) key-value stores such as RocksDB and LevelDB, the in-memory write buffer (MemTable) sits on both the read and write paths of the engine . RocksDB's default implementation uses a concurrent skip list, which chases pointers across independently allocated nodes and evaluates data-dependent, …

   This Zenodo record is a permanently preserved version of a Structured PREreview. You can view the complete PREreview at https://prereview.org/reviews/22960770.

   Does the introduction explain the objective of the research presented in the preprint? Yes Justification: The introduction and abstract clearly articulate the research problem, hardware motivation, and explicit objectives of the manuscript: Problem Context: In Log-Structured Merge-tree (LSM-tree) key-value stores such as RocksDB and LevelDB, the in-memory write buffer (MemTable) sits on both the read and write paths of the engine . RocksDB's default implementation uses a concurrent skip list, which chases pointers across independently allocated nodes and evaluates data-dependent, unpredictable branches per key comparison. On modern hardware, this creates dependent chains of cache misses and branch mispredictions that limit engine throughput. Core Research Objective: The author proposes Aparajita, a novel MemTable representation designed to replace the skip list with cache-line-sized nodes searched by a branchless Single Instruction Multiple Data (SIMD) kernel . The explicit objective is to demonstrate that aligning MemTable nodes to 64-byte cache lines and replacing pointer chasing with vector comparison instructions significantly reduces instruction counts and Level 1 cache misses during lookups while preserving ordered iteration. Specific Design Innovations: The introduction outlines four key structural mechanisms developed to achieve this objective: Branchless SIMD Search Kernel: A vector relational comparison over fifteen order-preserving key surrogates and a sentinel that computes the lower bound via population count without conditional branches. Prefix-Relative Key Surrogates: A local surrogate extraction technique that takes key bytes after the node's shared prefix, overcoming the complete collapse of absolute leading-byte surrogates on realistic keyspaces. Append-Only Nodes & 64-Bit Order Word: A lock-free read / single-release-store write design that encodes sorted key order in a 64-bit integer, eliminating the need to physically rearrange keys during inserts. Descent Hints: Eight-byte key prefixes cached in tower headers to replace virtual comparator calls during skip-list tower descents with fast integer comparisons. Implementation & Evaluation Scope: The objective is validated by implementing Aparajita as a zero-patch RocksDB C++20 plugin and benchmarking it against SkipListRep and VectorRep across single-threaded and multi-threaded workloads on an Emerald Rapids host.

   Are the methods well-suited for this research? Highly appropriate Justification: The methodology employed in developing and evaluating Aparajita is exceptionally rigorous, hardware-conscious, and well-designed to isolate the performance impact of the MemTable data structure from the surrounding storage engine overhead. Methodological Strengths: Hardware-Aligned Cache-Line Architecture: Designing nodes to fit exactly into 64-byte cache lines aligned to memory boundaries ensures that search probes require only a single cache line fill without crossing line boundaries. Branchless SIMD Search Kernel: Using vector relational comparison instructions coupled with population count directly derives the lower-bound index without conditional branches, eliminating data-dependent branch mispredictions during lookups. Prefix-Relative Surrogate Design: To prevent surrogate collapse on structured keyspaces (where absolute leading key bytes are identical across keys), taking surrogates after each node's local shared prefix restores full key discrimination across realistic workloads. Append-Only Lock-Free Read Protocol: Utilizing append-only node slots coupled with a 64-bit order word allows atomic publication of inserts via a single release store, enabling lock-free concurrent reads without requiring node rebuilds or expensive memory reallocations. Descent Hints: Caching 8-byte key prefixes in skip-list tower headers replaces virtual comparator calls during tower descents with fast integer comparisons on already-loaded cache lines. Rigorous Experimental Isolation: The evaluation implements Aparajita as a zero-patch RocksDB C++20 plugin and employs a exact two-point counter differencing methodology (subtracting different operation counts at identical fill seeds) to isolate MemTable CPU and cache metrics from setup, flush, and benchmark harness noise. Comprehensive Validation Suite: Correctness is verified via differential testing against RocksDB's default SkipListRep, while concurrency safety is validated across thread counts using ThreadSanitizer. Constructive Feedback: Memory & Storage Overhead Bounds: The append-only node design incurs an arena memory footprint roughly 1.4 times larger than the default skip list, causing earlier MemTable flushes and generating approximately 40% more Level 0 files under fixed write-buffer sizes. Highlighting this memory-versus-lookup trade-off in the system configuration guidelines will help practitioners tune write-buffer sizes effectively.

   Are the conclusions supported by the data? Highly supported Justification: The manuscript's conclusions are thoroughly supported by rigorous empirical data, meticulous performance profiling, and an exceptionally honest discussion of system trade-offs and measurement limitations. Key Empirical Grounding: Point Lookup Acceleration: Benchmarks across 1, 4, 16, and 64 threads demonstrate that Aparajita achieves 22% to 39% higher point lookup throughput than RocksDB's default concurrent skip list. Micro-architectural counters confirm the underlying mechanisms: a 55% reduction in retired instructions (3,271.5 vs. 7,349.9 instructions per operation) and a 40% reduction in Level 1 cache misses (62.18 vs. 103.99 misses per operation). Branchless SIMD Efficiency: Isolated kernel benchmarks verify that the vector search kernels eliminate data-dependent branch mispredictions entirely (recording 0.0000 branch mispredictions per probe across both AVX2 and AVX-512) compared to the scalar baseline. Ordered Iteration Trade-offs: The data confirms that while initial seek operations are 15% to 29% faster, issuing a seek followed by ten sequential iterator steps is 3% to 4% slower. The author correctly attributes this to the append-only order word, where decoding a rank nibble per step incurs slightly more work than following a physical pointer chain. Avoidance of Overreaching & Honest Reporting: Recognizing Write-Path Ceilings: The paper explicitly refrains from making ungrounded multi-threaded write scaling claims. While single-threaded inserts are 18.8% faster and standalone MemTable benchmarks are 48% to 52% faster , the author demonstrates that multi-threaded db_bench inserts are bottlenecked by RocksDB's write-thread group (retiring over 22,000 instructions per operation across all data structures) rather than the MemTable itself. Transparent Memory & Flush Analysis: The evaluation explicitly measures the arena memory penalty: Aparajita charges 1.4 times the skip list's arena space per key, fitting fewer keys per 64 MiB write buffer (285,714 vs. 400,000 keys) and generating 40% more Level 0 files (7 vs. 5 files) upon flushing. Detailed Limitations Section: Section 6 openly reports unmeasured parameters, including the inability to capture cross-core Last-Level Cache invalidation hardware counters on virtualized cloud instances (due to disabled PEBS performance counters), lack of headroom testing beyond 12 physical cores, and unmeasured downstream compaction stalls from additional Level 0 files.

   Are the data presentations, including visualizations, well-suited to represent the data? Highly appropriate and clear Justification: The data presentations, visual diagrams, and performance tables in the manuscript are exceptionally well-crafted, highly accurate, and clear. They effectively translate complex low-level hardware structures and multi-threaded system benchmarks into intuitive visual representations. Visual & Presentational Strengths: Architectural Layout Diagrams (Figures 1 and 3): Figure 1 provides a precise, byte-scale structural diagram illustrating the exact 64-byte alignment boundary that separates vector search lanes from cold metadata fields. Figure 3 visually details the mechanics of the append-only node design, clearly illustrating arrival-order slot storage, 64-bit order word rank encoding, and atomic logical view publication. Empirical Distribution Visualizations (Figure 2): Figure 2 uses a clear horizontal bar chart on a logarithmic scale to contrast absolute surrogates against prefix-relative surrogates across eight key distributions. It visually demonstrates the complete collapse of absolute surrogates on structured keyspaces while proving that prefix-relative surrogates preserve key discrimination. Kernel & Engine Performance Profiling (Figures 4 and 5): Figure 4 effectively contrasts isolated search kernel cycles across instruction set architectures (AVX2, AVX-512, branchless scalar, and branchy scalar baselines). Figure 5 provides a comprehensive summary bar chart displaying relative throughput across all five core workloads and thread counts compared to RocksDB's default skip list. Comprehensive Tabular Transparency (Tables 1 through 6): Tables 1 through 6 provide meticulous, transparent statistical data. They report sample medians, range variations, micro-architectural hardware counters (retired instructions, branch misprediction counts, and Level 1 cache misses), thread-scaling metrics, and arena memory flush costs. Constructive Recommendation for Enhancement: Data Annotations in Summary Charts: In Figure 5 (relative throughput across thread counts), adding explicit numeric percentage labels directly above the bar clusters would enable readers to quickly digest exact relative performance differences without having to cross-reference Tables 2 through 5.

   How clearly do the authors discuss, explain, and interpret their findings and potential next steps for the research? Very clearly Justification: The discussion, interpretation of empirical findings, and outline of potential next steps in the manuscript are exceptionally thorough, self-aware, and insightful. Rather than simply reporting raw throughput numbers, the author provides deep micro-architectural explanations, isolates benchmark harness bottlenecks from data structure performance, and transparently documents system trade-offs and measurement limitations. Strengths in Discussion and Interpretation: Deconstructing Hardware & Architectural Mechanisms: The author clearly explains why point lookups are accelerated (yielding a 55% reduction in retired instructions and a 40% reduction in Level 1 cache misses per lookup) , attributing these gains to replacing pointer-chasing and data-dependent branch comparisons with 64-byte cache-line SIMD vector compares and prefix-relative key surrogates. Transparent Trade-off Analysis: The discussion provides a remarkably candid evaluation of structural trade-offs. For example, while initial seek operations are 15% to 29% faster, sequential iteration (a seek followed by ten iterator steps) is 3% to 4% slower because decoding rank nibbles from the 64-bit order word requires slightly more per-step work than following a physical pointer chain . Additionally, the paper explicitly reports the 1.4 times arena memory footprint penalty per key, which fits fewer keys into a 64 MiB write buffer and generates 40% more Level 0 files upon flushing. Separating Harness Bottlenecks from Representation Performance: The author explicitly identifies where benchmark harness machinery dominates performance. The discussion explains why multi-threaded insert benchmarks tie across representations: RocksDB's write-thread group retires over 22,000 instructions per operation regardless of the MemTable structure. The paper responsibly reports this ceiling rather than making ungrounded write-scaling claims. Explicit and Actionable Next Steps: Evaluating Compaction Stalls: Section 6 and Section 7 identify an essential next experiment: evaluating full storage engine throughput under active background compaction to measure the downstream impact of generating 40% more Level 0 files. Iterative Scan Optimization: The author outlines an explicit algorithmic fix for sequential scans: decoding multiple rank nibbles from the order word at once to amortize per-step decoding overhead. Bare-Metal Hardware Counter Collection: The manuscript details necessary future hardware benchmarking on bare-metal systems or hypervisors with Processor Event-Based Sampling (PEBS) support to collect cross-core Last-Level Cache invalidation metrics that were unavailable on virtualized cloud instances.

   Is the preprint likely to advance academic knowledge? Highly likely Justification: The manuscript makes significant, practical, and highly rigorous contributions to database storage engine design, hardware-conscious data structures, and benchmarking methodology in main-memory key-value systems. Key Academic & Technical Contributions: Bridging SIMD Vectorization to Mutable LSM MemTables: While SIMD vectorization has been widely applied to static read-optimized indexes [8–11], adapting branchless vector comparisons to a continuously written, lock-free concurrent MemTable represents a major architectural contribution. Aparajita demonstrates that replacing pointer-chasing skip lists with 64-byte cache-line nodes searched by a population-count vector kernel achieves 22% to 39% higher point lookup throughput. Prefix-Relative Key Surrogates: The paper identifies and solves a major flaw in naïve bi-encoder/key-slicing designs . The author proves empirically that absolute leading-byte surrogates collapse into a single value across 200,000 keys in five of eight realistic key distributions (including db_bench). Taking surrogates after each node's local shared prefix restores full key discrimination (achieving near 1.0 full-key comparisons per lookup across all distributions). Atomic Order-Word Publication for Append-Only Nodes: The manuscript introduces an append-only node design where key slot insertion order remains fixed, and sorted logical rank order is updated via a single 64-bit release store. This reduces arena memory consumption from 445.4 bytes to 100.6 bytes per key compared to payload-rebuilding designs while guaranteeing lock-free reads. Methodological Rigor & Benchmark Transparency: Beyond the data structure itself, the paper provides exemplary contributions to systems measurement methodology: Harness Isolation: It demonstrates how to use exact two-point counter differencing (subtracting identical fill runs at identical seeds) to isolate MemTable CPU and cache metrics from setup, flush, and harness noise. Reporting Harness Ceilings: It transparently demonstrates that multi-threaded write benchmarks in db_bench are ceiling-bounded by RocksDB's write-thread group (retiring over 22,000 instructions per operation) rather than the MemTable itself, setting a standard for honest performance reporting. Open Science & Direct Reusability: The author delivers a zero-patch, header-only C++20 plugin (github.com/sinhaparth5/aparajita-memtable) that integrates directly into RocksDB via the standard plugin interface, alongside archived Zenodo measurement scripts and raw benchmark logs for full reproducibility.

   Would it benefit from language editing? No Justification: The manuscript is exceptionally well-written, highly articulate, and demonstrates outstanding technical precision throughout. The prose is concise, logically structured, and uses clear systems engineering terminology to explain complex hardware-software interactions without ambiguity. Key Writing Strengths: Technical Precision & Clarity: The author explains low-level assembly SIMD semantics, C++20 memory orderings, atomic release-store publication protocols, and cache-line alignment boundaries with exceptional clarity. Transparent & Narrative Style: The paper employs a refreshingly candid narrative style that openly details measurement mistakes made during initial development (such as benchmark working-set sweeps and counter-differencing setup noise) and explains how they were systematically corrected. High-Quality Terminology & Structure: Section headings, figure captions, and table footnotes are precise, self-contained, and directly assist the reader in interpreting micro-architectural hardware counter metrics. No language editing is required prior to publication.

   Would you recommend this preprint to others? Yes, it's of high quality Justification: I strongly recommend this preprint to systems researchers, database engineers, and performance architects working on storage engine internals, main-memory indexes, and hardware-conscious concurrent data structures. The paper represents an outstanding piece of systems research that combines novel data structure design with rigorous micro-architectural profiling. Key Reasons for Recommendation: Innovative Hardware-Aligned Design: By replacing pointer-chasing skip lists with 64-byte cache-line nodes searched via a branchless population-count SIMD kernel, Aparajita demonstrates a principled approach to eliminating CPU cache misses and branch mispredictions in mutable key-value MemTables. Solving Real-World Edge Cases: The introduction of prefix-relative key surrogates successfully solves the surrogate collapse problem that degrades bi-encoder indexes on structured keyspaces, preserving full key discrimination across realistic workloads. Lock-Free Concurrency & Minimal Memory Overhead: The append-only node layout uses a single 64-bit release store to publish sorted key order atomically, reducing arena memory usage from 445.4 bytes to 100.6 bytes per key compared to payload-rebuilding vector designs while guaranteeing lock-free reads. Exceptional Experimental & Measurement Rigor: The paper uses exact two-point counter differencing to isolate MemTable CPU and cache metrics from benchmark harness noise, proving a 55% reduction in retired instructions and a 40% reduction in Level 1 cache misses for point lookups. Furthermore, the author demonstrates commendable scientific honesty by transparently analyzing memory consumption trade-offs, scan iterator overheads, and write-thread harness ceilings.

   Is it ready for attention from an editor, publisher or broader audience? Yes, as it is Justification: The manuscript represents an outstanding, highly rigorous, and publication-ready contribution to database systems research. It excels across every evaluation dimension in the PREreview framework: Rigorous & Innovative Methodology: The paper introduces a novel, hardware-aligned MemTable architecture that replaces pointer-chasing skip lists with 64-byte cache-line nodes searched by a branchless population-count SIMD kernel and prefix-relative key surrogates. Solid Empirical Grounding: Evaluated across multiple thread counts and benchmark workloads on an Emerald Rapids host, Aparajita achieves a 22% to 39% throughput increase for point lookups, verified by micro-architectural hardware counters showing a 55% reduction in retired instructions and a 40% reduction in Level 1 cache misses. Scientific Honesty & Transparency: The author transparently documents system trade-offs—including the 1.4 times arena memory footprint penalty per key and the slight 3% to 4% throughput drop for long-range iterator scans—while accurately identifying write-thread group ceilings in db_bench. Exemplary Presentation & Reproducibility: Visual layout diagrams, logarithmic surrogate distribution charts, and performance tables are exceptionally clear. The work includes a zero-patch, header-only C++20 RocksDB plugin (github.com/sinhaparth5/aparajita-memtable) and archived Zenodo measurement scripts for full end-to-end reproducibility. While minor quality-of-life enhancements (such as adding explicit numeric percentage labels above the bar clusters in Figure 5) could be incorporated in a final camera-ready version, the manuscript in its current form is thoroughly prepared for publication and broad dissemination to the computer systems and database research community.

   Competing interests

   The author declares that they have no competing interests.

   Use of Artificial Intelligence (AI)

   The author declares that they used generative AI to come up with new ideas for their review.

   Read the original source
2. Version published to 10.20944/preprints202609.0995.v1

   Sep 14, 2026