LearnedKV: Integrating LSM and Learned Index for Superior Performance on SSD

• URL: http://arxiv.org/abs/2406.18892v1
• Date: Thu, 27 Jun 2024 05:08:09 GMT
• Title: LearnedKV: Integrating LSM and Learned Index for Superior Performance on SSD
• Authors: Wenlong Wang, David Hung-Chang Du,
• Abstract summary: We introduce LearnedKV, a novel tiered key-value store that seamlessly integrates a Log-Structured Merge (LSM) tree with a Learned Index. Our results show that LearnedKV outperforms state-of-the-art solutions by up to 1.32x in read requests and 1.31x in write performance.
• Score: 0.6774462529828165
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce LearnedKV, a novel tiered key-value (KV) store that seamlessly integrates a Log-Structured Merge (LSM) tree with a Learned Index. This integration yields superior read and write performance compared to standalone indexing structures on SSDs. Our design capitalizes on the LSM tree's high write/update throughput and the Learned Index's fast read capabilities, enabling each component to leverage its strengths. We analyze the impact of size on LSM tree performance and demonstrate how the tiered Learned Index significantly mitigates the LSM tree's size-related performance degradation, particularly by reducing the intensive I/O operations resulting from re-insertions after Garbage Collection (GC). To maintain rapid read performance for newly inserted keys, we introduce a non-blocking conversion mechanism that efficiently transforms the existing LSM tree into a new Learned Index with minimal overhead during GC. Our experimental results, conducted across diverse workloads, show that LearnedKV outperforms state-of-the-art solutions by up to 1.32x in read requests and 1.31x in write performance.

Related papers

• LSM Trees in Adversarial Environments [0.0]
  We focus on adversarial workloads that lead to a sharp degradation in read performance. Our evaluation shows up to $800%$ increase in the read latency of lookups for popular LSM stores. We implement adversary resilience into two popular LSM stores, LevelDB and RocksDB.
  arXiv  Detail & Related papers  (2025-02-12T22:45:46Z)
• DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees [4.077820670802213]
  DobLIX is a dual-objective learned index specifically designed for Log-Structured Merge(LSM) tree-based key-value stores. We show that DobLIX reduces indexing overhead and improves throughput by 1.19 to 2.21 times compared to state-of-the-art methods within RocksDB.
  arXiv  Detail & Related papers  (2025-02-07T22:48:14Z)
• TreeKV: Smooth Key-Value Cache Compression with Tree Structures [19.06842704338332]
  TreeKV is a training-free method that employs a tree structure for smooth cache compression. It consistently surpasses all baseline models in language modeling tasks on PG19 and OpenWebText2.
  arXiv  Detail & Related papers  (2025-01-09T06:00:27Z)
• CSR:Achieving 1 Bit Key-Value Cache via Sparse Representation [63.65323577445951]
  We propose a novel approach called Cache Sparse Representation (CSR) CSR transforms the dense Key-Value cache tensor into sparse indexes and weights, offering a more memory-efficient representation during LLM inference. Our experiments demonstrate CSR achieves performance comparable to state-of-the-art KV cache quantization algorithms.
  arXiv  Detail & Related papers  (2024-12-16T13:01:53Z)
• Towards Scalable Semantic Representation for Recommendation [65.06144407288127]
  Mixture-of-Codes is proposed to construct semantic IDs based on large language models (LLMs) Our method achieves superior discriminability and dimension robustness scalability, leading to the best scale-up performance in recommendations.
  arXiv  Detail & Related papers  (2024-10-12T15:10:56Z)
• ThinK: Thinner Key Cache by Query-Driven Pruning [63.13363917871414]
  Large Language Models (LLMs) have revolutionized the field of natural language processing, achieving unprecedented performance across a variety of applications. This paper focuses on the long-context scenario, addressing the inefficiencies in KV cache memory consumption during inference. We propose ThinK, a novel query-dependent KV cache pruning method designed to minimize attention weight loss while selectively pruning the least significant channels.
  arXiv  Detail & Related papers  (2024-07-30T17:59:08Z)
• A Thorough Performance Benchmarking on Lightweight Embedding-based Recommender Systems [67.52782366565658]
  State-of-the-art recommender systems (RSs) depend on categorical features, which ecoded by embedding vectors, resulting in excessively large embedding tables. Despite the prosperity of lightweight embedding-based RSs, a wide diversity is seen in evaluation protocols. This study investigates various LERS' performance, efficiency, and cross-task transferability via a thorough benchmarking process.
  arXiv  Detail & Related papers  (2024-06-25T07:45:00Z)
• ChunkAttention: Efficient Self-Attention with Prefix-Aware KV Cache and Two-Phase Partition [3.659659889927316]
  ChunkAttention is a prefix-aware self-attention module for large language models. It can detect matching prompt prefixes across multiple requests and share their key/value tensors in memory at runtime. Experiments show that ChunkAttention can speed up the self-attention kernel by 3.2-4.8$times$ compared to the state-of-the-art implementation.
  arXiv  Detail & Related papers  (2024-02-23T09:29:19Z)
• SubGen: Token Generation in Sublinear Time and Memory [48.35076900702408]
  Large language models (LLMs) have extensive memory requirements for token generation. In this work, we focus on developing an efficient compression technique for the KV cache. We have devised a novel caching method with sublinear complexity, employing online clustering on key tokens and online $ell$ sampling on values. Not only does this algorithm ensure a sublinear memory footprint and sublinear time complexity, but we also establish a tight error bound for our approach.
  arXiv  Detail & Related papers  (2024-02-08T22:17:40Z)
• Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads [16.898360021759487]
  We present RusKey, a key-value store with the following new features. RusKey is a first attempt to orchestrate LSM-tree structures online. New LSM-tree design, named FLSM-tree, for efficient transition between different compaction policies.
  arXiv  Detail & Related papers  (2023-08-14T09:00:58Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  Performance embeddings enable knowledge transfer of performance tuning between applications. We demonstrate this transfer tuning approach on case studies in deep neural networks, dense and sparse linear algebra compositions, and numerical weather prediction stencils.
  arXiv  Detail & Related papers  (2023-03-14T15:51:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.