#5683

Committed 26 Jul 2026 05:59AM UTC coverage: 99.907% (-0.05%) from 99.953%

Build # #5683

Build Type

push

github

Committed by

ben-manes

Commit Message

Adapt the window by hit density with starvation-guarded probes

Large caches size the admission window by the within-sample hit density
of the two regions, ln(windowDensity / mainDensity), taking proportional
steps that are immune to the cross-sample hit rate swings of a phasey
workload. The signal is resident-only, so a region earning ~nothing is
its blind state: it cannot see what a different split would earn, and
holding such a position can pin the window at an extreme (constructible
steady-state workloads pinned it ~28pp below LRU at any scale).

Starved samples at a blind corner therefore probe by hit rate. Walks
are bounded by a sample budget, by a reversal that crosses back through
the probe's start, and by an absolute hit rate veto that undoes damage;
the density signal adjudicates each endpoint under strict confirmation.
A crash re-arms the refractory without doubling, since an exogenous
workload shift is indistinguishable from probe damage and mispricing it
would starve the re-exploration the shift calls for. Escalating
commitment resolves the stray-exit dilemma: first-round probes exit
cheaply when the watched region earns without density confirmation
(stray and transferred hits scale with a region's size, and thin-signal
workloads correctly at the floor must not pay deep-walk displacement),
while each adjudicated failure lengthens the refractory ladder and its
deeper rungs commit the walk past the stray zone, converting a deep
silent reuse band from an absorbing pin into a bounded, temporary dip.
Deep rungs also stride at 2x and 4x (capped at the 30% max step): the
ladder previously bought a committed walk permission to pass the stray
zone but not speed, so deep reuse bands were reached only by outlasting
the budget, and stray walls calibrated wider than a flat stride's reach
were absorbing. Failed walks still undo in full, which is what
distinguishes this from the rejected travel-budget exits. The sample
period is capped by the sketch's e... (continued)

Coverage Stats

4285 of 4315 branches covered (99.3%)

186 of 191 new or added lines in 5 files covered. (97.38%)

8590 of 8598 relevant lines covered (99.91%)

1.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.77

/caffeine/src/main/java/com/github/benmanes/caffeine/cache/WindowClimber.java

/*
 * Copyright 2026 Ben Manes. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.benmanes.caffeine.cache;

import com.google.errorprone.annotations.Var;

/**
 * A hill climber that adapts the size of the admission window to balance the cache's recency and
 * frequency regions.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 */
final class WindowClimber {

  /*
   * This class determines how to adapt the size of W-TinyLfu's admission window, which balances
   * the cache between recency (the window, admitting every new arrival) and frequency (the main
   * space, guarded by the TinyLfu filter). The best split is workload dependent, so it is climbed
   * online using the cache's own behavior as feedback. Small and medium caches climb reactively
   * on the hit rate: continue in the same direction while a sample's hit rate improves over the
   * previous sample's, reverse otherwise, and decay the step towards convergence. Large caches
   * instead compare the hit density (hits per slot) of the two regions within a single sample and
   * step proportionally, shifting capacity towards the region earning more per slot. That signal
   * is immune to workload phases but blind when a region is too starved to measure, so at those
   * corners the climber probes: it temporarily walks the window by the hit rate and keeps the new
   * position only if the density signal validates it, retreating and backing off otherwise.
   *
   * [1] The Density Climber, From First Principles
   * https://github.com/ben-manes/caffeine/.claude/docs/hill-climber-design.html
   */

  /** The difference in hit rates that restarts the climber. */
  static final double HILL_CLIMBER_RESTART_THRESHOLD = 0.05d;
  /** The percent of the total size to adapt the window by. */
  static final double HILL_CLIMBER_STEP_PERCENT = 0.0625d;
  /** The rate to decrease the step size to adapt by. */
  static final double HILL_CLIMBER_STEP_DECAY_RATE = 0.98d;
  /** Lower bound on the initial step size so that small caches have an opportunity to adapt. */
  static final double HILL_CLIMBER_MIN_INITIAL_STEP = 2.0d;
  /**
   * The size at/below which the hit-rate climber adapts slowly and deliberately: the window is only
   * a few integer entries (a 1%-of-512 window is ~5) and a single sample is too noisy to trust, so
   * it grows the window first, stretches its sample period as the step decays, and decays the step
   * slowly.
   */
  static final long HILL_CLIMBER_SLOW_ADAPT_THRESHOLD = 512L;
  /**
   * The size above which the window is sized by the density climber rather than the hit-rate
   * climber. The density signal, being resident-only, is both unreliable and prone to pinning at an
   * extreme when a region is small, and its within-sample gains only exceed the hit-rate climber's
   * above this size (they are ~neutral below it) — so it is scoped here to keep the hit-rate
   * climber's robustness at smaller sizes while adding density's wins for large caches.
   */
  static final long HILL_CLIMBER_DENSITY_THRESHOLD = 4096L;
  /** Maximum factor by which the sample period may grow in the slow-adapt regime. */
  static final double HILL_CLIMBER_SLOW_ADAPT_RATIO_CAP = 4.0d;
  /**
   * The step decay rate in the slow-adapt regime, slower to keep the step large enough for
   * restarts.
   */
  static final double HILL_CLIMBER_SLOW_ADAPT_DECAY_RATE = 0.995d;
  /**
   * The density climber's step per unit of log density-ratio error, as a fraction of the maximum.
   */
  static final double HILL_CLIMBER_DENSITY_GAIN = 0.03d;
  /** The density climber's largest single step, as a fraction of the maximum. */
  static final double HILL_CLIMBER_MAX_STEP_FRACTION = 0.30d;
  /**
   * The density climber's lower bound on the window as a fraction of the maximum. It is a
   * signal-capable floor, not merely off the zero cliff: below it a starved window catches too few
   * hits to estimate its own density, so the climber can pin there and never recover when the
   * workload turns recency-heavy. 2% keeps the window measurable at negligible cost to workloads
   * whose true optimum is smaller.
   */
  static final double HILL_CLIMBER_WINDOW_FLOOR_FRACTION = 0.02d;
  /**
   * The density climber's sample period, as a multiple of the maximum size. It is far shorter than
   * the sketch's 10x reset period so a large cache takes enough steps over a finite trace to reach
   * a large optimal window; kept at 4x (not lower) so brief, noisy density estimates near a small
   * converged window do not jitter it off a frequency-friendly optimum.
   */
  static final long HILL_CLIMBER_SAMPLE_MULTIPLIER = 4L;
  /**
   * The density climber's signal-capability bar: a region is starved when its hits in the sample
   * fall below requestCount >> shift (0.1%). A starved region cannot estimate its own density —
   * trapped regions measure ~2 orders of magnitude below this bar, while regions correctly at the
   * floor on frequency-biased workloads measure well above it.
   */
  static final int HILL_CLIMBER_MIN_SIGNAL_SHIFT = 10;
  /**
   * The initial refractory period after a failed probe, in samples; doubles per failure so that
   * workloads whose floor is genuinely correct pay a single bounded exploration cost.
   */
  static final int HILL_CLIMBER_PROBE_BACKOFF_INITIAL = 16;
  /** The longest refractory period between probes after repeated failures. */
  static final int HILL_CLIMBER_PROBE_BACKOFF_MAX = 64;
  /**
   * The number of samples a probe may walk without confirmation before it is judged a failed
   * experiment. Bounds every walk (stray hits scale with the region size and must not end one
   * early; a hit-rate veto cannot fire when the base rate is smaller than its threshold), while
   * comfortably exceeding the longest confirmed escape (a corner-to-corner traverse needs ~13
   * decaying steps). While probing, the refractory countdown field carries this budget — the two
   * uses cannot overlap.
   */
  static final int HILL_CLIMBER_PROBE_WALK_BUDGET = 16;

  double stepSize;
  long adjustment;
  long hitsInSample;
  long missesInSample;
  long windowHitsInSample;

  boolean probing;
  boolean probeDown;
  long probeBaseWindow;
  int probeBackoffLeft;
  int probeBackoffLength;
  double probeBaseHitRate;
  double previousSampleHitRate;

  /** Resets the state and seeds the step size when the cache's maximum size is changed. */
  void resized(long maximum) {
    resetSample();
    adjustment = 0;
    probing = false;
    probeBackoffLeft = 0;
    probeBackoffLength = HILL_CLIMBER_PROBE_BACKOFF_INITIAL;
    double stepSize = Math.max(HILL_CLIMBER_STEP_PERCENT * maximum,
        HILL_CLIMBER_MIN_INITIAL_STEP);
    this.stepSize = (maximum <= HILL_CLIMBER_SLOW_ADAPT_THRESHOLD) ? stepSize : -stepSize;
  }

  void resetSample() {
    previousSampleHitRate = 0.0;
    windowHitsInSample = 0;
    missesInSample = 0;
    hitsInSample = 0;
  }

  /** Records a cache hit on an entry residing in the window or main space. */
  void recordHit(boolean inWindow) {
    hitsInSample++;
    if (inWindow) {
      windowHitsInSample++;
    }
  }

  /** Records a cache miss. */
  void recordMiss() {
    missesInSample++;
  }

  /** Calculates the amount to adapt the window by and sets {@link #adjustment} accordingly. */
  void determineAdjustment(long maximum, long windowMaximum, int sketchSampleSize) {
    long requestCount = hitsInSample + missesInSample;
    if (requestCount < samplePeriod(maximum, sketchSampleSize)) {
      return;
    }

    double hitRate = (double) hitsInSample / requestCount;
    double amount = (maximum <= HILL_CLIMBER_DENSITY_THRESHOLD)
        ? reactiveStep(hitRate, maximum)
        : densityClimb(hitRate, requestCount, maximum, windowMaximum);
    previousSampleHitRate = hitRate;
    adjustment = (long) amount;
    windowHitsInSample = 0;
    missesInSample = 0;
    hitsInSample = 0;
  }

  /** The number of requests in an adaptation sample, by the size tier. */
  @SuppressWarnings("MathClampDouble")
  private long samplePeriod(long maximum, int sketchSampleSize) {
    if (maximum > HILL_CLIMBER_DENSITY_THRESHOLD) {
      // The density climber adapts far more often than the sketch ages: its within-sample hit
      // density needs only enough requests to estimate each region's hits-per-entry, so a period
      // well below the sketch's 10x reset lets a large cache take many steps over a finite trace
      // and reach a large optimal window. The sketch's own sample is the ceiling: it is entry
      // denominated, whereas a weighted maximum is in weight units, multiplying it against a
      // request counter would inflate the period by the mean entry weight and freeze adaptation,
      // and the multiplication of a near-Long.MAX_VALUE maximum overflows.
      @Var long period = HILL_CLIMBER_SAMPLE_MULTIPLIER * maximum;
      if ((period / HILL_CLIMBER_SAMPLE_MULTIPLIER) != maximum) {
        period = Long.MAX_VALUE;
      }
      return Math.min(period, sketchSampleSize);
    } else if (maximum <= HILL_CLIMBER_SLOW_ADAPT_THRESHOLD) {
      // Grows the sample period as the step size decays to avoid converging near the initial ratio
      double initialStep = HILL_CLIMBER_STEP_PERCENT * maximum;
      double magnitude = Math.max(Math.abs(stepSize),
          initialStep / HILL_CLIMBER_SLOW_ADAPT_RATIO_CAP);
      double ratio = (magnitude == 0.0)
          ? 1.0
          : Math.max(1.0, Math.min(HILL_CLIMBER_SLOW_ADAPT_RATIO_CAP, initialStep / magnitude));
      return (long) (sketchSampleSize * ratio);
    }

    // Between the thresholds, the hit-rate climber uses the sketch's standard period
    return sketchSampleSize;
  }

  /** The step decay rate, slower in the slow-adapt regime to keep restarts reachable. */
  private static double stepDecayRate(long maximum) {
    return (maximum <= HILL_CLIMBER_SLOW_ADAPT_THRESHOLD)
        ? HILL_CLIMBER_SLOW_ADAPT_DECAY_RATE
        : HILL_CLIMBER_STEP_DECAY_RATE;
  }

  /**
   * The hit-rate-comparison climber for small and medium caches: walk in the direction that
   * improved the hit rate, decaying the step and restarting on a workload shift.
   */
  private double reactiveStep(double hitRate, long maximum) {
    double hitRateChange = hitRate - previousSampleHitRate;
    double amount = (hitRateChange >= 0) ? stepSize : -stepSize;
    stepSize = (Math.abs(hitRateChange) >= HILL_CLIMBER_RESTART_THRESHOLD)
        ? Math.copySign(
            Math.max(HILL_CLIMBER_STEP_PERCENT * maximum, HILL_CLIMBER_MIN_INITIAL_STEP), amount)
        : (stepDecayRate(maximum) * amount);
    return amount;
  }

  /**
   * The density climber for large caches directs and sizes the window step from the within-sample
   * hit density of the two regions. The signed error is ln(windowDensity / mainDensity): positive
   * when the admission window earns more hits per entry than the main space, so capacity is more
   * valuable in the window and it should grow; negative otherwise. The step is that error scaled
   * by a gain, so a tiny window on a recency-heavy workload takes a large step and reaches its
   * optimum in a few samples, while near the balance point the step shrinks to zero and the window
   * settles. Being computed inside one sample it is immune to the cross-sample hit-rate swings
   * that phasey workloads impose, which otherwise bury the window's shallow gradient and leave the
   * climber stuck. A signal-capable floor keeps the window large enough to estimate its own
   * density, so it cannot collapse to a starved size and pin there when the workload turns
   * recency-heavy.
   * <p>
   * The density signal is resident-only, so a region earning ~nothing is its blind state: it
   * cannot see what a different split WOULD earn, and trusting such a sample can pin the window at
   * an extreme forever. Starved samples therefore fall back to a goal-driven probe: a bold-driver
   * walk out of the blind corner that reverses only on a crash-scale hit-rate drop (so plateau
   * crossings persist through workload jitter). The probe ends when its own damage aborts it, or
   * when the watched region earns enough for the density signal to adjudicate: a validated
   * position is kept (a reuse band was found), while a rejected one is undone with exponentially
   * longer refractory periods between attempts — so workloads whose small window is genuinely
   * correct pay one bounded exploration cost and then hold still.
   */
  private double densityClimb(double hitRate, long requestCount, long maximum, long windowMax) {
    long windowHits = windowHitsInSample;
    long mainHits = (hitsInSample - windowHits);
    double floor = HILL_CLIMBER_WINDOW_FLOOR_FRACTION * maximum;
    double windowDensity = (windowHits / (double) Math.max(1L, windowMax));
    double mainDensity = (mainHits / (double) Math.max(1L, maximum - windowMax));
    double error = Math.log((windowDensity + 1e-9) / (mainDensity + 1e-9));
    long bar = Math.max(4, requestCount >> HILL_CLIMBER_MIN_SIGNAL_SHIFT);
    boolean windowStarved = (windowHits < bar);
    boolean mainStarved = (mainHits < bar);
    if (probing) {
      switch (probeEnding(hitRate, error, windowHits, mainHits, bar)) {
        case CRASHED:
          return undoProbe(/* failed= */ false, windowMax);
        case FAILED:
          return undoProbe(/* failed= */ true, windowMax);
        case WALKING:
          return walkStep(/* entry= */ false, hitRate, maximum, windowMax, floor);
        case CONFIRMED:
          break;  // the validated position is held by the density step below
      }
    } else if (armProbe(hitRate, maximum, windowMax, windowStarved, mainStarved)) {
      return walkStep(/* entry= */ true, hitRate, maximum, windowMax, floor);
    }
    return densityStep(error, maximum, windowMax, floor);
  }

  /** How the probe's walk ends, judged once the sample completes. */
  private ProbeEnding probeEnding(double hitRate, double error,
      long windowHits, long mainHits, long bar) {
    double probeDirection = probeDown ? -1.0 : 1.0;
    long watched = probeDown ? mainHits : windowHits;
    if (hitRate <= (probeBaseHitRate - HILL_CLIMBER_RESTART_THRESHOLD)) {
      // The hit rate collapsed below the probe's start, so the movement is undone. The
      // collapse may be the probe's own damage or an exogenous workload shift which are
      // indistinguishable here, so the refractory re-arms at its current length instead of
      // doubling: mispricing a workload phase as a failed experiment would starve the very
      // re-exploration the shift calls for.
      probing = false;
      return ProbeEnding.CRASHED;
    } else if ((watched >= (4 * bar))
        && ((HILL_CLIMBER_PROBE_WALK_BUDGET - probeBackoffLeft) >= probeCommitment())) {
      // The watched region earns enough to judge. Density confirming the probed direction is
      // a reuse band: keep the position, let density take over, and make probes cheap again.
      // Anything else is a completed, failed experiment: stray and transferred hits reach
      // this bar on workloads whose small window is genuinely correct, so first probes must
      // exit cheaply on them, but the same physics ends a deep walk a stride short of a denser
      // reuse band, which would make that trap absorbing. Escalating commitment breaks the tie:
      // each adjudicated failure lengthens the refractory ladder, and the deeper rungs commit
      // the next walk past the stray zone before this exit may fire, so a steady trap is
      // escaped within a few rounds while short-lived probing on a healthy workload never
      // escalates far enough to pay the deep-walk cost.
      probing = false;
      if ((error * probeDirection) > 0.0) {
        probeBackoffLength = 1;
        probeBackoffLeft = 0;
        return ProbeEnding.CONFIRMED;
      }
      return ProbeEnding.FAILED;
    } else if (probeBackoffLeft == 0) {
      // the walk budget is spent without any signal: undo and double the refractory
      probing = false;
      return ProbeEnding.FAILED;
    }
    return ProbeEnding.WALKING;
  }

  /**
   * A probe is justified only at a blind corner: the starved region is the small one (it cannot
   * measure itself), or the whole sample is dead. A large region earning nothing is visible to
   * density (the other region's share dominates) and needs no probe, e.g. a scan-filled main
   * earning zero next to a small window earning everything must NOT trigger a shrink probe of the
   * one region that is working.
   *
   * @return whether a probe was armed, making this sample the walk's entry stride
   */
  private boolean armProbe(double hitRate, long maximum, long windowMax,
      boolean windowStarved, boolean mainStarved) {
    boolean deadSample = windowStarved && mainStarved;
    boolean windowBlind = windowStarved && (windowMax <= (maximum >>> 2));
    boolean mainBlind = mainStarved && (windowMax >= (maximum - (maximum >>> 2)));
    if (deadSample || windowBlind || mainBlind) {
      if (probeBackoffLeft > 0) {
        probeBackoffLeft = probeBackoffLeft - 1;  // refractory: act as if not starved
      } else {
        probing = true;
        probeBaseHitRate = hitRate;
        probeBaseWindow = windowMax;
        probeBackoffLeft = HILL_CLIMBER_PROBE_WALK_BUDGET;
        probeDown = mainBlind || (deadSample && (windowMax >= (maximum >>> 1)));
        return true;
      }
    }
    return false;
  }

  /** Returns to where the probe started; only a completed failure escalates the ladder. */
  private double undoProbe(boolean failed, long windowMax) {
    if (failed) {
      probeBackoffLength = Math.min(HILL_CLIMBER_PROBE_BACKOFF_MAX, 2 * probeBackoffLength);
    }
    double amount = (probeBaseWindow - windowMax);
    probeBackoffLeft = probeBackoffLength;
    stepSize = amount;
    return amount;
  }

  /**
   * A bold-driver stride of the probe's walk: seeded at the restart magnitude in the probe
   * direction and scaled by the refractory rung (deep rungs bought a committed walk permission to
   * pass the stray zone but not speed, so stray walls calibrated wider than a flat stride's reach
   * were absorbing), reversing only on a crash-scale hit-rate drop so that plateau crossings
   * persist through workload jitter, and finishing as a failed experiment if a reversal would
   * cross back through the probe's own start rather than walking out the other side of the base.
   */
  private double walkStep(boolean entry, double hitRate,
      long maximum, long windowMax, double floor) {
    int rung = probeBackoffLength;
    double probeDirection = probeDown ? -1.0 : 1.0;
    double strideScale = (rung >= HILL_CLIMBER_PROBE_BACKOFF_MAX) ? 4 : (rung >= 32) ? 2 : 1;
    double restartMagnitude = Math.min(HILL_CLIMBER_MAX_STEP_FRACTION * maximum,
        strideScale * Math.max(
            HILL_CLIMBER_STEP_PERCENT * maximum, HILL_CLIMBER_MIN_INITIAL_STEP));

    @Var double step;
    if (entry) {
      step = probeDirection * restartMagnitude;
    } else {
      double hitRateChange = hitRate - previousSampleHitRate;
      step = (hitRateChange > -HILL_CLIMBER_RESTART_THRESHOLD) ? stepSize : -stepSize;
      step = (Math.abs(hitRateChange) >= HILL_CLIMBER_RESTART_THRESHOLD)
          ? Math.copySign(restartMagnitude, step)
          : (HILL_CLIMBER_STEP_DECAY_RATE * step);
      if (Math.abs(step) < HILL_CLIMBER_MIN_INITIAL_STEP) {
        step = probeDirection * restartMagnitude;
      }
    }

    boolean completed = (probeDirection > 0.0)
        ? ((windowMax + step) < probeBaseWindow)
        : ((windowMax + step) > probeBaseWindow);
    if (completed) {
      // a reversal that crosses the probe's own start found nothing: finish as a completed,
      // failed experiment rather than walking out the other side of the base
      probeBackoffLength = Math.min(HILL_CLIMBER_PROBE_BACKOFF_MAX, 2 * probeBackoffLength);
      probeBackoffLeft = probeBackoffLength;
      step = probeBaseWindow - windowMax;
      probing = false;
    } else if ((step < 0) && ((windowMax + step) < floor)) {
      // walks honor the signal-capable floor
      step = Math.min(0.0, floor - windowMax);
      probeBackoffLeft--;
    } else {
      probeBackoffLeft--;
    }
    stepSize = step;
    return step;
  }

  /** A proportional step by the density error, clamped to the signal-capable floor. */
  @SuppressWarnings("MathClampDouble")
  private double densityStep(double error, long maximum, long windowMax, double floor) {
    double magnitude = Math.min(HILL_CLIMBER_MAX_STEP_FRACTION * maximum,
        Math.abs(error) * HILL_CLIMBER_DENSITY_GAIN * maximum);
    double step = (error >= 0) ? magnitude : -magnitude;
    @Var double clamped = ((step < 0) && ((windowMax + step) < floor))
        ? Math.min(0.0, floor - windowMax)
        : step;
    if (windowMax < floor) {
      // keep the floor signal-capable: lift a below-floor window up to it
      clamped = Math.max(clamped, floor - windowMax);
    }
    stepSize = clamped;
    return clamped;
  }

  /** The walk samples a probe must take before stray hits may end it, from the ladder's rung. */
  private int probeCommitment() {
    int length = probeBackoffLength;
    return (length >= HILL_CLIMBER_PROBE_BACKOFF_MAX) ? 10 : (length >= 32) ? 2 : 0;
  }

  /** How a probe's walk ends. */
  private enum ProbeEnding {
    /** The hit rate collapsed below the probe's start: undo without escalating the ladder. */
    CRASHED,
    /** Density validated the probed direction: keep the position and make probes cheap again. */
    CONFIRMED,
    /** A completed, failed experiment: undo and double the refractory ladder. */
    FAILED,
    /** No ending fired: take the next bold-driver stride. */
    WALKING
  }
}

ben-manes / caffeine / #5683

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous