Algorithms.pudu

Pudu123 lines5.4 KB

Copy pathGitHub ↗

1/** @Domain.Algorithms.Module — how each limiter kind counts permits */2module PuduLangResilience.Domain.Algorithms34import Std.Math as Math5import PuduLangResilience.Domain.Permits as Permits6import PuduLangResilience.Utils.Numeric as Numeric78/** @Domain.Algorithms.Bucket — tokens left and when they were last topped up */9export type Bucket = { tokens: Int, stamp: Int }1011/** @Domain.Algorithms.Window — permits used since the window began */12export type Window = { used: Int, start: Int }1314/** @Domain.Algorithms.Segments — permits used per segment, oldest first */15export type Segments = { counts: Array[Int], start: Int }1617/// Permits held while an execution runs and handed back when it ends.18export fn concurrency(limit: Int) -> Permits.Algorithm[Int] {19  Permits.Algorithm {20    refresh: fn(held: Int, _now: Int) -> Int { held },21    available: fn(held: Int) -> Int { held },22    take: fn(held: Int, permits: Int) -> Int { held - permits },23    giveBack: fn(held: Int, permits: Int) -> Int { Math.min(held + permits, limit) },24    retryAfter: fn(_held: Int, _now: Int, _permits: Int) -> Option[Int] { None },25    replenish: fn(held: Int) -> (Int, Bool) { (held, false) }26  }27}2829/// A bucket of at most `limit` tokens gaining `perPeriod` tokens every `period` milliseconds,30/// by itself when `automatic` and otherwise only when replenished by hand.31export fn tokenBucket(limit: Int, perPeriod: Int, period: Int, automatic: Bool) -> Permits.Algorithm[Bucket] {32  Permits.Algorithm {33    refresh: fn(held: Bucket, now: Int) -> Bucket {34      if !automatic { return held }35      let periods = Math.max(0, (now - held.stamp) / period)36      Bucket{tokens: Math.min(Numeric.add(held.tokens, Numeric.multiply(periods, perPeriod)), limit), stamp: held.stamp + periods * period}37    },38    available: fn(held: Bucket) -> Int { held.tokens },39    take: fn(held: Bucket, permits: Int) -> Bucket { Bucket{..held, tokens: held.tokens - permits} },40    giveBack: fn(held: Bucket, _permits: Int) -> Bucket { held },41    retryAfter: fn(held: Bucket, now: Int, permits: Int) -> Option[Int] {42      if !automatic { return None }43      let missing = permits - held.tokens44      let periods = (missing + perPeriod - 1) / perPeriod45      Some(Math.max(0, Numeric.multiply(periods, period) - (now - held.stamp)))46    },47    replenish: fn(held: Bucket) -> (Bucket, Bool) {48      if automatic { (held, false) } else { (Bucket{..held, tokens: Math.min(Numeric.add(held.tokens, perPeriod), limit)}, true) }49    }50  }51}5253/// At most `limit` permits in each window of `window` milliseconds, the window moving by itself54/// when `automatic` and otherwise only when replenished by hand.55export fn fixedWindow(limit: Int, window: Int, automatic: Bool) -> Permits.Algorithm[Window] {56  Permits.Algorithm {57    refresh: fn(held: Window, now: Int) -> Window {58      if !automatic { return held }59      let passed = (now - held.start) / window60      if passed <= 0 { held } else { Window{used: 0, start: held.start + passed * window} }61    },62    available: fn(held: Window) -> Int { limit - held.used },63    take: fn(held: Window, permits: Int) -> Window { Window{..held, used: held.used + permits} },64    giveBack: fn(held: Window, _permits: Int) -> Window { held },65    retryAfter: fn(held: Window, now: Int, _permits: Int) -> Option[Int] {66      if automatic { Some(Math.max(0, held.start + window - now)) } else { None }67    },68    replenish: fn(held: Window) -> (Window, Bool) {69      if automatic { (held, false) } else { (Window{..held, used: 0}, true) }70    }71  }72}7374/// At most `limit` permits in any `window` milliseconds, counted in `segments` equal segments;75/// the segments move by themselves when `automatic` and otherwise only when replenished by hand.76export fn slidingWindow(limit: Int, window: Int, segments: Int, automatic: Bool) -> Permits.Algorithm[Segments] {77  let length = window / segments78  Permits.Algorithm {79    refresh: fn(held: Segments, now: Int) -> Segments {80      if !automatic { return held }81      let passed = Math.max(0, (now - held.start) / length)82      Segments{counts: shifted(&held.counts, passed), start: held.start + passed * length}83    },84    available: fn(held: Segments) -> Int { limit - total(&held.counts) },85    take: fn(held: Segments, permits: Int) -> Segments {86      let last = held.counts.length() - 187      Segments{..held, counts: held.counts.slice(0, last).push(held.counts[last] + permits)}88    },89    giveBack: fn(held: Segments, _permits: Int) -> Segments { held },90    retryAfter: fn(held: Segments, now: Int, permits: Int) -> Option[Int] {91      if !automatic { return None }92      let missing = permits - (limit - total(&held.counts))93      var freed = 094      var index = 095      for count in held.counts {96        freed = freed + count97        if freed >= missing { return Some(Math.max(0, held.start + (index + 1) * length - now)) }98        index = index + 199      }100      None101    },102    replenish: fn(held: Segments) -> (Segments, Bool) {103      if automatic { (held, false) } else { (Segments{..held, counts: shifted(&held.counts, 1)}, true) }104    }105  }106}107108/// Segment counts after `steps` segments have passed: the oldest drop out and empty ones join.109export fn shifted(counts: &Array[Int], steps: Int) -> Array[Int] {110  let size = counts.length()111  let dropped = Math.min(steps, size)112  var next = counts.slice(dropped, size)113  while next.length() < size { next = next.push(0) }114  next115}116117/// The sum of the counts.118fn total(counts: &Array[Int]) -> Int {119  var sum = 0120  for count in counts { sum = Numeric.add(sum, count) }121  sum122}123