Implementation of a Distributed Rate Limiter

Prerequisite

Basic understanding of rate limiting algorithms. You can refer the following blog to understand about different rate limiting algorithms:

Assessment of all libraries explored

I found 4 candidates for rate limiter. Below is the comparison of all 4:

1. Basic Redis Rate Limit

Link: https://redislabs.com/redis-best-practices/basic-rate-limiting/

Pros: No need to import additional package

Cons: No burst capability. No information to retrieve remaining, retry and reset information.

2. Rate Limit by Gojek

Link: https://github.com/gojekfarm/go-ratelimit

Pros: Simple to implement because it is just an improvement from Basic Redis Rate Limit.

Cons: Not Future Proof. Last updated 4 years ago. No burst capability. No information to retrieve remaining, retry and reset information

3. Rate Limiter by Golang

Link: https://pkg.go.dev/golang.org/x/time/rate

Pros: Simple to implement. Works on token bucket algorithm internally which is quite fast.

Cons: Not a distributed rate limiter. Works fine on one server, fails to rate limit when multiple servers are involved. Doesn’t have redis built in.

4. Rate Limit by Go-Redis

Link: https://github.com/go-redis/redis_rate

Pros:

  • Powerful and more mature rate limit capability than other candidates.
  • Supports burst.
  • Supports Information to retrieve remaining, retry and Full reset. information.
  • Supports RPS, RPM, RPH by default.
  • Still maintained by developers (last update 5 month ago).

Cons:

  • Need to import additional package.
  • Burst value same as rate limit value.

Internal working of Go-Redis Library

After much consideration, I found out that Rate Limit by Go-Redis is the one that meets all our requirements. This library internally uses GCRA algorithm with built in lua script with redis to do rate limit calculations.

Link to library: https://github.com/go-redis/redis_rate

Below is the flow for how Rate Limiter by Go-Redis works:

Explanation:

  • Begin initialisation of redis connection and rate go-redis rate limit package.
  • When there is a first trigger after the initialisation of go-redis rate limit package, go-redis rate limit will load the lua script that has the core logic of how their rate limiter calculates the limit.
  • Rate limit calculation process will be triggered by using redis replicate command EvalSHA by passing SHA result into this command
  • The script will be perform all the calculations and returns the result.

Below is the script that is used by the library internally to calculate go-redis rate limit:

-- this script has side-effects, so it requires replicate commands mode
redis.replicate_commands()
local rate_limit_key = KEYS[1]
local burst = ARGV[1]
local rate = ARGV[2]
local period = ARGV[3]
local cost = tonumber(ARGV[4])
local emission_interval = period / rate
local increment = emission_interval * cost
local burst_offset = emission_interval * burst
-- redis returns time as an array containing two integers: seconds of the epoch
-- time (10 digits) and microseconds (6 digits). for convenience we need to
-- convert them to a floating point number. the resulting number is 16 digits,
-- bordering on the limits of a 64-bit double-precision floating point number.
-- adjust the epoch to be relative to Jan 1, 2017 00:00:00 GMT to avoid floating
-- point problems. this approach is good until "now" is 2,483,228,799 (Wed, 09
-- Sep 2048 01:46:39 GMT), when the adjusted value is 16 digits.
local jan_1_2017 = 1483228800
local now = redis.call("TIME")
now = (now[1] - jan_1_2017) + (now[2] / 1000000)
local tat = redis.call("GET", rate_limit_key)if not tat then
tat = now
else
tat = tonumber(tat)
end
tat = math.max(tat, now)local new_tat = tat + increment
local allow_at = new_tat - burst_offset
local diff = now - allow_at
local remaining = diff / emission_interval
if remaining < 0 then
local reset_after = tat - now
local retry_after = diff * -1
return {
0, -- allowed
0, -- remaining
tostring(retry_after),
tostring(reset_after),
}
end
local reset_after = new_tat - now
redis.call("SET", rate_limit_key, new_tat, "EX", math.ceil(reset_after))
local retry_after = -1
return {cost, remaining, tostring(retry_after), tostring(reset_after)}

Explanation :

  • Before running this script, go-redis rate limiter need to pass 4 parameters : Key, Rate, Burst, Period(seconds)
  • Example of EvalSHA run go-redis rate limiter script

evalsha b51fcf1fec2622e401ecd1495ba719a525362891 1 rate:project:1 7 7 1 1

  • They use “GET” and “SET” command to store and retrieve key value
  • The key value that are stored into redis are epoch time values.

Implementation Details

Following are the steps that I followed during implementation:

  • Store rate limit configuration in a config table corresponding to a particular client. Example configuration can look like this:
{ 
"limit": 20,
"rate_unit": "s",
"endpoint": "/rate_limiter/test/endpoint"
}

The above config means that this client has a threshold limit of 20 rps with endpoint /rate_limiter/test/endpoint

  • Bring all the rate limiting configuration of all the clients from DB on app initialisation and store it in some map.
  • Add a rate limiting middleware which will be executed for each request. The job of this middleware will be to calculate rate limit for every request and either reject or allow the request based on remaining number of requests.
  • Sample code for this rate limiter middleware can look like this:
import (
"fmt"
"github.com/go-redis/redis_rate/v9"
"github.com/path-to-your-repo/pkg/rate_limiter"
"github.com/path-to-your-repo/log"
"net/http"
"strconv"
"time"
)
// Handler rate limiter middlewarefunc (hm *helperModule) RateLimit(next http.HandlerFunc) http.HandlerFunc {
return func(w http.ResponseWriter, r *http.Request) {
var (
start = time.Now()
RateLimiterPrefixKey = "client_code:client_key:endpoint:%s:%d:%s"
ctx = r.Context()
clientCode = "test-client"
clientID = 12
limitRes *redis_rate.Result
laasClient entity.Client
err error
)
// default rate limiter config
rateLimiterConfig := rate_limiter.RateLimitConfig{
Limit: 40,
RateUnit: "second",
Endpoint: "/default/endpoint",
}
// Get Rate Limit Config for Client ID
// hm.rateLimiterConfig.RateLimiterConfigMap -> This is the map that // was created during app initialisation. Map structure looks like // this --> [2 --> rate_limiter.RateLimitConfig{Endpoint: //"/test/endpoint", Limit: 10, rate_unit: "second"}] which is //basically client_id --> rate_limiter.RateLimitConfig{}

if _, ok := hm.rateLimiterConfig.RateLimiterConfigMap[clientID]; !ok {
log.StdError(ctx, nil, err, "Rate limiter config missing for client ID: "+clientID)
} else {
rateLimiterConfig = hm.rateLimiterConfig.RateLimiterConfigMap[clientID]
}
// Begin Rate Limit Calculations
// CalculateRateLimit: Does all the calculations and returns the //number of allowed, remaining requests

limitRes, err = rate_limiter.CalculateRateLimit(ctx, fmt.Sprintf(RateLimiterPrefixKey, clientID, clientCode, rateLimiterConfig.Endpoint), rateLimiterConfig.Limit, rateLimiterConfig.RateUnit)
if err != nil {
log.StdError(ctx, nil, err, "error occurred while calculating rate limit")
next(w, r)
return
}
if limitRes != nil {
// HeaderRateLimitInformationWriter: Writes response header //information
rate_limiter.HeaderRateLimitInformationWriter(w, rate_limiter.RateLimitHeaderResponse{
RateLimitVal: limitRes.Limit.String(),
RateLimitRemaining: strconv.Itoa(limitRes.Remaining),
RateResetAfter: fmt.Sprintf("%f", limitRes.RetryAfter.Seconds()),
RateFullResetAfter: fmt.Sprintf("%f", limitRes.ResetAfter.Seconds()),
})
// Rate Limit exceeded
if limitRes.Allowed == 0 {
WriteError(w, http.StatusTooManyRequests, "Too many requests: Rate Limit", nil)
return
}
}
next(w, r)
}
}

Create a separate package for rate_limiter in your repository. Directory structure can look like this after adding some files

/pkg/rate_limiter/rate_limiter.go
/pkg/rate_limiter/types.go

File /pkg/rate_limiter/rate_limiter.go

import (
"github.com/go-redis/redis/v8"
"github.com/go-redis/redis_rate/v9"
)
type RedisConfig struct {
EngineType string `json:"engine_type" yaml:"engine_type"`
Address []string `json:"address" yaml:"address"`
MaxIdle int `json:"maxidle" yaml:"maxidle"`
MaxActive int `json:"maxactive" yaml:"maxactive" default:"50"`
Timeout int `json:"timeout" yaml:"timeout"`
DialConnectTimeout int `json:"dial_connect_timeout" yaml:"dial_connect_timeout"`
WriteTimeout int `json:"write_timeout" yaml:"write_timeout"`
ReadTimeout int `json:"read_timeout" yaml:"read_timeout"`
DialDatabase int `json:"database" yaml:"database"`
DialPassword string `json:"password" yaml:"password"`
RetryCount int `json:"retry_count" yaml:"retry_count"`
RetryDuration int `json:"retry_duration" yaml:"retry_duration"`
MaxConnLifetime int `json:"maxconnlifetime" yaml:"maxconnlifetime"`
PoolWaitMs int `json:"pool_wait_ms" yaml:"pool_wait_ms"`
}
var rl *RateLimiter

// New: to initialize limiter config
func New(rdsCfg RedisConfig, isEnabled bool) {
rdsClient := initGoRedisClient(rdsCfg)

rl = &RateLimiter{
Limiter: redis_rate.NewLimiter(rdsClient),
IsEnabled: isEnabled,
RdsClient: rdsClient,
}
}

// initGoRedisClient: initialize golang redis client
func initGoRedisClient(redisConfig RedisConfig) *redis.Client {

return redis.NewClient(&redis.Options{
Addr: redisConfig.Address[0],
DB: redisConfig.DialDatabase,
Password: redisConfig.DialPassword,
ReadTimeout: time.Duration(redisConfig.ReadTimeout),
WriteTimeout: time.Duration(redisConfig.WriteTimeout),
DialTimeout: time.Duration(redisConfig.DialConnectTimeout),
MaxConnAge: time.Duration(redisConfig.MaxConnLifetime) * time.Second,
PoolTimeout: time.Duration(redisConfig.PoolWaitMs) * time.Millisecond,
IdleTimeout: time.Duration(redisConfig.MaxIdle) * time.Second,
})
}
// CalculateRateLimit: core logic calculate rate limiter
func CalculateRateLimit(ctx context.Context, key string, limit int, rateUnit string) (*redis_rate.Result, error) {
var (
result *redis_rate.Result
err error
limitObj redis_rate.Limit
)

if rl == nil {
return result, errors.New("[middleware-ratelimit] Rate Limiter not initialised")
}

if !rl.IsEnabled {
log.Info("[middleware-ratelimit] Rate Limiter is not enabled")
return result, nil
}

// calculate Rate
limitObj, err = calculateRate(limit, rateUnit)
if err != nil {
return result, errors.New("[middleware-ratelimit][calculateRateLimit] error calculating rate limit")
}

result, err = rl.Limiter.Allow(ctx, key, limitObj)
if err != nil {
return result, errors.New("[middleware-ratelimit] error processing rate limit into go-redis rate")
}

return result, nil
}

//calculateRate: returns limit on the basis of s, m or h
func calculateRate(limit int, rateUnit string) (redis_rate.Limit, error) {
var (
result redis_rate.Limit
errMessage string
)

if rateUnit == "second" {
result = redis_rate.PerSecond(limit)
} else if rateUnit == "minute" {
result = redis_rate.PerMinute(limit)
} else if rateUnit == "hour" {
result = redis_rate.PerHour(limit)
} else {
errMessage = fmt.Sprintf("Rate Limiter aborted : Invalid rate format, correct format example : `s` or `m` or `h`. Current rate format [%s]", rateUnit)
return result, errors.New(errMessage)
}

return result, nil
}

// HeaderRateLimitInformationWriter: to write rate limit information into header response
func HeaderRateLimitInformationWriter(w http.ResponseWriter, res RateLimitHeaderResponse) {
h := w.Header()

if res.RateLimitVal != "" {
h.Set("X-RateLimit-Limit", res.RateLimitVal)
}

if res.RateLimitRemaining != "" {
h.Set("X-RateLimit-Remaining", res.RateLimitRemaining)
}

if res.RateResetAfter != "" {
h.Set("X-RateLimit-Reset-After", res.RateResetAfter)
}

if res.RateFullResetAfter != "" {
h.Set("X-RateLimit-Full-Reset-After", res.RateFullResetAfter)
}

}

File /pkg/rate_limiter/types.go

import (
"github.com/go-redis/redis/v8"
"github.com/go-redis/redis_rate/v9"
)
type RateLimiter struct {
Limiter *redis_rate.Limiter
IsEnabled bool
RdsClient *redis.Client
}

type RateLimitHeaderResponse struct {
RateLimitVal string
RateLimitRemaining string
RateResetAfter string
RateFullResetAfter string
}

type RateLimitConfig struct {
Limit int `json:"limit"`
RateUnit string `json:"rate_unit"`
Endpoint string `json:"endpoint"`
}

That’s all folks. In case of any doubts, please feel free to reach out :)

Software Engineer