Open in app

Sign in

Write

Sign in

Implementation of a Distributed Rate Limiter

Aman Jain
7 min readMay 7, 2021

Prerequisite

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

Rate Limiter

Requirements and Goals

aman-jain24.medium.com

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)
endtat = math.max(tat, now)local new_tat = tat + increment
local allow_at = new_tat - burst_offsetlocal diff = now - allow_at
local remaining = diff / emission_intervalif remaining < 0 then
  local reset_after = tat - now
  local retry_after = diff * -1
  return {
    0, -- allowed
    0, -- remaining
    tostring(retry_after),
    tostring(reset_after),
  }
endlocal 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 //informationrate_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 :)

Rate Limiting
Implementation
Golang
Ddos

--

--

Aman Jain

Written by Aman Jain

13 Followers

Software Engineer

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams