Install
One module, one dependency beyond the standard library. Durations are Spans, so moondate comes with it.
moon add moonbitstack/moonward@0.2.1
The package is imported as @moonward. Nothing else is needed: there is no configuration, no runtime, no global to install.
import {
"moonbitstack/moonward",
"moonbitstack/moondate",
}
The first call
Ask for permission, and settle the answer when the call is over. allow returns a Promise or nothing, and the promise is settled exactly once with pass or fail. Both take the clock reading the call finished at.
let now = 0L
let breaker = @moonward.Breaker::new()
match breaker.allow(now, 0.42) {
Some(call) => call.pass(now)
None => println("backend refused")
}
println("empty window, ratio \{percent(breaker.ratio(now))}")
empty window, ratio 0%
0.42 is the draw, not a probability you choose: it is what your random number generator gave you this time, in [0, 1). A fresh breaker has no failures behind it, so nothing is refused and the draw is never consulted.
Reading the breaker
Ten good calls, then a backend that has stopped answering. The ratio is the fraction of calls the breaker would refuse at that instant — a number for a dashboard, and the same number allow compares the draw against.
let breaker = @moonward.Breaker::new()
let mut at = 0L
for _ in 0..<10 {
at = tick(breaker, at, true)
}
println("10 good ratio \{percent(breaker.ratio(at))}")
for _ in 0..<15 {
at = tick(breaker, at, false)
}
println("15 bad ratio \{percent(breaker.ratio(at))}")
10 good ratio 0% 15 bad ratio 22% 15 more ratio 51%
A success pays for one and a half calls, and every backend is allowed five calls regardless, so a window has to be about a third failures before anything is refused. Past that the fraction climbs with every bad call and falls again as the failures age out of the ten-second window.
failing and working count buckets, not calls: the run of all-failure buckets at the head of the window and the run of all-success ones. A bucket that saw both ends both runs.
A bucket
A token bucket holds a burst and refills at a rate. Two tokens a second with room for three: three calls go through at once, the fourth does not, and half a second later there is another token.
let bucket = @moonward.Bucket::new(2.0, burst=3.0)
let took = [0, 1, 2, 3].map(_ => bucket.take(0L))
println("took \{@debug.to_string(took)}")
println("tokens \{bucket.tokens(0L)}")
println("next \{bucket.next(0L).nanos / 1_000_000L} ms")
took [true, true, true, false] tokens 0 next 500 ms
next is what a refusal is worth telling the caller: how long until a token is there, without spending one to find out. It is the number a Retry-After header is made of.
Quotas
A rate is not a quota. "A thousand a day" counted as a rate would let a client spend the day's allowance before breakfast. Both of these count instead — one over any window-long stretch, one per fixed period.
let second = @moondate.Span::new(seconds=1L)
let sliding = @moonward.Sliding::new(2, second)
let period = @moonward.Period::new(2, second, align=true)
println("sliding \{@debug.to_string([0L, 1L, 2L].map(_ => sliding.take(0L)))}")
println("period \{@debug.to_string([0L, 1L, 2L].map(_ => period.take(0L)))}")
println("left \{sliding.left(0L)} of 2")
sliding [true, true, false] period [Under, Hit, Over] left 0 of 2
Hit is the call that lands exactly on the quota. It is admitted, but it is told apart from Under because it is the last one — the moment to warn rather than wait for the next refusal.
The difference between the two shows up under bursty traffic: a period can spend one quota at the end of a period and another at the start of the next, so forty calls can pass in a second that allows twenty. The limiters example runs exactly that and prints the three answers side by side.
Room
A concurrency limit is the one primitive here that has nothing to do with time. Two slots, three calls: the third is answered no rather than queued, which is what keeps a queue from becoming the outage.
let gate = @moonward.Gate::new(2)
println("enter \{gate.enter()} \{gate.enter()} \{gate.enter()}")
println("held \{gate.held()}")
gate.leave()
println("after one leaves, held \{gate.held()}, enter \{gate.enter()}")
enter true true false held 2 after one leaves, held 1, enter true
leave is safe to call more often than enter succeeded: it stops at zero rather than going negative.
Load
The shedder is the last thing between an overloaded server and its event loop. It refuses work only when the server is both hot and full: the CPU at or over the threshold, and more calls in flight than the server has shown it can finish.
let shedder = @moonward.Shedder::new()
let open : Array[(@moonward.Ticket, Int64)] = []
let mut refused = 0
for i in 0L..<2000L {
let now = ms(i)
// ... settle every ticket whose 50 ms are up ...
// Idle at first, then the CPU pins at 95%.
let cpu = if i < 500L { 200 } else { 950 }
match shedder.allow(now, cpu) {
Some(ticket) => open.push((ticket, i + 50L))
None => refused = refused + 1
}
}
println("in flight \{shedder.flying()} refused \{refused} of 2000")
in flight 26 refused 720 of 2000
A CPU spike with nothing queued refuses nothing, and neither does a long queue on an idle CPU — both have to be true. The capacity it compares against is the busiest bucket's passes per millisecond times the fastest bucket's mean response time, scaled down as the CPU nears 100%.
Waiting
Retries without jitter synchronise: every client that failed together comes back together, and one outage becomes two. The policy carries the schedule, the caller carries the randomness.
let rigid = @moonward.Backoff::new(jitter=Rigid)
let full = @moonward.Backoff::new(jitter=Full)
let spread = @moonward.backoff
println(@debug.to_string([1, 2, 3].map(r => (spread.ceiling(r).nanos / 1_000_000L).to_int())))
println(@debug.to_string(rigid.schedule(randoms=[0.9, 0.9]).map(d => (d.nanos / 1_000_000L).to_int())))
println(@debug.to_string(full.schedule(randoms=[0.9, 0.9]).map(d => (d.nanos / 1_000_000L).to_int())))
println(@debug.to_string(spread.schedule(randoms=[0.9, 0.1]).map(d => (d.nanos / 1_000_000L).to_int())))
println("more \{spread.more(2)} \{spread.more(3)}")
ceiling [100, 200, 400] ms rigid [100, 200] ms full [90, 180] ms spread [116, 168] ms more true false
ceiling is public and jitter-free on purpose: it is the number to compare against when the same policy is written somewhere else. more(3) is false because the preset allows three attempts, and the first attempt counts.
Five strategies ship in Jitter: Rigid, Full, Equal, Decorrelated and Spread(f), which keeps the wait within f of the ceiling in either direction and is what the preset uses at a fifth.
A budget
A deadline is a start and a budget, and it answers two questions: has it run out, and how much is left. A budget of zero or less never expires, so a timeout left unset cannot time everything out at once.
let deadline = @moonward.Deadline::start(@moondate.Span::new(seconds=2L), 0L)
println("at 1.5 s expired \{deadline.expired(ms(1500L))}")
println("at 2.0 s expired \{deadline.expired(ms(2000L))}")
match deadline.remaining(ms(1500L)) {
Some(left) => println("left \{left.nanos / 1_000_000L} ms")
None => println("left none")
}
at 1.5 s expired false at 2.0 s expired true left 500 ms
remaining returns None rather than zero when there is no budget, because an unlimited budget has no finite remainder — and a caller should not treat "no deadline" as "almost out".
A window of your own
The breaker and the shedder are both a rolling window with arithmetic on top. The window itself is public, and any type with a Default can be a bucket — here, a count of calls per hundred milliseconds.
struct Hits {
mut calls : Int64
} derive(Default, Debug)
let window : @moonward.Window[Hits] = @moonward.Window::new(
size=4,
window=@moondate.Span::new(millis=400L),
)
window.slot(0L).calls += 3
window.slot(ms(100L)).calls += 5
window.slot(ms(150L)).calls += 2
let mut seen = 0L
window.each(ms(150L), b => seen = seen + b.calls)
println("width \{window.width().nanos / 1_000_000L} ms, \{window.size()} buckets")
println("calls \{seen} inside the window")
width 100 ms, 4 buckets calls 10 inside the window
Writing at a later now clears the buckets the gap swept past. Reading at a later now skips them without clearing, so a window nobody writes to still ages out, and two reads at the same now agree.
each visits the live buckets oldest first. Pass current=false to leave out the bucket now falls in: it has seen only part of its time, and a reading that takes the busiest or the fastest bucket should not compare a partial one against whole ones.
Next
Four programs in the repository, each one runnable as it stands.
The API reference lists every type and method with its parameters and defaults. The bay lets you turn the knobs and watch the same code answer.