Implementing distributed rate limit in Go
If you write a bug management system, with this
PeriodLimityou can limit each tester can only assign one bug to you per day. :P
Nowadays, microservices architecture is popular because it is necessary to reduce the overall complexity of the system. Dividing the risk of the system to the subsystem so as to maximize the stability of the system. And splitting the domain into different subsystems so that each subsystem can be developed, tested and released independently. So the development efficiency can be significantly improved.
But at the same time, it also brings problems, such as: the call chain is too long, the complexity of deployment architecture is increased, and various middleware needs to support distributed scenarios. To ensure the proper operation of microservices, service governance is indispensable, which usually includes: rate limit, degradation, and circuit breaker.
Rate limiting refers to limiting the frequency of the calls so as not to exceed the upper limit of the bearer and bring down the system. For example
- e-commerce spike scenario
- API for different customers to limit the QPS
Commonly used rate limiting algorithms are
- Fixed time window rate limit
- Sliding time window rate limit
- Leaky bucket rate limit
- Token bucket rate limit
This article focuses on the fixed time window rate limit algorithm.
Algorithm
Starting from a certain point in time, each request comes with +1 request number, while determining whether the number of requests in the current time window exceeds the limit, then the request is rejected if it exceeds the limit, and then the counter is cleared at the beginning of the next time window to wait for the request.
Advantages and disadvantages
Pros
Simple and efficient implementation, especially suitable for limiting a user to 10 posts a day, 5 SMS verification codes, 5 login attempts, etc. Such scenarios are very common in practices.
Disadvantages
The disadvantage of fixed time window rate limit is that it cannot handle burst request scenarios in critical areas.
Suppose the rate is limited to 100 requests per second, and the user starts to make 200 requests in 1s in the middle 500ms, then all 200 requests can be passed. This does not match our expectation of 100 requests per second, and the root cause is that the granularity of the rate limit is too coarse.
go-zero code implementation
core/limit/periodlimit.go
Use redis expire time in go-zero to simulate a fixed time window.
redis lua script.
-- KYES[1]:limiter key
-- ARGV[1]:qos,maximum number of requests per unit time
-- ARGV[2]:unit rate limiter window time
-- maximum number of requests, equal to p.quota
local limit = tonumber(ARGV[1])
-- window that is a unit limit period, here use expired simulated window effect, equal to p.permit
local window = tonumber(ARGV[2])
-- the number of requests + 1, to get the total number of requests
local current = redis.call("INCRBY",KYES[1],1)
-- If this is the first request, set the expiration time and return success
if current == 1 then
redis.call("expire",KYES[1],window)
return 1
-- return success if current request is less than limit
elseif current < limit then
return 1
-- if current number of requests == limit then return last request
elseif current == limit then
return 2
-- return if the number of requests > limit fails
else
return 0
endFixed time window limit definition
type (
// PeriodOption defines the method to customize a PeriodLimit.
// A common option parameter pattern in go
// This mode is recommended for setting parameters if they are very large
PeriodOption func(l *PeriodLimit) // A PeriodLimit is used to limit requests during a period of time.
// Fixed time window limiter
PeriodLimit struct {
// Window size in s
period int
// The upper limit of requests
quota int
// Store
limitStore *redis.Redis
// key prefix
keyPrefix string
// Linear limit, this option can be turned on to achieve periodic limit
// For example, if quota=5, the actual value of quota may be 5.4.3.2.1 showing a periodic change
align bool
}
)
Note the align parameter, when align=true the request limit will vary periodically. For example, if quota=5, the actual quota may be 5.4.3.2.1 showing periodic changes.
Rate limit logic
In fact, the rate limit logic is implemented in the above lua script, and it is important to note that the return value
- 0: indicates an error, such as a possible redis failure or overload
- 1: allowed
- 2: allowed but the current window has reached the upper limit, if you are running a batch business, then you can sleep for a while and wait for the next window (the author is very careful)
- 3：rejected
// Take requests a permit, it returns the permit state.
// Execute the rate restriction
// Take note of the return values.
// 0: indicates an error, such as a possible redis failure or overload
// 1: Allowed
// 2: Allowed but the limit has been reached in the current window
// 3: denied
func (h *PeriodLimit) Take(key string) (int, error) {
// Execute the lua script
resp, err := h.limitStore.Eval(periodScript, []string{h.keyPrefix + key}, []string{
strconv.Itoa(h.quota),
strconv.Itoa(h.calcExpireSeconds()),
})
if err ! = nil {
return Unknown, err
} code, ok := resp.(int64)
if !ok {
return Unknown, ErrUnknownCode
} switch code {
case internalOverQuota:
return OverQuota, nil
case internalAllowed:
return Allowed, nil
case internalHitQuota:
return HitQuota, nil
default:
return Unknown, ErrUnknownCode
}
}
This fixed window limit may be used to restrict a user to send only 5 CAPTCHA messages a day, at this point we need to correspond to the local time zone and actually the limit time should start from 0'clock, at this point we need additional alignment (set align to true).
// Calculate the expiration time which is the window time size
// if align==true
// Linear rate limiting, with this option on you can achieve periodic rate limiting
// For example, if quota=5, the actual value of quota may be 5.4.3.2.1 showing a periodic variation
func (h *PeriodLimit) calcExpireSeconds() int {
if h.align {
now := time.Now()
_, offset := now.Zone()
unix := now.Unix() + int64(offset)
return h.period - int(unix%int64(h.period))
} return h.period
}
Project address
https://github.com/zeromicro/go-zero
Feel free to use go-zero and star support us!
Join FAUN: Website 💻|Podcast 🎙️|Twitter 🐦|Facebook 👥|Instagram 📷|Facebook Group 🗣️|Linkedin Group 💬| Slack 📱|Cloud Native News 📰|More.
If this post was helpful, please click the clap 👏 button below a few times to show your support for the author 👇
