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:
- 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.
- 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).
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.
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.
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