Low Level Design (LLD) Interview Questions
Design a Rate Limiter
Tier: CommonDifficulty: MediumAsked of: Mid, SeniorAsked at: Stripe, Google, Amazon
Video chapters
- 0:00 A counter is not enough
- 0:30 Return a decision, not just false
- 1:06 Four tokens. One per second.
- 1:39 Make the arithmetic visible
- 2:28 Follow a request that costs two permits
- 2:59 Time belongs behind an interface
- 3:15 Two threads. One remaining token.
- 4:23 Why not a fixed window?
- 4:56 The map is part of the design
- 5:29 On Android, pace the queue
- 5:50 What changes with several servers?
- 6:26 Test boundaries without waiting
- 6:44 An answer you can say in the interview
Video transcript
Your app comes back online with two hundred requests waiting. Sending all of them at once can overwhelm the backend. You add a counter. But what happens at the window boundary, or when two threads ask for the last permit? Those are the questions that turn a counter into a rate limiter design.
I would first clarify the key, the allowed burst, and where the limiter runs. Is the limit per user, device, or endpoint? Does one request cost one permit? Are we protecting one process or several servers? For this walkthrough, we will allow short bursts and start inside one process.
The public method tries to acquire permits for a key. If the request is allowed, the result says how much budget remains. A rejected result says how long to wait. A boolean throws that second piece away and makes every caller invent a retry delay. A useful result gives the caller enough information to schedule its next attempt.
The limiter looks up the bucket for this user. The bucket runs one algorithm. A rule describes the capacity and refill rate, and an injected clock supplies time. Each bucket owns its own state. Users should not share one accidental global budget, and independent users should not wait behind one global lock.
Imagine a bucket that holds four tokens and refills at one token per second. A request costs one. After a quiet period, the bucket is full. Four requests can pass immediately. The fifth is rejected because there is no token left. The size controls the burst. The refill rate controls the sustained traffic.
We do not need a timer adding tokens in the background. Store the token count and the last refill time. When the next request arrives, calculate how much time passed and add the missing refill, capped at four. A bucket nobody is using does no work. This is called lazy refill.
The calculation is available tokens equals the smaller of capacity, or saved tokens plus elapsed time times refill rate. Suppose the bucket is empty and half a second passes. It now has half a token. That is not enough for a request, but it is real progress toward the next permit.
Do not round that half token down while also moving the timestamp forward. If a client keeps checking before a whole token appears, throwing away every fraction can stop it recovering. Keep fractional tokens in the internal state. Round only where the public result needs a whole count or a delay.
The rejected request needs one token and has half. At one token per second, it needs another half second. Return five hundred milliseconds. The caller should schedule work later, not spin in a loop. If the request asks for more than the entire bucket can hold, waiting will never fix it. Reject that input.
Let us follow a request that costs two permits. Our bucket still holds four and refills one token per second. It starts empty at time zero. After one and a half seconds, the request arrives. The balance has reached one and a half tokens, so it still cannot cover the cost of two.
It is rejected. One and a half seconds adds one and a half tokens. The request needs two, so it is short by half a token. The delay is half a second. Notice that a rejected request does not spend the partial balance. At two seconds, the same two permit request can succeed.
The clock is a dependency, not a direct call hidden inside the algorithm. A manual clock lets a test advance exactly five hundred milliseconds without sleeping. In production, elapsed time should come from a monotonic clock, which does not jump when the user changes the displayed date or time.
Now the concurrency question. Two threads read a balance of one. Each decides to allow a request, then each writes zero. Two requests passed, but only one token was spent. A concurrent map does not prevent this race inside the object it stores. Reading, deciding, and consuming must form one protected operation.
The Kotlin example keeps the token count and timestamp in one immutable state object. That pair matters. Updating the count without the corresponding time can make the next refill wrong. An atomic reference lets us replace the complete pair only if it still matches the state we just read.
Inside the loop, read the state, calculate the refill, and check the cost. Build the next state with the permits removed. Compare and set publishes it only if no other thread changed the old state. If that fails, start again. Never reuse a calculation made from a balance that another thread already spent.
A synchronized operation per bucket is often simpler to explain and can be perfectly correct. The atomic loop is one implementation choice, not a requirement to collect pattern names. The key interview point is the scope of the protection. Competing requests for one user coordinate, while unrelated users can proceed independently.
A fixed window counter is cheap, but its boundary permits a burst. With a limit of one hundred per minute, a client can send one hundred just before the boundary and another one hundred just after it. Each minute obeys the rule, yet two hundred arrive almost together. Ask whether that behaviour is acceptable.
A sliding log keeps individual timestamps and can enforce an exact rolling window, at a memory cost. A sliding counter estimates the overlap with the previous window, so the estimate can be high or low. A leaky queue releases work at a steady pace. Token bucket is useful when short bursts are allowed.
What if every request invents a new key? One bucket per key becomes a memory problem. Bound the key space or the map size, and remove entries only when forgetting them cannot reset an active limit. For a token bucket, being fully refilled is necessary, but there is still a concurrency question.
A request may hold a bucket reference while cleanup removes that bucket from the map. A second request then creates a new bucket for the same key. Both can spend separate balances. Coordinate lookup, use, and eviction for the key, or keep a safe ownership scheme. Calling the map concurrent does not solve this.
On Android, the repository or upload worker can use the limiter before sending queued work. The ViewModel observes progress. A rejection schedules a later attempt and never blocks the main thread. Backoff slows one failing request. A limiter controls the total across requests. Client pacing helps reliability, but server limits still enforce abuse protection.
If three app servers each give a user four tokens, that user can spend twelve. A shared limit needs shared state or an explicitly coordinated budget. With Redis, the refill, decision, and consume must run atomically together, commonly in a script. Separate network calls for read and write recreate the same race.
Do we allow requests when the shared limiter fails, or refuse them? There is no universal answer. Availability may justify a stricter local fallback for a low risk endpoint. An abuse sensitive or expensive operation may need to refuse. State the product tradeoff and decide it deliberately before an outage does it for you.
My tests cover an initial burst, the next rejected request, exact refill boundaries, fractional progress, and two callers fighting for the last token. I would also test oversized costs, independent users, clock behaviour, and eviction during an active request. A fake clock and controlled thread ordering make these repeatable.
I return an allowed or rejected result from try acquire. Each key owns an algorithm and its state. Token bucket refills from elapsed time and keeps fractional progress. Check and consume are atomic. The clock is injected, memory is bounded, and a distributed version coordinates the decision in shared storage.
If the interviewer changes the allowed burst or asks for an exact rolling window, explain how that changes the algorithm choice. If they add threads or servers, explain where the atomic decision moves. Those connections matter more than memorizing five names. The full walkthrough and Kotlin source are linked on Android Interview.
A rate limiter controls how often a user can perform an action. Before processing a request, it answers whether that user has any allowance left.
The problem
Give each user room for four requests and refill one request per second. If Ana sends five requests immediately, the first four pass and the fifth is refused. After one second, she can send one more. Ben has his own allowance.
Start with one process and one unit of allowance per request. Return true or false immediately. Retry scheduling, distributed storage and multiple algorithms are follow-ups.
How to explain the design
“I use a token bucket for each user. A token is permission to make one request. Before checking a request, I add the tokens earned since the last check, up to the bucket's capacity. If at least one token remains, I consume it and allow the request. Otherwise, I reject it.”
RateLimiter owns the user map. Each Bucket stores its remaining tokens and last update time. The clock is passed into allow, so tests can advance time without waiting.
Walk through one request
- A new user's bucket starts full with four tokens.
- A request consumes one, leaving three.
- Three more immediate requests empty the bucket. The next is refused.
- One second later, refill adds one token. The next request consumes it.
No background timer is needed. Refill is calculated when a request arrives. Keep fractional tokens so two half seconds still earn one whole token.
Interview implementation
Check and consumption happen under one lock. That makes two concurrent requests unable to spend the same final token. Use elapsed time from a monotonic clock, such as System.nanoTime, whose purpose is measuring time intervals.
Java
RateLimiter.java
package interview.ratelimiter;
import java.util.HashMap;
import java.util.Map;
public class RateLimiter {
private static class Bucket {
double tokens;
long updatedAt;
Bucket(double tokens, long updatedAt) {
this.tokens = tokens;
this.updatedAt = updatedAt;
}
}
private final int capacity;
private final double refillPerSecond;
private final Map<String, Bucket> buckets = new HashMap<>();
public RateLimiter(int capacity, double refillPerSecond) {
if (capacity <= 0 || !Double.isFinite(refillPerSecond) || refillPerSecond <= 0) {
throw new IllegalArgumentException("Capacity and refill rate must be positive");
}
this.capacity = capacity;
this.refillPerSecond = refillPerSecond;
}
// nowNanos must come from a monotonic clock, such as System.nanoTime().
public synchronized boolean allow(String user, long nowNanos) {
Bucket bucket = buckets.computeIfAbsent(user, key -> new Bucket(capacity, nowNanos));
if (nowNanos < bucket.updatedAt) throw new IllegalArgumentException("Clock moved backwards");
double seconds = (nowNanos - bucket.updatedAt) / 1_000_000_000.0;
bucket.tokens = Math.min(capacity, bucket.tokens + seconds * refillPerSecond);
bucket.updatedAt = nowNanos;
if (bucket.tokens < 1) return false;
bucket.tokens -= 1;
return true;
}
}
package interview.ratelimiter;
import java.util.HashMap;
import java.util.Map;
public class RateLimiter {
private static class Bucket {
double tokens;
long updatedAt;
Bucket(double tokens, long updatedAt) {
this.tokens = tokens;
this.updatedAt = updatedAt;
}
}
private final int capacity;
private final double refillPerSecond;
private final Map<String, Bucket> buckets = new HashMap<>();
public RateLimiter(int capacity, double refillPerSecond) {
if (capacity <= 0 || !Double.isFinite(refillPerSecond) || refillPerSecond <= 0) {
throw new IllegalArgumentException("Capacity and refill rate must be positive");
}
this.capacity = capacity;
this.refillPerSecond = refillPerSecond;
}
public synchronized boolean allow(String user, long nowNanos) {
Bucket bucket = buckets.computeIfAbsent(user, key -> new Bucket(capacity, nowNanos));
if (nowNanos < bucket.updatedAt) throw new IllegalArgumentException("Clock moved backwards");
double seconds = (nowNanos - bucket.updatedAt) / 1_000_000_000.0;
bucket.tokens = Math.min(capacity, bucket.tokens + seconds * refillPerSecond);
bucket.updatedAt = nowNanos;
if (bucket.tokens < 1) return false;
bucket.tokens -= 1;
return true;
}
}
Kotlin
RateLimiter.kt
package interview.ratelimiter
class RateLimiter(private val capacity: Int, private val refillPerSecond: Double) {
private data class Bucket(var tokens: Double, var updatedAt: Long)
private val buckets = mutableMapOf<String, Bucket>()
init {
require(capacity > 0 && refillPerSecond.isFinite() && refillPerSecond > 0)
}
// nowNanos must come from a monotonic clock, such as System.nanoTime().
@Synchronized
fun allow(user: String, nowNanos: Long): Boolean {
val bucket = buckets.getOrPut(user) { Bucket(capacity.toDouble(), nowNanos) }
require(nowNanos >= bucket.updatedAt)
val seconds = (nowNanos - bucket.updatedAt) / 1_000_000_000.0
bucket.tokens = minOf(capacity.toDouble(), bucket.tokens + seconds * refillPerSecond)
bucket.updatedAt = nowNanos
if (bucket.tokens < 1) return false
bucket.tokens -= 1
return true
}
}
package interview.ratelimiter
class RateLimiter(private val capacity: Int, private val refillPerSecond: Double) {
private data class Bucket(var tokens: Double, var updatedAt: Long)
private val buckets = mutableMapOf<String, Bucket>()
init {
require(capacity > 0 && refillPerSecond.isFinite() && refillPerSecond > 0)
}
@Synchronized
fun allow(user: String, nowNanos: Long): Boolean {
val bucket = buckets.getOrPut(user) { Bucket(capacity.toDouble(), nowNanos) }
require(nowNanos >= bucket.updatedAt)
val seconds = (nowNanos - bucket.updatedAt) / 1_000_000_000.0
bucket.tokens = minOf(capacity.toDouble(), bucket.tokens + seconds * refillPerSecond)
bucket.updatedAt = nowNanos
if (bucket.tokens < 1) return false
bucket.tokens -= 1
return true
}
}
Follow-up questions
Many users?
“I would periodically remove idle buckets, but only when they would have refilled completely.” Recreating an empty bucket too early would give that user a fresh burst. An empty bucket with capacity 4 and a refill of 1 per second can safely be removed after 4 idle seconds.
This helper checks the condition. Calculate idle time and remove eligible entries under the same lock as allow.
Kotlin
fun canEvict(tokens: Double, idleSeconds: Double,
capacity: Int, refillPerSecond: Double): Boolean =
tokens + idleSeconds * refillPerSecond >= capacityJava
static boolean canEvict(double tokens, double idleSeconds,
int capacity, double refillPerSecond) {
return tokens + idleSeconds * refillPerSecond >= capacity;
}Many threads?
“I would lock each user's bucket, so unrelated users can proceed at the same time.” The refill, check and subtraction still happen together inside that lock. The map also needs safe lookup and creation. If buckets can be removed, coordinate removal with requests so a request cannot spend from an old bucket while another spends from its replacement.
Several servers?
“Every server must check the same allowance.” Put bucket state in shared storage and perform refill, check and subtraction as one atomic operation, meaning no other request can slip between those steps. Separate reads and writes could both approve the last token. Use a common time source for refill, rather than comparing System.nanoTime readings from different processes.
What should I test?
“With capacity 4, four immediate requests should pass and the fifth should fail.” After half a second at 1 token per second, another request should still fail. At one full second it should pass. A long idle period should refill only to 4, and another user should have an independent bucket. With one token and two simultaneous requests, exactly one should pass.
Extended implementation and optional features
This reference explores a larger scope. Use it after you can explain and write the interview version. Its extra types and features are not required for the scope above.
Java
com.androidinterview.ratelimiter.KeyedRateLimiter.java
package com.androidinterview.ratelimiter;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Supplier;
import com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm;
import com.androidinterview.ratelimiter.core.Clock;
import com.androidinterview.ratelimiter.core.Decision;
// A limit is never global, it is per user, per API key, per device, per
// endpoint. So the limiter is a map from key to one bucket.
//
// The supplier is the seam. Swapping the whole fleet from a fixed window to a
// token bucket is one lambda at the construction site.
public final class KeyedRateLimiter implements RateLimiter {
private final Clock clock;
private final Supplier<RateLimitAlgorithm> newBucket;
private final long sweepEveryMillis;
private final ConcurrentHashMap<String, RateLimitAlgorithm> buckets = new ConcurrentHashMap<>();
private final AtomicLong nextSweepMillis;
public KeyedRateLimiter(Clock clock, Supplier<RateLimitAlgorithm> newBucket) {
this(clock, newBucket, 60_000L);
}
public KeyedRateLimiter(Clock clock, Supplier<RateLimitAlgorithm> newBucket, long sweepEveryMillis) {
this.clock = clock;
this.newBucket = newBucket;
this.sweepEveryMillis = sweepEveryMillis;
this.nextSweepMillis = new AtomicLong(clock.nowMillis() + sweepEveryMillis);
}
@Override
public Decision tryAcquire(String key) {
return tryAcquire(key, 1);
}
// Lookup and use stay inside one map computation. Eviction uses the same
// coordination, so it cannot remove a bucket during a request. Keep this
// callback short and do no network work here. Keys sharing a hash bin may
// also wait for each other; this is not one global lock.
@Override
public Decision tryAcquire(String key, int permits) {
long now = clock.nowMillis();
sweepIfDue(now);
Decision[] result = new Decision[1];
buckets.compute(key, (ignored, current) -> {
RateLimitAlgorithm bucket = current != null ? current : newBucket.get();
result[0] = bucket.tryAcquire(now, permits);
return bucket;
});
return result[0];
}
public int size() {
return buckets.size();
}
// Check and remove using the same coordination as lookup and use. A full
// bucket is safe to forget only when nobody can still spend through an
// old reference. Count actual removals rather than a changing map size.
public int evictIdle(long nowMillis) {
int[] removed = {0};
for (String key : buckets.keySet()) {
buckets.computeIfPresent(key, (ignored, bucket) -> {
if (!bucket.isIdle(nowMillis)) return bucket;
removed[0]++;
return null;
});
}
return removed[0];
}
// One sweep per interval across all threads. The compare and set is what
// stops fifty threads sweeping at once the moment the interval passes.
private void sweepIfDue(long nowMillis) {
long due = nextSweepMillis.get();
if (nowMillis < due || !nextSweepMillis.compareAndSet(due, nowMillis + sweepEveryMillis)) {
return;
}
evictIdle(nowMillis);
}
}
package com.androidinterview.ratelimiter;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Supplier;
import com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm;
import com.androidinterview.ratelimiter.core.Clock;
import com.androidinterview.ratelimiter.core.Decision;
public final class KeyedRateLimiter implements RateLimiter {
private final Clock clock;
private final Supplier<RateLimitAlgorithm> newBucket;
private final long sweepEveryMillis;
private final ConcurrentHashMap<String, RateLimitAlgorithm> buckets = new ConcurrentHashMap<>();
private final AtomicLong nextSweepMillis;
public KeyedRateLimiter(Clock clock, Supplier<RateLimitAlgorithm> newBucket) {
this(clock, newBucket, 60_000L);
}
public KeyedRateLimiter(Clock clock, Supplier<RateLimitAlgorithm> newBucket, long sweepEveryMillis) {
this.clock = clock;
this.newBucket = newBucket;
this.sweepEveryMillis = sweepEveryMillis;
this.nextSweepMillis = new AtomicLong(clock.nowMillis() + sweepEveryMillis);
}
@Override
public Decision tryAcquire(String key) {
return tryAcquire(key, 1);
}
@Override
public Decision tryAcquire(String key, int permits) {
long now = clock.nowMillis();
sweepIfDue(now);
Decision[] result = new Decision[1];
buckets.compute(key, (ignored, current) -> {
RateLimitAlgorithm bucket = current != null ? current : newBucket.get();
result[0] = bucket.tryAcquire(now, permits);
return bucket;
});
return result[0];
}
public int size() {
return buckets.size();
}
public int evictIdle(long nowMillis) {
int[] removed = {0};
for (String key : buckets.keySet()) {
buckets.computeIfPresent(key, (ignored, bucket) -> {
if (!bucket.isIdle(nowMillis)) return bucket;
removed[0]++;
return null;
});
}
return removed[0];
}
private void sweepIfDue(long nowMillis) {
long due = nextSweepMillis.get();
if (nowMillis < due || !nextSweepMillis.compareAndSet(due, nowMillis + sweepEveryMillis)) {
return;
}
evictIdle(nowMillis);
}
}
com.androidinterview.ratelimiter.RateLimiter.java
package com.androidinterview.ratelimiter;
import com.androidinterview.ratelimiter.core.Decision;
// The whole public surface. A caller never learns whether it is talking to a
// token bucket, a sliding window or a Redis script, which is what lets the
// algorithm be swapped in one line.
public interface RateLimiter {
Decision tryAcquire(String key);
// Several permits at once, for a batch that should cost what it costs.
// More permits than the limit itself throws, because waiting cannot fix it.
Decision tryAcquire(String key, int permits);
}
package com.androidinterview.ratelimiter;
import com.androidinterview.ratelimiter.core.Decision;
public interface RateLimiter {
Decision tryAcquire(String key);
Decision tryAcquire(String key, int permits);
}
com.androidinterview.ratelimiter.algorithm.FixedWindowCounter.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// Two numbers per key whatever the traffic, and a boundary burst. A hundred
// requests in the last millisecond of one window and a hundred in the first
// millisecond of the next is two hundred inside two milliseconds, and the
// counter sees nothing wrong because it saw a hundred and then a hundred.
public final class FixedWindowCounter implements RateLimitAlgorithm {
private final Rule rule;
private long windowStart;
private int used;
public FixedWindowCounter(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
roll(nowMillis);
if (used + permits <= rule.permits()) {
used += permits;
return new Decision.Allowed(rule.permits() - used);
}
// Nothing can help before the window turns over, so that is the wait.
return new Decision.Rejected(windowStart + rule.windowMillis() - nowMillis);
}
// Aligned to the epoch rather than to the first request, so every key rolls
// at the same instant. That makes the boundary burst reproducible instead
// of random, which is what you want from a bug you decided to live with.
private void roll(long nowMillis) {
long start = nowMillis - Math.floorMod(nowMillis, rule.windowMillis());
if (start != windowStart) {
windowStart = start;
used = 0;
}
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return nowMillis - windowStart >= rule.windowMillis();
}
}
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
public final class FixedWindowCounter implements RateLimitAlgorithm {
private final Rule rule;
private long windowStart;
private int used;
public FixedWindowCounter(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
roll(nowMillis);
if (used + permits <= rule.permits()) {
used += permits;
return new Decision.Allowed(rule.permits() - used);
}
return new Decision.Rejected(windowStart + rule.windowMillis() - nowMillis);
}
private void roll(long nowMillis) {
long start = nowMillis - Math.floorMod(nowMillis, rule.windowMillis());
if (start != windowStart) {
windowStart = start;
used = 0;
}
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return nowMillis - windowStart >= rule.windowMillis();
}
}
com.androidinterview.ratelimiter.algorithm.LeakyBucket.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// The token bucket read backwards, and the arithmetic mirrors it, which is why
// the two get confused. The difference is intent. A token bucket lets an idle
// client spend saved credit all at once, a leaky bucket used as a queue never
// lets a burst through at all, so whatever is downstream sees a flat line.
//
// This is the metering version. Parking requests instead of refusing them
// means owning a queue, a timer and a story about a full queue, and none of
// that belongs behind a method that answers yes or no.
public final class LeakyBucket implements RateLimitAlgorithm {
private final Rule rule;
private final double capacity;
private final double leakPerMillis;
private double level;
private long lastLeakMillis;
public LeakyBucket(Rule rule, long startMillis) {
this.rule = rule;
this.capacity = rule.permits();
this.leakPerMillis = rule.permitsPerMillis();
this.lastLeakMillis = startMillis;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
leak(nowMillis);
if (level + permits <= capacity) {
level += permits;
return new Decision.Allowed((int) Math.floor(capacity - level));
}
double overflow = level + permits - capacity;
long wait = (long) Math.ceil(overflow / leakPerMillis);
return new Decision.Rejected(Math.max(1L, wait));
}
private void leak(long nowMillis) {
long elapsed = nowMillis - lastLeakMillis;
if (elapsed <= 0) {
return;
}
level = Math.max(0.0, level - elapsed * leakPerMillis);
lastLeakMillis = nowMillis;
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return level - (nowMillis - lastLeakMillis) * leakPerMillis <= 0.0;
}
}
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
public final class LeakyBucket implements RateLimitAlgorithm {
private final Rule rule;
private final double capacity;
private final double leakPerMillis;
private double level;
private long lastLeakMillis;
public LeakyBucket(Rule rule, long startMillis) {
this.rule = rule;
this.capacity = rule.permits();
this.leakPerMillis = rule.permitsPerMillis();
this.lastLeakMillis = startMillis;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
leak(nowMillis);
if (level + permits <= capacity) {
level += permits;
return new Decision.Allowed((int) Math.floor(capacity - level));
}
double overflow = level + permits - capacity;
long wait = (long) Math.ceil(overflow / leakPerMillis);
return new Decision.Rejected(Math.max(1L, wait));
}
private void leak(long nowMillis) {
long elapsed = nowMillis - lastLeakMillis;
if (elapsed <= 0) {
return;
}
level = Math.max(0.0, level - elapsed * leakPerMillis);
lastLeakMillis = nowMillis;
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return level - (nowMillis - lastLeakMillis) * leakPerMillis <= 0.0;
}
}
com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// The strategy, and the only extension point in the design. One instance holds
// the state of one key.
//
// Time arrives as a parameter rather than being read inside, so the caller
// reads the clock once per request and every implementation agrees on what now
// means. Each implementation owns its own thread safety, because the lock that
// matters is the one around a single key.
public interface RateLimitAlgorithm {
Decision tryAcquire(long nowMillis, int permits);
// True when this bucket holds no state that could change a future answer,
// so a fresh one would give the same result. Coordinate this check and
// removal with active use of the bucket.
boolean isIdle(long nowMillis);
// A request bigger than the whole limit can never be served however long
// the caller waits, so it is a bug and not a rate limit decision.
static void checkPermits(int permits, Rule rule) {
if (permits <= 0 || permits > rule.permits()) {
throw new IllegalArgumentException(
permits + " permits can never fit a limit of " + rule.permits());
}
}
}
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
public interface RateLimitAlgorithm {
Decision tryAcquire(long nowMillis, int permits);
boolean isIdle(long nowMillis);
static void checkPermits(int permits, Rule rule) {
if (permits <= 0 || permits > rule.permits()) {
throw new IllegalArgumentException(
permits + " permits can never fit a limit of " + rule.permits());
}
}
}
com.androidinterview.ratelimiter.algorithm.SlidingWindowCounter.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// Estimate a rolling count by weighting the previous window. Thirty seconds
// into a minute, eighty last minute and twenty this minute estimates sixty.
// This assumes evenly spread traffic, so it can be too high or too low.
public final class SlidingWindowCounter implements RateLimitAlgorithm {
private final Rule rule;
private long windowStart;
private int current;
private int previous;
public SlidingWindowCounter(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
roll(nowMillis);
double estimate = estimate(nowMillis);
if (estimate + permits <= rule.permits()) {
current += permits;
return new Decision.Allowed((int) Math.floor(rule.permits() - estimate - permits));
}
return new Decision.Rejected(retryAfter(nowMillis, permits));
}
// Rolling one window forward carries current back into previous. Rolling
// further means the key went quiet for a whole window, so both go to zero.
private void roll(long nowMillis) {
long start = nowMillis - Math.floorMod(nowMillis, rule.windowMillis());
if (start == windowStart) {
return;
}
previous = (start - windowStart == rule.windowMillis()) ? current : 0;
current = 0;
windowStart = start;
}
private double estimate(long nowMillis) {
long elapsed = nowMillis - windowStart;
double weight = (rule.windowMillis() - elapsed) / (double) rule.windowMillis();
return previous * weight + current;
}
// Waiting works by letting the previous window's weight fall, so solve for
// the weight at which this request fits and turn it back into a time. When
// the current window alone is already over, or there is no previous window
// to shrink, only the next window helps.
private long retryAfter(long nowMillis, int permits) {
long window = rule.windowMillis();
long elapsed = nowMillis - windowStart;
double headroom = rule.permits() - current - permits;
if (headroom <= 0 || previous == 0) {
return window - elapsed;
}
double allowedWeight = headroom / previous;
long needed = (long) Math.ceil(window * (1.0 - allowedWeight));
return Math.max(1L, needed - elapsed);
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return nowMillis - windowStart >= 2L * rule.windowMillis();
}
}
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
public final class SlidingWindowCounter implements RateLimitAlgorithm {
private final Rule rule;
private long windowStart;
private int current;
private int previous;
public SlidingWindowCounter(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
roll(nowMillis);
double estimate = estimate(nowMillis);
if (estimate + permits <= rule.permits()) {
current += permits;
return new Decision.Allowed((int) Math.floor(rule.permits() - estimate - permits));
}
return new Decision.Rejected(retryAfter(nowMillis, permits));
}
private void roll(long nowMillis) {
long start = nowMillis - Math.floorMod(nowMillis, rule.windowMillis());
if (start == windowStart) {
return;
}
previous = (start - windowStart == rule.windowMillis()) ? current : 0;
current = 0;
windowStart = start;
}
private double estimate(long nowMillis) {
long elapsed = nowMillis - windowStart;
double weight = (rule.windowMillis() - elapsed) / (double) rule.windowMillis();
return previous * weight + current;
}
private long retryAfter(long nowMillis, int permits) {
long window = rule.windowMillis();
long elapsed = nowMillis - windowStart;
double headroom = rule.permits() - current - permits;
if (headroom <= 0 || previous == 0) {
return window - elapsed;
}
double allowedWeight = headroom / previous;
long needed = (long) Math.ceil(window * (1.0 - allowedWeight));
return Math.max(1L, needed - elapsed);
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return nowMillis - windowStart >= 2L * rule.windowMillis();
}
}
com.androidinterview.ratelimiter.algorithm.SlidingWindowLog.java
package com.androidinterview.ratelimiter.algorithm;
import java.util.ArrayDeque;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// Exactly right, and that is its only argument. No boundary burst, and retry
// after is exact. It also costs one timestamp per request per key held for a
// whole window, which is why nobody ships it at scale.
public final class SlidingWindowLog implements RateLimitAlgorithm {
private final Rule rule;
private final ArrayDeque<Long> hits = new ArrayDeque<>();
public SlidingWindowLog(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
prune(nowMillis);
if (hits.size() + permits <= rule.permits()) {
for (int i = 0; i < permits; i++) {
hits.addLast(nowMillis);
}
return new Decision.Allowed(rule.permits() - hits.size());
}
// How many of the oldest hits have to age out before this request
// fits, and when the last of those ages out.
int mustExpire = hits.size() + permits - rule.permits();
return new Decision.Rejected(oldest(mustExpire - 1) + rule.windowMillis() - nowMillis);
}
// A hit at t leaves at exactly t plus the window. Rejected requests are
// never logged. Logging them would let a client already being refused push
// its own recovery further away every time it retried.
private void prune(long nowMillis) {
long cutoff = nowMillis - rule.windowMillis();
while (!hits.isEmpty() && hits.peekFirst() <= cutoff) {
hits.pollFirst();
}
}
private long oldest(int index) {
int i = 0;
for (long hit : hits) {
if (i++ == index) {
return hit;
}
}
throw new IllegalStateException("no hit at index " + index);
}
@Override
public synchronized boolean isIdle(long nowMillis) {
prune(nowMillis);
return hits.isEmpty();
}
}
package com.androidinterview.ratelimiter.algorithm;
import java.util.ArrayDeque;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
public final class SlidingWindowLog implements RateLimitAlgorithm {
private final Rule rule;
private final ArrayDeque<Long> hits = new ArrayDeque<>();
public SlidingWindowLog(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
prune(nowMillis);
if (hits.size() + permits <= rule.permits()) {
for (int i = 0; i < permits; i++) {
hits.addLast(nowMillis);
}
return new Decision.Allowed(rule.permits() - hits.size());
}
int mustExpire = hits.size() + permits - rule.permits();
return new Decision.Rejected(oldest(mustExpire - 1) + rule.windowMillis() - nowMillis);
}
private void prune(long nowMillis) {
long cutoff = nowMillis - rule.windowMillis();
while (!hits.isEmpty() && hits.peekFirst() <= cutoff) {
hits.pollFirst();
}
}
private long oldest(int index) {
int i = 0;
for (long hit : hits) {
if (i++ == index) {
return hit;
}
}
throw new IllegalStateException("no hit at index " + index);
}
@Override
public synchronized boolean isIdle(long nowMillis) {
prune(nowMillis);
return hits.isEmpty();
}
}
com.androidinterview.ratelimiter.algorithm.TokenBucket.java
package com.androidinterview.ratelimiter.algorithm;
import java.util.concurrent.atomic.AtomicReference;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// The one to ship. A bucket holds up to a limit's worth of tokens, tokens
// arrive at a steady rate, a request costs one. A quiet client has a full
// bucket and may burst, a hammering client runs it dry and is metered at the
// refill rate. Neither window algorithm gives you that.
//
// The refill is lazy. No timer, no scheduled executor, no thread per bucket.
// A request looks at how long it has been since the last one and adds that
// much refill, capped at the bucket size, so an idle bucket runs no code.
//
// Tokens are a double. One token per ten seconds is a ten thousandth of a
// token per millisecond, and truncating that to a whole number on every call
// means a client polling once a second adds zero tokens forever while the
// timestamp keeps moving. The bucket never refills and nobody can work out why.
public final class TokenBucket implements RateLimitAlgorithm {
// The pair that has to change together. One immutable value means the
// update is a single reference swap, which is what makes it lock free.
private record State(double tokens, long atMillis) {}
private final Rule rule;
private final double capacity;
private final double perMillis;
private final AtomicReference<State> state;
public TokenBucket(Rule rule, long startMillis) {
this.rule = rule;
this.capacity = rule.permits();
this.perMillis = rule.permitsPerMillis();
this.state = new AtomicReference<>(new State(capacity, startMillis));
}
// Lock free, and the loop is the whole trick. Read the state, work out what
// it should be now, and swap it in only if nobody changed it first. If
// somebody did, the read is stale, so throw the answer away and go round
// again. A rejection writes nothing, so a refused client contends with
// nobody.
@Override
public Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
while (true) {
State seen = state.get();
State filled = refill(seen, nowMillis);
if (filled.tokens() < permits) {
double missing = permits - filled.tokens();
long wait = (long) Math.ceil(missing / perMillis);
return new Decision.Rejected(Math.max(1L, wait));
}
State next = new State(filled.tokens() - permits, filled.atMillis());
if (state.compareAndSet(seen, next)) {
return new Decision.Allowed((int) Math.floor(next.tokens()));
}
}
}
private State refill(State seen, long nowMillis) {
long elapsed = nowMillis - seen.atMillis();
if (elapsed <= 0) {
return seen;
}
return new State(Math.min(capacity, seen.tokens() + elapsed * perMillis), nowMillis);
}
// A full bucket is indistinguishable from one never used, so it can be
// thrown away without forgiving anybody.
@Override
public boolean isIdle(long nowMillis) {
return refill(state.get(), nowMillis).tokens() >= capacity;
}
}
package com.androidinterview.ratelimiter.algorithm;
import java.util.concurrent.atomic.AtomicReference;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
public final class TokenBucket implements RateLimitAlgorithm {
private record State(double tokens, long atMillis) {}
private final Rule rule;
private final double capacity;
private final double perMillis;
private final AtomicReference<State> state;
public TokenBucket(Rule rule, long startMillis) {
this.rule = rule;
this.capacity = rule.permits();
this.perMillis = rule.permitsPerMillis();
this.state = new AtomicReference<>(new State(capacity, startMillis));
}
@Override
public Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
while (true) {
State seen = state.get();
State filled = refill(seen, nowMillis);
if (filled.tokens() < permits) {
double missing = permits - filled.tokens();
long wait = (long) Math.ceil(missing / perMillis);
return new Decision.Rejected(Math.max(1L, wait));
}
State next = new State(filled.tokens() - permits, filled.atMillis());
if (state.compareAndSet(seen, next)) {
return new Decision.Allowed((int) Math.floor(next.tokens()));
}
}
}
private State refill(State seen, long nowMillis) {
long elapsed = nowMillis - seen.atMillis();
if (elapsed <= 0) {
return seen;
}
return new State(Math.min(capacity, seen.tokens() + elapsed * perMillis), nowMillis);
}
@Override
public boolean isIdle(long nowMillis) {
return refill(state.get(), nowMillis).tokens() >= capacity;
}
}
com.androidinterview.ratelimiter.core.Clock.java
package com.androidinterview.ratelimiter.core;
// Nothing in this package reads the system time directly. A limiter that calls
// the clock inside itself can only be tested by sleeping, so a test of a one
// minute window takes a minute and a boundary test is a coin toss.
@FunctionalInterface
public interface Clock {
long nowMillis();
// Monotonic on purpose. Wall clock time steps backwards whenever the
// device corrects itself against a time server, and a limiter that sees
// time run backwards either locks everyone out or hands out a free window.
Clock SYSTEM = () -> System.nanoTime() / 1_000_000L;
}
package com.androidinterview.ratelimiter.core;
@FunctionalInterface
public interface Clock {
long nowMillis();
Clock SYSTEM = () -> System.nanoTime() / 1_000_000L;
}
com.androidinterview.ratelimiter.core.Decision.java
package com.androidinterview.ratelimiter.core;
// The answer, and the reason it is a type rather than a boolean. A boolean
// makes the caller invent a retry delay, and every client inventing the same
// delay is how a backend gets a synchronised stampede. Carrying retryAfter
// turns a refusal into a schedule.
public sealed interface Decision {
boolean allowed();
// Zero when allowed. How long until this request could succeed otherwise.
long retryAfterMillis();
// What a server would put in an X-RateLimit-Remaining header.
record Allowed(int remaining) implements Decision {
@Override
public boolean allowed() {
return true;
}
@Override
public long retryAfterMillis() {
return 0L;
}
}
record Rejected(long retryAfterMillis) implements Decision {
@Override
public boolean allowed() {
return false;
}
}
}
package com.androidinterview.ratelimiter.core;
public sealed interface Decision {
boolean allowed();
long retryAfterMillis();
record Allowed(int remaining) implements Decision {
@Override
public boolean allowed() {
return true;
}
@Override
public long retryAfterMillis() {
return 0L;
}
}
record Rejected(long retryAfterMillis) implements Decision {
@Override
public boolean allowed() {
return false;
}
}
}
com.androidinterview.ratelimiter.core.ManualClock.java
package com.androidinterview.ratelimiter.core;
// The clock the tests use. Time moves only when a test moves it, so an hour of
// traffic runs in a microsecond and a boundary is checked at the exact
// millisecond. This is what makes the fixed window burst demonstrable rather
// than something to take on faith.
public final class ManualClock implements Clock {
private long nowMillis;
public ManualClock() {
this(0L);
}
public ManualClock(long startMillis) {
this.nowMillis = startMillis;
}
@Override
public synchronized long nowMillis() {
return nowMillis;
}
public synchronized void advance(long millis) {
nowMillis += millis;
}
}
package com.androidinterview.ratelimiter.core;
public final class ManualClock implements Clock {
private long nowMillis;
public ManualClock() {
this(0L);
}
public ManualClock(long startMillis) {
this.nowMillis = startMillis;
}
@Override
public synchronized long nowMillis() {
return nowMillis;
}
public synchronized void advance(long millis) {
nowMillis += millis;
}
}
com.androidinterview.ratelimiter.core.Rule.java
package com.androidinterview.ratelimiter.core;
// The limit as one value. Every algorithm needs both numbers and several need
// the ratio, so a loose int and a loose long travelling separately is two
// chances to pair the wrong pair.
public record Rule(int permits, long windowMillis) {
public Rule {
if (permits <= 0) {
throw new IllegalArgumentException("permits must be positive, got " + permits);
}
if (windowMillis <= 0) {
throw new IllegalArgumentException("window must be positive, got " + windowMillis);
}
}
// The refill and leak rate. A double on purpose. One permit per ten
// seconds is 0.0001 per millisecond, and rounding that to a whole number
// is how a slow bucket never refills at all.
public double permitsPerMillis() {
return (double) permits / windowMillis;
}
public static Rule perSecond(int permits) {
return new Rule(permits, 1_000L);
}
public static Rule perMinute(int permits) {
return new Rule(permits, 60_000L);
}
}
package com.androidinterview.ratelimiter.core;
public record Rule(int permits, long windowMillis) {
public Rule {
if (permits <= 0) {
throw new IllegalArgumentException("permits must be positive, got " + permits);
}
if (windowMillis <= 0) {
throw new IllegalArgumentException("window must be positive, got " + windowMillis);
}
}
public double permitsPerMillis() {
return (double) permits / windowMillis;
}
public static Rule perSecond(int permits) {
return new Rule(permits, 1_000L);
}
public static Rule perMinute(int permits) {
return new Rule(permits, 60_000L);
}
}
Kotlin
com.androidinterview.ratelimiter.RateLimiter.kt
package com.androidinterview.ratelimiter
import com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm
import com.androidinterview.ratelimiter.core.Clock
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.atomic.AtomicLong
// The whole public surface. A default argument covers the common call, so
// tryAcquire("user-42") is what almost every caller writes and the batch case
// is still there when a flush of forty events should cost forty.
interface RateLimiter {
fun tryAcquire(key: String, permits: Int = 1): Decision
}
// A limit is never global, it is per user, per API key, per device, per
// endpoint. So the limiter is a map from key to one bucket.
//
// newBucket is the seam, and in Kotlin it is a function type rather than a
// factory interface. Swapping the fleet from a fixed window to a token bucket
// is one lambda at the construction site.
class KeyedRateLimiter(
private val clock: Clock,
private val sweepEvery: Millis = Millis(60_000),
private val newBucket: () -> RateLimitAlgorithm,
) : RateLimiter {
private val buckets = ConcurrentHashMap<String, RateLimitAlgorithm>()
private val nextSweep = AtomicLong(clock.now().value + sweepEvery.value)
val size get() = buckets.size
// Lookup and use stay inside one map computation. Eviction uses the same
// coordination, so it cannot remove a bucket while a request is using it.
// Keep the callback short and do no network work here. The map may also
// serialize keys that share a hash bin; this is not one global lock.
override fun tryAcquire(key: String, permits: Int): Decision {
val now = clock.now()
sweepIfDue(now)
lateinit var decision: Decision
buckets.compute(key) { _, current ->
val bucket = current ?: newBucket()
decision = bucket.tryAcquire(now, permits)
bucket
}
return decision
}
// Check idleness and remove inside the same per key computation as use.
// Otherwise an old reference and a newly created bucket could both spend
// a balance for the same key. Count actual removals, not a changing map size.
fun evictIdle(now: Millis = clock.now()): Int {
var removed = 0
for (key in buckets.keys) {
buckets.computeIfPresent(key) { _, bucket ->
if (bucket.isIdle(now)) { removed++; null } else bucket
}
}
return removed
}
// One sweep per interval across all threads. The compare and set is what
// stops fifty threads sweeping at once the moment the interval passes.
private fun sweepIfDue(now: Millis) {
val due = nextSweep.get()
if (now.value < due || !nextSweep.compareAndSet(due, now.value + sweepEvery.value)) return
evictIdle(now)
}
}
package com.androidinterview.ratelimiter
import com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm
import com.androidinterview.ratelimiter.core.Clock
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.atomic.AtomicLong
interface RateLimiter {
fun tryAcquire(key: String, permits: Int = 1): Decision
}
class KeyedRateLimiter(
private val clock: Clock,
private val sweepEvery: Millis = Millis(60_000),
private val newBucket: () -> RateLimitAlgorithm,
) : RateLimiter {
private val buckets = ConcurrentHashMap<String, RateLimitAlgorithm>()
private val nextSweep = AtomicLong(clock.now().value + sweepEvery.value)
val size get() = buckets.size
override fun tryAcquire(key: String, permits: Int): Decision {
val now = clock.now()
sweepIfDue(now)
lateinit var decision: Decision
buckets.compute(key) { _, current ->
val bucket = current ?: newBucket()
decision = bucket.tryAcquire(now, permits)
bucket
}
return decision
}
fun evictIdle(now: Millis = clock.now()): Int {
var removed = 0
for (key in buckets.keys) {
buckets.computeIfPresent(key) { _, bucket ->
if (bucket.isIdle(now)) { removed++; null } else bucket
}
}
return removed
}
private fun sweepIfDue(now: Millis) {
val due = nextSweep.get()
if (now.value < due || !nextSweep.compareAndSet(due, now.value + sweepEvery.value)) return
evictIdle(now)
}
}
com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm.kt
package com.androidinterview.ratelimiter.algorithm
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import com.androidinterview.ratelimiter.core.Permits
import com.androidinterview.ratelimiter.core.Rule
import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.max
// The strategy, and the only extension point. One instance holds the state of
// one key. Time arrives as a parameter, so the caller reads the clock once per
// request and every implementation agrees on what now means, and each owns its
// own thread safety, because the lock that matters is per key.
interface RateLimitAlgorithm {
fun tryAcquire(now: Millis, permits: Int = 1): Decision
// True when this bucket holds no state that could change a future answer.
// Coordinate this check and removal with active use of the bucket.
fun isIdle(now: Millis): Boolean
}
// A request bigger than the whole limit can never be served however long the
// caller waits, so it is a bug and not a rate limit decision.
internal fun Rule.checkPermits(permits: Int) {
require(permits in 1..limit) { "$permits permits can never fit a limit of $limit" }
}
// Aligned to the epoch rather than to the first request, so every key rolls at
// the same instant. That makes the boundary burst reproducible instead of
// random, which is what you want from a bug you decided to live with.
internal fun Rule.windowStartAt(now: Millis) = now.value - Math.floorMod(now.value, windowMillis)
// Two numbers per key whatever the traffic, and a boundary burst. A hundred
// requests in the last millisecond of one window and a hundred in the first
// millisecond of the next is two hundred inside two milliseconds, and the
// counter sees nothing wrong because it saw a hundred and then a hundred.
class FixedWindowCounter(private val rule: Rule) : RateLimitAlgorithm {
private var windowStart = 0L
private var used = 0
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
roll(now)
if (used + permits > rule.limit) {
// Nothing helps before the window turns over, so that is the wait.
return Decision.Rejected(Millis(windowStart + rule.windowMillis - now.value))
}
used += permits
return Decision.Allowed(Permits(rule.limit - used))
}
private fun roll(now: Millis) {
val start = rule.windowStartAt(now)
if (start != windowStart) {
windowStart = start
used = 0
}
}
@Synchronized
override fun isIdle(now: Millis) = now.value - windowStart >= rule.windowMillis
}
// Exactly right, and that is its only argument. No boundary burst, and retry
// after is exact. It also costs one timestamp per request per key held for a
// whole window, which is why nobody ships it at scale.
class SlidingWindowLog(private val rule: Rule) : RateLimitAlgorithm {
private val hits = ArrayDeque<Long>()
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
prune(now)
if (hits.size + permits > rule.limit) {
// How many of the oldest hits must age out before this fits, and
// when the last of those goes.
val mustExpire = hits.size + permits - rule.limit
val leavesAt = hits[mustExpire - 1] + rule.windowMillis
return Decision.Rejected(Millis(leavesAt - now.value))
}
repeat(permits) { hits.addLast(now.value) }
return Decision.Allowed(Permits(rule.limit - hits.size))
}
// A hit at t leaves at exactly t plus the window. Rejected requests are
// never logged. Logging them would let a client already being refused push
// its own recovery further away every time it retried.
private fun prune(now: Millis) {
val cutoff = now.value - rule.windowMillis
while (hits.isNotEmpty() && hits.first() <= cutoff) hits.removeFirst()
}
@Synchronized
override fun isIdle(now: Millis): Boolean {
prune(now)
return hits.isEmpty()
}
}
// Estimate a rolling count by weighting the previous window. Thirty seconds
// into a minute, eighty last minute and twenty this minute estimates sixty.
// The estimate assumes evenly spread traffic, so it can be too high or too
// low. An exact rolling limit needs timestamps or another exact algorithm.
class SlidingWindowCounter(private val rule: Rule) : RateLimitAlgorithm {
private var windowStart = 0L
private var current = 0
private var previous = 0
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
roll(now)
val estimate = estimate(now)
if (estimate + permits > rule.limit) {
return Decision.Rejected(retryAfter(now, permits))
}
current += permits
return Decision.Allowed(Permits(floor(rule.limit - estimate - permits).toInt()))
}
// Rolling one window forward carries current back into previous. Rolling
// further means the key went quiet for a whole window, so both go to zero.
private fun roll(now: Millis) {
val start = rule.windowStartAt(now)
if (start == windowStart) return
previous = if (start - windowStart == rule.windowMillis) current else 0
current = 0
windowStart = start
}
private fun estimate(now: Millis): Double {
val elapsed = now.value - windowStart
return previous * ((rule.windowMillis - elapsed) / rule.windowMillis.toDouble()) + current
}
// Waiting works by letting the previous window's weight fall, so solve for
// the weight at which this request fits and turn it back into a time. With
// the current window already over, or no previous window to shrink, only
// the next window helps.
private fun retryAfter(now: Millis, permits: Int): Millis {
val elapsed = now.value - windowStart
val headroom = rule.limit - current - permits
if (headroom <= 0 || previous == 0) return Millis(rule.windowMillis - elapsed)
val needed = ceil(rule.windowMillis * (1.0 - headroom.toDouble() / previous)).toLong()
return Millis(max(1L, needed - elapsed))
}
@Synchronized
override fun isIdle(now: Millis) = now.value - windowStart >= 2 * rule.windowMillis
}
// The token bucket read backwards, and the arithmetic mirrors it, which is why
// the two get confused. The difference is intent. A token bucket lets an idle
// client spend saved credit all at once, a leaky bucket used as a queue never
// lets a burst through at all, so whatever is downstream sees a flat line.
//
// This is the metering version. Parking requests instead of refusing them
// means owning a queue, a timer and a story about a full queue, and none of
// that belongs behind a method that answers yes or no.
class LeakyBucket(private val rule: Rule, start: Millis) : RateLimitAlgorithm {
private val capacity = rule.limit.toDouble()
private var level = 0.0
private var lastLeak = start.value
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
leak(now)
val overflow = level + permits - capacity
if (overflow > 0) {
return Decision.Rejected(Millis(max(1L, ceil(overflow / rule.perMillis).toLong())))
}
level += permits
return Decision.Allowed(Permits(floor(capacity - level).toInt()))
}
private fun leak(now: Millis) {
val elapsed = now.value - lastLeak
if (elapsed <= 0) return
level = max(0.0, level - elapsed * rule.perMillis)
lastLeak = now.value
}
@Synchronized
override fun isIdle(now: Millis) = level - (now.value - lastLeak) * rule.perMillis <= 0.0
}
package com.androidinterview.ratelimiter.algorithm
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import com.androidinterview.ratelimiter.core.Permits
import com.androidinterview.ratelimiter.core.Rule
import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.max
interface RateLimitAlgorithm {
fun tryAcquire(now: Millis, permits: Int = 1): Decision
fun isIdle(now: Millis): Boolean
}
internal fun Rule.checkPermits(permits: Int) {
require(permits in 1..limit) { "$permits permits can never fit a limit of $limit" }
}
internal fun Rule.windowStartAt(now: Millis) = now.value - Math.floorMod(now.value, windowMillis)
class FixedWindowCounter(private val rule: Rule) : RateLimitAlgorithm {
private var windowStart = 0L
private var used = 0
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
roll(now)
if (used + permits > rule.limit) {
return Decision.Rejected(Millis(windowStart + rule.windowMillis - now.value))
}
used += permits
return Decision.Allowed(Permits(rule.limit - used))
}
private fun roll(now: Millis) {
val start = rule.windowStartAt(now)
if (start != windowStart) {
windowStart = start
used = 0
}
}
@Synchronized
override fun isIdle(now: Millis) = now.value - windowStart >= rule.windowMillis
}
class SlidingWindowLog(private val rule: Rule) : RateLimitAlgorithm {
private val hits = ArrayDeque<Long>()
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
prune(now)
if (hits.size + permits > rule.limit) {
val mustExpire = hits.size + permits - rule.limit
val leavesAt = hits[mustExpire - 1] + rule.windowMillis
return Decision.Rejected(Millis(leavesAt - now.value))
}
repeat(permits) { hits.addLast(now.value) }
return Decision.Allowed(Permits(rule.limit - hits.size))
}
private fun prune(now: Millis) {
val cutoff = now.value - rule.windowMillis
while (hits.isNotEmpty() && hits.first() <= cutoff) hits.removeFirst()
}
@Synchronized
override fun isIdle(now: Millis): Boolean {
prune(now)
return hits.isEmpty()
}
}
class SlidingWindowCounter(private val rule: Rule) : RateLimitAlgorithm {
private var windowStart = 0L
private var current = 0
private var previous = 0
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
roll(now)
val estimate = estimate(now)
if (estimate + permits > rule.limit) {
return Decision.Rejected(retryAfter(now, permits))
}
current += permits
return Decision.Allowed(Permits(floor(rule.limit - estimate - permits).toInt()))
}
private fun roll(now: Millis) {
val start = rule.windowStartAt(now)
if (start == windowStart) return
previous = if (start - windowStart == rule.windowMillis) current else 0
current = 0
windowStart = start
}
private fun estimate(now: Millis): Double {
val elapsed = now.value - windowStart
return previous * ((rule.windowMillis - elapsed) / rule.windowMillis.toDouble()) + current
}
private fun retryAfter(now: Millis, permits: Int): Millis {
val elapsed = now.value - windowStart
val headroom = rule.limit - current - permits
if (headroom <= 0 || previous == 0) return Millis(rule.windowMillis - elapsed)
val needed = ceil(rule.windowMillis * (1.0 - headroom.toDouble() / previous)).toLong()
return Millis(max(1L, needed - elapsed))
}
@Synchronized
override fun isIdle(now: Millis) = now.value - windowStart >= 2 * rule.windowMillis
}
class LeakyBucket(private val rule: Rule, start: Millis) : RateLimitAlgorithm {
private val capacity = rule.limit.toDouble()
private var level = 0.0
private var lastLeak = start.value
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
leak(now)
val overflow = level + permits - capacity
if (overflow > 0) {
return Decision.Rejected(Millis(max(1L, ceil(overflow / rule.perMillis).toLong())))
}
level += permits
return Decision.Allowed(Permits(floor(capacity - level).toInt()))
}
private fun leak(now: Millis) {
val elapsed = now.value - lastLeak
if (elapsed <= 0) return
level = max(0.0, level - elapsed * rule.perMillis)
lastLeak = now.value
}
@Synchronized
override fun isIdle(now: Millis) = level - (now.value - lastLeak) * rule.perMillis <= 0.0
}
com.androidinterview.ratelimiter.algorithm.TokenBucket.kt
package com.androidinterview.ratelimiter.algorithm
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import com.androidinterview.ratelimiter.core.Permits
import com.androidinterview.ratelimiter.core.Rule
import java.util.concurrent.atomic.AtomicReference
import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.max
import kotlin.math.min
// The one to ship. A bucket holds up to a limit's worth of tokens, tokens
// arrive at a steady rate, a request costs one. A quiet client has a full
// bucket and may burst, a hammering client runs it dry and is metered at the
// refill rate. Neither window algorithm gives you that.
//
// The refill is lazy. No timer, no scheduled executor, no thread per bucket.
// A request looks at how long it has been since the last one and adds that
// much refill, capped at the bucket size, so an idle bucket runs no code.
//
// Tokens are a Double. One token per ten seconds is a ten thousandth of a
// token per millisecond, and truncating that to a whole number on every call
// means a client polling once a second adds zero tokens forever while the
// timestamp keeps moving. The bucket never refills and nobody can work out why.
class TokenBucket(private val rule: Rule, start: Millis) : RateLimitAlgorithm {
// The pair that has to change together. One immutable value means the
// update is a single reference swap, which is what makes it lock free.
private data class State(val tokens: Double, val at: Long)
private val capacity = rule.limit.toDouble()
private val state = AtomicReference(State(capacity, start.value))
// Lock free, and the loop is the whole trick. Read the state, work out what
// it should be now, and swap it in only if nobody changed it first. If
// somebody did, the read is stale, so throw the answer away and go round
// again. A rejection writes nothing, so a refused client contends with
// nobody.
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
while (true) {
val seen = state.get()
val filled = seen.refilled(now)
if (filled.tokens < permits) {
val missing = permits - filled.tokens
return Decision.Rejected(Millis(max(1L, ceil(missing / rule.perMillis).toLong())))
}
val next = filled.copy(tokens = filled.tokens - permits)
if (state.compareAndSet(seen, next)) {
return Decision.Allowed(Permits(floor(next.tokens).toInt()))
}
}
}
private fun State.refilled(now: Millis): State {
val elapsed = now.value - at
if (elapsed <= 0) return this
return State(min(capacity, tokens + elapsed * rule.perMillis), now.value)
}
// A full bucket is indistinguishable from one never used, so it can be
// thrown away without forgiving anybody.
override fun isIdle(now: Millis) = state.get().refilled(now).tokens >= capacity
}
package com.androidinterview.ratelimiter.algorithm
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import com.androidinterview.ratelimiter.core.Permits
import com.androidinterview.ratelimiter.core.Rule
import java.util.concurrent.atomic.AtomicReference
import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.max
import kotlin.math.min
class TokenBucket(private val rule: Rule, start: Millis) : RateLimitAlgorithm {
private data class State(val tokens: Double, val at: Long)
private val capacity = rule.limit.toDouble()
private val state = AtomicReference(State(capacity, start.value))
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
while (true) {
val seen = state.get()
val filled = seen.refilled(now)
if (filled.tokens < permits) {
val missing = permits - filled.tokens
return Decision.Rejected(Millis(max(1L, ceil(missing / rule.perMillis).toLong())))
}
val next = filled.copy(tokens = filled.tokens - permits)
if (state.compareAndSet(seen, next)) {
return Decision.Allowed(Permits(floor(next.tokens).toInt()))
}
}
}
private fun State.refilled(now: Millis): State {
val elapsed = now.value - at
if (elapsed <= 0) return this
return State(min(capacity, tokens + elapsed * rule.perMillis), now.value)
}
override fun isIdle(now: Millis) = state.get().refilled(now).tokens >= capacity
}
com.androidinterview.ratelimiter.core.Clock.kt
package com.androidinterview.ratelimiter.core
// Nothing in this package reads the system time directly. A limiter that calls
// the clock inside itself can only be tested by sleeping, so a test of a one
// minute window takes a minute and a boundary test is a coin toss.
//
// One method, so a fun interface, and a clock is a lambda outside tests.
fun interface Clock {
fun now(): Millis
}
// Monotonic on purpose. Wall clock time steps backwards whenever the device
// corrects itself against a time server, and a limiter that sees time run
// backwards either locks everyone out or hands out a free window.
object SystemClock : Clock {
override fun now() = Millis(System.nanoTime() / 1_000_000L)
}
// Time moves only when a test moves it, so an hour of traffic runs in a
// microsecond and a boundary is checked at the exact millisecond.
class ManualClock(start: Millis = Millis(0)) : Clock {
private var current = start
@Synchronized
override fun now() = current
@Synchronized
fun advance(millis: Long) {
current += Millis(millis)
}
}
package com.androidinterview.ratelimiter.core
fun interface Clock {
fun now(): Millis
}
object SystemClock : Clock {
override fun now() = Millis(System.nanoTime() / 1_000_000L)
}
class ManualClock(start: Millis = Millis(0)) : Clock {
private var current = start
@Synchronized
override fun now() = current
@Synchronized
fun advance(millis: Long) {
current += Millis(millis)
}
}
com.androidinterview.ratelimiter.core.Decision.kt
package com.androidinterview.ratelimiter.core
// Two units, two types, and neither costs an object at runtime. A Long called
// now and a Long called retryAfter are the same thing to the compiler and
// different things to a reader.
@JvmInline
value class Millis(val value: Long) : Comparable<Millis> {
operator fun plus(other: Millis) = Millis(value + other.value)
operator fun minus(other: Millis) = Millis(value - other.value)
override fun compareTo(other: Millis) = value.compareTo(other.value)
override fun toString() = "${value}ms"
}
@JvmInline
value class Permits(val count: Int) {
override fun toString() = "$count permits"
companion object {
val ONE = Permits(1)
}
}
// The answer, and the reason it is a type rather than a Boolean. A Boolean
// makes the caller invent a retry delay, and every client inventing the same
// delay is how a backend gets a synchronised stampede.
//
// Sealed, so a when over a decision is exhaustive and a third outcome, say a
// shadow mode that would have refused but let the request through, is a
// compile error at every call site instead of a silent default branch.
sealed interface Decision {
val allowed: Boolean
val retryAfter: Millis
// What a server would put in an X-RateLimit-Remaining header.
data class Allowed(val remaining: Permits) : Decision {
override val allowed get() = true
override val retryAfter get() = Millis(0)
}
data class Rejected(override val retryAfter: Millis) : Decision {
override val allowed get() = false
}
}
// The limit as one value, because every algorithm needs both numbers and
// several need the ratio.
data class Rule(val permits: Permits, val window: Millis) {
init {
require(permits.count > 0) { "permits must be positive, got $permits" }
require(window.value > 0) { "window must be positive, got $window" }
}
val limit get() = permits.count
val windowMillis get() = window.value
// A Double on purpose. One permit per ten seconds is a ten thousandth of a
// permit per millisecond, and rounding that to a whole number is how a
// slow bucket never refills at all.
val perMillis get() = limit.toDouble() / windowMillis
companion object {
fun perSecond(permits: Int) = Rule(Permits(permits), Millis(1_000))
fun perMinute(permits: Int) = Rule(Permits(permits), Millis(60_000))
}
}
package com.androidinterview.ratelimiter.core
@JvmInline
value class Millis(val value: Long) : Comparable<Millis> {
operator fun plus(other: Millis) = Millis(value + other.value)
operator fun minus(other: Millis) = Millis(value - other.value)
override fun compareTo(other: Millis) = value.compareTo(other.value)
override fun toString() = "${value}ms"
}
@JvmInline
value class Permits(val count: Int) {
override fun toString() = "$count permits"
companion object {
val ONE = Permits(1)
}
}
sealed interface Decision {
val allowed: Boolean
val retryAfter: Millis
data class Allowed(val remaining: Permits) : Decision {
override val allowed get() = true
override val retryAfter get() = Millis(0)
}
data class Rejected(override val retryAfter: Millis) : Decision {
override val allowed get() = false
}
}
data class Rule(val permits: Permits, val window: Millis) {
init {
require(permits.count > 0) { "permits must be positive, got $permits" }
require(window.value > 0) { "window must be positive, got $window" }
}
val limit get() = permits.count
val windowMillis get() = window.value
val perMillis get() = limit.toDouble() / windowMillis
companion object {
fun perSecond(permits: Int) = Rule(Permits(permits), Millis(1_000))
fun perMinute(permits: Int) = Rule(Permits(permits), Millis(60_000))
}
}
Watch