AppStreamer: Reducing Storage Requirements of Mobile Games through Predictive Streaming

Nawanol Theera-Ampornpunt, Shikhar Suryavansh, Sameer Manchanda, Rajesh K. Panta, Kaustubh Joshi, Mostafa H. Ammar, Mung Chiang, Saurabh Bagchi

TL;DR

AppStreamer is a system-level middleware for Android that slashes the storage footprint of heavy mobile games by over 85% through predictive asset streaming. By modeling file access patterns with a Continuous-Time Markov Chain (CTMC), it speculatively prefetches data blocks from the cloud, maintaining a local-storage-like user experience without requiring access to an application's source code.

What Problem Does This Paper Address?

Mobile games are caught in a "storage crunch." As graphics and content complexity explode, games like Dead Effect 2 easily exceed 1 GB, while smartphone internal storage growth remains relatively slow. Users frequently uninstall apps just to make room for new ones.

Existing solutions fall short: microSD cards are often slower than internal storage and unsupported by many flagship devices. "Cloud Gaming" (streaming rendered video) solves the storage problem but introduces massive bandwidth overhead and intolerable latency for interactive titles. Traditional prefetching techniques are often too coarse-grained or require developers to manually insert hints into their code—a non-starter for the vast majority of closed-source commercial games. AppStreamer aims to provide the storage benefits of the cloud with the low latency of local execution, all while remaining agnostic to the specific game being played.

Methods

AppStreamer operates at the Android virtual file system (VFS) layer, intercepting vfs_read calls. This allows it to work with any app without modification. The system functions in two phases:

  1. Offline Training: The system collects file access traces from multiple users. To make the prediction space manageable, it doesn't track individual 4 KB blocks. Instead, it groups blocks into Partitions (accessed close in time), merges similar ones into Equivalent Partitions, and finally identifies Superblocks—intersections of partitions that appear across different users and playstyles.
  2. Online Prediction: As a user plays, AppStreamer uses a Continuous-Time Markov Chain (CTMC) where each state is a Superblock. The model predicts which Superblocks will be needed in the near future (the "lookahead" period).
Figure 1. Overview diagram of AppStreamer, showing the components on the mobile device and the cloud, as well as the offline training and online phases.

A key innovation is the Data Block Fetcher, which manages two queues: a low-priority background thread for predicted blocks and a high-priority "urgent" path for cache misses. The system even adjusts its lookahead window dynamically based on how fast a specific user is progressing through the game.

Figure 3. Grouping of blocks during training. Concepts of Partition and Equivalent Partition within a single trace and Superblock across multiple traces.

Datasets

The authors evaluated AppStreamer using two popular, resource-intensive Android games:

  • Dead Effect 2: A 3D first-person shooter (FPS) representing high-action, linear gameplay. The OBB resource file is ~1.1 GB.
  • Fire Emblem Heroes: A 2D turn-based strategy RPG representing non-linear gameplay with multiple modes (story, training, PvP). It consists of ~5,200 individual files totaling ~577 MB.

Traces were collected from multiple players to capture diverse playing styles and paths for the offline training phase.

Key Insights and Ideas

  • Superblocks as States: The "aha moment" here is that predicting individual 4 KB blocks is computationally infeasible (billions of transitions). By grouping blocks that are naturally accessed together into Superblocks, the authors reduced the state space enough to run the Markov model in real-time on a mobile CPU.
  • Temporal Awareness: Unlike standard Markov chains, the CTMC captures duration. Knowing when a block will be needed allows the system to prioritize bandwidth and avoid fetching data too early (wasting cache space) or too late (causing stalls).
  • Source-Agnosticism: By implementing the logic at the VFS layer, the authors proved you can achieve high-accuracy prefetching without knowing anything about the game's internal logic or having access to its source code.
  • Bandwidth Efficiency: Streaming raw assets (textures, audio) is far more efficient than streaming rendered video. AppStreamer uses ~77% less bandwidth than traditional cloud gaming platforms.

Key Results

AppStreamer achieved massive storage savings while maintaining high user satisfaction:

  • Storage Reduction: Permanent storage requirements dropped by 87% for Dead Effect 2 and 86% for Fire Emblem Heroes.
  • User Experience: In user studies, 70% to 88% of participants rated the experience as identical to playing with all files stored locally.
  • Performance: The system achieved a cache hit rate of 97-99%. For Dead Effect 2, the average total delay added by the network was a negligible 0.15 seconds over 28 minutes of gameplay.
  • Comparison: Compared to cloud gaming (GaminAnywhere), AppStreamer reduced latency by 98% and bandwidth usage by 4.3x.
Figure 4. Storage requirements for Dead Effect 2

Limitations and Future Work

  • Trace Dependency: The system relies on having a diverse set of initial traces. If a user takes a path never seen in training, the predictor may fail, leading to "urgent" fetches and potential stalls.
  • Network Sensitivity: While it handles average LTE speeds well, performance degrades significantly on very slow connections (e.g., below 10 Mbps).
  • Write Operations: The current design focuses on read-only assets. User-specific save data and configuration files are still stored locally, though these are typically small.
  • Future Directions: The authors suggest exploring a "middle ground" where some computation (like heavy shader rendering) is offloaded to the cloud alongside the asset streaming to further assist low-end devices.

Summary updated

Abstract

Storage has become a constrained resource on smartphones. Gaming is a popular activity on mobile devices and the explosive growth in the number of games coupled with their growing size contributes to the storage crunch. Even where storage is plentiful, it takes a long time to download and install a heavy app before it can be launched. This paper presents AppStreamer, a novel technique for reducing the storage requirements or startup delay of mobile games, and heavy mobile apps in general. AppStreamer is based on the intuition that most apps do not need the entirety of its files (images, audio and video clips, etc.) at any one time. AppStreamer can, therefore, keep only a small part of the files on the device, akin to a "cache", and download the remainder from a cloud storage server or a nearby edge server when it predicts that the app will need them in the near future. AppStreamer continuously predicts file blocks for the near future as the user uses the app, and fetches them from the storage server before the user sees a stall due to missing resources. We implement AppStreamer at the Android file system layer. This ensures that the apps require no source code or modification, and the approach generalizes across apps. We evaluate AppStreamer using two popular games: Dead Effect 2, a 3D first-person shooter, and Fire Emblem Heroes, a 2D turn-based strategy role-playing game. Through a user study, 75% and 87% of the users respectively find that AppStreamer provides the same quality of user experience as the baseline where all files are stored on the device. AppStreamer cuts down the storage requirement by 87% for Dead Effect 2 and 86% for Fire Emblem Heroes.
BibTeX
@misc{theeraampornpunt2020appstreamer,
  author = {Nawanol Theera-Ampornpunt and Shikhar Suryavansh and Sameer Manchanda and Rajesh K. Panta and Kaustubh Joshi and Mostafa H. Ammar and Mung Chiang and Saurabh Bagchi},
  title = {{AppStreamer: Reducing Storage Requirements of Mobile Games through Predictive Streaming}},
  year = {2020},
  eprint = {2001.08169},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.08169},
}
Figure