Distributed Rate Limiter Service

A high-performance, containerized, distributed rate limiting service backed by Redis. Exposes a stateless REST API built on FastAPI, scaled with Docker Compose, and load-balanced via Nginx.

Designed for high-throughput, low-latency, and absolute mathematical accuracy under concurrent requests by utilizing atomic Redis Lua scripts.

---

Architecture

The system utilizes a canonical distributed design:

1. Nginx Reverse Proxy & Load Balancer: Listens on port 8000 and load-balances requests across the scaled FastAPI nodes using a round-robin routing strategy.
2. Stateless FastAPI Nodes: Multiple backend containers that receive requests, parse criteria, and run rate limit checks.
3. Centralized Redis Store: Holds the state of all rate limiting keys. Rate-limiting logic runs as atomic Lua scripts inside Redis, executing in a single thread to guarantee race-condition-free operation (no check-then-set concurrency bugs).

graph TD
    Client[Benchmark / Client] -->|HTTP Requests| Nginx[Nginx Load Balancer]
    Nginx -->|Route 1| App1[FastAPI Node 1]
    Nginx -->|Route 2| App2[FastAPI Node 2]
    Nginx -->|Route 3| App3[FastAPI Node 3]
    App1 -->|Lua Script / EVALSHA| Redis[(Central Redis)]
    App2 -->|Lua Script / EVALSHA| Redis
    App3 -->|Lua Script / EVALSHA| Redis

Loading

---

Supported Algorithms

1. Token Bucket

• Concept: A bucket has a maximum capacity of tokens. Tokens refill at a constant fill_rate (tokens per second). Each request consumes 1 (or more) tokens. If the bucket has enough tokens, the request is allowed; otherwise, it is blocked.
• Distributed Implementation: Instead of running background workers to refill tokens periodically, we calculate the token count lazily on each request. The Redis hash stores tokens and last_updated.
• Atomic Lua Math: $$\text{refilled_tokens} = \min(\text{capacity}, \text{current_tokens} + (\text{current_time} - \text{last_updated}) \times \text{fill_rate})$$

2. Sliding Window Log

• Concept: Tracks the precise timestamp of every request in a sliding window (e.g., 100 requests per 60 seconds). A request is allowed if the count of timestamps within the last window is less than the limit.
• Distributed Implementation: Timestamps are stored in a Redis Sorted Set (ZSET) for each client ID. The members are made unique using a combination of the current timestamp and a UUID.
• Atomic Lua Math:
  1. ZREMRANGEBYSCORE removes timestamps older than now - window_size.
  2. ZCARD counts the remaining timestamps.
  3. If count < limit, ZADD inserts the current request timestamp.

---

Benchmark Metrics

Benchmarks were run locally on a macOS host (Apple Silicon M-series) with 3 FastAPI replicas behind Nginx:

• Concurrency: 100 parallel workers
• Total Requests: 20,000 requests

Metric	Token Bucket	Sliding Window Log
Throughput (RPS)	9,461.49 req/sec	10,381.77 req/sec
Average Latency	10.52 ms	9.59 ms
p50 (Median) Latency	2.55 ms	5.14 ms
p90 Latency	29.09 ms	27.60 ms
p99 Latency	81.18 ms	57.08 ms
Max Latency	285.43 ms	345.92 ms
Concurrency Accuracy	100% (Exactly 100/100 allowed)	100% (Exactly 100/100 allowed)

Concurrency Accuracy Verification

Under an extreme test (firing 250 requests concurrently for a single client with a limit of 100), our Lua implementation guarantees that exactly 100 requests are allowed (HTTP 200) and exactly 150 are denied (HTTP 429). This proves the rate limiter is fully atomic and free of race conditions.

---

Quick Start

Prerequisites

• Docker & Docker Compose
• Python 3.8+ (for running the benchmark script)

1. Spin up the cluster

Build and scale the backend instances using Docker Compose:

docker compose up --build -d --scale backend=3

Verify that the services are up:

curl -i "http://localhost:8000/health"

2. Check the Rate Limiter API

The endpoint is GET /check with parameters:

• client_id (string): Client ID (e.g. IP, API key).
• algorithm (string): token_bucket or sliding_window.
• limit (integer): Max allowed requests.
• rate_or_window (float): Refill rate for Token Bucket (tokens/sec) OR window size for Sliding Window Log (seconds).

Example Token Bucket request (Capacity 10, refill rate 1/s):

curl -i "http://localhost:8000/check?client_id=user_123&algorithm=token_bucket&limit=10&rate_or_window=1"

Response Headers returned:

• X-RateLimit-Limit: Maximum configuration limit
• X-RateLimit-Remaining: Remaining capacity or tokens
• X-RateLimit-Allowed: true or false

3. Run Benchmarks

Create a virtual environment and run the benchmark stress-tester:

# Set up venv and install dependencies
python3 -m venv .venv
source .venv/bin/activate
pip install aiohttp

# Run the benchmark
python benchmark/benchmark.py --url "http://localhost:8000/check" --concurrency 100 --requests 20000 --algorithm token_bucket --limit 20000 --rate-or-window 2000 --unique-clients