Capital One API Rate Limiting And Quotas

What's being tested

Interviewers are probing your ability to design, implement, and reason about scalable API rate limiting and quota systems: correctness under concurrency, latency and memory tradeoffs, and operational behavior under failure. At Capital One they care about protecting downstream systems and customers from noisy tenants while preserving low latency and clear failure semantics. Expect to justify algorithm choice, state placement, eviction/sharding strategy, and observability for production readiness.

Core knowledge

Token bucket vs leaky bucket: token bucket allows bursts up to capacity; leaky bucket smooths output. Token bucket good for API bursts, leaky bucket for fixed pacing.
Fixed window, sliding window log, sliding window counter tradeoffs: fixed-window is O(1) but has boundary anomalies; sliding-log is accurate but O(k) memory; sliding-counter (bucketed) approximates sliding window with O(1) cost.
Distributed state: central stores like `Redis` (single cell) offer strong counters and `INCR` atomicity; local caches reduce latency but require synchronization or token plumbing for accuracy.
Atomicity patterns: use `Redis` `INCR` for fixed windows; use `Lua` scripts for check-and-increment to avoid race conditions; pipeline to reduce RTTs.
Sharding and collision: shard by API key or customer ID using consistent hashing; ensure hot keys handled with token refill heuristics or hot-key split to avoid single-node overload.
Accuracy vs performance: approximate algorithms (fixed-window + boundary mitigation, bucketed sliding) scale to tens of millions of keys; sliding logs do not when k per key grows.
Enforcement point: gateway (e.g., `Envoy`, `NGINX`) enforces early with lower latency; application-layer enforcement gives richer context but higher cost and CPU.
Failure modes & degraded behavior: define fail-open vs fail-closed semantics; prefer fail-open for non-critical read endpoints, fail-closed for abuse-protection endpoints, and always document SLO impacts.
Response semantics: return `HTTP 429` with `Retry-After` header; include rate-limit headers like `X-RateLimit-Limit`, `X-RateLimit-Remaining`, `X-RateLimit-Reset` for client observability.
Burst and refill math: token bucket refill rate r tokens/sec with capacity b allows immediate burst of up to b tokens and sustained rate r; compute refill intervals as delta*tokens = r * Δt.
Monitoring & SLOs: track `p99` latency impact of limiter, error-rate (429s), throttle ratio per customer, and token-store capacity; alert on hot-key saturations and global saturation.
Testing & validation: load-test with realistic traffic shapes, simulate clock drift across nodes, and validate corner cases like clock skew, network partitions, and store failover.

Worked example — Design a distributed rate limiter for per-client quotas with burst allowances

Frame the problem: ask for the granularity (per API key/customer vs per-endpoint), expected QPS per key and total, burst size, latency SLO for request path, and acceptable accuracy (±what). Skeleton of response: (1) pick algorithm (token bucket per key with capacity = burst), (2) choose enforcement location (gateway-level for low latency with fallback to app), (3) store design (sharded `Redis` cluster with `Lua` scripts for atomic check-and-consume), (4) scaling & hot-key mitigation (split hot keys, local-cache tokens for microbursts), (5) observability and failure semantics (emit metrics, `HTTP 429`, fail-open policy). Tradeoff to call out: using local token caches reduces RTTs but sacrifices global accuracy and complicates refill coordination; quantify: local cache handles bursts ≤100ms without contacting central store. Close by stating testing plan (chaos test partitions, large-scale load tests) and next steps: implement a `Lua` atomic check-increment-refill script and integrate with gateway rate-limit filter.

A second angle — Enforcing global quotas across multiple regions with eventual consistency

If the constraint shifts to multi-region enforcement, prioritize availability and latency: use local enforcement with periodic reconciliation to approximate global quotas, or implement a global token service with consensus (higher latency). For high accuracy, use a central counter (sharded `Redis` with geo-replication) and accept cross-region RTTs or use a hierarchical token bucket: local buckets draw from a regional pool and the regional pool from a global coordinator. Discuss tradeoffs: strict global accuracy requires synchronous coordination and hurts latency; eventual consistency risks small overages but supports better user experience. Suggest mitigations: small local borrowing allowances, backpressure signals, and corrective reconciliation jobs.

Common pitfalls

Pitfall: Treating rate limiting as purely algorithmic — many failures come from placement and operational behavior, not math. Explicitly state enforcement point and failure-mode policy.

Pitfall: Choosing sliding-log for high-cardinality workloads — it can blow memory when per-key event rate is large; prefer bucketed sliding counters or token buckets.

Pitfall: Ignoring observability — returning `HTTP 429` without headers or metrics prevents clients from backoff and operators from diagnosing hot keys; always emit limit headers and per-key metrics.

Connections

Interviewers may pivot to adjacent topics like circuit breakers and backpressure strategies, API gateway design (authentication, routing), or consistency tradeoffs in distributed counters. Be ready to discuss caching strategies and capacity planning for the token-store.