Current limiters are a very important component in services and are common in gateway design, microservices, and ordinary backend applications. It can limit the frequency and speed of accessing services, preventing services from being overloaded and being flushed.
There are many algorithms for current limiters, common ones such as token bucket algorithm, funnel algorithm, semaphore, etc. This article mainly introduces the implementation of a current limiter based on the funnel algorithm. Text also provides several other open source implementation methods.
Current limiter implementation based on token bucket
In golang's official expansion package time (github/go/time), an implementation of a current limiter based on the token bucket algorithm is provided.
principle
Token bucket current limiter has two concepts:
- Token: You need to get the token every time before you can access it
- Bucket: There are buckets of a certain size, and you can put up a certain number of tokens in the bucket.
- Put frequency: Put tokens into the pass at a certain frequency, but the number of tokens cannot exceed the capacity of the bucket
Therefore, a token bucket current limiter can limit the access frequency of the bucket capacity within a time interval. Let’s take a look at the official implementation.
accomplish
Definition of current limiter
Here is the definition of a current limiter:
type Limiter struct {
limit Limit // The frequency of the bucket is placed (Limit is float64 type) burst int // The size of the bucket
mu
tokens float64 // The number of tokens remaining in the bucket last // The time I took the token recently lastEvent // Time of the latest current limit event}
Among them, the core parameters are limit and burst. burst represents the size of the bucket. In a practical sense, it can be understood as the concurrency amount that a service can carry; limit represents the frequency of putting it into the bucket. It can be understood as the number of requests that our service can handle within 1s under normal circumstances.
After the token is issued, it will be retained in the Reservation object, defined as follows:
type Reservation struct {
ok bool // Whether the conditions are met are assigned tokens lim *Limiter // Current limiter for sending tokens tokens int // The number of tokens timeToAct // Meet the time of issuance of tokens limit Limit // Token issuance speed}
The Reservation object describes the number of tokens that can be obtained after the timeToAct time is reached. (Because some requirements will provide reserved functions, timeToAct is not necessarily the current time.
How to limit current
The official current limiter provides blocking and waiting methods, and provides a self-maintaining and reserved method, but the core implementations are all the reserveN method below.
//N tokens are needed in the current time, and the maximum time you can wait is maxFutureResrve// The result will return an object with a reserved tokenfunc (lim *Limiter) reserveN(now , n int, maxFutureReserve ) Reservation {
()
// First, determine whether the frequency of the input is infinite. If it is infinite, it means that the current limit is not available. if == Inf {
// ...
}
// When you get the current time, the number of tokens that can be obtained, the last time you took the token last now, last, tokens := (now)
// Then update the number of tokens and remove the ones that need to be taken tokens -= float64(n)
// If tokens is a negative number, it means that you need to wait and calculate the waiting time var waitDuration
if tokens < 0 {
waitDuration = (-tokens)
}
// Calculate whether the allocation conditions are met // ① The size required to be allocated shall not exceed the bucket capacity // ② The waiting time does not exceed the set waiting time ok := n <= && waitDuration <= maxFutureReserve
// Finally construct a Reservation object r := Reservation{
ok: ok,
lim: lim,
limit: ,
}
if ok {
= n
= (waitDuration)
}
// and update the current limiter value if ok {
= now
= tokens
=
} else {
= last
}
()
return r
}
From an implementation perspective, limiter does not update the number of tokens in the current bucket every once in a while, but records the last access time and the number of tokens in the current bucket. When accessed again, the number of tokens in the current bucket is calculated by the last access time, and whether tokens can be issued is determined.
use
Let’s learn the use of the current limiter introduced above through a simple example.
limiter := ((100*), 10)
("/", func(w , r *) {
if () {// do something
("say hello")
}
})
_ = (":13100", nil)
Above, 1 token is placed in the token bucket every 100 ms, so when you access the interface in batches, you can see the following results:
2020/06/26 14:34:16 says hello has 18 records
2020/06/26 14:34:17 says hello has 10 records
2020/06/26 14:34:18 says hello has 10 records
...
At the beginning, the funnel is full, which can alleviate some sudden traffic. When the funnel is not empty, the frequency of access and the frequency of token putting becomes consistent.
Implementation of other current limiters
A current limiter is implemented in the uber open source library based on the funnel algorithm. The funnel algorithm can limit the request speed of traffic and play a role in cutting peaks and filling valleys./uber-go/ratelimit
Didi Open Source implements a current limiter middleware for http requests. Current limiting can be based on the following modes.
- Based on IP, path, method, header, authorized users and other stream limits
- Limit current through custom methods
- It also supports setting up stream limit data based on http header
- The implementation method is based on github/go/time, and different categories of data are stored in a data pool with timeout time.
- Code Address/didip/tollbooth
There are also current limiters based on semaphore implementation in golang network packets./golang/net/blob/master/netutil/It's also worth learning.
Summarize
The current limiter algorithm implemented by token bucket can allow burst traffic to enter our applications to a certain extent, so it is the most widely used in web applications.
In actual use, global current limiting is generally not done, but refined current limiting is done for certain features. For example: restrict access to crawlers through header, x-forward-for, etc., and restrict access to individual users through user information such as ip, session, etc.
This is the article about the use and implementation examples of Golang current limiter. For more related contents of Golang current limiter, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!