Class LatencyAdaptiveGroupSelector

java.lang.Object
com.linkedin.venice.stats.routing.LatencyAdaptiveGroupSelector

public class LatencyAdaptiveGroupSelector extends Object
Latency-adaptive weighted group selection, shared by the router and fast-client routing strategies. Given each group's measured average latency it picks a group by a weighted-random draw whose skew adapts to the slowest group's latency: even routing while every group is fast, steering share onto the faster groups as the slowest group slows.
   strength(g) = 1 / max(latency(g), MIN_LATENCY_MS)                     // faster group => stronger
   slowest     = max(latency)                  over measured groups (ms)
   skew        = 0                                          if slowest <= evenUntilLatencyMs
                 1                                          if slowest >= fullSkewAtLatencyMs
                 ((slowest - evenUntil) / (fullSkew - evenUntil))^m  otherwise
   share(g)    = (1 - skew) * (1 / G)  +  skew * strength(g) / sum(strength)
   share(g)    = max(share(g), PROBE_FLOOR_FRACTION * (1 / G))           // never fully starve a group
 

Equal-latency groups keep equal strength, so all-slow-but-equal routing stays even; an unmeasured group (latency <= 0) is neutral and excluded from the skew, and the probe floor keeps every group observable.

Latency is tracked per key-count bucket so request size does not conflate a slow host with a large request: each request maps to a bucket by key count, reading the signal and recording its sample in that bucket. Bucket boundaries and per-bucket full-skew thresholds are supplied pre-parsed; bucketKeyForKeyCount(int) exposes the mapping so callers record into the bucket the selector reads. Each bucket's stay-even threshold is a fixed fraction of its full-skew threshold, and a bucket under minSampleCount samples for a group falls back to even routing there.

Holds no per-request state; thread-safe given thread-safe providers and randomSupplier. The only mutable state is a lock-free throttle timestamp for the optional periodic weight log, which does not affect selection.

  • Field Details

    • MAX_ALLOWED_GROUP

      public static final int MAX_ALLOWED_GROUP
      See Also:
    • DEFAULT_WEIGHT_LOG_INTERVAL_MS

      public static final long DEFAULT_WEIGHT_LOG_INTERVAL_MS
      Default interval (ms) between periodic per-group weight log lines at INFO; <= 0 disables.
      See Also:
    • DEFAULT_EVEN_UNTIL_LATENCY_MS

      public static final double DEFAULT_EVEN_UNTIL_LATENCY_MS
      Default single-bucket stay-even threshold (ms): skew stays 0 while the slowest group is at or below it.
      See Also:
    • DEFAULT_FULL_SKEW_AT_LATENCY_MS

      public static final double DEFAULT_FULL_SKEW_AT_LATENCY_MS
      Default full-skew threshold (ms): routing reaches its full split (skew == 1) once the slowest hits it.
      See Also:
    • DEFAULT_EVEN_UNTIL_FRACTION

      public static final double DEFAULT_EVEN_UNTIL_FRACTION
      Default fraction of a bucket's full-skew threshold used as its stay-even threshold (the 10 / 30 ratio).
      See Also:
    • DEFAULT_MIN_SAMPLE_COUNT

      public static final long DEFAULT_MIN_SAMPLE_COUNT
      Default minimum per-(group, bucket) samples before a bucket's average latency is acted on.
      See Also:
    • DEFAULT_INTERPOLATION_EXPONENT

      public static final double DEFAULT_INTERPOLATION_EXPONENT
      Default in-band ramp exponent m: 1.0 is linear, > 1 steepens toward the full-skew end.
      See Also:
    • MIN_LATENCY_MS

      public static final double MIN_LATENCY_MS
      Lower bound on a group's latency before inverting it into a strength, so near-zero latency stays bounded.
      See Also:
    • PROBE_FLOOR_FRACTION

      public static final double PROBE_FLOOR_FRACTION
      Minimum share every group retains, as a fraction of the even share 1 / G, so no group is fully starved.
      See Also:
  • Constructor Details

    • LatencyAdaptiveGroupSelector

      public LatencyAdaptiveGroupSelector(IntToDoubleFunction latencyProvider)
      Single-bucket selector with default knobs and ThreadLocalRandom; see the five-argument constructor.
    • LatencyAdaptiveGroupSelector

      public LatencyAdaptiveGroupSelector(IntToDoubleFunction latencyProvider, double evenUntilLatencyMs, double fullSkewAtLatencyMs, double interpolationExponent, DoubleSupplier randomSupplier)
      Single-bucket (non size-aware) selector. All key counts map to one bucket with dead-band [evenUntilLatencyMs, fullSkewAtLatencyMs] and no minimum-sample floor.
      Parameters:
      latencyProvider - group id -> avg response time in ms; non-positive = not measured (neutral).
      evenUntilLatencyMs - stay-even threshold in ms; >= 0 and < fullSkewAtLatencyMs.
      fullSkewAtLatencyMs - full-skew threshold in ms; > evenUntilLatencyMs.
      interpolationExponent - ramp exponent m between thresholds (1.0 = linear); > 0.
      randomSupplier - uniform random double in [0, 1); injectable for deterministic tests.
    • LatencyAdaptiveGroupSelector

      public LatencyAdaptiveGroupSelector(LatencyAdaptiveGroupSelector.GroupBucketLatencyProvider latencyProvider, LatencyAdaptiveGroupSelector.GroupBucketSampleCountProvider sampleCountProvider, NavigableMap<Integer,Integer> fullSkewMsByLowerBound, double evenUntilFraction, double interpolationExponent, long minSampleCount, DoubleSupplier randomSupplier)
      Size-aware (bucketed) selector. Latency is tracked and thresholds applied per key-count bucket.
      Parameters:
      latencyProvider - (groupId, bucketKey) -> avg response time in ms; non-positive = not measured.
      sampleCountProvider - (groupId, bucketKey) -> sample count; below minSampleCount = unmeasured.
      fullSkewMsByLowerBound - bucket lower bound -> full-skew threshold ms; non-empty, starts at key 1, positive.
      evenUntilFraction - fraction of a bucket's full-skew threshold used as its stay-even threshold; (0, 1).
      interpolationExponent - ramp exponent m between thresholds (1.0 = linear); > 0.
      minSampleCount - minimum per-(group, bucket) samples before the average is acted on; >= 0.
      randomSupplier - uniform random double in [0, 1); injectable for deterministic tests.
  • Method Details

    • bucketKeyForKeyCount

      public int bucketKeyForKeyCount(int keyCount)
      The inclusive lower key-count bound identifying the bucket a keyCount-key request falls into. Callers record a request's sample under this same key so the selector reads a size-matched signal; below range clamps to bucket 0.
    • selectGroup

      public int selectGroup(int groupCount, int startGroupId)
      Single-bucket selection across all groups; selectGroup(int, int, int, int) with no exclusion.
    • selectGroup

      public int selectGroup(int groupCount, int startGroupId, int excludedGroupId)
      Single-bucket weighted-random selection, optionally excluding one group. Retained for the non size-aware path.
    • selectGroup

      public int selectGroup(int groupCount, int startGroupId, int excludedGroupId, int keyCount)
      Weighted-random reservoir selection across the groups for a request of keyCount keys, optionally excluding one group. The key count selects the bucket whose latency signal and thresholds drive the draw; each candidate is adopted with probability share(g) / cumulativeShare, so the final selection probability is proportional to share(g) in a single pass. The scan starts at startGroupId only to avoid biasing toward group 0.
      Parameters:
      groupCount - number of groups; must be in [1, MAX_ALLOWED_GROUP].
      startGroupId - group id the scan starts from (typically requestId % groupCount).
      excludedGroupId - group to exclude from selection and skew (e.g. the group already tried); -1 excludes none.
      keyCount - number of keys in the request, used to pick the key-count bucket.
    • selectGroup

      public int selectGroup(int groupCount, int startGroupId, int excludedGroupId, int keyCount, double fullSkewMs)
      As selectGroup(int, int, int, int) with this request's full-skew threshold (<= 0 keeps the bucket's; stay-even scales by the same fraction), so callers can follow a runtime threshold such as a retry policy.
    • setWeightLogIntervalMs

      public void setWeightLogIntervalMs(long weightLogIntervalMs)
      Sets how often (ms) per-group weights are logged at INFO (<= 0 disables); default DEFAULT_WEIGHT_LOG_INTERVAL_MS.
    • setLogContext

      public void setLogContext(String logContext)
      Sets a short identifier (e.g. "router") included in the periodic weight log line for attribution.
    • formatWeights

      public String formatWeights(int groupCount, int keyCount)
      Renders the routing picture for the keyCount-key request's bucket as one log line. Pure.