Katkat
Back

Design a Multi-Dimensional Job Rate Limiter

ZscalerSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests the ability to design a thread-safe, distributed rate-limiting system that supports multi-dimensional, nested quota enforcement.

Problem Statement

You are tasked with designing a rate-limiting service that governs job execution based on multiple, overlapping constraints. A single job submission consumes capacity across four dimensions simultaneously:

  1. Effort (Cost): The computational weight of the job.
  2. Per-User Quota: Maximum effort allowed per user.
  3. Hourly Window: Maximum effort allowed globally per hour.
  4. Daily Window: Maximum effort allowed globally per 24 hours.

Requirements

  • Atomicity: A request must be accepted if and only if it passes all four quota checks. If accepted, all buckets must be decremented atomically.
  • Distributed System: The system must handle requests across multiple application server instances.
  • Consistency: Use a distributed data store (e.g., Redis) to manage state.
  • Performance: Minimizing latency is critical; avoid blocking or distributed locks if possible.

API Interface

Define an interface RateLimiter with a method: boolean allowRequest(String userId, int effort)

Considerations

  • How will you handle the atomicity of updating multiple independent buckets (User, Hour, Day) in a distributed environment?
  • How do you handle race conditions during the "check-then-act" phase?
  • How would you mitigate performance degradation when a specific user sends thousands of requests simultaneously (hot users)?

Hints

Hint 1

Consider using Lua scripts in Redis to execute the check and decrement logic as a single atomic operation.

Hint 2

For windowing, use rolling windows represented by timestamped keys or fixed-window counters based on epoch time.

Hint 3

To handle hot users, consider a multi-level approach where local cache handles high-frequency traffic with eventual synchronization to the global store.

Follow-up questions

  • How would you adjust your design if the hourly quota was a 'sliding window' rather than a 'fixed window'?
  • What strategies would you implement to prevent 'quota starvation' where a few large jobs consume the entire daily limit?
  • If the Redis instance goes down, should the system fail-open (allow all requests) or fail-closed (deny all)? How do you decide?