Design a Rate Limiter

public interface RateLimiter {
    boolean isAllowed(String clientId);
    int getRemainingQuota(String clientId);
}

public record RateLimitRule(
    String endpoint,
    int maxRequests,
    Duration window,
    RateLimiter limiter
) {}

public record RateLimitResult(
    boolean allowed,
    int remaining,
    long retryAfterMs
) {}

public class RateLimiterService {
    private final Map<String, RateLimitRule> rules = new ConcurrentHashMap<>();

    public void addRule(String endpoint, RateLimitRule rule) {
        rules.put(endpoint, rule);
    }

    public RateLimitResult checkRateLimit(String endpoint, String clientId) {
        RateLimitRule rule = rules.get(endpoint);
        if (rule == null) return new RateLimitResult(true, -1, 0);

        boolean allowed = rule.limiter().isAllowed(clientId);
        int remaining = rule.limiter().getRemainingQuota(clientId);
        long retryAfter = allowed ? 0 : rule.window().toMillis();

        return new RateLimitResult(allowed, remaining, retryAfter);
    }
}

public class TokenBucketLimiter implements RateLimiter {
    private final int maxTokens;
    private final double refillRatePerMs;  // tokens added per millisecond
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

    public TokenBucketLimiter(int maxTokens, int refillPerSecond) {
        this.maxTokens = maxTokens;
        this.refillRatePerMs = refillPerSecond / 1000.0;
    }

    @Override
    public boolean isAllowed(String clientId) {
        Bucket bucket = buckets.computeIfAbsent(clientId,
            k -> new Bucket(maxTokens, refillRatePerMs));
        return bucket.tryConsume();
    }

    @Override
    public int getRemainingQuota(String clientId) {
        Bucket bucket = buckets.get(clientId);
        return bucket == null ? maxTokens : bucket.getTokens();
    }
}

class Bucket {
    private final int maxTokens;
    private final double refillRatePerMs;
    private double tokens;
    private long lastRefillTime;

    Bucket(int maxTokens, double refillRatePerMs) {
        this.maxTokens = maxTokens;
        this.refillRatePerMs = refillRatePerMs;
        this.tokens = maxTokens;  // start full
        this.lastRefillTime = System.currentTimeMillis();
    }

    synchronized boolean tryConsume() {
        refill();
        if (tokens >= 1.0) {
            tokens -= 1.0;
            return true;
        }
        return false;
    }

    synchronized int getTokens() {
        refill();
        return (int) tokens;
    }

    private void refill() {
        long now = System.currentTimeMillis();
        long elapsed = now - lastRefillTime;
        if (elapsed > 0) {
            tokens = Math.min(maxTokens, tokens + elapsed * refillRatePerMs);
            lastRefillTime = now;
        }
    }
}
// Usage: new TokenBucketLimiter(10, 10) → max 10 tokens, refill 10/sec
// Allows bursts up to 10 requests, then smooths to 10 req/sec

public class SlidingWindowLogLimiter implements RateLimiter {
    private final int maxRequests;
    private final long windowSizeMs;
    private final ConcurrentHashMap<String, Deque<Long>> requestLogs =
        new ConcurrentHashMap<>();

    public SlidingWindowLogLimiter(int maxRequests, Duration windowSize) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSize.toMillis();
    }

    @Override
    public boolean isAllowed(String clientId) {
        long now = System.currentTimeMillis();
        Deque<Long> log = requestLogs.computeIfAbsent(clientId,
            k -> new ConcurrentLinkedDeque<>());

        // Remove expired timestamps
        long cutoff = now - windowSizeMs;
        while (!log.isEmpty() && log.peekFirst() <= cutoff) {
            log.pollFirst();
        }

        if (log.size() < maxRequests) {
            log.addLast(now);
            return true;
        }
        return false;
    }

    @Override
    public int getRemainingQuota(String clientId) {
        Deque<Long> log = requestLogs.get(clientId);
        if (log == null) return maxRequests;
        long cutoff = System.currentTimeMillis() - windowSizeMs;
        long active = log.stream().filter(t -> t > cutoff).count();
        return Math.max(0, maxRequests - (int) active);
    }
}
// Precise but memory-heavy: stores every timestamp
// 1M users × 100 requests = 100M Long objects (~800MB)

public class SlidingWindowCounterLimiter implements RateLimiter {
    private final int maxRequests;
    private final long windowSizeMs;
    private final ConcurrentHashMap<String, WindowCounter> counters =
        new ConcurrentHashMap<>();

    public SlidingWindowCounterLimiter(int maxRequests, Duration windowSize) {
        this.maxRequests = maxRequests;
        this.windowSizeMs = windowSize.toMillis();
    }

    @Override
    public boolean isAllowed(String clientId) {
        WindowCounter counter = counters.computeIfAbsent(clientId,
            k -> new WindowCounter(windowSizeMs));
        return counter.tryIncrement(maxRequests);
    }

    @Override
    public int getRemainingQuota(String clientId) {
        WindowCounter counter = counters.get(clientId);
        if (counter == null) return maxRequests;
        return Math.max(0, maxRequests - (int) counter.getWeightedCount());
    }
}

class WindowCounter {
    private final long windowSizeMs;
    private long currentWindowStart;
    private long currentCount;
    private long previousCount;

    WindowCounter(long windowSizeMs) {
        this.windowSizeMs = windowSizeMs;
        this.currentWindowStart = System.currentTimeMillis();
    }

    synchronized boolean tryIncrement(int maxRequests) {
        advanceWindow();
        double weighted = getWeightedCount();
        if (weighted < maxRequests) {
            currentCount++;
            return true;
        }
        return false;
    }

    synchronized double getWeightedCount() {
        advanceWindow();
        long now = System.currentTimeMillis();
        double elapsedRatio = (now - currentWindowStart) / (double) windowSizeMs;
        double previousWeight = 1.0 - elapsedRatio;
        // KEY FORMULA: weighted = prev * (1 - elapsed%) + current
        return previousCount * previousWeight + currentCount;
    }

    private void advanceWindow() {
        long now = System.currentTimeMillis();
        long elapsed = now - currentWindowStart;
        if (elapsed >= windowSizeMs) {
            long windowsElapsed = elapsed / windowSizeMs;
            if (windowsElapsed == 1) {
                previousCount = currentCount;
            } else {
                previousCount = 0; // more than 1 window passed
            }
            currentCount = 0;
            currentWindowStart += windowsElapsed * windowSizeMs;
        }
    }
}
// WHY this approximation works:
// Assume requests in previous window were uniformly distributed.
// If window = 60s, we're 20s into current window:
//   weighted = prevCount * 0.67 + currentCount
// Error margin is typically < 1% under uniform traffic.
// Memory: 2 longs per client vs. N timestamps per client.