Files
Thuongvu HoCodexmergify[bot] <37929162+mergify[bot]@users.noreply.github.com>Or Ozeri
02653fa22c [Bugfix][KV Offload] Fix inaccurate proportional store dropping (#59140)
Signed-off-by: Thuongvu Ho <thuongvuho@gmail.com>
Co-authored-by: Codex <noreply@openai.com>
Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>
Co-authored-by: Or Ozeri <oro@il.ibm.com>
2026-10-14 17:05:21 +03:00

394 lines
14 KiB
Python

# SPDX-License-Identifier: Apache-2.0
# SPDX-FileCopyrightText: Copyright contributors to the vLLM project
from __future__ import annotations
import time
from abc import ABC, abstractmethod
class BackpressurePolicy(ABC):
"""Decides what action to take when a detector signals pressure."""
@abstractmethod
def should_store(self, detector: BackpressureDetector) -> bool: ...
@abstractmethod
def on_store_skipped(self, num_blocks: int) -> None: ...
@abstractmethod
def pop_stores_dropped(self) -> tuple[int, int]:
"""Return and reset (stores_dropped, blocks_dropped)."""
...
@abstractmethod
def reset(self) -> None: ...
class DropAccountingPolicy(BackpressurePolicy):
"""Base policy that tracks dropped store/block counters.
Subclasses implement ``should_store``; the shared drop accounting
(``on_store_skipped``/``pop_stores_dropped``/``reset``) lives here so
every policy reports these counters identically. Subclasses that add
their own state override ``reset`` and call ``super().reset()``.
"""
def __init__(self):
self._stores_dropped: int = 0
self._blocks_dropped: int = 0
def on_store_skipped(self, num_blocks: int) -> None:
self._stores_dropped += 1
self._blocks_dropped += num_blocks
def pop_stores_dropped(self) -> tuple[int, int]:
stores, blocks = self._stores_dropped, self._blocks_dropped
self._stores_dropped = 0
self._blocks_dropped = 0
return stores, blocks
def reset(self) -> None:
self._stores_dropped = 0
self._blocks_dropped = 0
class DropStorePolicy(DropAccountingPolicy):
"""Silently drop stores to pressured tiers."""
def should_store(self, detector) -> bool:
return not detector.is_under_pressure()
class ThrottledDropPolicy(DropAccountingPolicy):
"""Drop stores proportionally to pressure severity.
Instead of dropping all stores when pressure is detected, the drop
rate scales with how far the EMA exceeds the high watermark::
overshoot = (ema - high_water) / high_water
drop_rate = min(1.0, overshoot / ramp_factor)
With the default ``ramp_factor=2.0``, stores ramp from 0% drop at
the high watermark to 100% drop at 3x the high watermark. This
keeps secondary tiers populated under moderate pressure, reducing
cache misses (and therefore recomputation / ITL regression) while
still protecting TTFT under severe congestion.
Accumulate ``drop_rate`` across store decisions. When the accumulator
reaches one, drop the store and subtract one from the accumulator,
carrying the remaining fraction into the next decision.
"""
def __init__(self, ramp_factor: float = 2.0):
"""Initialize the drop accumulator and severity ramp."""
super().__init__()
self._drop_accumulator: float = 0.0
self._ramp_factor = ramp_factor
def should_store(self, detector: BackpressureDetector) -> bool:
"""Return whether to allow the store."""
# Proportional throttling needs the EMA and high watermark, which
# only the EMA detector exposes.
assert isinstance(detector, EMABackpressureDetector), (
"ThrottledDropPolicy requires an EMABackpressureDetector"
)
if not detector.is_under_pressure():
return True
ema = detector.store_latency_ema
high = detector._high
if high <= 0:
return False
overshoot = max(0.0, ema - high) / high
drop_rate = min(1.0, overshoot / self._ramp_factor)
if drop_rate <= 0:
return True
if drop_rate >= 1.0:
return False
self._drop_accumulator += drop_rate
if self._drop_accumulator >= 1.0:
self._drop_accumulator -= 1.0
return False
return True
def reset(self) -> None:
"""Clear the drop accumulator and dropped store and block counts."""
super().reset()
self._drop_accumulator = 0.0
class BackpressureDetector(ABC):
"""Observes store completion signals and determines pressure state."""
def __init__(
self,
policy: BackpressurePolicy | None = None,
):
self._policy = policy or ThrottledDropPolicy()
@property
def policy(self) -> BackpressurePolicy:
return self._policy
@abstractmethod
def on_store_completed(self, elapsed_s: float, num_bytes: int) -> None: ...
@abstractmethod
def is_under_pressure(self) -> bool: ...
@abstractmethod
def reset(self) -> None: ...
def update(self, submit_time: float, num_bytes: int) -> None:
"""Update pressure state from a completed store job.
Args:
submit_time: ``time.monotonic()`` when the job was submitted.
num_bytes: Total bytes written (num_blocks * block_size_bytes).
"""
if num_bytes <= 0:
return
elapsed = time.monotonic() - submit_time
self.on_store_completed(elapsed, num_bytes)
def should_store(self, num_blocks: int) -> bool:
"""Check policy and record skip if rejected."""
if not self._policy.should_store(self):
self._policy.on_store_skipped(num_blocks)
return False
return True
@classmethod
def default_config(
cls, tier_type: str, *, locality: str | None = None
) -> dict | None:
"""Return default constructor kwargs for ``tier_type``, or None.
Args:
tier_type: The tier type string (e.g. ``"fs"``, ``"obj"``).
locality: Optional locality hint from the tier config
(``"LOCAL"`` or ``"REMOTE"``). When ``"REMOTE"``, tiers
that would normally get local-storage watermarks (e.g.
``"fs"``) receive network watermarks instead.
"""
return None
@property
def stats(self) -> dict[str, float]:
return {}
class EMABackpressureDetector(BackpressureDetector):
"""EMA of store latency normalized by transfer size.
The EMA tracks seconds per megabyte (s/MiB) so that the metric is
comparable regardless of how many blocks are in a job or how large
each block is. Water marks are in the same unit.
Default water marks are derived from fio benchmarks on the WDC H100
cluster. Two presets are provided:
LOCAL (NVMe/SSD): NVMe sustains ~5 GB/s writes.
high=0.005 s/MiB (~200 MB/s) catches severe congestion;
low=0.001 s/MiB (~1 GB/s) requires meaningful recovery.
NETWORK (CephFS, object store, ``obj``tiers, or any tier
with ``"locality": "REMOTE"``): CephFS sustains ~1.5 GB/s.
high=0.020 s/MiB (~50 MB/s); low=0.005 s/MiB (~200 MB/s).
``obj`` tiers get NETWORK defaults automatically. An
``fs`` tier defaults to LOCAL (appropriate for NVMe/SSD); set
``"locality": "REMOTE"`` in the tier config for network-backed
filesystems like CephFS.
"""
_MIB = 1 << 20
# EMA smoothing factor: higher values (→1) react faster to latency
# spikes but are noisier; lower values (→0) smooth more but lag.
DEFAULT_ALPHA = 0.15
# Number of store completions to collect before seeding the EMA.
# During warmup, pressure is never signalled; the EMA is initialized
# to the mean of the warmup samples to avoid cold-start false positives.
DEFAULT_WARMUP_COMPLETIONS = 10
# When under pressure and no completions arrive, the EMA decays
# toward zero so the detector can eventually recover. The half-life
# controls how quickly: after this many seconds of silence the EMA
# halves. With a 2 s half-life and high_water=0.005, an EMA frozen
# at 0.010 reaches low_water=0.001 in ~6.6 s.
DEFAULT_DECAY_HALF_LIFE_S = 2.0
# After pressure clears, stores are throttled to 50% for this many
# seconds to prevent a burst of stores from re-overwhelming the tier.
DEFAULT_COOLDOWN_S = 1.0
# Number of consecutive sub-low-watermark completions before the
# detector enters a "healthy" fast-path that bypasses policy checks.
_HEALTHY_THRESHOLD = 10
LOCAL_HIGH_WATER_S = 0.010
LOCAL_LOW_WATER_S = 0.002
NETWORK_HIGH_WATER_S = 0.050
NETWORK_LOW_WATER_S = 0.010
_NETWORK_TIER_TYPES = frozenset({"obj"})
@classmethod
def default_config(
cls, tier_type: str, *, locality: str | None = None
) -> dict | None:
is_remote = locality is not None and locality.upper() == "REMOTE"
if is_remote or tier_type in cls._NETWORK_TIER_TYPES:
return {
"high_water_s": cls.NETWORK_HIGH_WATER_S,
"low_water_s": cls.NETWORK_LOW_WATER_S,
}
return {
"high_water_s": cls.LOCAL_HIGH_WATER_S,
"low_water_s": cls.LOCAL_LOW_WATER_S,
}
def __init__(
self,
high_water_s: float,
low_water_s: float,
alpha: float = DEFAULT_ALPHA,
warmup_completions: int = DEFAULT_WARMUP_COMPLETIONS,
decay_half_life_s: float = DEFAULT_DECAY_HALF_LIFE_S,
cooldown_s: float = DEFAULT_COOLDOWN_S,
policy: BackpressurePolicy | None = None,
):
super().__init__(policy=policy)
if not (0 < alpha <= 1):
raise ValueError(f"alpha must be in (0, 1], got {alpha}")
if low_water_s > high_water_s:
raise ValueError(
f"low_water_s ({low_water_s}) must be <= high_water_s ({high_water_s})"
)
self._alpha = alpha
self._high = high_water_s
self._low = low_water_s
self._warmup_completions = warmup_completions
self._decay_half_life_s = decay_half_life_s
self._cooldown_s = cooldown_s
# Exponential moving average of store latency in seconds.
self._ema: float = 0.0
# Whether the tier is currently considered under pressure.
self._under_pressure: bool = False
# Number of store completions observed (for warmup gating).
self._completions: int = 0
# Samples collected during warmup; used to seed the EMA.
self._warmup_samples: list[float] = []
# Monotonic timestamp of the last EMA update; used for idle decay.
self._last_update: float = 0.0
# Consecutive completions with EMA below low watermark.
self._healthy_streak: int = 0
# Monotonic timestamp when pressure was last cleared (for cooldown).
self._pressure_cleared_at: float = 0.0
self._cooldown_count: int = 0
def _apply_idle_decay(self) -> None:
"""Decay the EMA toward zero based on elapsed idle time.
Uses the formula ``ema * 0.5^(dt / half_life)`` so the EMA
halves every ``decay_half_life_s`` seconds of silence. This
lets the detector recover from pressure when no stores are
attempted (and therefore no completions arrive to update the
EMA organically).
"""
now = time.monotonic()
dt = now - self._last_update
if dt <= 0 or self._decay_half_life_s <= 0:
return
self._ema *= 0.5 ** (dt / self._decay_half_life_s)
self._last_update = now
def on_store_completed(self, elapsed_s: float, num_bytes: int) -> None:
now = time.monotonic()
s_per_mib = elapsed_s / (num_bytes / self._MIB)
self._completions += 1
if self._completions <= self._warmup_completions:
self._warmup_samples.append(s_per_mib)
if self._completions == self._warmup_completions:
self._ema = sum(self._warmup_samples) / len(self._warmup_samples)
self._last_update = now
return
self._ema = self._alpha * s_per_mib + (1 - self._alpha) * self._ema
self._last_update = now
if self._ema > self._high:
self._under_pressure = True
self._pressure_cleared_at = 0.0
self._healthy_streak = 0
elif self._ema < self._low:
if self._under_pressure:
self._pressure_cleared_at = now
self._cooldown_count = 0
self._under_pressure = False
self._healthy_streak += 1
else:
self._healthy_streak = 0
def is_under_pressure(self) -> bool:
if self._under_pressure and self._completions >= self._warmup_completions:
self._apply_idle_decay()
if self._ema < self._low:
self._under_pressure = False
self._pressure_cleared_at = time.monotonic()
self._cooldown_count = 0
return self._under_pressure
def is_healthy(self) -> bool:
"""True when the tier has been consistently fast.
After ``_HEALTHY_THRESHOLD`` consecutive store completions with
EMA below the low watermark (and no active pressure), the
detector enters a healthy fast-path: ``should_store()`` returns
``True`` immediately, skipping the policy check entirely.
"""
return (
not self._under_pressure and self._healthy_streak >= self._HEALTHY_THRESHOLD
)
def should_store(self, num_blocks: int) -> bool:
under_pressure = self.is_under_pressure()
if self.is_healthy():
return True
if (
not under_pressure
and self._pressure_cleared_at > 0
and time.monotonic() - self._pressure_cleared_at < self._cooldown_s
):
self._cooldown_count += 1
if self._cooldown_count % 2 == 0:
self._policy.on_store_skipped(num_blocks)
return False
return super().should_store(num_blocks)
def reset(self) -> None:
self._ema = 0.0
self._under_pressure = False
self._completions = 0
self._warmup_samples.clear()
self._last_update = 0.0
self._healthy_streak = 0
self._pressure_cleared_at = 0.0
self._cooldown_count = 0
self._policy.reset()
@property
def store_latency_ema(self) -> float:
return self._ema
@store_latency_ema.setter
def store_latency_ema(self, value: float) -> None:
self._ema = value
@property
def stats(self) -> dict[str, float]:
return {"store_latency_ema": self._ema}