Lab L07 · Java + Go

Implementing a per-client rate limiter

Build a per-client rate limiter using token buckets. Each client has a bucket that holds up to burst tokens and refills continuously at rate tokens per second; each request spends one token or is rejected immediately (no waiting). The limiter also caps how many clients it tracks at once and forgets clients that have been idle for a configured time.

The task

An API gateway lets each API key make about 5 requests per second, with short bursts of up to 10. A token bucket gives exactly that: a full bucket allows a burst, and a steady refill allows the long-run rate. Tracking every key ever seen would leak memory, so buckets idle for longer than idle are dropped — a returning client simply starts with a full bucket again — and the total number of tracked clients is capped.

Left: the bucket model. Right: tokens for client x in the worked example. The line climbs at rate, never above burst; a request needs at least one whole token.

What you implement

public final class RateLimiter {
    public enum Result { ALLOWED, LIMITED, CLIENT_LIMIT }
    public RateLimiter(double rate,          // tokens per second, > 0 and finite
                       int burst,            // bucket size, > 0
                       int maxClients,       // max tracked clients, > 0
                       Duration idle,        // forget clients idle this long, > 0
                       LongSupplier now);    // monotonic nanoseconds (fake in tests)
    public Result allow(String client);
}

Rules

A client seen for the first time gets a full bucket (burst tokens).
On each call: tokens = min(burst, tokens + elapsedSeconds × rate). Fractional tokens accumulate.
If tokens ≥ 1: spend one and return ALLOWED. Otherwise return LIMITED — nothing is queued.
Before deciding, drop every client whose last call was at least idle ago.
A new client when maxClients are already tracked → CLIENT_LIMIT, and no bucket is created.
Clock moving backwards → IllegalStateException. Invalid configuration → IllegalArgumentException. Thread-safe.

Worked example

rate = 1/s, burst = 2. At t=0: allow(x) → ALLOWED (1 left), ALLOWED (0 left), LIMITED.
t=0.5 s: bucket refilled to 0.5 → LIMITED.
t=1.5 s: 0.5 + 1.0 = 1.5 → ALLOWED (0.5 left).
With maxClients = 1, allow(y) while x is still tracked → CLIENT_LIMIT.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: RateLimiter.java · tests: RateLimiterTest.java. Go starter: limiter.go · tests: limiter_test.go.

cd java
./gradlew test --tests 'labs.ratelimiter.*'

cd go
go test -race -count=1 ./ratelimiter

Reveal the reference solutions

Java: RateLimiter.java
Go: limiter.go

When to use

Use this lab to cap admission for individual client identities in one process. A token bucket starts with a positive burst capacity, refills at a positive finite rate measured in tokens per second, and consumes one token for each admitted request. A rejected request is not queued. The retained client count also has a positive limit; a new client receives a distinct cardinality rejection if no slot is available.

This is not a global distributed quota. Multiple independent processes multiply the effective allowance unless routing or a shared coordinator establishes another guarantee. Client identities must be authenticated or otherwise trustworthy: unlimited identities defeat a per-client policy. The cardinality bound limits entries, not identifier lengths or caller-owned request memory.

Steps

Define the state. Each client owns a fractional token count and a last-observed time. One lock protects cleanup, refill, and admission as a compound operation. Java uses an injected monotonic nanosecond supplier; Go uses an injected time function whose normal implementation can be time.Now.
Refill without minting excess credit. Add elapsed seconds multiplied by the rate, clamp at burst capacity, and consume one token only if at least one is available. Preserve fractional credit rather than truncating it after every request. Reject invalid rates including infinity and NaN at construction.
Specify idle cleanup. Every request sweeps buckets whose last attempt was at least the configured idle duration ago. Attempts that are denied still update last activity. A recreated bucket receives a full burst. Thus idle eviction changes admission semantics: configure the idle duration deliberately, normally no shorter than the time needed to refill a burst if equivalent refill behavior matters.
Bound cardinality. After sweeping, reject a new identity if the limit is still reached. Do not evict a busy client's bucket merely to admit a new identity, which would reset quotas unexpectedly. Cleanup is O(n) in retained clients and happens under the lock; benchmark before replacing it with an expiry structure.
Control time in tests. At two tokens per second and burst two, two immediate requests succeed, the third fails, and advancing by half a second permits one more. Advance to the idle boundary to reclaim the old identity and admit a new one.
Exercise concurrent admission. With a fixed fake clock and burst five, run a hundred requests and require exactly five successes. This tests the compound credit check and decrement without relying on sleeps. Floating-point arithmetic can still round near boundaries; choose a numerical representation appropriate to stricter accounting requirements.

Checklist

Recall and variation

Rebuild fractional refill before reading Go or Java. Variation: deny several requests between half-token clock advances. Acceptance: partial credit survives denial, the burst is never exceeded, and client cleanup follows the documented idle boundary.

Rate, burst, idle duration, and client limit are valid
Token consumption and refill share the same atomic boundary
Saturation and client-cardinality rejection are distinct outcomes
Idle reset behavior and distributed limitations are explicit
The clock does not move backwards and comparisons stay within their range

Signals

Working: fake-clock tests predict each admission and concurrent requests cannot consume the same token twice.

Going wrong: every denied request loses fractional credit, idle cleanup silently resets active clients, or local limits are advertised as a fleet-wide quota.

Implementing a Bounded Worker Pool, because limiting admitted work differs from limiting executing work.