Katkat
Back

Design a Thread-Safe Multi-Rule Rate Limiter

SnowflakeSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests the ability to design a thread-safe, flexible rate-limiting system that handles multiple constraints, atomic permit management, and graceful error handling.

Problem Statement

Design a thread-safe RateLimiter class that manages multiple independent rate-limiting rules. A rule is defined by a capacity C (max requests) and a time window W (in milliseconds). A request is only permitted if it satisfies all active rules.

Requirements

  1. add_rule(capacity, window_ms): Dynamically add a new rate-limiting constraint.
  2. try_acquire(): Attempts to consume a permit across all rules. Returns True if successful, False otherwise.
  3. release(): If a request fails during processing (e.g., an exception), the permit must be returned to the bucket to maintain accurate counting.
  4. Thread-Safety: The implementation must handle high concurrency without leaking permits or violating rate constraints.

Constraints

  • The number of rules is small (1-10).
  • try_acquire() must be non-blocking.
  • Operations must be atomic across all rules: if a request cannot satisfy rule A but satisfies rule B, no permits should be consumed.

Example

limiter = RateLimiter()
limiter.add_rule(10, 1000) # 10 requests per second

if limiter.try_acquire():
    try:
        # Perform work
        pass
    except Exception:
        limiter.release()

Edge Cases

  • A release() call triggered after a rule is removed.
  • Extremely high concurrency causing timestamp contention.
  • Ensuring try_acquire is atomic (all-or-nothing consumption).

Hints

Hint 1

Consider using a 'sliding window log' or 'token bucket' implementation for individual rules.

Hint 2

To ensure atomicity, use a reentrant lock or an atomic composite structure to update all rule states together.

Hint 3

For the 'release' functionality, keep track of which rule states were modified during a successful acquire to avoid over-counting if a request fails.

Follow-up questions

  • How would you adapt this design to work in a distributed environment where multiple instances of the application share the same rate limits?
  • If the rate-limited requests must be queued rather than dropped, what data structure would you use to manage fairness and prevent memory exhaustion?
  • How would you ensure deterministic testing for this class given the dependency on system time?