Distributed rate limiter

A token bucket based rate limiter written in Go. It uses Redis as a data store and Lua scripting for performing atomic operations.

This repo is intended for practising Go, learning Lua scripting (for Redis) and putting some rate limiter theory into practise.

Architecture diagram

High-level overview of components

Development/usage

This repo isn't intended for production, therefor these usage instructions will be geared towards development and testing locally. The project uses docker compose to allow us to replicate a real production environment more easily with little setup and not having to worry about dependencies etc. So you will only really need docker installed.

Running and making changes

You can start the project with the following command

docker compose watch

You could use build if you like, but watch allows you to make changes to the rate limiter and the container will rebuild automatically with the new binary.

Testing

To test the rate limiter there is a single mock service currently (users). It has two exposed endpoints, however, the mock services can easily be expanded and configured in the rate limiter. The mock service was purely for testing the rate limiter logic.

# Mock users service
GET http://localhost:8080/users
GET http://localhost:8080/users/summary

You can view rate-limiter/services.go for the current configuration of each endpoint along with their limits. In future these will be configured via a YAML file instead.

If a buckets tokens are depleted you will recieve a 429 status along with Retry-After response header containing the number of seconds in which you can reattempt.

General features

First iteration - basic features to get kick started

• Use docker compose for running in dev/test
• Simple NGINX load balancer that distributes traffic to rate limiter nodes (single node for now)
• API that sits behind rate limiter - couple of endpoints with mock data/responses. Single node for now
• Rate limiter data is managed in-memory for initial setup - this is only ideal for the single limiter node to begin with. Later I will move to redis cluster and increase limiter nodes - easier to share.
• Implement basic token bucket algorithm where every endpoint has same number of hard coded tokens - will be made dynamic later
• Identify users with IP only to begin with
• Should return appropriate limit headers e.g. when client can next try etc.

Second iteration - solving known problems

• Make token limit configurable per endpoint
• Move limiter data to Redis cluster - consider race conditions. Enables the ability to add extra rate limiter nodes - can add an extra one for testing
• Manage context appropriately; timeouts, cancelation. logging etc.

Extra features/concerns

• Important next update: Instead of having separate buckets per endpoint, a user should have a single bucket where endpoints could have different weights/costs e.g. endpoint A is 1 token, endpoint B is 3 tokens etc. This prevents malicious actions like spreading a large amount of requests across various different endpoints (buckets) to avoid limits and potentially perform DoS attacks.
• Implement retry mechanism with exponenial backoff?
• For authenticated user's cache key use known user identifiers (e.g. JWT sub claim) - better than IP which is problematic for VPN users for example. For unauthenticated endpoints/users I will need to consider this.
• Make rate limit service configuration file-based (e.g. read from a YAML file). At present its hard coded inside services.go
• Update rate limit config to allow patterns/wildcards for params etc
• Expand unit tests to cover Lua script logic (using redismock)
• Could hash cache keys for consistency
• Add second API service node - will need to load balance from rate limiter (use internal docker network with --scale?)

Useful resources/docs

• NGINX load balancing https://nginx.org/en/docs/http/load_balancing.html
• General rate limiting info w/ strategies https://redis.io/glossary/rate-limiting/
• Redis race conditions https://redis.io/glossary/redis-race-condition/
• Redis locks https://redis.io/docs/latest/develop/clients/patterns/distributed-locks/
• Lua scripting https://redis.io/docs/latest/develop/programmability/eval-intro/
• Go Redis https://redis.io/docs/latest/develop/clients/go/
• Read file contents at build time https://pkg.go.dev/embed