Rate Limiter

4 classes 79 lines Strategy View on GitHub ↗

Question

Three rate-limiting algorithms as separate classes: fixed window, sliding window and token bucket. Each answers “is this request allowed right now?”. The full design with a shared store is in phonepe/questions/ratelimiter.

strategy/FixedWindow.java 25 lines GitHub ↗

package lld.ratelimiter.strategy;

public class FixedWindow {
    private int capacity;
    private int currentcapacity;
    private long nextRefillTime;
    private long windowDuration;

    public FixedWindow(int capacity, long windowDuration) {
        this.capacity = capacity;
        this.currentcapacity = 0;
        this.windowDuration = windowDuration;
        this.nextRefillTime = System.currentTimeMillis() + windowDuration;
    }

    public synchronized boolean isAllowed() {
        long now =  System.currentTimeMillis();
        if(now >= nextRefillTime) {
            nextRefillTime = now+ windowDuration;
            currentcapacity = 0;
        }
        if(currentcapacity < capacity) {
            currentcapacity++;
            return true;
        }
        return false;
    }
}

strategy/SlidingWindow.java 25 lines GitHub ↗

package lld.ratelimiter.strategy;

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindow {

    private final int capacity;
    private long windowDurationMs;
    private final Deque<Long> timestamps = new ArrayDeque<>();
    //final on a reference field means the reference
    //can't be reassigned, not that the object it points to can't change. The two are separate things in Java.

    public SlidingWindow(int capacity, long windowDurationMs) {
        this.capacity = capacity;
        this.windowDurationMs = windowDurationMs;
    }

    public synchronized boolean isAllowed() {
        long now = System.currentTimeMillis();

        while(timestamps.isEmpty() && now - windowDurationMs >= timestamps.peekFirst()){
            timestamps.pollFirst();
        }

        if(timestamps.size() < capacity) {
            timestamps.addLast(now);
            return true;
        }

        return false;
    }

}

strategy/TokenBucket.java 26 lines GitHub ↗

package lld.ratelimiter.strategy;

public class TokenBucket {
    private final int capacity;
    private final double tokenRefillRatePerMs;
    public double tokens;
    private long lastRefillTime;

    public TokenBucket(int capacity, double tokenRefillRatePerSecond) {
        this.capacity = capacity;
        this.tokenRefillRatePerMs = tokenRefillRatePerSecond / 1000.0;
        this.tokens = capacity;
        this.lastRefillTime = System.currentTimeMillis();
    }

    public synchronized boolean isAllowed() {
        refill();
        if(tokens >= 1) {
            tokens--;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.currentTimeMillis();
        tokens = Math.min(capacity , tokens + (now - lastRefillTime)*tokenRefillRatePerMs);
        lastRefillTime = now;
    }
}

RateLimiterDemo.java 3 lines GitHub ↗

package lld.ratelimiter;

public class RateLimiterDemo {
}