Lab 02 — Design Tradeoffs: Comparing RateLimiter Implementations
Phase: 06 — Review Culture and Patch Workflow
Difficulty: ⭐⭐⭐⭐☆ | Estimated Time: 3–3.5 hours
Primary Artifact: Two RateLimiter implementations + benchmark comparison
Verify: mvn test passes all correctness tests; benchmark output printed to console
Scenario
A contributor proposed switching the existing TokenBucketRateLimiter to a SlidingWindowRateLimiter on the grounds that sliding window is "fairer":
The token bucket allows bursts — a client that was idle for 10 seconds can suddenly fire 10x the normal rate. The sliding window guarantees that no client ever exceeds the rate in any rolling time window, not just on average.
Your job is to:
- Understand both implementations by reading the code and the tests
- Run the benchmark and compare the results
- Write a "+1 with conditions" or "-0" review that makes a concrete recommendation
Background: Token Bucket vs. Sliding Window
Token Bucket — conceptual model:
- Imagine a bucket that holds tokens. Tokens are added at a fixed rate (e.g., 10/sec).
- Each request consumes one token. If the bucket is empty, the request is rejected.
- If the requester was idle, tokens accumulate (up to the bucket capacity), allowing a burst.
Sliding Window Log — conceptual model:
- Keep a log of timestamps for every allowed request.
- When a new request arrives, count the requests in the last N seconds.
- If the count is below the limit, allow it (and add a timestamp). Otherwise, reject.
- No burst allowance — strictly "no more than N requests in any rolling window of size W".
Setup
cd phase-06-review-culture/lab-02-design-tradeoffs
mvn test && mvn compile exec:java -Dexec.mainClass=org.example.review.RateLimiterBenchmark
The test suite verifies both implementations are correct. The benchmark prints throughput comparison output.
Steps
Step 1 — Read both implementations
Before running anything: read TokenBucketRateLimiter.java and SlidingWindowRateLimiter.java. For each, answer:
- What data structure stores the state?
- What is the time complexity of
tryAcquire()? - What is the space complexity relative to the rate limit and window size?
- Under what traffic pattern does this algorithm perform worst?
Step 2 — Run the tests
mvn test
Both implementations should pass. If either fails, read the test to understand the invariant being tested.
Step 3 — Run the benchmark
mvn compile exec:java -Dexec.mainClass=org.example.review.RateLimiterBenchmark
Record the throughput numbers. Note the difference under:
- Steady-state load (requests at exactly the allowed rate)
- Burst load (10x rate for 1 second, then idle)
- High-load rejection (20x rate sustained)
Step 4 — Write the vote email
Write a 200–400 word message to dev@project.example.com in the following format:
Subject: [DISCUSS] PROJ-4512 — switching rate limiter from token bucket to sliding window
Hi all,
I reviewed both implementations. Here is my analysis:
Performance:
- Token bucket tryAcquire(): O(1) time, O(1) space
- Sliding window tryAcquire(): O(k) time (k = requests in window), O(k) space
Fairness:
- Token bucket allows burst of [capacity] requests after idle period
- Sliding window enforces hard ceiling in any rolling window
My recommendation: [+1 for / -0 for / -1 against] switching because:
...
Conditions / caveats:
...
— [Your name]
Fill in the real numbers from your benchmark. This is the skill that distinguishes a "I wrote it so it must be good" contributor from an Apache committer.
Verification
# All correctness tests pass
mvn test
# Benchmark output is produced
mvn compile exec:java -Dexec.mainClass=org.example.review.RateLimiterBenchmark 2>/dev/null | grep -E 'throughput|burst|Approach'
Source Files
pom.xml
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>org.example.review</groupId>
<artifactId>design-tradeoffs-lab</artifactId>
<version>1.0.0-SNAPSHOT</version>
<packaging>jar</packaging>
<name>Review Culture Lab 02 — Design Tradeoffs</name>
<properties>
<maven.compiler.source>11</maven.compiler.source>
<maven.compiler.target>11</maven.compiler.target>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
</properties>
<dependencies>
<dependency>
<groupId>org.junit.jupiter</groupId>
<artifactId>junit-jupiter</artifactId>
<version>5.10.2</version>
<scope>test</scope>
</dependency>
</dependencies>
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-surefire-plugin</artifactId>
<version>3.2.5</version>
</plugin>
<!--
exec-maven-plugin: lets you run a main class directly with `mvn exec:java`.
Used to run the RateLimiterBenchmark without packaging a fat jar.
Command: mvn compile exec:java -Dexec.mainClass=org.example.review.RateLimiterBenchmark
-->
<plugin>
<groupId>org.codehaus.mojo</groupId>
<artifactId>exec-maven-plugin</artifactId>
<version>3.1.0</version>
<configuration>
<mainClass>org.example.review.RateLimiterBenchmark</mainClass>
</configuration>
</plugin>
</plugins>
</build>
</project>
RateLimiter.java
package org.example.review;
/**
* A rate limiter that allows up to a maximum number of requests in a rolling
* time window.
*
* <p>
* Two implementations are provided for comparison:
* <ul>
* <li>{@link TokenBucketRateLimiter} — allows bursting; O(1) time and
* space</li>
* <li>{@link SlidingWindowRateLimiter} — strict fairness; O(k) time and
* space</li>
* </ul>
*
* <p>
* All implementations must be thread-safe.
*/
public interface RateLimiter {
/**
* Attempts to acquire permission to proceed. Returns immediately.
*
* @return {@code true} if the request is allowed; {@code false} if the rate
* limit
* has been exceeded and the request should be rejected
*/
boolean tryAcquire();
/**
* Resets the rate limiter to its initial state.
* Used in tests to provide a clean baseline between test cases.
*/
void reset();
}
TokenBucketRateLimiter.java
package org.example.review;
/**
* Token bucket rate limiter.
*
* <p>
* <strong>Algorithm:</strong>
*
* <pre>
* Capacity: maximum tokens the bucket can hold (= maximum burst size)
* Refill rate: tokens added per second
* Current state: how many tokens are currently in the bucket
*
* On tryAcquire():
* 1. Compute elapsed time since last refill
* 2. Add (elapsed × refillRate) tokens to the bucket, capped at capacity
* 3. If bucket has ≥ 1 token, consume 1 token and return true
* 4. Otherwise return false
* </pre>
*
* <p>
* <strong>Complexity:</strong>
* <ul>
* <li>Time: O(1) per {@code tryAcquire()}</li>
* <li>Space: O(1) — only stores current token count and last refill
* timestamp</li>
* </ul>
*
* <p>
* <strong>Burst behavior:</strong> A client that is idle for {@code k} seconds
* accumulates up to {@code min(k × refillRate, capacity)} tokens and can fire
* that many requests in rapid succession. This is intentional — the algorithm
* models "credit" for unused capacity.
*
* <p>
* This implementation is thread-safe.
*/
public class TokenBucketRateLimiter implements RateLimiter {
private final int capacity; // maximum tokens (= burst ceiling)
private final double refillRate; // tokens per nanosecond
private double tokens; // current token count (fractional to avoid drift)
private long lastRefillNanos; // System.nanoTime() at last refill
/**
* @param capacity maximum burst size (tokens that can accumulate while idle)
* @param ratePerSec maximum sustained request rate (tokens added per second)
*/
public TokenBucketRateLimiter(int capacity, int ratePerSec) {
if (capacity <= 0) {
throw new IllegalArgumentException("capacity must be > 0");
}
if (ratePerSec <= 0) {
throw new IllegalArgumentException("ratePerSec must be > 0");
}
this.capacity = capacity;
this.refillRate = (double) ratePerSec / 1_000_000_000L; // tokens per nanosecond
this.tokens = capacity;
this.lastRefillNanos = System.nanoTime();
}
@Override
public synchronized boolean tryAcquire() {
refill();
if (tokens >= 1.0) {
tokens -= 1.0;
return true;
}
return false;
}
@Override
public synchronized void reset() {
tokens = capacity;
lastRefillNanos = System.nanoTime();
}
/**
* Adds tokens proportional to elapsed time since the last refill.
* Called on every {@code tryAcquire()} to lazily update the bucket.
*/
private void refill() {
long now = System.nanoTime();
double elapsed = now - lastRefillNanos;
tokens = Math.min(capacity, tokens + elapsed * refillRate);
lastRefillNanos = now;
}
}
SlidingWindowRateLimiter.java
package org.example.review;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* Sliding window log rate limiter.
*
* <p>
* <strong>Algorithm:</strong>
*
* <pre>
* Window: time duration in nanoseconds (e.g., 1 second)
* Limit: maximum requests in any window of that duration
* Log: timestamps of every allowed request in the current window
*
* On tryAcquire():
* 1. Remove all timestamps older than (now - window)
* 2. If log.size() < limit, add 'now' to the log and return true
* 3. Otherwise return false
* </pre>
*
* <p>
* <strong>Complexity:</strong>
* <ul>
* <li>Time: O(k) per {@code tryAcquire()}, where k = number of requests in the
* current window (expiry sweep). In the worst case (high sustained load) k =
* limit.</li>
* <li>Space: O(k) — the log stores one timestamp per allowed request in the
* window.
* At maximum sustained load: O(limit) entries.</li>
* </ul>
*
* <p>
* <strong>Fairness guarantee:</strong> No more than {@code limit} requests are
* allowed in any rolling window of {@code windowMillis} milliseconds — not just
* on a fixed-clock boundary, but in any contiguous window. This prevents the
* "reset burst" problem of fixed-window algorithms.
*
* <p>
* This implementation is thread-safe.
*/
public class SlidingWindowRateLimiter implements RateLimiter {
private final int limit; // max requests per window
private final long windowNanos; // window size in nanoseconds
private final Deque<Long> log; // timestamps of allowed requests
/**
* @param limit maximum number of requests per window
* @param windowMillis window duration in milliseconds
*/
public SlidingWindowRateLimiter(int limit, long windowMillis) {
if (limit <= 0) {
throw new IllegalArgumentException("limit must be > 0");
}
if (windowMillis <= 0) {
throw new IllegalArgumentException("windowMillis must be > 0");
}
this.limit = limit;
this.windowNanos = windowMillis * 1_000_000L;
this.log = new ArrayDeque<>(limit);
}
@Override
public synchronized boolean tryAcquire() {
long now = System.nanoTime();
long windowStart = now - windowNanos;
// Evict timestamps older than the window start (O(k) where k = expired entries)
while (!log.isEmpty() && log.peekFirst() <= windowStart) {
log.pollFirst();
}
if (log.size() < limit) {
log.addLast(now);
return true;
}
return false;
}
@Override
public synchronized void reset() {
log.clear();
}
}
RateLimiterBenchmark.java
package org.example.review;
/**
* Throughput comparison for {@link TokenBucketRateLimiter} vs
* {@link SlidingWindowRateLimiter}.
*
* <p>
* This is NOT a rigorous microbenchmark (no JVM warmup isolation, no JIT
* stabilization).
* It is a first-pass comparison that gives you order-of-magnitude numbers for
* the
* vote email. For production profiling, use JMH.
*
* <p>
* Run with:
*
* <pre>
* mvn compile exec:java -Dexec.mainClass=org.example.review.RateLimiterBenchmark
* </pre>
*/
public class RateLimiterBenchmark {
// Limit so high that tryAcquire() never rejects — we're measuring call
// overhead,
// not rejection logic. The real-world comparison matters when the limiter is
// under constant accepted load.
private static final int LARGE_LIMIT = 10_000_000;
private static final int ITERATIONS = 5_000_000;
private static final int WARMUP_ITER = 500_000;
public static void main(String[] args) throws InterruptedException {
System.out.println("=== RateLimiter Throughput Comparison ===\n");
System.out.println("Iterations: " + ITERATIONS + " (+ " + WARMUP_ITER + " warmup)\n");
// --- Token Bucket ---
TokenBucketRateLimiter tokenBucket = new TokenBucketRateLimiter(LARGE_LIMIT, LARGE_LIMIT);
long tbResult = measure(tokenBucket, "TokenBucketRateLimiter ");
// Small pause between runs to let the OS scheduler settle
Thread.sleep(200);
// --- Sliding Window ---
SlidingWindowRateLimiter slidingWindow = new SlidingWindowRateLimiter(LARGE_LIMIT, 1000L);
long swResult = measure(slidingWindow, "SlidingWindowRateLimiter");
// --- Summary ---
System.out.println("\n=== Summary ===");
System.out.printf("Token bucket: %,d ns per call%n", tbResult);
System.out.printf("Sliding window: %,d ns per call%n", swResult);
double ratio = (double) swResult / tbResult;
System.out.printf("Ratio (SW / TB): %.2fx%n", ratio);
System.out.println("\nInterpretation:");
if (ratio > 3.0) {
System.out.println("Sliding window is >3x slower per call.");
System.out.println("Under high-rate sustained load (the common case for a rate limiter),");
System.out.println("this overhead is significant. Token bucket is the better choice for");
System.out.println("throughput-sensitive paths.");
} else if (ratio > 1.5) {
System.out.println("Sliding window is moderately slower.");
System.out.println("The tradeoff may be acceptable if strict per-window fairness is required.");
} else {
System.out.println("Performance is comparable. Choose based on fairness requirements.");
}
}
/**
* Runs warmup iterations (ignored), then measures the time for
* {@code ITERATIONS}
* calls to {@code tryAcquire()}.
*
* @return average nanoseconds per call
*/
private static long measure(RateLimiter limiter, String label) {
// Warmup: prime the JIT
limiter.reset();
for (int i = 0; i < WARMUP_ITER; i++) {
limiter.tryAcquire();
}
// Measure
limiter.reset();
long start = System.nanoTime();
for (int i = 0; i < ITERATIONS; i++) {
limiter.tryAcquire();
}
long elapsed = System.nanoTime() - start;
long nsPerCall = elapsed / ITERATIONS;
System.out.printf("%-25s total=%,d ms per-call=%,d ns throughput=%.1f M/sec%n",
label,
elapsed / 1_000_000,
nsPerCall,
ITERATIONS / (elapsed / 1e9) / 1_000_000.0);
return nsPerCall;
}
}
RateLimiterTest.java
package org.example.review;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.MethodSource;
import java.util.stream.Stream;
import static org.junit.jupiter.api.Assertions.*;
/**
* Correctness tests for both {@link RateLimiter} implementations.
*
* Uses parameterized tests so the same invariants are verified against both
* TokenBucketRateLimiter and SlidingWindowRateLimiter.
*/
class RateLimiterTest {
/** Provides both implementations for parameterized tests. */
static Stream<RateLimiter> implementations() {
return Stream.of(
new TokenBucketRateLimiter(5, 5), // 5 tokens, 5/sec
new SlidingWindowRateLimiter(5, 1000L) // 5 per 1-second window
);
}
/**
* Within the burst/limit budget the limiter must allow all requests.
*/
@ParameterizedTest
@MethodSource("implementations")
void testAllowsUpToLimit(RateLimiter limiter) {
limiter.reset();
for (int i = 0; i < 5; i++) {
assertTrue(limiter.tryAcquire(),
"Expected tryAcquire() to return true for request " + (i + 1) + " of 5");
}
}
/**
* After the limit is exhausted, the next request must be rejected.
*/
@ParameterizedTest
@MethodSource("implementations")
void testRejectsWhenLimitExhausted(RateLimiter limiter) {
limiter.reset();
for (int i = 0; i < 5; i++) {
limiter.tryAcquire(); // consume all budget
}
assertFalse(limiter.tryAcquire(),
"Expected tryAcquire() to return false after limit is exhausted");
}
/**
* reset() must restore the limiter to its initial state so all requests
* are allowed again.
*/
@ParameterizedTest
@MethodSource("implementations")
void testResetRestoresBudget(RateLimiter limiter) {
limiter.reset();
for (int i = 0; i < 5; i++) {
limiter.tryAcquire(); // exhaust budget
}
limiter.reset();
assertTrue(limiter.tryAcquire(),
"Expected tryAcquire() to return true after reset()");
}
/**
* Both implementations must reject invalid construction arguments.
*/
@Test
void testTokenBucket_rejectsInvalidArgs() {
assertThrows(IllegalArgumentException.class,
() -> new TokenBucketRateLimiter(0, 5));
assertThrows(IllegalArgumentException.class,
() -> new TokenBucketRateLimiter(5, 0));
}
@Test
void testSlidingWindow_rejectsInvalidArgs() {
assertThrows(IllegalArgumentException.class,
() -> new SlidingWindowRateLimiter(0, 1000L));
assertThrows(IllegalArgumentException.class,
() -> new SlidingWindowRateLimiter(5, 0L));
}
/**
* Token bucket ONLY: after sleeping 1 second with a 5/sec refill rate,
* the bucket should have refilled and allow another 5 requests.
*
* This test documents the burst behavior that sliding window does NOT exhibit.
*/
@Test
void testTokenBucket_refillsAfterIdle() throws InterruptedException {
TokenBucketRateLimiter limiter = new TokenBucketRateLimiter(5, 5);
limiter.reset();
for (int i = 0; i < 5; i++) {
limiter.tryAcquire(); // exhaust
}
Thread.sleep(1100); // wait > 1 second for refill
assertTrue(limiter.tryAcquire(),
"Expected token bucket to allow requests after idle refill period");
}
/**
* Sliding window ONLY: after the window elapses, the count resets.
*
* This test documents the strict window enforcement that token bucket
* allows to be bypassed via burst.
*/
@Test
void testSlidingWindow_allowsAfterWindowElapses() throws InterruptedException {
SlidingWindowRateLimiter limiter = new SlidingWindowRateLimiter(5, 500L);
limiter.reset();
for (int i = 0; i < 5; i++) {
limiter.tryAcquire(); // exhaust
}
assertFalse(limiter.tryAcquire(), "Should be rate-limited immediately after exhaustion");
Thread.sleep(600); // wait for window to elapse
assertTrue(limiter.tryAcquire(),
"Expected sliding window to allow requests after window has elapsed");
}
}