Design a Rate Limiter for an API Service

Requirements: Design a rate limiter that throttles requests to an API service per client (e.g., per API key or IP) to protect backend capacity, with configurable limits (e.g., N requests per M seconds).

Design: Discuss common algorithms - Fixed Window Counter (simple but bursty at window edges), Sliding Window Log/Counter (smoother, more memory), Token Bucket (allows bursts up to bucket size, refills at a steady rate), and Leaky Bucket (smooths bursts into a constant output rate). For a distributed system, back the limiter with Redis (atomic INCR + EXPIRE, or a Lua script for atomicity) so all API instances share limiter state; discuss scaling considerations (Redis as a bottleneck/single point of failure, sharding limiter state by client key, and trade-offs between strict accuracy and latency under high request volume).