PaperlayerView exact revision on arXiv

Source-linked AI summary

RECIPE : Converting Concurrent DRAM Indexes to Persistent-Memory Indexes

Se Kwon Lee, Jayashree Mohan, Sanidhya Kashyap, Taesoo Kim, Vijay Chidambaram

arXiv:1909.13670v4cs.DCcs.DBcs.DS

TL;DR

Building crash-consistent PM indexes from scratch is difficult and can introduce subtle recovery bugs. Recipe converts compatible concurrent DRAM indexes using conditions and persistence actions, requiring small code changes; five converted indexes achieved up to 5.2× better performance than hand-crafted PM indexes on multi-threaded workloads.

  • Problem

    Designing PM indexes that provide high performance and concurrency while recovering correctly from crashes is difficult and has led to subtle bugs.

  • Method

    Recipe identifies DRAM indexes meeting three conditions and applies corresponding conversion actions to make them persistent and crash-consistent.

  • Results

    Up to 5.2×: Recipe-converted PM indexes outperformed state-of-the-art hand-crafted PM indexes on multi-threaded YCSB workloads.

  • Takeaways & Limitations

    Five indexes using different data structures were converted with less than 200 LOC, or 1–9% of the core codebase.

  • Takeaways & Limitations

    Recipe applies only to DRAM indexes satisfying one of its three conditions and excludes indexes with blocking reads or version-based retry.

Abstract

from arXiv · show

We present Recipe, a principled approach for converting concurrent DRAM indexes into crash-consistent indexes for persistent memory (PM). The main insight behind Recipe is that isolation provided by a certain class of concurrent in-memory indexes can be translated with small changes to crash-consistency when the same index is used in PM. We present a set of conditions that enable the identification of this class of DRAM indexes, and the actions to be taken to convert each index to be persistent. Based on these conditions and conversion actions, we modify five different DRAM indexes based on B+ trees, tries, radix trees, and hash tables to their crash-consistent PM counterparts. The effort involved in this conversion is minimal, requiring 30-200 lines of code. We evaluated the converted PM indexes on Intel DC Persistent Memory, and found that they outperform state-of-the-art, hand-crafted PM indexes in multi-threaded workloads by up-to 5.2x. For example, we built P-CLHT, our PM implementation of the CLHT hash table by modifying only 30 LOC. When running YCSB workloads, P-CLHT performs up to 2.4x better than Cacheline-Conscious Extendible Hashing (CCEH), the state-of-the-art PM hash table.

1 Introduction

Recipe converts compatible concurrent DRAM indexes into crash-consistent PM indexes by translating existing isolation mechanisms into persistence actions. Five conversions required only 1–9% core-code changes and outperformed hand-crafted PM indexes by up to 5.2×.

  • Motivation: Designing PM indexes from scratch is challenging because they must combine performance, concurrency, and correct crash recovery.This complexity has produced previously unknown data-loss and crash-recovery bugs in FAST & FAIR and CCEH.
  • Conversions: Five indexes spanning hash tables, tries, B+ trees, radix trees, and combined tries/B+ trees were converted with less than 200 LOC, or 1–9% of core code.The converted indexes were ART, HOT, BwTree, CLHT, and Masstree; Masstree was the most complicated conversion.
  • Recipe insight: Recipe identifies DRAM indexes whose isolation and inconsistency-handling behavior can support crash recovery after conversion.The approach adds ordered stores, fences, and cache-line flushes rather than new crash-recovery algorithms.
  • Evaluation: Up to 5.2×: converted PM indexes outperformed state-of-the-art hand-crafted PM indexes on multi-threaded YCSB workloads.The gains are attributed to the source DRAM indexes’ concurrency and cache-efficiency optimizations, which matter more under PM’s high read latency.
  • Limitations: Recipe requires compatible DRAM synchronization behavior and assumes reinitialized locks, garbage collection, and correctness of the source index.It cannot be applied to indexes with blocking reads or non-blocking reads that use version-based retry.

2 Background

DRAM indexes support key-value operations and concurrent access, while PM indexes add persistence and crash-recovery requirements. Non-blocking synchronization improves parallelism but requires careful ordering and inconsistency handling.

  • Index interfaces: DRAM indexes provide insert, update, lookup, range-query, and delete operations for efficient data access in storage systems.Lookup returns a key’s associated value, while range queries return key-value pairs within a specified key range.
  • Index structures: Structural modification operations preserve data-structure invariants or performance, including B-tree splits and merges and hash-table rehashing.These operations are internal to the data structure rather than part of its external interface.
  • Concurrency and isolation: Concurrent DRAM indexes use isolation so concurrent updates produce a state corresponding to some sequential order and reads remain correct.Blocking locks serialize access, whereas reader-writer locks allow shared readers but writers contend on one lock.
  • Concurrency and isolation: Non-blocking operations use carefully ordered loads and stores, often with memory fences, to provide progress without mutual exclusion.Lock-free operations guarantee that some operation finishes after finitely many steps; wait-free operations additionally guarantee this for every thread.
  • Concurrency and isolation: High contention can reduce non-blocking performance and lead to starvation, so many indexes combine non-blocking reads with blocking, lock-protected writes.Interrupted lock-free writes may need to retry when shared state changes.
  • Persistent memory: Persistent memory combines storage-like persistence with DRAM-like access, but cache lines may reach persistent media in an arbitrary order.PM indexes therefore require ordered stores, fences, and cache-line flushes to recover correctly after power loss or kernel crashes.
  • Persistent memory: PM’s larger capacity and immediate post-crash availability motivate PM indexes, avoiding reconstruction of large DRAM indexes that can take minutes or hours.PM indexes can therefore be larger than DRAM-only indexes while remaining close to DRAM latency.

3 Motivation

Existing hand-crafted PM indexes are difficult to reason about under concurrent writes and crashes, and the investigation uncovered design and implementation bugs that can lose data or degrade performance.

  • FAST & FAIR: Concurrent writes in FAST & FAIR could lose a successfully written key because a thread inserted into the wrong node after a concurrent split.
  • FAST & FAIR: Consecutive crashes during FAST & FAIR split and merge operations caused keys in the right node to be lost despite the intended recovery design.
  • FAST & FAIR: Repeated crashes during FAST & FAIR splits can transform the recovered B+ tree into a linked list, causing poor read and write performance.
  • The investigation motivates principled PM-index design and systematic testing of crash recovery.
  • CCEH: CCEH contains directory-doubling and crash-recovery bugs that can make insertions or recovery loop infinitely.
  • Ad-hoc concurrent, crash-consistent PM index designs are hard to reason about and can lead to bugs.

4 The Recipe Approach

Recipe converts a suitable concurrent DRAM index into a crash-consistent PM index by connecting read/write isolation with crash consistency and applying condition-specific persistence actions. Its scope is restricted to indexes satisfying one of three conditions, with actions ranging from persistence ordering to explicit helping.

  • Recipe converts a specific class of concurrent DRAM indexes into crash-consistent PM counterparts while preserving the source index’s correctness and scalability.
  • Recipe classifies eligible DRAM indexes into three condition-and-action categories for conversion.
  • Overall Intuition: The approach relies on non-blocking reads tolerating inconsistencies and writes fixing them, reducing the need for separate crash-recovery algorithms.
  • Assumptions and Limitations: Recipe assumes nonpersistent locks are reinitialized after crashes, unreachable PM objects are garbage-collected, and the DRAM index handles concurrent writes correctly.
  • Assumptions and Limitations: Recipe excludes indexes with blocking reads or non-blocking reads that retry after detecting inconsistencies.
  • Condition #1: For single-atomic-store updates, add cache-line flushes and memory fences after stores so the update reaches PM in order.
  • Condition #3: For indexes lacking helpers, add explicit recovery logic that identifies and finishes interrupted writes before subsequent writes proceed.
  • Condition #2: For ordered non-blocking writes, reads and writes tolerate inconsistencies while helping mechanisms complete interrupted operations; persistence instructions follow loads and stores.

5 Testing Crash Recovery of PM Indexes

Recipe introduces crash-recovery testing that injects failures after atomic stores and separately checks consistency and durability of the converted PM indexes.

  • Recipe’s crash-recovery methodology tests both return to a consistent state and preservation of data successfully persisted before a crash.
  • The method simulates crashes after atomic stores because PM-index operations usually contain only a small number of such stores.
  • Testing consistency: Consistency testing probabilistically crashes insertions or structural modifications, then performs recovery, reads, and writes to validate subsequent behavior.
  • Testing durability: Durability testing traces allocations, stores, and flushes, then verifies that every dirtied cache line is persisted to PM.
  • Table 2 categorizes converted DRAM indexes by conversion category and synchronization properties.

6 Case Studies

Recipe converts diverse concurrent DRAM indexes by preserving their atomic update mechanisms and adding persistence ordering or recovery where needed. The case studies cover HOT, CLHT, BwTree, ART, and Masstree with index-specific changes.

  • Trie: Height Optimized Trie (HOT): HOT’s atomic pointer-swap updates require ordered stores and flushes; P-HOT adds 38 LOC, under 2% of its 2K-line core.HOT’s copy-on-write updates install changes through one parent-pointer swap.
  • Hash Table: Cache-Line Hash Table (CLHT): CLHT’s inserts, deletes, and rehashing use single atomic stores; P-CLHT adds flushes and fences with 30 LOC.Common-case non-SMOs require one cache-line flush per update, excluding rehashing.
  • B+ Tree: BwTree: BwTree non-SMOs use a single mapping-table CAS, while SMOs use helper-based recovery; P-BwTree adds persistence operations with 85 LOC.Non-SMO flushing occurs only after a successful CAS, whereas SMOs flush after node and mapping-table stores and loads.
  • Radix Tree: Adaptive Radix Tree (ART): P-ART adds write-path crash detection and recovery, persisting corrected prefixes after try-lock acquisition, with 52 LOC added to ART.The converted write path detects inconsistencies during node traversal and recalculates the correct prefix.
  • Hybrid Index: Masstree: Masstree’s SMO recovery replays node splitting after detected crashes, completing splits or undoing merges to restore consistency.Its SMOs fit Condition #3 because reads remain consistent while writers lack an inherent repair mechanism.

7 Evaluation

Recipe-converted indexes were evaluated against hand-crafted persistent-memory indexes using multi-threaded YCSB workloads on Intel Optane DC Persistent Memory. Results favored converted indexes overall, while workload, key type, and data structure affected the comparison.

  • Ordered indexes: P-ART outperforms FAST & FAIR by up to 1.6× on write-heavy workloads with integer keys.FAST’s in-place sorting causes more cache-line flushes than P-ART.
  • Ordered indexes: P-HOT outperforms FAST & FAIR by 1.5× on read-intensive integer-key workloads and incurs 3× lower LLC misses.Trie-based search paths avoid full-key comparisons in internal nodes.
  • Ordered indexes: FAST & FAIR outperforms all other indexes in range scans because B+ trees pack keys compactly and prefix tries require extensive traversals.For string keys, B+ tree and FAST & FAIR performance drops more sharply because of string comparisons and pointer dereferences.
  • Ordered indexes: B+ tree cache inefficiency produces 3.2−5.2× worse string-key performance than P-HOT, while Masstree performs better than its B+ tree counterparts across all workloads.Masstree combines trie-based key comparison with prefetching, reduced tree depth, and cache-conscious layout.
  • Unordered indexes: P-CLHT outperforms CCEH by up to 2.4×, although it is 2× worse on concurrent-insert-only workloads because globally locked rehashing throttles concurrency.When rehashing is absent, P-CLHT requires only one clwb per insert, whereas CCEH performs segment splits and copy-on-write.
  • Overall results: Recipe-converted indexes outperform state-of-the-art hand-crafted PM indexes by up to 5.2× on multi-threaded YCSB workloads.The reported gains are associated with cache efficiency, concurrency, fewer cache misses, and up to 2× fewer cache-line flushes for P-ART than FAST & FAIR.
  • Crash-recovery testing: All Recipe-converted indexes passed crash-recovery testing, while FAST & FAIR and CCEH exhibited crash-consistency bugs and durability issues.FAST & FAIR could lose data after consecutive crashes during node split and merge; CCEH could stall during directory doubling.

8 Discussion

Recipe’s optimizations and automation have practical boundaries. Flush and fence optimization depends on index-specific implementations, while automatic conversion must handle varied implementations of equivalent atomic steps.

  • Optimization: Flush and fence optimizations such as persist buffering and coalescing are implementation-dependent and must be identified by the developer.Recipe inserts flush and fence operations after each store before these optimizations are applied.
  • Automation: Automating conversion is difficult because identical logical atomic steps may be implemented through different C++ atomic or pointer-assignment patterns.Condition #1 and #2 conversions otherwise require cache-line flushes and memory fences after every store.

9 Related Work

Related work connects crash recovery with memory consistency, proposes alternative conversion mechanisms, develops concurrent PM indexes, automates transactional persistence, and tests PM applications. Recipe distinguishes itself by providing practical index conversions through reuse of mature DRAM designs.

  • Isolation and crash recovery: Memory Persistency, Durable Linearizability, and Recoverable Linearizability relate crash recovery to memory consistency but primarily provide model semantics rather than practical index structures.These works establish theoretical relationships with non-blocking synchronization.
  • Isolation and crash recovery: TSP proposes converting non-blocking indexes using Recovery Observer and Flush-on-Failure, whereas Recipe avoids additional hardware support and kernel modifications.Recipe extends the broad connection toward concurrent crash-consistent PM indexes.
  • Concurrent persistent indexes: Only three of fifteen PM indexes proposed in the prior five years had open-source concurrent implementations: FAST & FAIR, CCEH, and Level Hashing.Recipe is presented as complementary to these concurrent PM-index efforts.
  • Concurrent persistent indexes: Recipe reuses decades of concurrent in-memory-index research without modifying the underlying DRAM index design.Its approach is characterized as more principled than designing each concurrent PM index independently.
  • Transactional PM systems: Transactional PM systems persist updates at critical-section boundaries but may add persistent logging, cache-line flushes, and startup log-replay costs.The cited systems include Atlas, JUSTDO, NVThreads, and iDO.
  • Crash-consistency testing: Existing PM testing frameworks use random or exhaustive crash-state construction, while Recipe’s strategy exploits ordered atomic steps in index operations.The cited frameworks include Yat, Intel PM-Inspector, and pmreorder.

10 Conclusion

Recipe provides conditions and conversion actions for turning concurrent in-memory indexes into persistent indexes, and its five converted indexes outperform hand-crafted PM indexes by as much as 5.2× on Intel DC Persistent Memory.

  • Conclusion: Recipe provides three conditions and corresponding conversion actions for identifying DRAM indexes that can be converted to persistent memory.The approach was applied to five indexes based on different data structures.
  • Conclusion: The five Recipe-converted indexes outperform state-of-the-art hand-crafted PM indexes by as much as 5.2× on Intel DC Persistent Memory.The converted indexes are publicly available in the RECIPE repository.
Loading 1909.13670v4…