./ahmedhashim

Which rate-limiting algorithm to use and where to store your counters are two questions you’ll need to ask yourself when implementing a rate limiter. The answers depend on how much traffic you have and whether multiple services need to share state.

Naive approach

Begin with a fixed window algorithm and keep track of IPs and request counts in memory. This should be good enough for most use cases, so if your traffic isn’t too high, you can stop here.

counts := map[netip.Addr]int{} // requests in the current window

This will have two problems:

1. Edge bursts: with a limit of 100 req/minute, a client can make 100 requests at 11:59:59 and another 100 at 12:00:01, getting 200 through in two seconds.
2. Memory growth: the map holds on to clients it hasn’t seen in a long time unless you prune it.

Smoothing the curve

A sliding window log keeps a timestamp of every request and will only count requests within the given window, so there’s no window boundary left to burst across.

The trade-off is memory usage. Fixed windows only need to store one counter for each client, but logs need to store one timestamp per request. With a rate limit of 100 req/minute, your busiest client will hold 100 entries instead of one, and 10,000 busy clients add up to a million. If your use case is about bursting, it’s a good trade-off.

Offloading to Redis

When you’ve outgrown a single instance of your rate limiter, you’ll want to move your counters and algorithm to a shared resource. Redis will allow you to do both. You can store the timestamps of each client in a sorted set and run your algorithm on the set atomically with a Lua script.

Here’s an example in Go:

package ratelimit

import (
  "context"
  "fmt"
  "math/rand"
  "strconv"
  "time"

  "github.com/redis/go-redis/v9"
)

type Limiter struct {
  client *redis.Client
  burst  int
  window time.Duration
}

// Atomic sliding window log. Redis supplies the clock so app servers agree on it.
const limiterScript = `
  local key = KEYS[1]
  local window_ms = tonumber(ARGV[1])
  local limit = tonumber(ARGV[2])
  local t = redis.call('TIME')
  local now = t[1] * 1000 + math.floor(t[2] / 1000)

  redis.call('ZREMRANGEBYSCORE', key, 0, now - window_ms)
  if redis.call('ZCARD', key) >= limit then
    return 0
  end

  redis.call('ZADD', key, now, ARGV[3])
  redis.call('PEXPIRE', key, window_ms)
  return 1
`

// NewLimiter allows up to burst requests in any window of
// burst/requestsPerSecond seconds.
func NewLimiter(redisAddr string, requestsPerSecond float64, burst int) *Limiter {
  return &Limiter{
    client: redis.NewClient(&redis.Options{
      Addr: redisAddr,
    }),
    burst:  burst,
    window: time.Duration(float64(burst) / requestsPerSecond * float64(time.Second)),
  }
}

// Allow checks if a request from the given identifier should be allowed
func (l *Limiter) Allow(ctx context.Context, identifier string) (bool, error) {
  // Sorted set members must be unique, or same-millisecond requests collapse
  member := strconv.FormatInt(rand.Int63(), 36)

  allowed, err := l.client.Eval(ctx, limiterScript, []string{identifier},
    l.window.Milliseconds(),
    l.burst,
    member,
  ).Bool()
  if err != nil {
    return false, fmt.Errorf("rate limiter error: %w", err)
  }

  return allowed, nil
}

The window will be burst / requestsPerSecond, so with requestsPerSecond=10 and a burst of 50, you’ll have a window of 5 seconds. Your client can consume all 50 requests at once, but over time it’ll come to a rate of 10 per second.

Each request that’s allowed will update the TTL of the key to the length of the window. This lets Redis expire clients that have stopped hitting your service and keeps memory usage low with millions of unique IDs.

By storing your state in Redis, you can make your application servers stateless. Adding and removing servers from your pool won’t have any effect on your clients’ rate limits. Each call to Redis will be sub-millisecond, which is negligible in your overall latency.