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.
The DEI workflow operates as follows:
- Observation: Upon a query arrival, the agent observes the state, including record-level write rates and cache miss rates.
- Action: The agent outputs a TTL duration.
- 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.
- 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.
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