Common current limiting algorithms
Fixed window counter algorithm
The fixed window counter algorithm divides time into fixed-sized windows, such as 1 second. In each window, the service records the number of requests it receives. If the number of requests in one window exceeds a preset threshold, the new request will be denied until the next window is entered.
This algorithm is simple and easy to implement, but may cause request bursts near the window boundary. For example, if the window size is 1 second and the threshold is 100, then at the boundary of 1 second, the service may process 200 requests in a short time.
Sliding window counter algorithm
The sliding window counter algorithm attempts to solve the request burst problem in the fixed window counter algorithm. It divides the window into smaller subwindows, for example, dividing 1 second into 10 100 millisecond subwindows. Each time a request is received, the service updates the counter of the current subwindow. The service checks the sum of counters of the past N subwindows, and if this sum exceeds the threshold, the new request will be denied.
This algorithm can better smooth request traffic, but it is relatively complex to implement because it requires tracking counters for multiple subwindows.
Token bucket algorithm
The token bucket algorithm maintains a token bucket containing a certain number of tokens. The token is added to the bucket at a constant rate until the bucket's capacity is reached. Each time a request is received, the service tries to get a token from the bucket. If there are enough tokens in the bucket, the request is allowed to be processed; if there are not enough tokens, the request is denied.
The token bucket algorithm allows for short request bursts, because during low traffic times, the token can accumulate to the bucket's capacity. This algorithm performs well in practice, but is relatively complex to implement.
Leak bucket algorithm
The leaky bucket algorithm uses a queue to simulate a leaky bucket. The request is entered into the queue as a drop of water, removed from the queue at a constant rate and processed. If the queue is full, new requests will be denied.
The leaky bucket algorithm can smooth request traffic, but it cannot handle burst traffic because the request processing rate is fixed. Implementing a leak bucket algorithm is also relatively complex, because it is necessary to use a timer or other mechanism in the background to process requests in the queue at a constant rate.
time/rate
Main methods
-
NewLimiter(limit Limit, burst int) *Limiter: Create a new current limiter with parameters including the number of events allowed per second and the token bucket capacity (burst). -
(lim *Limiter) Allow() bool: Check if there are available tokens in the token bucket. If a token is available, a token is taken from the bucket and returns true; otherwise, false is returned. -
(lim *Limiter) AllowN(now , n int) bool: andAllow()Similar, but check whether n tokens are available. If there are enough tokens, take n tokens from the bucket and return true; otherwise, return false. -
(lim *Limiter) Wait(ctx ) error: Blocking and waiting until there is an available token. If context is cancelled or timed out during the waiting process, an error will be returned. -
(lim *Limiter) WaitN(ctx , n int) error: Block and wait until there are n available tokens. If context is cancelled or timed out during the waiting process, an error will be returned. -
(lim *Limiter) Reserve() *Reservation: Returns a reserved tokenReservationObject. You can wait for the reservation token or cancel the reservation as needed. -
(lim *Limiter) ReserveN(now , n int) *Reservation: Similar toReserve(), but reserve n tokens.
The role of each method
-
NewLimiterUsed to create a new current limiter instance. -
AllowandAllowNUsed to quickly check if there are enough tokens available, these methods are non-blocking. -
WaitandWaitNUsed to block and wait until enough tokens are available, these methods will block. -
ReserveandReserveNUsed for reserved tokens, allowing you to wait for reserved tokens or cancel reservations as needed.
How does time/rate achieve current limiting
time/rateThe package implements current limiting based on the token bucket algorithm. The current limiter passes a constant rate (limit) Add token to the token bucket until the bucket's capacity (burst) reaches the upper limit. Whenever a request is processed, the current limiter tries to retrieve one or more tokens from the token bucket.
AllowandAllowNMethod check whether there are enough tokens in the token bucket. If there are not enough tokens, these methods will immediately return false, indicating that the request should be rejected.WaitandWaitNThe method will block and wait until enough tokens are available. If the context is cancelled or timed out during the waiting process, these methods will return an error indicating that the request was denied.ReserveandReserveNThe method provides a more flexible way to reserve tokens, where you can wait for the reserved token or cancel the reservation as needed.
Through these methods,time/rateThe current limiter can control the rate at which requests are processed to ensure that it does not exceed the set limit. By adjusting the token generation rate and token bucket capacity, you can adjust the current limiting policy based on actual needs and system load.
Source code analysis
Definition of token bucket current limiter
existIn the file, it is definedLimiterStructure:
type Limiter struct {
mu
limit Limit
tokens float64
// last is the time when the token bucket was last updated last
// The clock used to adjust the token bucket update time clock Clock
// Timer for sleeping in Wait series methods sleepFn func()
}LimiterThe structure contains some key attributes, such as the token generation rate (limit), current number of tokens (tokens) and last updated time (last）。
Token bucket update
time/rateOne of the core functions in the package isreserveN, it is responsible for reserveing N tokens. During this process, the token bucket is updated according to time.
func (lim *Limiter) reserveN(now , n int) *Reservation {
()
defer ()
// Update the token bucket now, tokens := (now)
// Calculate the difference between the required number of tokens and the currently available number of tokens delta := float64(n) - tokens
// Calculate the waiting time waitDuration := (delta)
// Update the token bucket status tokens -= float64(n)
= (waitDuration)
= tokens
return &Reservation{
ok: true,
lim: lim,
tokens: n,
timeToAct: (waitDuration),
}
}existreserveNIn the function, first calladvanceFunction to update the token bucket:
func (lim *Limiter) advance(now ) (, float64) {
last :=
// Calculate the elapsed time since the last update elapsed := (last)
// Calculate the number of generated tokens based on the elapsed time delta := () * float64()
// Update the number of tokens in the token bucket, but not exceed the token bucket capacity tokens := (+delta, float64(()))
return now, tokens
}advanceThe function updates the token bucket based on time, calculates the number of tokens generated since the last update, and adds a new token to the bucket, but does not exceed the bucket's capacity.
Token reservation and waiting
existreserveNIn the function, first calculate the difference between the required number of tokens and the currently available number of tokens. Then calculate the waiting time based on the difference. If the waiting time is positive, it means that you need to wait for a period of time
Only then can you get enough tokens. Finally, update the token bucket status and subtract the required number of tokens from the current number of tokens.
reserveNThe function returns aReservationObject, which contains information such as the number of tokens reserved, waiting time, etc.ReservationThe structure is defined as follows:
type Reservation struct {
ok bool
lim *Limiter
tokens int
timeToAct
}ReservationObjects provide some methods, such asDelay(Return the time needed to wait) andCancel(Cancel reservation). These methods allow users to wait for the reserved token when needed, or to cancel the reservation when the token is no longer needed.
Public API
time/ratePackage provides a series of public APIs, such asAllow, AllowN, Wait, WaitN, ReserveandReserveN. These methods are based onreserveNEncapsulation of functions. For example,AllowThe method simply checks whether the reserved waiting time is zero:
func (lim *Limiter) Allow() bool {
return ((), 1)
}
func (lim *Limiter) AllowN(now , n int) bool {
return (now, n).Delay() == 0
}Similarly,WaitandWaitNThe method will block the waiting until the reserved waiting time has passed:
func (lim *Limiter) Wait(ctx ) error {
return (ctx, 1)
}
func (lim *Limiter) WaitN(ctx , n int) error {
if n > () {
return ("rate: Wait(n=%d) exceeds limiter's burst %d", n, ())
}
r := ((), n)
delay := (())
if delay == 0 {
return nil
}
t := (delay, )
defer ()
select {
case <-():
()
return ()
case <-:
return nil
}
}Anyway,time/rateThe package realizes current limit through the token bucket algorithm. It provides a series of APIs that allow users to flexibly control request rates in different scenarios. Internal implementation mainly depends onreserveNFunctions to update the token bucket status and wait or reserve the token as needed.
This is the article about the detailed explanation of the use and implementation of Golang official current limiter time/rate. For more relevant content on Golang current limiter time/rate, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!