PaperlayerView exact revision on arXiv

Source-linked AI summary

LSM-based Storage Techniques: A Survey

Chen Luo, Michael J. Carey

arXiv:1812.07527v3cs.DB

TL;DR

LSM-trees have attracted extensive improvement efforts because their widespread adoption creates important design trade-offs. This paper surveys those efforts through a general taxonomy, detailed analysis, representative system reviews, and future research directions. It concludes by identifying state-of-the-art techniques, trade-offs, and open opportunities for LSM-based storage.

  • Problem

    LSM-tree improvements span many techniques and trade-offs, creating a need for a structured account of the state of LSM-based storage research.

  • Method

    The paper develops a taxonomy, surveys improvement techniques and their trade-offs, reviews representative open-source NoSQL systems, and derives future research directions.

  • Results

    The survey classifies existing improvements, discusses their strengths and trade-offs, reviews representative LSM-based systems, and identifies future research directions.

  • Takeaways & Limitations

    The taxonomy and system survey provide a guide to state-of-the-art LSM-based storage techniques for researchers, practitioners, and users.

  • Takeaways & Limitations

    Performance stability remains insufficiently addressed because bLSM bounds memory-write latency but end-to-end write latency can still vary due to queuing.

Abstract

from arXiv · show

Recently, the Log-Structured Merge-tree (LSM-tree) has been widely adopted for use in the storage layer of modern NoSQL systems. Because of this, there have been a large number of research efforts, from both the database community and the operating systems community, that try to improve various aspects of LSM-trees. In this paper, we provide a survey of recent research efforts on LSM-trees so that readers can learn the state-of-the-art in LSM-based storage techniques. We provide a general taxonomy to classify the literature of LSM-trees, survey the efforts in detail, and discuss their strengths and trade-offs. We further survey several representative LSM-based open-source NoSQL systems and discuss some potential future research directions resulting from the survey.

1 Introduction

LSM-trees are widely used in modern NoSQL storage because out-of-place, sequential writes provide strong write performance and other systems benefits. This survey organizes recent improvements, representative systems, trade-offs, and future directions.

  • Motivation: LSM-trees buffer writes in memory, then flush and merge them to disk using sequential I/Os.This differs from traditional in-place update structures.
  • Motivation: This design provides superior write performance, high space utilization, tunability, and simpler concurrency control and recovery.
  • Survey scope: The survey classifies LSM-tree improvements by optimization target and discusses their strengths and trade-offs.
  • Survey scope: It also surveys five representative open-source LSM-based NoSQL systems and identifies future research directions.

2 LSM-tree Basics

LSM-trees use out-of-place updates and integrated merging to balance write, read, and space costs. Their structure, optimizations, concurrency mechanisms, and merge policies determine these trade-offs.

  • Background: Out-of-place updates improve writes through sequential I/O but can reduce read performance because records may occupy multiple locations.
  • History: The original LSM-tree integrates merging into a hierarchy of memory and disk B+-tree components, providing high write performance with bounded query and space costs.
  • Optimizations: Range partitioning divides disk components into SSTables, limiting merge size and temporary space while merging only overlapping key ranges.
  • Optimizations: Vertical grouping makes overlapping SSTables disjoint after merging, allowing a point lookup to examine only one resulting SSTable.
  • Concurrency Control and Recovery: Concurrent flushes and merges require synchronized component metadata, while reference counters prevent deletion of components still being accessed.
  • Cost Analysis: Leveling favors query performance and space utilization, whereas tiering favors writes but worsens query performance and space utilization by a factor of T.

3 LSM-tree Improvements

The paper presents a taxonomy for classifying LSM-tree improvements and surveys the literature according to the aspects each technique attempts to optimize.

  • 3 LSM-tree Improvements: The taxonomy organizes existing research efforts by the specific aspects of LSM-trees they aim to optimize.
  • 3 LSM-tree Improvements: The survey then examines the classified LSM-tree literature in depth.
  • 3 LSM-tree Improvements: This structure is intended to support systematic comparison of proposed LSM-tree improvements.

3.1 A Taxonomy of LSM-tree Improvements

The survey organizes LSM-tree improvements around drawbacks of the basic design, including write amplification, merge costs, hardware use, special workloads, tuning, and secondary indexing.

  • Write Amplification: High write amplification limits write performance and can reduce SSD lifespan through frequent disk writes.
  • Merge Operations: Merge operations can cause buffer cache misses and write stalls, motivating improvements to merge implementation.
  • Hardware and Special Workloads: LSM-tree research adapts the design for new hardware platforms and special workloads to exploit their distinctive characteristics.
  • Auto-Tuning: Auto-tuning addresses the difficulty of balancing read, write, and space objectives across many configuration knobs.
  • Secondary Indexing: Secondary-indexing research targets efficient maintenance of related indexes while keeping write overhead small.
  • The taxonomy is based on major issues in the basic LSM-tree design and highlights the aspects that existing research seeks to optimize.

3.2 Reducing Write Amplification

Write-amplification research primarily uses tiering and related grouping strategies, while also exploring merge skipping and workload-specific techniques; these approaches involve important trade-offs and evaluation gaps.

  • Most write-amplification improvements use tiering because it writes more efficiently than leveling.
  • Tiering lowers write amplification but worsens query performance and space utilization relative to leveling.
  • Vertical Grouping: WB-tree, LWC-tree, PebblesDB, and dCompaction share partitioned tiering with vertical grouping but differ in workload balancing.
  • Merge Skipping: The skip-tree reduces write cost by pushing entries directly to a higher-level mutable buffer and skipping intermediate merges.
  • Skewed Workloads: TRIAD separates hot and cold keys so obsolete hot-key versions can be discarded without being flushed to disk.
  • Trade-offs and Evaluation: The survey notes that grouping strategies need evaluation and that many studies compare against untuned LevelDB or RocksDB configurations.

3.3 Optimizing Merge Operations

The surveyed merge optimizations target merge speed, cache disruption, and write stalls through page stitching, pipelining, cache-management strategies, and scheduling.

  • Merge-operation improvements address merge performance, buffer cache misses, and write stalls.
  • Merge Performance: VT-tree stitching reuses non-overlapping input pages without rereading and copying them, though it can cause fragmentation.
  • Merge Performance: Pipelined merging overlaps read, merge-sort, and write phases to use CPU and I/O parallelism more effectively.
  • Buffer Cache Misses: Merge completion can trigger buffer cache misses because newly produced components are not cached and indiscriminate caching evicts working pages.
  • Buffer Cache Misses: LSbM-tree delays deletion of old SSTables, searches them during queries, and gradually deletes them according to access frequency without extra merge I/O.
  • Write Stalls: bLSM controls parallel merge progress to limit memory-component write speed and reduce large write stalls, but end-to-end latency can still vary due to queuing.

3.4 Hardware Opportunities

Hardware-oriented LSM research modifies memory management, concurrency, storage-device use, and key-value layout to exploit large memory, multicore systems, SSDs, NVMs, and native storage interfaces.

  • Hardware-focused improvements adapt LSM-tree designs to the distinct capabilities of large memory, multicore systems, SSDs, NVMs, and native storage.
  • Large Memory: FloDB uses a fast hash-table layer over a range-query-friendly skip-list, but mixed writes and range queries can contend and reduce memory utilization.
  • Large Memory: Accordion flushes full mutable memory components into compact immutable components and merges them in memory.
  • Multicore: cLSM organizes components in a concurrent linked list and designs flushes and merges to modify it atomically without blocking queries.
  • SSD and NVM: FD-tree uses fractional cascading and fence pointers to improve query performance on SSD-oriented components.
  • SSD and NVM: WiscKey stores values in an append-only log while the LSM-tree indexes their locations, reducing write cost by merging only keys.
  • SSD and NVM: NoveLSM uses an NVM memory component to avoid stalls when DRAM fills, skips logging on persistent NVM, and searches levels concurrently.
  • Native Storage: NoFTL-KV extracts the flash translation layer from the device into the key-value store to gain direct storage control.

3.5 Handling Special Workloads

The survey reviews LSM-tree improvements tailored to temporal, small, semi-sorted, and append-mostly workloads. These techniques modify metadata organization, merge policies, and indexing structures, but their benefits depend on workload fit.

  • Specialized LSM-tree improvements target temporal, small, semi-sorted, and append-mostly workloads.
  • Temporal data: LHAM attaches disjoint timestamp ranges to components and merges oldest records forward, enabling pruning of irrelevant components for temporal queries.
  • Small data: LSM-trie reduces metadata overhead through hash-prefix SSTable organization, fixed-size buckets, migration metadata, and grouped Bloom-filter I/O.
  • Semi-sorted data: SlimDB combines lower-level tiering with higher-level leveling, multi-level cuckoo filters, and prefix/suffix indexes for semi-sorted data.
  • These optimizations may be useless or inapplicable to general workloads; LSM-trie supports only point lookups, while SlimDB offers limited prefix-based range queries.

3.6 Auto-Tuning

The survey covers auto-tuning methods that optimize LSM-tree parameters, merge policies, Bloom filters, and data placement for particular workloads. These approaches expand the design space, but differ in the aspects they tune and the workload trade-offs they target.

  • Auto-tuning techniques reduce end-user tuning burden through co-tuning or targeted optimization of merge policies, Bloom filters, and data placement.
  • Parameter Tuning: Lim et al. model key distributions to estimate duplicate elimination during merges and tune parameters by minimizing total write cost.
  • Parameter Tuning: Monkey co-tunes merge policy, size ratio, and memory allocation, assigning more Bloom-filter bits to lower levels to optimize workload throughput.
  • Tuning Merge Policies: Dostoevsky combines tiering and leveling through lazy-leveling or hybrid policies, improving write cost while preserving several leveling-like query and space properties.
  • Tuning Merge Policies: ChooseBest and mixed merging use partition overlap and learned size thresholds to balance partitioned and full merges for lower write cost.
  • ElasticBF dynamically adjusts Bloom-filter false-positive rates using data hotness and access frequency, while Mutant places selected SSTables on fast storage under a monetary budget.
  • Lim et al. tune maximum leveling-level sizes, whereas Monkey and follow-up work address a broader LSM-tree design space.

3.7 Secondary Indexing

LSM-based secondary-indexing research targets efficient query processing and index maintenance across diverse workloads. Key techniques include specialized indexes, filters, deferred cleanup, optimized lookups, statistics collection, and distributed indexing.

  • Index Structures: LSM-based secondary indexes store secondary keys with primary keys, then use matching primary keys to fetch records from the primary index.Composite-key and key-list approaches support this pattern.
  • Index Structures: LSII supports exact real-time keyword search by storing significance-, freshness-, and frequency-ordered inverted lists for disk components.A threshold algorithm stops evaluation when unseen results cannot enter the top K.
  • Index Structures: No spatial index structure clearly dominates, while the LSM-based R-tree performs reasonably well for ingestion and queries without extensive tuning.The R-tree also handles point and non-point data well.
  • Index Structures: Filters prune components using minimum and maximum filter-key values and are especially effective for time-correlated workloads with small storage overhead.Evaluations compared range filters, Bloom filters, composite keys, and eager or lazy key lists.
  • Index Maintenance: Secondary-index updates require obsolete-entry cleanup because changing a secondary key prevents the primary-index overwrite mechanism from applying directly.Diff-Index offers synchronous and asynchronous schemes that trade ingestion overhead against index freshness.
  • Index Maintenance: Deferred cleanup methods use queries, primary-index scans, or primary-key indexes to avoid synchronous point lookups, but may require result validation.DELI cannot efficiently support index-only queries, while batched lookup reduces random I/Os most effectively among the evaluated optimizations.
  • Statistics and Distributed Indexing: Statistics collection can be integrated with flush and merge operations, while distributed indexing uses global or local designs and staged partitioning.These techniques extend LSM-based indexing toward cost-based optimization and distributed query processing.
  • Summary: The survey identifies workload-dependent maintenance choices and calls for adaptive mechanisms, alongside LSM-based inverted, spatial, secondary, and distributed indexes.The main maintenance approaches differ in how they clean secondary indexes in the background.

3.8 Discussion of Overall Trade-offs

LSM-tree improvements must balance write performance against query performance, space utilization, supported query types, and implementation complexity. The survey emphasizes exploring this design space to choose workload-appropriate trade-offs.

  • Overall Trade-offs: Most improvements target the leveling policy’s high write amplification, often adopting tiering at the cost of query performance and space utilization.Tiering harms range queries more than point lookups because range queries cannot benefit from Bloom filters.
  • Overall Trade-offs: Skip-tree, TRIAD, and VT-tree improve write performance but introduce non-trivial implementation complexity and additional query or space overhead.Their designs conflict with immutable components, conventional transaction-log interfaces, or Bloom-filter compatibility.
  • Overall Trade-offs: LSM-trie and SlimDB improve performance by limiting range-query support, making them suitable when complete range queries are unnecessary.LSM-trie does not support range queries, while SlimDB supports only a common-prefix form.
  • Overall Trade-offs: Separating keys from values can improve writes but significantly harms range queries and may reduce disk efficiency and space utilization.SSD I/O parallelism can mitigate, but not eliminate, the range-query impact.
  • Overall Trade-offs: Design-space methods seek better trade-offs through level sizing, Bloom-filter memory allocation, and hybrid merge policies.Monkey improves point lookups without negative impact on other metrics, while Dostoevsky combines tiering at lower levels with leveling at the largest level.

4 Representative LSM-based Systems

The survey examines five representative open-source NoSQL systems and their LSM-based storage layers. These systems vary in merge policies, indexing support, partitioning, maintenance, and transaction designs.

  • LevelDB: LevelDB is an embedded key-value storage engine supporting puts, gets, and scans, and it pioneered partitioned leveling.It is intended to support higher-level applications rather than provide a full data-management system.
  • RocksDB: RocksDB extends LevelDB with flexible merge policies, including partitioned leveling, tiering, and FIFO, plus policies for skewed workloads and deletion-heavy components.It also supports rate limiting and read-modify-write operations.
  • HBase: HBase partitions data into regions managed by LSM-trees and supports dynamic region management and several tiering-policy variants.Its exploring policy selects the mergeable sequence with the smallest write cost, and stripping independently merges key-space partitions.
  • HBase: HBase lacks native secondary indexes, but they can be implemented as separate tables storing secondary keys with primary keys through co-processors.This follows the global-index pattern described for HBase.
  • Cassandra: Cassandra uses decentralized LSM-based storage for each data partition and supports tiering, partitioned leveling, date-tiered policies, and lazy local secondary indexes.Its lazy maintenance resembles DELI and avoids some point-lookup overhead.
  • AsterixDB: AsterixDB hash-partitions records across nodes, manages each partition with multiple LSM-based indexes, and uses record-level transactions to keep them consistent.Its generic LSM-ification framework supports B+-trees, R-trees, and inverted indexes.

5 Future Research Directions

The survey identifies evaluation gaps and design opportunities for LSM-trees, including clearer trade-offs among tiering schemes, hybrid merge policies, performance variance, and broader database-engine settings.

  • Thorough Performance Evaluation: Default untuned baselines make it unclear how proposed improvements compare with well-tuned LSM-trees for specific workloads.Many studies also emphasize query performance while neglecting space utilization.
  • Partitioned Tiering Structure: The performance characteristics and trade-offs of horizontal and vertical partitioned tiering schemes remain unclear.These schemes cover virtually all recently proposed tiering-related improvements.
  • Hybrid Merge Policy: Hybrid leveling-and-tiering policies are a promising direction because they can improve write performance with minimal impact on several read and space metrics.The survey reports that hybrid policies can outperform leveling on write performance while minimally affecting point lookups, long range queries, and space amplification.
  • Minimizing Performance Variance: LSM-trees often exhibit large performance variance because in-memory writes are decoupled from expensive background I/Os.bLSM is identified as the only surveyed attempt to minimize write stalls, but it remains limited in scope and target metric.
  • Minimizing Performance Variance: Future mechanisms should address bLSM’s restriction to unpartitioned leveling and its focus on long write latencies rather than overall ingestion-throughput variance.The survey calls for mechanisms that minimize performance variance more broadly.
  • Towards Database Storage Engines: LSM research should expand from single-tree key-value stores to multi-index database storage engines.Suggested directions include adaptive auxiliary-structure maintenance and LSM-aware query optimization.

6 Conclusion

LSM-trees have become widely adopted in modern NoSQL systems because of their storage and write-performance advantages. This paper surveys research improvements, classifies them with a taxonomy, reviews representative systems, and identifies future research directions.

  • LSM-trees are increasingly popular in modern NoSQL systems because they offer superior write performance, high space utilization, immutable on-disk data, and tunability.
  • The survey covers database- and systems-community efforts to improve LSM-trees and classifies them by the aspects they optimize.
  • The paper also reviews representative open-source LSM-based NoSQL systems and identifies future research directions.
Loading 1812.07527v3…