Documentation
¶
Overview ¶
Package rate provides a rate limiter.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Limit ¶
type Limit float64
Limit defines the maximum frequency of some events. Limit is represented as number of events per second. A zero Limit is invalid.
type Limiter ¶
type Limiter struct {
// contains filtered or unexported fields
}
A Limiter controls how frequently events are allowed to happen. It implements a token bucket of a particular size b, initially full and refilled at rate r tokens per second. Informally, in any large enough time interval, the Limiter limits the rate to r tokens per second, with a maximum burst size of b events. Use NewLimiter to create non-zero Limiters.
func NewLimiter ¶
NewLimiter returns a new Limiter that allows events up to rate r and permits bursts of at most b tokens.
type Value ¶ added in v1.38.0
type Value struct {
// HalfLife specifies how quickly the rate reacts to rate changes.
//
// Specifically, if there is currently a steady-state rate of
// 0 events per second, and then immediately the rate jumped to
// N events per second, then it will take HalfLife seconds until
// the Value represents a rate of N/2 events per second and
// 2*HalfLife seconds until the Value represents a rate of 3*N/4
// events per second, and so forth. The rate represented by Value
// will asymptotically approach N events per second over time.
//
// In order for Value to stably represent a steady-state rate,
// the HalfLife should be larger than the average period between
// calls to Value.Add.
//
// A zero or negative HalfLife is by default 1 second.
HalfLife time.Duration
// contains filtered or unexported fields
}
Value measures the rate at which events occur, exponentially weighted towards recent activity. It is guaranteed to occupy O(1) memory, operate in O(1) runtime, and is safe for concurrent use. The zero value is safe for immediate use.
The algorithm is based on and semantically equivalent to exponentially weighted moving averages (EWMAs), but modified to avoid assuming that event samples are gathered at fixed and discrete time-step intervals.
In EWMA literature, the average is typically tuned with a λ parameter that determines how much weight to give to recent event samples. A high λ value reacts quickly to new events favoring recent history, while a low λ value reacts more slowly to new events. The EWMA is computed as:
zᵢ = λxᵢ + (1-λ)zᵢ₋₁
where:
- λ is the weight parameter, where 0 ≤ λ ≤ 1
- xᵢ is the number of events that has since occurred
- zᵢ is the newly computed moving average
- zᵢ₋₁ is the previous moving average one time-step ago
As mentioned, this implementation does not assume that the average is updated periodically on a fixed time-step interval, but allows the application to indicate that events occurred at any point in time by simply calling Value.Add. Thus, for every time Value.Add is called, it takes into consideration the amount of time elapsed since the last call to Value.Add as opposed to assuming that every call to Value.Add is evenly spaced some fixed time-step interval apart.
Since time is critical to this measurement, we tune the metric not with the weight parameter λ (a unit-less constant between 0 and 1), but rather as a half-life period t½. The half-life period is mathematically equivalent but easier for humans to reason about. The parameters λ and t½ and directly related in the following way:
t½ = -(ln(2) · ΔT) / ln(1 - λ) λ = 1 - 2^-(ΔT / t½)
where:
- t½ is the half-life commonly used with exponential decay
- λ is the unit-less weight parameter commonly used with EWMAs
- ΔT is the discrete time-step interval used with EWMAs
The internal algorithm does not use the EWMA formula, but is rather based on half-life decay. The formula for half-life decay is mathematically related to the formula for computing the EWMA. The calculation of an EWMA is a geometric progression [1] and is essentially a discrete version of an exponential function [2], for which half-life decay is one particular expression. Given sufficiently small time-steps, the EWMA and half-life algorithms provide equivalent results.
The Value type does not take ΔT as a parameter since it relies on a timer with nanosecond resolution. In a way, one could treat this algorithm as operating on a ΔT of 1ns. Practically speaking, the computation operates on non-discrete time intervals.
func (*Value) Add ¶ added in v1.38.0
Add records that n number of events just occurred, which must be a finite and non-negative number.
Source Files