Implement a leaky-bucket rate limiter

Q: Implement a leaky-bucket rate limiter

This question evaluates understanding of rate-limiting algorithms (leaky-bucket semantics), resource accounting (capacity and drain rate), timing precision, concurrency control, testing, and distributed coordination.

Q: How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty System Design question, commonly asked during Onsite rounds at Box.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Box during technical interviews.

Question

Implement a Leaky-Bucket Rate Limiter with Tests and Distributed Design

Context and Assumptions

Implement in a general-purpose language; the reference solution uses Python 3 for clarity and unit tests.
Leaky bucket semantics: a fixed drain rate r units/sec, a finite capacity b units. Each request consumes 1 unit unless specified otherwise. The bucket "leaks" continuously at rate r.
The limiter should support:
1. try_acquire(n=1) that returns whether a request of size n is allowed now and, if not, the wait time until it would be allowed.
2. Unit tests for steady-state, burst, and boundary conditions.
3. Discussion of concurrency safety (multi-thread/process) and distributed extension (e.g., Redis) with consistency & failure-mode considerations.

Task

Implement a leaky-bucket rate limiter enforcing a maximum average request rate with a fixed drain rate.
Write unit tests to validate:
- Steady-state behavior at/under the configured rate.
- Burst behavior up to capacity.
- Boundary/edge conditions (precision, zero/near-zero time deltas, exact thresholds).
Explain how to make the limiter safe under concurrency.
Propose a design to extend it in a distributed setting (e.g., Redis), including consistency and failure-mode considerations.

Implement a leaky-bucket rate limiter

Quick Overview

Implement a Leaky-Bucket Rate Limiter with Tests and Distributed Design

Context and Assumptions

Task

Solution

Comments (0)