A Practical Learning-Based Approach for Dynamic Storage Bandwidth Allocation

Vijay Sundaram, Prashant J. ShenoyIWQoS 2003 · DOI

TL;DR

This paper tackles the challenge of dynamically allocating storage bandwidth to different application classes to meet their response time requirements. They propose a practical reinforcement learning approach that leverages application-specific knowledge to efficiently manage storage resources, significantly reducing Quality of Service (QoS) violations compared to static or non-learning dynamic methods.

What Problem Does This Paper Address?

Modern enterprise storage systems are complex, managing numerous disks and serving diverse application workloads. Manually configuring and managing these systems is costly and time-consuming. A key challenge is dynamically allocating storage bandwidth to different application classes (e.g., databases, file servers) to ensure they meet their Quality of Service (QoS) requirements, specifically their target response times. When multiple applications share storage devices, the system must intelligently partition the available bandwidth. Existing approaches often struggle with the dynamic nature of workloads, the potential for performance interference between applications, and stability issues under overload.

Methods

The authors propose a reinforcement learning (RL) based approach for dynamic storage bandwidth allocation. Instead of a naive RL approach that might explore all possible allocations (leading to prohibitive overheads), they introduce an enhanced, application-specific learning-based technique.

Key aspects of their method include:

  • Discretized State Space: The system state is defined by the observed response times of application classes, which are discretized into categories (e.g., "underloaded," "on-target," "overloaded") to manage complexity.
  • Discretized Action Space: The bandwidth allocation (reservations) for each class is also discretized into steps (e.g., 1% or 5% increments) to create a finite set of possible actions.
  • Reinforcement Learning Core: The system learns by associating rewards (or costs) with actions taken in specific states. The goal is to maximize reward, which in this case means minimizing the aggregate QoS violations (i.e., how much response times exceed targets). They use an exponential average of past rewards to guide future decisions, making it suitable for non-stationary environments.
  • Application-Specific Knowledge Integration: This is a crucial enhancement. The learning algorithm uses knowledge about the system state to prune the search space. For instance, if all classes are overloaded, no reallocation is attempted. If some are overloaded and others underloaded, bandwidth is only reallocated from underloaded ("lender") classes to overloaded ("borrower") classes.
  • Performance Isolation: The approach prioritizes reclaiming bandwidth only from classes that have spare capacity (underloaded) and reassigning it to those that need it (overloaded), thus preventing underloaded classes from being negatively impacted by overloaded ones.
  • Stability Under Overload: The system is designed to exhibit stable behavior even during overload conditions. In severe overload, it can revert to default allocations to prevent oscillations.
  • Online Learning: The system learns and adapts in real-time without requiring prior training data.

Datasets

The paper uses two types of workloads for evaluation:

  • Trace-driven workloads: Portions of an NFS trace gathered from the Auspex file server at Berkeley were used. This trace is described as "bursty" with a peak-to-average bit rate of 12.5.
  • Synthetic workloads: These were generated using Poisson arrival processes for clients reading randomly selected files with heavy-tailed file sizes. This allowed for controlled creation of transient overload scenarios.

The paper does not introduce new benchmarks but uses these existing trace and synthetic workload generation methods to evaluate their proposed system.

Key Insights and Ideas

  • Leveraging Application-Specific Knowledge is Key: A purely generic reinforcement learning approach is impractical due to massive state and action spaces. By incorporating knowledge about storage system behavior (e.g., where to get spare bandwidth, what constitutes an overload), the learning process becomes efficient and effective.
  • Dynamic Allocation Outperforms Static: Even a dynamic allocation strategy without learning provides significant benefits over static allocation, highlighting the importance of adapting to changing workloads.
  • Learning Adds Further Significant Gains: The reinforcement learning component further improves QoS violations beyond dynamic allocation without learning, demonstrating the value of adaptive decision-making.
  • Performance Isolation is Achievable: The method successfully isolates applications by only reallocating spare bandwidth, preventing performance degradation for well-behaved applications.
  • Online Learning is Practical: The system's ability to learn and adapt in real-time without pre-training makes it suitable for dynamic, unpredictable storage environments.

Key Results

  • Reduced QoS Violations: The learning-based approach reduced the number of QoS violations by a factor of 2.1 compared to dynamic allocation without learning, and a factor of 3.8 compared to static allocation.
  • Small Implementation Overheads: The implementation of the learning-based bandwidth allocator in the Linux kernel incurred small CPU and memory overheads, even for simulated systems with up to 500 disks. CPU usage was less than 0.1%, and memory usage was around 0.7% for a 500-disk system.
  • Adaptation to Workload Changes: Experiments showed the system effectively adapting to workload increases and decreases, maintaining response times close to targets.
  • Stability During Overload: In overload scenarios, the system demonstrated stable behavior, reverting to default allocations when necessary.

Limitations and Future Work

  • Limitations:
    • The simple learning approach has prohibitive memory and search space overheads.
  • The enhanced approach still requires careful tuning of parameters (smoothing factor, step size, history size).
  • The current implementation requires modification of application source code or a command-line utility to associate I/O with application classes.
  • Future Work:
    • The authors plan to explore the use of similar learning techniques for other storage management tasks, such as configuration, data placement, and load balancing.
  • Investigating more sophisticated strategies for selecting lenders and borrowers.
  • Exploring alternative state discretization methods.

Summary updated

BibTeX
@inproceedings{sundaram2003practical,
  author = {Vijay Sundaram and Prashant J. Shenoy},
  title = {{A Practical Learning-Based Approach for Dynamic Storage Bandwidth Allocation}},
  booktitle = {IWQoS},
  year = {2003},
  doi = {10.1007/3-540-44884-5\_26},
}
Figure