In-Memory Caching for Distributed Iterative Computations

195 concepts130 papers

The Disk I/O Tax on Iteration

Traditional distributed data-flow frameworks like Hadoop MapReduce were designed primarily for acyclic, batch data processing. As noted by Shilpa Shukla et al. in Parallelizing ListNet training using spark, these frameworks force intermediate states to be written to persistent storage between processing steps to guarantee fault tolerance. While this model works well for single-pass ETL (Extract, Transform, Load) jobs, it introduces a catastrophic bottleneck for iterative algorithms.

Algorithms such as gradient descent, graph mining, and recursive query evaluation require multiple passes over the same dataset. Under a disk-based model, each iteration incurs a heavy tax: data must be serialized, written to disk, and then reloaded and deserialized in the next step. As Salman Salloum et al. observe in Big data analytics on Apache Spark, and as echoed by Pietro Michiardi et al. in Determining the k in k-means with MapReduce, the time spent on disk access and serialization quickly dwarfs the actual computational time. For instance, Christos Faloutsos highlights in Mining Billion-Node Graphs: Patterns, Generators and Tools that distributed graph mining systems built on MapReduce suffer severely from this intermediate storage bottleneck.

Bypassing Storage via In-Memory Abstractions

The core insight of in-memory iterative processing is simple: keep the data where the CPU can reach it instantly. By utilizing distributed memory abstractions, frameworks can cache datasets in RAM across multiple optimization steps or iterations.

One approach, demonstrated by David Cunningham et al. in M3R: Increased performance for in-memory Hadoop jobs, is to intercept distributed file system calls, redirecting intermediate outputs to a local memory cache instead of persistent storage. This allows subsequent tasks to pull data directly from RAM.

Furthermore, keeping data in memory preserves execution pipelining. As Matthew Perron et al. point out in How I Learned to Stop Worrying and Love Re-optimization, writing intermediate results to disk breaks the continuous flow of data through execution operators. In-memory processing maintains this pipeline, allowing for near-linear speedups in workloads like machine learning training (Parallelizing ListNet training using spark; Mohammad Abu Alsheikh in Mobile Big Data Analytics Using Deep Learning and Apache Spark) and large-scale matrix operations where loading data from disk is the primary bottleneck (Shanshan Wu in Single Pass PCA of Matrix Products).

Shared Mutable State vs. Data-Flow Joins

Beyond merely caching static datasets, iterative algorithms often need to update shared state (e.g., vertex ranks in PageRank or cluster centroids in $k$-means). Traditional data-flow frameworks lack support for shared mutable state, forcing algorithms to emulate updates by performing expensive data joins and network shuffles at every iteration.

To solve this, Russell Power et al. developed Piccolo, as described in Piccolo: Building Fast, Distributed Programs with Partitioned Tables, which provides parallel tasks with direct access to shared, mutable state via partitioned in-memory tables. Eliminating the need to recreate and rejoin data structures at each step drastically reduces data shuffling overhead, yielding massive performance gains over standard data-flow models.

Amortizing Data Movement via Multi-Update Processing

When datasets exceed memory capacity, or when data must be fetched from external storage, the goal shifts to maximizing the utility of every single read operation. Wotao Yin et al. note in Block stochastic gradient iteration for convex and nonconvex optimization that optimization algorithms often waste cycles by fetching fresh data samples for every individual variable update. By contrast, performing multiple computational updates on a block of data while it is already cached in main memory exploits CPU efficiency and amortizes the transfer cost. This principle is also leveraged by Peng Dai 0001 et al. in Partitioned External-Memory Value Iteration, allowing systems to process models orders of magnitude larger than available RAM by maximizing in-memory updates per disk-load.

Caching Intermediate Query and Shuffle States

In multi-stage queries or recurring analytical tasks, the overlap between iterations can be exploited. For example, Chuan Lei et al. in Redoop: Supporting Recurring Queries in Hadoop and Elke A. Rundensteiner et al. in Redoop Infrastructure for Recurring Big Data Queries demonstrate that caching intermediate data at the reduce-input stage can eliminate the network-intensive shuffle process for recurring tasks. By persisting these segments locally or in memory, subsequent iterations or sliding window queries can bypass expensive network data movement entirely. Similarly, Huajun Chen et al. show in SparkRDF: Elastic Discreted RDF Graph Processing Engine With Distributed Memory that caching intermediate query results allows for near real-time processing of complex graph joins.

The Hidden Costs: Memory Pressure and Fault Tolerance

While shifting computation to RAM eliminates I/O bottlenecks, it introduces new systemic challenges. The most prominent is memory pressure. In frameworks that rely on tracking data lineage to provide fault tolerance without writing checkpoints to disk, the lineage graph grows with every iteration. As Khaled Ammar observes in Experimental Analysis of Distributed Graph Systems, this can lead to memory exhaustion or severe performance degradation in long-running graph algorithms.

Furthermore, recursive workloads often exhibit a "long tail" where later iterations produce very few new facts but still incur high overhead if data structures or indexes are not persistently maintained across iterations (Towards Better Understanding of the Performance and Design of Datalog Systems by ZHIWEI FAN et al.).

To achieve fault tolerance without the heavy time and energy penalties of traditional disk checkpointing, researchers like Carlos Pachajoa et al. in How to Make the Preconditioned Conjugate Gradient Method Resilient Against Multiple Node Failures propose storing redundant state information directly in the RAM of neighboring nodes, allowing for exact state reconstruction while keeping runtime penalties minimal.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 123 papers
  2. Version 1 · 2026-10-04 · 62 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_in_memory_iterative_processing_1f3f38f2,
  title = {in-memory iterative processing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/in-memory-iterative-processing/rdr_1f3f38f229494ffe88d783e909ec7ff6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_in_memory_iterative_processing_1f3f38f2_v2,
  title = {in-memory iterative processing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/in-memory-iterative-processing/rdr_1f3f38f229494ffe88d783e909ec7ff6/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake