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

• LServe: Efficient Long-sequence LLM Serving with Unified Sparse Attention [26.54297116028556]
  Large language models (LLMs) have shown remarkable potential in processing long sequences and complex reasoning tasks. We introduce LServe, an efficient system that accelerates long-sequence LLM serving via hybrid sparse attention. On average, LServe accelerates LLM prefilling by up to 2.9x and decoding by 1.3-2.1x over vLLM.
  arXiv  Detail & Related papers  (2025-02-20T18:59:52Z)
• 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)
• 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)
• Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks [21.815661269986425]
  We propose a novel KV cache merging approach, called KVMerger, to achieve adaptive KV cache compression for long-context tasks. Our approach is inspired by the intriguing observation that key states exhibit high similarity at the token level within a single sequence. We conduct extensive experiments to demonstrate the effectiveness of KVMerger for long-context tasks under constrained memory budgets.
  arXiv  Detail & Related papers  (2024-07-11T12:50:42Z)
• 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)
• Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory [14.432536669959218]
  Vector searches on large-scale datasets are critical to modern online services like web search and RAG. We characterize the trade-off of performance and index size in existing SSD-based graph and cluster indexes. We show that vector indexes can achieve optimal performance with orders of magnitude smaller index amplification on a variety of second-tier memory devices.
  arXiv  Detail & Related papers  (2024-05-06T08:38:14Z)
• MemLLM: Finetuning LLMs to Use An Explicit Read-Write Memory [49.96019697955383]
  We introduce MemLLM, a novel method of enhancing knowledge capabilities by integrating a structured and explicit read-and-write memory module. Our experiments indicate that MemLLM enhances performance and interpretability, in language modeling general and in particular. We see MemLLM as an important step towards making LLMs more grounded and factual through memory augmentation.
  arXiv  Detail & Related papers  (2024-04-17T18:13:16Z)
• 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)
• RA-DIT: Retrieval-Augmented Dual Instruction Tuning [90.98423540361946]
  Retrieval-augmented language models (RALMs) improve performance by accessing long-tail and up-to-date knowledge from external data stores. Existing approaches require either expensive retrieval-specific modifications to LM pre-training or use post-hoc integration of the data store that leads to suboptimal performance. We introduce Retrieval-Augmented Dual Instruction Tuning (RA-DIT), a lightweight fine-tuning methodology that provides a third option.
  arXiv  Detail & Related papers  (2023-10-02T17:16:26Z)
• L2MAC: Large Language Model Automatic Computer for Extensive Code Generation [52.81694565226513]
  Transformer-based large language models (LLMs) are constrained by the fixed context window of the underlying transformer architecture. This paper presents L2MAC, the first practical LLM-based general-purpose stored-program automatic computer (von Neumann architecture) framework, for long and consistent output generation.
  arXiv  Detail & Related papers  (2023-10-02T16:55:19Z)
• 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)
• RET-LLM: Towards a General Read-Write Memory for Large Language Models [53.288356721954514]
  RET-LLM is a novel framework that equips large language models with a general write-read memory unit. Inspired by Davidsonian semantics theory, we extract and save knowledge in the form of triplets. Our framework exhibits robust performance in handling temporal-based question answering tasks.
  arXiv  Detail & Related papers  (2023-05-23T17:53:38Z)
• 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)
• NumS: Scalable Array Programming for the Cloud [82.827921577004]
  We present NumS, an array programming library which optimize NumPy-like expressions on task-based distributed systems. This is achieved through a novel scheduler called Load Simulated Hierarchical Scheduling (LSHS) We show that LSHS enhances performance on Ray by decreasing network load by a factor of 2x, requiring 4x less memory, and reducing execution time by 10x on the logistic regression problem.
  arXiv  Detail & Related papers  (2022-06-28T20:13:40Z)
• From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees [1.9003569830436575]
  BOURBON is a log-structured merge (LSM) tree that utilizes machine learning to provide fast lookups. We show that BOURBON improves lookup performance by 1.23x-1.78x as compared to state-of-the-art production LSMs.
  arXiv  Detail & Related papers  (2020-05-28T18:05:46Z)

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.