Katkat
Back

Design a Distributed Rate Limiter

OracleBackend Engineer · Onsite
MediumBackend EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design a scalable, low-latency distributed system for enforcing traffic quotas across multiple geographic regions with considerations for consistency and burst handling.

Problem Statement

Design a distributed rate limiter for a multi-tenant SaaS platform. Each tenant has a defined request-per-second (RPS) quota, and the system must ensure these limits are enforced across multiple data centers.

Functional Requirements

  1. Enforce rate limits per tenant (identified by tenant_id).
  2. Support 'burst' traffic (allowing temporary spikes above the sustained RPS).
  3. Support dynamic policy updates (e.g., changing the limit for a tenant without service restart).

Non-Functional Requirements

  1. Low latency: The decision to allow or block a request must add negligible overhead (sub-10ms).
  2. High availability: If the rate limiter service is unreachable, the system should fail-open or fail-closed based on configuration.
  3. Accuracy vs. Performance: Discuss the trade-offs between local-node caching and centralized state storage.

Submission Guidelines

  • Describe the high-level architecture (e.g., sidecars vs. centralized service).
  • Specify the storage mechanism for tracking request counts.
  • Explain how you would handle 'hot keys' (e.g., a single large tenant consuming all global capacity).
  • Provide an API contract for the rate limiter service.

Hints

Hint 1

Consider using the Token Bucket or Leaky Bucket algorithm to handle burstiness requirements effectively.

Hint 2

For multi-region consistency, evaluate whether you need strong consistency (using a global coordinator) or if eventual consistency (with atomic counters) is sufficient.

Hint 3

Think about using a distributed cache like Redis to store counters, and consider partitioning the keys to mitigate hot-key issues.

Follow-up questions

  • How would you implement a 'sliding window log' algorithm instead of a fixed window, and what are the memory trade-offs?
  • If the centralized database experiences a network partition, how would you ensure the system remains functional while maintaining overall quota compliance?
  • How would you integrate a feedback loop that automatically throttles specific API endpoints if the backend services report high latency or error rates?