Abuse prevention & rate limiting

Data structure per identity: A hash bucket:{api_key} with two fields:

• tokens — current token count (float, supports partial refill).
• last_refill — millisecond timestamp of the last refill.

Request flow (atomic via Lua script to avoid races):

-- KEYS[1] = bucket key, ARGV = {now_ms, refill_rate, burst}
local now   = tonumber(ARGV[1])
local rate  = tonumber(ARGV[2])   -- tokens per ms
local burst = tonumber(ARGV[3])

local data = redis.call('HMGET', KEYS[1], 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or burst
local last   = tonumber(data[2]) or now

-- Refill based on elapsed time, capped at burst
tokens = math.min(burst, tokens + (now - last) * rate)

if tokens >= 1 then
  tokens = tokens - 1
  redis.call('HSET', KEYS[1], 'tokens', tokens, 'last_refill', now)
  redis.call('PEXPIRE', KEYS[1], 60000)   -- TTL idle identities out
  return 1   -- allow
else
  redis.call('HSET', KEYS[1], 'tokens', tokens, 'last_refill', now)
  return 0   -- deny
end

Why a Lua script: two-command sequences (GET then SET) race under concurrency — two gateways could both see 1 token and both allow. The script is atomic inside Redis.

Edge cases:

1. 1First request from an identity — key doesn't exist; initialise to full burst. Handled by or burst / or now.
2. 2Long idle period — without TTL, Redis keeps the key forever. PEXPIRE resets on every access; idle keys evict automatically.
3. 3Clock skew between gateways — use redis.call('TIME') inside the script instead of client-sent time. Cleaner but one extra cmd.
4. 4Hot key — one celebrity API key could overload the shard hosting its bucket. Mitigate with client-side local pre-check (skip the Redis call if locally we know the bucket is very empty) + sharding the bucket across bucket:{api_key}:{shard_n}.

Per-request cost: ~1 ms (Redis RTT within the region) + ~50 μs of script execution. At 100K QPS, one Redis primary handles this comfortably.

Two strategies depending on what the limit protects:

1. DDoS-style volumetric limits: FAIL OPEN.

• If the limiter is unavailable, allow the request.
• Log the gap; alert on sustained fail-open.
• Rationale: a DoS attack on the limiter (or a Redis cluster incident) should not itself cause a full API outage. Fail-open trades some worst-case overage for resilience.
• Downstream capacity absorbs it; overload alarms fire if there is actually a flood.

2. Quota / billing limits: FAIL LOCAL.

• Each gateway falls back to an in-memory bucket with a conservative limit (say 1/N of the global, where N is the gateway count).
• Still enforces some limit; accepts over-limit by a factor during the outage.
• Logs the identities that were throttled locally — post-incident, reconcile billing.
• Rationale: a 15-minute outage where a single customer consumes 10× their quota is a billing issue, not a business risk.

3. Hard, must-enforce limits (financial, compliance): FAIL CLOSED.

• Reject requests. Return 503 Service Unavailable.
• Only for flows where "serve no request" is genuinely better than "serve a request unlimited".
• Rare in practice. Most limits should not be in this category.

The anti-pattern to avoid: fail-closed by default. A single-point-of-failure limiter on the hot path is an outage waiting to happen. Default to fail-open, escalate fail-local only where quota matters, fail-closed almost never.

Operational tooling for fail-open:

• Kill switch — feature flag to force fail-open without redeploying. Useful when Redis is slow but not down.
• Circuit breaker on Redis calls — if Redis p99 spikes, short-circuit and fail-open proactively instead of letting every request pay the timeout.
• Degraded-mode metric — dashboard shows "limiter is in degraded mode" so incident response knows.

Status code: 429 Too Many Requests (RFC 6585).

Body (JSON):

{
  "error": "rate_limited",
  "message": "API rate limit exceeded. Retry after 12 seconds.",
  "limit": 100,
  "remaining": 0,
  "reset_at": "2026-04-23T14:35:00Z",
  "docs_url": "https://docs.example.com/api/rate-limits"
}

Headers (draft-ietf-httpapi-ratelimit-headers standard, increasingly supported):

• RateLimit-Limit: 100 — the policy limit.
• RateLimit-Remaining: 0 — how many requests they have left in the current window.
• RateLimit-Reset: 12 — seconds until the limit resets (or a unix timestamp with RateLimit-Policy).
• Retry-After: 12 — how long to wait before retrying (seconds or HTTP-date). Required — this is how well-behaved clients back off.

On every response (not just 429): Emit RateLimit-Limit, RateLimit-Remaining, and RateLimit-Reset. Clients can proactively throttle themselves before hitting the wall. This reduces 429 volume and makes abuse detection clearer (abusive clients ignore these headers).

What NOT to do:

• Silent drops. Closing the connection without a 429 leaves the client guessing between network failure and rate limit.
• 403 Forbidden. Implies permanent denial; clients won't retry. Use 429.
• 200 with error in body. Breaks clients that rely on HTTP status for retry logic.
• Exponential backoff math. Server tells the client how long to wait (Retry-After); don't rely on clients to calculate it.

Abuse-detection signals hidden here:

• Clients that ignore Retry-After and hammer anyway are candidates for aggressive throttling or IP-level blocks.
• Clients that back off exactly as instructed are good citizens; whitelist candidates for higher limits.

The core tension: global consistency (a single quota across regions) vs per-request latency (cross-region Redis call adds 50-150 ms).

Three strategies, pick by use case:

1. Regional limits, no global sync. Each region enforces its own bucket (e.g., 100K req/min per region per key). Users stay in their region (geo-DNS). Simple, low-latency, per-request cost ~1 ms local Redis.

• Overage: worst case, a user with cross-region requests gets N× their intended limit (where N = number of regions). Usually acceptable.
• Use case: most public APIs. Customers rarely cross regions; the overage is small.

2. Global limit with local leases. Each region gets a share of the global quota — e.g. the us-east gateway is leased 60% of the 100K/min limit. Regions negotiate lease sizes periodically based on demand (every 30 s). Requests check the local lease without cross-region round-trip.

• Overage: bounded to the lease granularity. Adjustment lag means a surging region is briefly under-provisioned before the next negotiation.
• Use case: workloads with high imbalance (big customer concentrated in one region). Closer to global accuracy without per-request latency.

3. Strict global via cross-region Redis (or a consensus store). Every request hits a single authoritative limiter, possibly replicated for availability but coordinating through Raft or similar.

• Overage: none (strict).
• Cost: per-request RTT includes cross-region hop. ~100 ms added latency for cross-continent.
• Use case: hard compliance / billing quotas where accuracy matters more than latency. Rarely the right answer.

Practical recommendation for most APIs: per-region limits with a global cap on paid tiers enforced asynchronously (at billing time, not at request time). This gives low latency for the hot path and accurate billing for customers, at the cost of accepting small intra-second overages.

The interview takeaway: don't propose strict global limits reflexively. Name the overage tolerance and match the strategy. "Per-region, global billing reconciliation" is the senior answer.

Token bucket — the default.

• Allows bursts up to B then sustained at R.
• Matches typical user behavior (occasional bursts) without punishing legitimate spikes.
• O(1) storage, trivial to implement in Redis.
• Pick when: most APIs. Unless you have a specific reason, this.

Leaky bucket — smoothing, not limiting.

• Queue at input, constant drain rate.
• Bursts get delayed, not rejected — adds latency.
• Pick when: you have a hard downstream rate limit (e.g., you call a 3rd-party API that accepts max 10 req/s) and want to smooth your outbound calls rather than drop them. It's an outbound shaping tool, not an inbound rejection tool.
• Don't pick when: your users prefer 429s to silent 5-second waits. Queueing violates user expectations.

Fixed window counter — avoid.

• Count requests per calendar minute.
• The edge-doubling problem: a client can do B in the last second of minute 1 and B in the first of minute 2 → 2B in 2 seconds.
• Pick when: you explicitly accept the 2× burst and want O(1) simplicity. Rare.

Sliding window log — accurate but expensive.

• Store every request timestamp, count those in the last N seconds.
• O(requests-in-window) memory; O(log n) or O(n) per check.
• Pick when: you need exact accuracy for small N (tiny per-second bucket) and memory isn't a concern. Rarely the right tradeoff at scale.

Sliding window counter — the compromise.

• Two adjacent fixed windows, weighted by position in current window.
• ~95% accurate, O(1) storage.
• Pick when: you want fixed-window simplicity without the edge-doubling problem. Good for analytics-style limits where a small error is acceptable.

GCRA (Generic Cell Rate Algorithm) — the sophisticated option.

• Mathematically equivalent to leaky bucket, but O(1) with a single timestamp (no queue).
• Used by Stripe's rate limiter; precise and cheap.
• Pick when: you want leaky-bucket semantics without queueing cost. High-QPS production limiters.

The interview default: token bucket. If asked why not X, name the specific tradeoff (edge-doubling for fixed-window, added latency for leaky-bucket, memory cost for sliding-log).