GIFT: A Coupon Based Throttle-and-Reward Mechanism for Fair and Efficient I/O Bandwidth Management on Parallel Storage Systems

Tirthak Patel, Rohan Garg, Devesh Tiwari

TL;DR

This paper introduces GIFT, a novel system for managing I/O bandwidth in large-scale parallel storage systems. GIFT addresses the critical challenge of I/O contention, which leads to inefficient resource utilization and unfairness among competing applications. By employing a unique "throttle-and-reward" mechanism with coupons, GIFT dynamically balances fairness and efficiency, significantly improving overall system performance.

What Problem Does This Paper Address?

High-performance computing (HPC) systems are increasingly data-intensive, with parallel applications routinely handling terabytes of data. This massive I/O activity often leads to contention on shared storage systems. This contention has two major negative consequences:

  1. Inefficiency: In HPC, applications often require synchronous I/O progress, meaning all processes of an application must complete their I/O before proceeding. I/O contention can cause some processes to lag, leading to wasted compute cycles as other processes wait. This also reduces the effective system I/O bandwidth, as not all available bandwidth is contributing to actual progress.
  2. Unfairness: When multiple applications compete for I/O resources, bandwidth can be allocated unevenly, leading to some applications being starved while others get disproportionately more. This is particularly problematic in HPC where applications may have varying I/O needs and sensitivities.

Existing approaches struggle to strike a balance between maximizing system throughput and ensuring fairness, often prioritizing one over the other.

Methods

GIFT introduces a principled dynamic approach with two core ideas:

  1. Relaxing the Fairness Window: Instead of aiming for instantaneous fairness at every I/O request, GIFT ensures fairness over multiple I/O phases and application runs. This is possible because HPC applications are often repetitive and exhibit similar behavior across runs.
  2. Throttle-and-Reward Mechanism: GIFT intelligently throttles the I/O bandwidth of certain applications when opportunities arise to improve overall system I/O bandwidth (i.e., reduce wasted bandwidth that doesn't contribute to synchronous progress). It then uses "coupons" to compensate these throttled applications later, ensuring fairness over a longer period.

Key components of the GIFT approach include:

  • Synchronous I/O Progress Enforcement: GIFT first ensures synchronous I/O progress for applications by allocating bandwidth based on the most contended Object Storage Target (OST) for that application (similar to the BSIP scheme).
  • Identifying Throttle-Friendly Applications: GIFT identifies applications that can be throttled with a high likelihood of their "stolen" bandwidth being redeemed later. This is done by monitoring a "receding window" of coupon redemption rates.
  • Optimal Bandwidth Allocation (LP): A linear programming (LP) optimization problem is formulated to maximize effective system I/O bandwidth. This LP considers constraints such as:
  • Throttle-friendly applications can be assigned less than their fair share (up to a configurable threshold, Bthres).
  • The total effective bandwidth must be at least as good as the BSIP scheme.
  • The gains from reducing bandwidth waste must outweigh the value of issued coupons.
  • Coupon Redemption Policy: GIFT redeems coupons only when it can do so without negatively impacting other applications (i.e., by utilizing spare bandwidth). This ensures fairness without introducing new unfairness.
  • System Regret Budget: A bounded "system regret budget" (in terms of compute node-hours) is used to compensate applications if coupons cannot be redeemed, ensuring fairness even in challenging scenarios.

Datasets

Not discussed in the paper. The evaluation uses real-world HPC system and application characteristics, and simulations.

Key Insights and Ideas

  • The "Throttle-and-Reward" Paradigm: The core innovation is the idea of temporarily sacrificing fairness for short-term efficiency gains, with a mechanism to "pay back" the throttled applications later. This breaks the traditional trade-off where fairness and efficiency are seen as mutually exclusive.
  • Leveraging Application Repetitiveness: The observation that HPC applications are highly repetitive is crucial. This allows GIFT to make fairness decisions over longer time scales, rather than being constrained by instantaneous demands.
  • Coupons as a Fairness Currency: Coupons act as a tangible representation of "stolen" bandwidth, providing a quantifiable way to track and redeem fairness debt.
  • System Regret Budget as a Safety Net: The bounded regret budget ensures that even if coupon redemption fails, fairness is ultimately maintained through compute time compensation, preventing long-term unfairness.
  • Dynamic, Adaptive Management: GIFT is not a static policy but a dynamic system that learns and adapts to changing application behavior and system conditions.

Key Results

  • Improved System Performance: GIFT significantly improves key metrics compared to baseline policies like POFS:
  • Mean Application I/O Time: Reduced by 10% (real system) and 15% (simulation).
  • Effective System I/O Bandwidth: Increased by over 17% (real system) and 25% (simulation).
  • Mean Application Runtime: Reduced by 3.5% (real system) and 7% (simulation).
  • System Throughput: Increased by 2% (real system) and 2% (simulation).
  • Fairness: GIFT achieves fairness comparable to POFS, with only a small percentage of applications experiencing worse performance, and this degradation is compensated by compute node-hours.
  • Low Overhead: The implementation has negligible computational and communication overhead, even under pessimistic scenarios.
  • Parameter Robustness: GIFT's performance is not highly sensitive to parameter tuning (e.g., receding window size N, redemption rate threshold τ, throttling factor Bthres), making it practical to deploy.
  • Bounded System Regret: The number of outstanding node-hours awarded is minimal, well within the system regret budget.

Limitations and Future Work

  • Fairness Definition: The paper acknowledges that GIFT's definition of fairness (compensating with compute time) is different from traditional notions of equal resource allocation. While it demonstrates comparable or better outcomes, direct comparison of "fairness" can be nuanced.
  • User-Level Tracking: The paper mentions that GIFT can be extended to track coupons at the user-level if fairness among users is desired, which would require modifications to track user identifiers.
  • Extending to Other Priorities: GIFT's current bandwidth allocation is based on fair share. It could be extended to support relative priority levels or weights for different applications.
  • Real-time Adaptation: While GIFT makes decisions at regular intervals, further research could explore more fine-grained, real-time adaptation to extremely dynamic I/O patterns.

Summary updated

BibTeX
@inproceedings{patel2020gift,
  author = {Tirthak Patel and Rohan Garg and Devesh Tiwari},
  title = {{GIFT: A Coupon Based Throttle-and-Reward Mechanism for Fair and Efficient I/O Bandwidth Management on Parallel Storage Systems}},
  booktitle = {Fast},
  year = {2020},
}
Figure