Distributed Rate Limiter

A distributed rate limiter built with FastAPI, Redis, Lua, and the Token Bucket algorithm.

The project demonstrates how an API can control request traffic, prevent excessive requests, and maintain shared rate-limit state across multiple application instances .

Features

• Token Bucket rate-limiting algorithm
• Redis-backed shared state
• Atomic operations using Lua
• Per-client rate limiting
• Per-endpoint rate-limit policies
• FastAPI middleware
• HTTP 429 responses
• Redis running in Docker

Architecture

Client
   |
   v
FastAPI
   |
   v
Rate Limit Middleware
   |
   v
Identify Client + Policy
   |
   v
Redis + Lua Script
   |
   +---- Allowed ----> API Endpoint ----> Response
   |
   +---- Rejected ---> HTTP 429

How It Works

When a request reaches the application, the rate-limit middleware runs before the request reaches the API endpoint.

The middleware:

1. Identifies the client.
2. Identifies the rate-limit policy for the requested endpoint.
3. Generates a Redis key for the client and policy.
4. Executes the Token Bucket logic through a Lua script.
5. Allows the request if a token is available.
6. Returns 429 Too Many Requests if the bucket does not contain enough tokens.

For example:

/login     -> 5 requests/minute
/search    -> 30 requests/minute
/products  -> 100 requests/minute

Each policy has its own bucket.

Token Bucket

The Token Bucket algorithm models a bucket that holds a fixed number of tokens.

For example:

Capacity: 5 tokens
Refill rate: 1 token/second

Initially:

[5 tokens]

Each accepted request consumes one token:

Request 1 -> 4 tokens
Request 2 -> 3 tokens
Request 3 -> 2 tokens
Request 4 -> 1 token
Request 5 -> 0 tokens
Request 6 -> rejected

Tokens are continuously added according to the configured refill rate, up to the bucket capacity.

This allows short bursts of traffic while still controlling the average request rate.

Why Token Bucket?

Common rate-limiting algorithms include:

• Fixed Window
• Sliding Window
• Sliding Window Counter
• Token Bucket
• Leaky Bucket

Token Bucket was selected because it supports controlled bursts while maintaining a defined long-term request rate.

It is also relatively simple to implement and works well for API rate limiting.

Redis

Redis stores the state of each client's token bucket.

The state contains values such as:

tokens
last_refill

A Redis key follows this structure:

rate_limit:{client_id}:{policy}

For example:

rate_limit:127.0.0.1:login
rate_limit:127.0.0.1:products
rate_limit:127.0.0.1:search

This means the same client can have independent rate limits for different endpoints.

For example, exhausting the /login bucket does not affect the /products bucket.

Why Redis?

A rate limiter needs shared state.

If the state is stored only in application memory, every server instance maintains a separate bucket:

                Load Balancer
               /      |      \
              /       |       \
             v        v        v
         Server 1  Server 2  Server 3
            |          |         |
         Memory     Memory    Memory

This can result in inconsistent rate limits because each server has different state.

Redis provides a shared state store:

                Load Balancer
               /      |      \
              v       v       v
         Server 1  Server 2  Server 3
              \       |       /
               \      |      /
                    Redis

All application instances can therefore access the same rate-limit state.

This is what allows the rate limiter to work across multiple application instances.

Why Lua?

The Token Bucket operation involves multiple steps:

1. Read current tokens
2. Read last refill time
3. Calculate elapsed time
4. Refill tokens
5. Check available tokens
6. Consume a token
7. Store updated state

If these operations were performed as separate Redis requests, concurrent requests could read the same state before another request updates it.

The Lua script executes the complete operation inside Redis as a single atomic operation.

Request A ----\
Request B ----- > Redis Lua Script
Request C ----/          |
                          v
                   Atomic operation

This reduces race conditions when multiple requests access the same bucket concurrently.

Rate Limit Policies

The rate-limiting mechanism is separated from the policy configuration.

The mechanism defines how rate limiting works:

Token Bucket
Redis
Lua

The policy defines how much traffic is allowed:

LOGIN_POLICY
    capacity = 5
    refill_rate = 5/60

SEARCH_POLICY
    capacity = 30
    refill_rate = 30/60

PRODUCTS_POLICY
    capacity = 100
    refill_rate = 100/60

This separation makes it possible to change endpoint limits without changing the underlying rate-limiting algorithm.

FastAPI Middleware

Rate limiting is implemented as FastAPI middleware.

Without middleware, every endpoint would need to contain its own rate-limiting logic.

With middleware:

Request
   |
   v
Rate Limit Middleware
   |
   +---- Rejected -> 429
   |
   +---- Allowed
            |
            v
       API Endpoint

This keeps the rate-limiting logic centralized and reusable.

HTTP 429

When a client exceeds its configured limit, the middleware returns:

HTTP/1.1 429 Too Many Requests

Example response:

{
    "detail": "Too many requests"
}

Redis and Docker

Redis is currently running inside a Docker container while the FastAPI application runs locally.

Local Machine
|
+-- FastAPI
|
+-- Docker
    |
    +-- Redis

Start Redis with:

docker run --name rate-limiter-redis -p 6379:6379 -d redis

Check the Redis connection:

docker exec -it rate-limiter-redis redis-cli ping

Expected output:

PONG

Project Structure

rate-limiter/
|
+-- app/
|   +-- __init__.py
|   +-- main.py
|   +-- middleware.py
|   +-- redis_client.py
|   +-- redis_token_bucket.py
|   +-- rate_limit_policy.py
|
+-- requirements.txt
+-- .gitignore
+-- README.md

main.py

Creates the FastAPI application and defines the API endpoints.

middleware.py

Intercepts incoming requests and performs the rate-limit check before the request reaches the endpoint.

redis_client.py

Creates the Redis connection used by the application.

redis_token_bucket.py

Contains the Redis-backed Token Bucket implementation and Lua script.

rate_limit_policy.py

Contains the rate-limit policies for different API endpoints.

Requirements

• Python 3.10+
• Docker
• Redis
• FastAPI

Install the Python dependencies:

pip install -r requirements.txt

Running Locally

Clone the repository:

git clone https://github.com/mohitrai810/distributed-rate-limiter
cd rate-limiter

Create and activate a virtual environment:

python -m venv venv

Windows:

venv\Scripts\activate

Install dependencies:

pip install -r requirements.txt

Start Redis:

docker run --name rate-limiter-redis -p 6379:6379 -d redis

Start the FastAPI application:

uvicorn app.main:app --reload

The API will be available at:

http://127.0.0.1:8000

Testing

The rate limiter can be tested by repeatedly sending requests to a protected endpoint.

For example:

GET /login

With a policy of 5 requests per minute:

200 OK
200 OK
200 OK
200 OK
200 OK
429 Too Many Requests

The /products endpoint uses a separate bucket, so exhausting the /login bucket does not affect it.

Redis state can also be inspected directly:

docker exec -it rate-limiter-redis redis-cli

List rate-limit keys:

KEYS rate_limit:*

Inspect a bucket:

HGETALL rate_limit:127.0.0.1:login

System Design Concepts

This project demonstrates several system design concepts:

• Rate limiting
• Token Bucket algorithm
• Distributed shared state
• Redis data modeling
• Atomic operations
• Lua scripting
• Concurrency
• Middleware
• API design
• Separation of mechanism and policy
• Horizontal scaling considerations

Future Improvements

The current version focuses on the core distributed rate-limiting implementation.

Planned improvements:

• Rate-limit response headers
• Retry-After support
• Async Redis
• Authentication-based rate limiting
• API-key-based rate limiting
• Configurable policies
• Load testing and benchmarking
• Prometheus metrics
• Monitoring and alerting
• Dockerize the FastAPI application
• Docker Compose for the complete stack
• Multiple FastAPI instances behind a load balancer
• Proxy-aware client identification.