ratelimiter

A token-bucket HTTP rate limiter and API gateway built as a study in hot-path performance and distributed state. V1 is a deliberately naive in-process implementation; V2 moves state to Redis and adds sliding-window algorithms, a fail-open fallback, and per-tenant quotas.

Architecture

graph LR
    Client -->|HTTP| GW1["Gateway 1\n:9090"]
    Client -->|HTTP| GW2["Gateway 2\n:9091"]
    GW1 & GW2 --> TL["TenantLimiter\nX-API-Key dispatch"]
    TL --> FL["FallbackLimiter"]
    FL -->|Redis up| SWC["SlidingWindowCounter\nLua INCR + interpolation"]
    FL -->|Redis down| TB["TokenBucket\nin-process fallback"]
    SWC --> Redis[("Redis")]
    FL -->|allowed| Backend["Backend API"]
    FL -->|denied| R429["429 + Retry-After"]

Loading

Every request passes through TenantLimiter (selects a per-key limiter from X-API-Key or falls back to IP), then FallbackLimiter (calls the Redis backend; on any error, fails open to the in-process token bucket). The sliding window counter keeps two adjacent fixed-window Redis keys and combines them with linear interpolation — O(1) per request, two atomic commands.

Why this design

Sliding window counter over fixed window — a fixed window resets sharply at the boundary; a client can double the limit by bursting at the end of one window and the start of the next. Linear interpolation over two adjacent counters smooths that boundary at O(1) cost.

Sliding window log as an alternative — implemented behind --algorithm sliding-window-log for benchmarking comparison. Uses a Redis sorted set for exact counts; O(N) per request. Useful for studying the accuracy vs. cost trade-off.

Fail-open on Redis unavailability — a Redis outage must not take down the upstream API. The in-process token bucket activates automatically; errors are logged once per 5 seconds to avoid log spam.

Token bucket (V1) — lazy refill: tokens added = rate × elapsed_seconds, capped at burst. No background goroutine, O(1) per request. Deliberately kept in-process to set up the V1 failure scenario.

IP-based identity with API key override — X-API-Key header is checked first (selects a tenant tier), then X-Forwarded-For (leftmost IP), then RemoteAddr. Unknown API keys fall back to the default IP limit.

What broke and how I fixed it

Limits leak across instances — TestMultiInstanceLimitLeak documented the core V1 failure: with burst=5 and 3 independent instances, a client round-robining requests across them hits a full bucket on each. All 15 requests succeed — 3× the intended quota.

The cause is purely that state lives in each process's heap with no coordination. A single shared limiter given the same 15 requests stops at 5.

V2 fixes this by moving counter state to Redis. All instances share one counter per client key. TestMultiInstanceGlobalEnforcement (internal/limiter/instance_leak_test.go) asserts the fix: 3 instances sharing a miniredis server allow exactly burst requests globally, regardless of how they're distributed across instances.

V1 weaknesses

Weakness	Effect
In-process state	3 instances = 3× the intended limit; limits don't hold globally
IP-only identity	Shared egress IPs (office NAT) over-limit legitimate users
Token bucket only	Burst resets are predictable and gameable at window boundaries
No persistence	Restart clears all buckets

V2 fixes

Fix	Status
Sliding window counter (Redis, O(1), Lua script)	✓
Sliding window log (Redis sorted set, exact counts)	✓
Fail-open fallback to in-process token bucket	✓
Per-tenant quotas via X-API-Key + tenants.json	✓

Build

Requires Go 1.22+.

make build    # outputs bin/gateway

Run

Local (in-process fallback, no Redis):

make run                        # uses tenants.json; falls back to token bucket without Redis
./bin/gateway --rate 100 --burst 50 --tenants tenants.json

Local with Redis:

make run-redis                  # starts Redis only (docker-compose up redis -d)
go run ./cmd/gateway --redis-addr localhost:6379 --tenants tenants.json

Full stack via Docker:

make run-docker                 # Redis + gateway1 (:9090) + gateway2 (:9091)

Flags:

--addr        string   HTTP listen address (default ":9090")
--rate        float64  requests per second — default limit (default 10)
--burst       int      max burst / window limit (default 20)
--redis-addr  string   Redis address (default "localhost:6379")
--algorithm   string   sliding-window-counter | sliding-window-log (default "sliding-window-counter")
--tenants     string   path to tenant config JSON (omit for IP-only mode)

Docker

docker-compose.yml runs two gateway instances and Redis. Both gateways share the same Redis, demonstrating global limit enforcement — the V2 fix:

docker-compose up --build

Demonstrate global enforcement across instances:

# Alternate requests across gateway1 (:9090) and gateway2 (:9091).
# burst=5, so the 6th request gets a 429 regardless of which port it hits.
for i in $(seq 1 7); do
  port=$((9089 + (i % 2) + 1))
  echo -n "port=$port → "
  curl -s -o /dev/null -w "remaining=%header{X-RateLimit-Remaining} status=%{http_code}\n" \
    http://localhost:$port/api/ping
done

Tenant limits via X-API-Key (tenants.json is mounted into both containers):

# key-abc123: burst=200 — won't hit 429 under normal load
curl -H "X-API-Key: key-abc123" http://localhost:9090/api/ping

# key-xyz789: burst=10
curl -H "X-API-Key: key-xyz789" http://localhost:9091/api/ping

# No key: falls back to --burst 5 default
curl http://localhost:9090/api/ping

Demonstrate fail-open fallback:

docker-compose stop redis
# Gateway still serves — falls back to in-process token bucket, logs once per 5 s
curl http://localhost:9090/api/ping

docker-compose start redis
# Redis recovers; next request resumes the sliding window counter

Test

make test
go test -race -count=1 -run TestName ./internal/limiter/...    # single test

Usage

# Allowed request — rate-limit headers on every response
curl -i http://localhost:9090/api/ping

# Exhaust the limit and observe 429
for i in $(seq 1 25); do curl -s -o /dev/null -w "%{http_code}\n" http://localhost:9090/api/ping; done

# POST echo
curl -X POST http://localhost:9090/api/echo -d "hello"

# Health check (never rate-limited)
curl http://localhost:9090/health

# Prometheus metrics (never rate-limited)
curl http://localhost:9090/metrics

Example metrics output:

# HELP ratelimiter_requests_total Rate-limit decisions by tenant and result (allowed|denied).
# TYPE ratelimiter_requests_total counter
ratelimiter_requests_total{result="allowed",tenant="default"} 30
ratelimiter_requests_total{result="denied",tenant="default"}  970
ratelimiter_requests_total{result="allowed",tenant="key-abc123"} 1000

# HELP ratelimiter_redis_errors_total Redis errors (every occurrence, not deduplicated).
# TYPE ratelimiter_redis_errors_total counter
ratelimiter_redis_errors_total 0

Reload tenants without restart:

# Edit tenants.json, then:
kill -HUP <gateway-pid>
# or inside docker: docker-compose kill -s HUP gateway1

Response headers on every rate-limited path:

X-RateLimit-Limit:     20
X-RateLimit-Remaining: 19
X-RateLimit-Reset:     1713830400

On 429:

Retry-After: 1

Benchmarks

Measured with cmd/loadtest against two gateway instances + Redis running locally via docker-compose. Gateway is the bottleneck; upstream is a no-op {"ok":true} handler.

Scenario	RPS	Duration	Success	p50	p99	max
High-burst tenant (key-abc123, burst=200)	100	10 s	100%	1.8 ms	3.2 ms	11.2 ms
Default IP limit (burst=5/s)	100	10 s	3%	2.0 ms	3.5 ms	6.3 ms

Notes:

• Allowed and denied paths have near-identical latency (~2 ms p50) — the sliding window counter decision is O(1) (one Redis GET + one Lua INCR) and adds negligible overhead regardless of outcome.
• 3% success at 100 RPS against a 5 req/s limit yields ~30 allowed over 10 s (expected ≈50). The delta is the sliding window interpolation being conservative at window boundaries: the weighted previous-window count pushes the estimated total over the limit slightly earlier than a pure fixed-window counter would. This is the algorithm working as intended — it trades a small reduction in effective throughput for smooth enforcement across window edges.
• Redis errors increment ratelimiter_redis_errors_total; all decisions are labelled in ratelimiter_requests_total{tenant, result} and visible at /metrics.

Run your own:

# Allowed path baseline
go run ./cmd/loadtest --rps 100 --dur 10s --api-key key-abc123

# Rate-limited path
go run ./cmd/loadtest --rps 100 --dur 10s

# Watch metrics live
curl -s http://localhost:9090/metrics | grep ratelimiter

What I'd do next

• Adaptive limits — reduce the allowed rate when downstream latency exceeds a threshold (backpressure from the protected service)
• Multi-region Redis — replace single Redis with a Redis Cluster or regional replicas to eliminate the single point of failure in the shared counter