proomt

Search

Search posts, papers, and topics

Hall of Fame

Hall of FamePatrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil199688 min readpaperintermediate

The Log-Structured Merge-Tree (LSM-Tree)

Read on umb.edu

Summary

The Log-Structured Merge-Tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for files with high insert rates, like history tables or logs. It defers and batches index changes, cascading them from memory to disk components, significantly reducing disk I/O compared to B-trees for writes.

  • LSM-trees reduce disk I/O for high-volume inserts by deferring and batching index changes.
  • Changes cascade from an in-memory component to one or more disk components, similar to merge sort.
  • All index values remain accessible during the merge process, either in memory or on disk.
  • Less efficient for immediate, random read queries compared to traditional B-trees.

Engineers building high-throughput data systems with write-heavy workloads, like databases or logging services, should understand LSM-trees to optimize indexing costs and performance.

9/10
storageperformancedatabasesindexingdata structureslsm tree

Related reading

  1. The Design and Implementation of a Log-Structured File System

    The paper introduces a log‑structured file system (LFS) that writes all data sequentially to a log and uses a segment cleaner to reclaim space. In the Sprite LFS prototype, write throughput reaches 65‑75 % of raw disk bandwidth, an order of magnitude faster than Unix for small files, while reads remain comparable.

    Hall of Fameberkeley.edu53 minpaper

  2. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging

    ARIES is a transaction recovery method using write-ahead logging (WAL) that supports fine-granularity locking and partial rollbacks. It introduces the "repeating history" paradigm to redo all missing updates before performing rollbacks of loser transactions during system restart, using Log Sequence Numbers (LSNs) on pages.

    Hall of Famestanford.edu155 minpaper

  3. Database Branching: A Developer's Guide to Git-Style Workflows

    Database branching uses copy‑on‑write to give developers, CI jobs, and AI agents isolated database snapshots without full copies. Branches share unchanged data, store only deltas, and are disposable, enabling production‑like testing, per‑PR isolation, safe experimentation, and rapid cleanup. Safe operation requires protecting parent branches, using mock data, TTLs, and treating migrations as the…

    Databricksdatabricks.com9 min

  4. CISA's Logging Reference Architecture for OMB M-26-14: What federal agencies should do next

    CISA’s Logging Reference Architecture translates OMB M‑26‑14 requirements into eight concrete shifts, from searchable storage tiers to schema‑first design and continuous validation. Agencies should use Elastic’s tools to build a heterogeneous, schema‑first logging architecture and file a plan by 18 Nov 2026 to meet the mandated maturity milestones.

    Elasticelastic.co11 min

  5. Microsoft Open-Sources TauGrid to Simplify AI Workload Management on Kubernetes

    Microsoft open‑sourced TauGrid, a Helm‑installable platform that bundles Kueue, KubeRay and other components to schedule, monitor and checkpoint AI workloads on GPU‑enabled Kubernetes clusters. Engineers define jobs in a simple `tau.yaml`, and TauGrid handles queuing, health checks, and observability, simplifying AI workload management.

    InfoQinfoq.com2 min

  6. How LLMs Can Find a Needle in a Haystack

    The post explains how retrieval‑augmented generation (RAG) lets LLM‑based assistants answer questions from private corpora. It covers chunking documents into passages, embedding queries and chunks, similarity metrics, and the trade‑offs of different vector indexes (flat, IVF, HNSW). The focus is on practical design choices rather than new research.

    ByteByteGobytebytego.com12 min