Katkat
Back

Design a Distributed Token-Bucket Rate Limiter

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design a scalable, low-latency distributed rate-limiting service using the token bucket algorithm while balancing consistency and performance.

Problem Statement

Design a distributed rate-limiting service that uses the token-bucket algorithm to enforce traffic policies (e.g., "100 requests per minute") for a global API gateway. The system must support thousands of concurrent requests across multiple geographically distributed application servers.

Functional Requirements

  • Enforce a configured limit (requests per time window) per user ID.
  • Provide an API for the gateway to check if a request should be allowed.
  • Allow configuration of different rate limits for different tiers of users.

Non-Functional Requirements

  • Low latency: The rate-check operation should add minimal overhead (ideally < 10ms).
  • High Availability: The system should remain functional even if a node fails.
  • Consistency: Ensure rate limits are respected as accurately as possible without severely compromising performance.

Requirements for your Design

  1. Propose an API interface for the rate limiter service.
  2. Describe the data storage strategy (e.g., centralized vs. local vs. hybrid).
  3. Explain how the token bucket state (tokens and last refill timestamp) is persisted and updated.
  4. Address how you would handle race conditions when multiple application servers update a bucket's state simultaneously.
  5. Discuss how to handle system failures and ensure the rate limiter does not become a single point of failure (SPOF) for your main API.

Hints

Hint 1

Consider using an in-memory data store like Redis to maintain state globally, utilizing atomic operations to avoid read-modify-write race conditions.

Hint 2

Think about the trade-offs between 'strict consistency' (using distributed locks) and 'eventual consistency' (using optimistic concurrency control or local caching).

Hint 3

Evaluate the impact of latency if the network between the application server and the rate limiter is slow; could local bucket buffering help?

Follow-up questions

  • How would you modify this design to support a 'burst' capacity versus a strictly sustained rate?
  • If the Redis cluster is overloaded, what fallback strategy would you implement to ensure your main API remains available?
  • How would you handle dynamic updates to rate limits for specific users without restarting the application servers?