Real-Time Search Indexing: LSM-Trees, Write-Ahead Logs & Segment Merging

Early generation search engines operated strictly as batch systems: new web pages and document modifications were queued throughout the day, indexed in bulk overnight via MapReduce jobs, and swapped into production during maintenance windows. In modern digital platforms, however, users demand Near-Real-Time (NRT) indexing—new articles, breaking news, inventory updates, and social posts must become searchable within one second of creation. Achieving sub-second indexing without locking search query concurrency requires adopting Log-Structured Merge-Tree (LSM-Tree) architectural principles: buffer incoming writes in memory, persist sequential Write-Ahead Logs (WAL) for durability, and continuously merge immutable index segments in the background.

1. The Near-Real-Time Ingestion Architecture

Modern real-time search architectures coordinate document ingestion through three distinct layers:

2. Search Refresh vs. Flush vs. Fsync

In distributed search engines, understanding the distinction between a refresh and a flush is critical for optimizing write throughput and durability:

• Refresh (Making Data Searchable): The in-memory buffer writes its data into a new small index segment residing in the operating system's filesystem page cache. An updated searcher point-in-time handle is opened. The data is now immediately visible to search queries, typically within 1 second, without executing an expensive disk fsync.
• Flush (Making Data Durable): A flush writes all memory segments to disk, triggers a physical kernel fsync() on all segment files, commits a new index generation marker (commit point), and truncates the transactional Write-Ahead Log.

3. Segment Merging: TieredMergePolicy Mechanics

Over time, thousands of 1-second refresh cycles produce hundreds of tiny, fragmented index segments. A query traversing 500 small segments experiences severe latency degradation. Background workers continuously execute Segment Merging:

• Tiered Merge Policy: Segments are categorized into logarithmic size tiers (e.g. <10MB, 10–100MB, 100MB–1GB). When a tier accumulates more than a configured threshold of segments (e.g. 10 segments), a background merge worker merges them into a single consolidated, optimized segment.
• Purging Tombstones: When documents are deleted or updated, a bitset marks the old Document ID as deleted. During segment merging, deleted documents are omitted from the newly written combined posting lists, reclaiming disk storage and defragmenting the index.

4. Write Amplification & Merge Throttling Invariants

While background segment merges are essential for query latency and tombstone collection, aggressive merges trigger severe write amplification: a single byte of ingested document data may be rewritten 10 to 30 times as it graduates through successive size tiers. Production search clusters enforce strict I/O throttling:

• I/O Throttling via Token Buckets: Merge threads are bounded by bandwidth limiters (e.g. 50MB/sec to 100MB/sec on NVMe storage) using token-bucket rate limiters. This prevents background compaction from starving incoming write requests and saturating storage controller queues.
• Adaptive Merge Scheduling: When indexing bursts overwhelm disk write capacity, the storage engine detects rising merge queue depth and dynamically throttles ingress indexing threads, prioritizing merge completion over raw ingestion to safeguard cluster health.
• Force-Merge Optimization: Once an index transitions from active write workloads to read-only historical archives (such as daily log partitions), administrators execute an explicit force-merge down to a single segment (max_num_segments = 1), eliminating tombstone overhead and maximizing query cache locality.

5. Production Implementation: LSM Memory Buffer & Segment Consolidator

The following TypeScript blueprint demonstrates an in-memory Near-Real-Time index buffer that batches documents and flushes immutable segments to a simulated storage layer:

export interface IndexSegment {
  segmentId: string;
  docCount: number;
  postings: Map<string, number[]>;
}

export class NRTIndexManager {
  private memoryBuffer: Map<string, number[]> = new Map();
  private bufferedDocCount: number = 0;
  private segments: IndexSegment[] = [];
  private maxBufferSize: number;

  constructor(maxBufferSize: number = 1000) {
    this.maxBufferSize = maxBufferSize;
  }

  // Add document to in-memory write buffer
  addDocument(docId: number, tokens: string[]): void {
    for (const token of tokens) {
      if (!this.memoryBuffer.has(token)) {
        this.memoryBuffer.set(token, []);
      }
      this.memoryBuffer.get(token)!.push(docId);
    }
    this.bufferedDocCount++;

    if (this.bufferedDocCount >= this.maxBufferSize) {
      this.flushToSegment();
    }
  }

  // Flush memory buffer into a new immutable segment
  flushToSegment(): void {
    if (this.bufferedDocCount === 0) return;

    const segment: IndexSegment = {
      segmentId: `seg_${Date.now()}_${Math.random().toString(36).substring(7)}`,
      docCount: this.bufferedDocCount,
      postings: new Map(this.memoryBuffer)
    };

    this.segments.push(segment);
    this.memoryBuffer.clear();
    this.bufferedDocCount = 0;

    // Trigger merge if small segments accumulate
    if (this.segments.length >= 5) {
      this.mergeSegments();
    }
  }

  // Consolidate segments into a single optimized segment
  private mergeSegments(): void {
    const mergedPostings = new Map<string, number[]>();
    let totalDocs = 0;

    for (const seg of this.segments) {
      totalDocs += seg.docCount;
      for (const [term, docIds] of seg.postings.entries()) {
        if (!mergedPostings.has(term)) {
          mergedPostings.set(term, []);
        }
        mergedPostings.get(term)!.push(...docIds);
      }
    }

    // Sort posting lists ascending
    for (const [term, ids] of mergedPostings.entries()) {
      ids.sort((a, b) => a - b);
    }

    this.segments = [{
      segmentId: `merged_${Date.now()}`,
      docCount: totalDocs,
      postings: mergedPostings
    }];
  }
}