Learning Runtime Parameters in Computer Systems with Delayed Experience Injection

Michael Schaarschmidt, Felix Gessert, Valentin Dalibard, Eiko YonekiarXiv 2016 · arXiv

Abstract

Tuning runtime parameters in cloud databases is notoriously difficult because feedback on system actions is often highly concurrent and delayed. This paper introduces Delayed Experience Injection (DEI) for Deep Reinforcement Learning (DRL), allowing an agent to learn optimal cache expiration times (TTLs) on the fly. By decoupling action execution from reward computation, the DRL agent successfully optimizes per-request parameters in real-time without requiring extensive offline pre-training.

Introduction

Modern cloud database services (DBaaS) handle thousands of concurrent requests per second. To minimize latency, these systems rely heavily on caching, often at the edge. A critical parameter in this architecture is the Time-To-Live (TTL) for a cached query: setting it too short leads to high latency from frequent cache misses, while setting it too long risks serving stale data or wasting cache capacity.

Traditionally, systems use static defaults or analytical models to set TTLs. Deep Reinforcement Learning (DRL) offers a compelling alternative for dynamic parameter tuning. However, standard DRL algorithms assume a sequential Markov Decision Process (MDP) where rewards are immediate. In concurrent systems, an agent might set a TTL for one request and only observe the outcome (e.g., a cache hit or an invalidation) after processing thousands of subsequent requests. This "concurrent delayed credit assignment" problem hinders the application of standard DRL in high-throughput environments.

System Architecture and Delayed Experience Injection

The authors frame TTL estimation as a continuous reinforcement learning problem using Normalized Advantage Functions (NAFs). NAFs are computationally efficient for continuous action spaces as they output both a value function and an advantage term from a single neural network.

To address the asynchronous nature of web servers, the paper introduces Delayed Experience Injection (DEI). The system architecture integrates an RL agent into the request pipeline to observe runtime metrics and manage requests dynamically.

System architecture for RL-based TTL estimation in a CDN/DBaaS environment.

The DEI workflow operates as follows:

  1. Observation: Upon a query arrival, the agent observes the state, including record-level write rates and cache miss rates.
  2. Action: The agent outputs a TTL duration.
  3. Queueing: Instead of waiting for a reward, the system creates an incomplete transition and places it in an "expiration queue," allowing the server to immediately process the next request.
  4. Injection: Once the TTL expires or an invalidation occurs, a background thread computes the reward and the next state, injecting the completed transition into the agent's replay memory for training.

Experimental Evaluation

The proposed method was evaluated using a custom Monte Carlo simulator modeling a CDN edge and a remote DBaaS. Workloads were generated using Zipfian distributions across 10,000 documents to mimic realistic power-law web traffic.

Key Results

The NAF-DEI agent demonstrated superior performance compared to both analytical baselines and naive DRL implementations. The agent maintains high cache hit rates while keeping invalidation rates low across various write intensities.

Cache hit rate and invalidation rate of NAF-DEI vs. Poisson estimator across different write rates.

Specifically, at a 10% write rate, NAF-DEI achieved an 88.5% cache hit rate with 7.3% invalidations, significantly outperforming a statistical Poisson estimator (79.5% hit rate). Furthermore, the DEI mechanism proved essential; a "naive" NAF implementation that ignored the delay in rewards resulted in a 38.5% higher Root Mean Square Error (RMSE) relative to the optimal policy. Trace logs also confirmed the agent's ability to dynamically lower TTLs as global cache capacity reached its limits.

Conclusion

This work demonstrates that small state spaces—focusing on record-level metrics rather than raw query strings—enable effective online learning in complex systems. By breaking the sequential MDP assumption through Delayed Experience Injection, DRL can be successfully adapted for highly concurrent, real-time system optimization. Future work will explore distributed learning environments and mapping dynamic rewards to specific Service Level Objectives (SLOs).

Summary updated

Abstract

Learning effective configurations in computer systems without hand-crafting models for every parameter is a long-standing problem. This paper investigates the use of deep reinforcement learning for runtime parameters of cloud databases under latency constraints. Cloud services serve up to thousands of concurrent requests per second and can adjust critical parameters by leveraging performance metrics. In this work, we use continuous deep reinforcement learning to learn optimal cache expirations for HTTP caching in content delivery networks. To this end, we introduce a technique for asynchronous experience management called delayed experience injection, which facilitates delayed reward and next-state computation in concurrent environments where measurements are not immediately available. Evaluation results show that our approach based on normalized advantage functions and asynchronous CPU-only training outperforms a statistical estimator.
BibTeX
@misc{schaarschmidt2016learning,
  author = {Michael Schaarschmidt and Felix Gessert and Valentin Dalibard and Eiko Yoneki},
  title = {{Learning Runtime Parameters in Computer Systems with Delayed Experience Injection}},
  year = {2016},
  eprint = {1610.09903},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1610.09903},
}
Figure