Permits.pudu

Pudu142 lines5.8 KB

Copy pathGitHub ↗

1/** @Domain.Permits.Module — permit accounting and the wait queue */2module PuduLangResilience.Domain.Permits34import Std.List as List5import PuduLangResilience.Utils.Numeric as Numeric67/** @Domain.Permits.Algorithm — how one kind of limiter counts permits */8export type Algorithm[S] = {9  refresh: fn(S, Int) -> S,10  available: fn(S) -> Int,11  take: fn(S, Int) -> S,12  giveBack: fn(S, Int) -> S,13  retryAfter: fn(S, Int, Int) -> Option[Int],14  replenish: fn(S) -> (S, Bool)15}1617/** @Domain.Permits.Order — which waiter is served first */18export type Order = Oldest | Newest1920/** @Domain.Permits.Waiter — one queued request */21export type Waiter = { ticket: Int, permits: Int }2223/** @Domain.Permits.Book — a limiter's counts and queue */24export type Book[S] = {25  held: S,26  waiters: Array[Waiter],27  evicted: Array[Int],28  nextTicket: Int,29  failed: Int,30  succeeded: Int,31  permitLimit: Int,32  queueLimit: Int,33  order: Order34}3536/** @Domain.Permits.Decision — the answer to a new request */37export type Decision = Grant | Deny(Option[Int]) | Queue(Int)3839/** @Domain.Permits.Turn — the answer to a waiter asking again */40export type Turn = Taken | Evicted | Waiting4142/// A book with no waiters over the algorithm state `held`.43export fn open[S](held: S, permitLimit: Int, queueLimit: Int, order: Order) -> Book[S] {44  Book{held: held, waiters: [], evicted: [], nextTicket: 1, failed: 0, succeeded: 0, permitLimit: permitLimit, queueLimit: queueLimit, order: order}45}4647/// The book at `now` after a request for `permits`. The request is granted when the permits are48/// available and no waiter comes first; otherwise it joins the queue when `mayQueue` and the49/// queue has room, evicting the oldest waiters when newest requests are served first; otherwise50/// it is denied. A request for more than the permit limit is always denied, and a request for no51/// permits is granted while any permit is available.52export fn request[S](book: &Book[S], algorithm: &Algorithm[S], now: Int, permits: Int, mayQueue: Bool) -> (Book[S], Decision) {53  let current = Book{..*book, held: (algorithm.refresh)(book.held, now)}54  let free = (algorithm.available)(current.held)55  if permits < 0 || permits > current.permitLimit { return deny(&current, None) }56  if permits == 0 { return if free > 0 { (current, Grant) } else { deny(&current, (algorithm.retryAfter)(current.held, now, 1)) } }57  let ahead = !current.waiters.isEmpty() && current.order == Oldest58  if free >= permits && !ahead { return (take(&current, algorithm, permits), Grant) }59  let retry = (algorithm.retryAfter)(current.held, now, permits)60  if !mayQueue || permits > current.queueLimit { return deny(&current, retry) }61  var queue = current.waiters62  var evicted = current.evicted63  var failed = current.failed64  if current.order == Newest {65    while queuedIn(&queue) + permits > current.queueLimit {66      evicted = evicted.push(queue[0].ticket)67      failed = failed + 168      queue = queue.slice(1, queue.length())69    }70  } else if queuedIn(&queue) + permits > current.queueLimit {71    return deny(&current, retry)72  }73  let ticket = current.nextTicket74  let joined = Book{..current, waiters: queue.push(Waiter{ticket: ticket, permits: permits}), evicted: evicted, failed: failed, nextTicket: ticket + 1}75  (joined, Queue(ticket))76}7778/// The book at `now` after the waiter holding `ticket` asks again. It takes its permits when it79/// is next in order and they are available.80export fn poll[S](book: &Book[S], algorithm: &Algorithm[S], now: Int, ticket: Int) -> (Book[S], Turn) {81  if List.contains(&book.evicted, ticket) {82    return (Book{..*book, evicted: book.evicted.filter(|held: Int| held != ticket)}, Evicted)83  }84  let current = Book{..*book, held: (algorithm.refresh)(book.held, now)}85  let next = match current.order {86    case Oldest => List.first(&current.waiters)87    case Newest => List.last(&current.waiters)88  }89  match next {90    case Some(waiter) => {91      if waiter.ticket == ticket && (algorithm.available)(current.held) >= waiter.permits {92        let served = Book{..current, waiters: current.waiters.filter(|held: Waiter| held.ticket != ticket)}93        (take(&served, algorithm, waiter.permits), Taken)94      } else {95        (current, Waiting)96      }97    }98    case None => (current, Waiting)99  }100}101102/// The book without the waiter holding `ticket`, counted as failed.103export fn withdraw[S](book: &Book[S], ticket: Int) -> Book[S] {104  Book{..*book, waiters: book.waiters.filter(|held: Waiter| held.ticket != ticket), evicted: book.evicted.filter(|held: Int| held != ticket), failed: book.failed + 1}105}106107/// The book with `permits` handed back.108export fn giveBack[S](book: &Book[S], algorithm: &Algorithm[S], permits: Int) -> Book[S] {109  Book{..*book, held: (algorithm.giveBack)(book.held, permits)}110}111112/// The book after one replenishment by hand, and whether the algorithm allows it.113export fn replenish[S](book: &Book[S], algorithm: &Algorithm[S]) -> (Book[S], Bool) {114  let next = (algorithm.replenish)(book.held)115  (Book{..*book, held: next[0]}, next[1])116}117118/// The permits available at `now`.119export fn available[S](book: &Book[S], algorithm: &Algorithm[S], now: Int) -> Int {120  (algorithm.available)((algorithm.refresh)(book.held, now))121}122123/// The permits all waiters are asking for.124export fn queued[S](book: &Book[S]) -> Int { queuedIn(&book.waiters) }125126/// The permits the given waiters are asking for.127fn queuedIn(waiters: &Array[Waiter]) -> Int {128  var total = 0129  for waiter in waiters { total = Numeric.add(total, waiter.permits) }130  total131}132133/// The book with `permits` taken and the grant counted.134fn take[S](book: &Book[S], algorithm: &Algorithm[S], permits: Int) -> Book[S] {135  Book{..*book, held: (algorithm.take)(book.held, permits), succeeded: book.succeeded + 1}136}137138/// The book with a denial counted, and the denial.139fn deny[S](book: &Book[S], retryAfter: Option[Int]) -> (Book[S], Decision) {140  (Book{..*book, failed: book.failed + 1}, Deny(retryAfter))141}142