Problem 15: Design a Rate Limiter (LLD)

The setup

"Implement a rate limiter that can be embedded in an API server. Configurable algorithm (token bucket, sliding window, etc.). Support per-user, per-API limits. Thread-safe."

The HLD version was about distributed state. The LLD version focuses on the algorithm classes and their integration.

The Strategy pattern

interface RateLimiterAlgorithm {
  boolean isAllowed(String key);
}

class TokenBucketRateLimiter implements RateLimiterAlgorithm {
  private final int bucketSize;
  private final double refillRatePerSecond;
  private final Map buckets = new ConcurrentHashMap<>();
  
  public synchronized boolean isAllowed(String key) {
    Bucket bucket = buckets.computeIfAbsent(key, k -> new Bucket(bucketSize));
    bucket.refill(refillRatePerSecond);
    if (bucket.tokens >= 1) {
      bucket.tokens -= 1;
      return true;
    }
    return false;
  }
  
  private static class Bucket {
    double tokens;
    Instant lastRefill;
    void refill(double ratePerSecond) {
      Instant now = Instant.now();
      double elapsedSeconds = Duration.between(lastRefill, now).toMillis() / 1000.0;
      tokens = Math.min(bucketSize, tokens + elapsedSeconds * ratePerSecond);
      lastRefill = now;
    }
  }
}

class SlidingWindowRateLimiter implements RateLimiterAlgorithm {
  private final int maxRequests;
  private final long windowMillis;
  private final Map> requestLogs = new ConcurrentHashMap<>();
  
  public synchronized boolean isAllowed(String key) {
    Deque log = requestLogs.computeIfAbsent(key, k -> new ArrayDeque<>());
    Instant now = Instant.now();
    Instant cutoff = now.minusMillis(windowMillis);
    while (!log.isEmpty() && log.peekFirst().isBefore(cutoff)) {
      log.pollFirst();
    }
    if (log.size() < maxRequests) {
      log.offerLast(now);
      return true;
    }
    return false;
  }
}

class RateLimiter {
  private final RateLimiterAlgorithm algorithm;
  
  public RateLimiter(RateLimiterAlgorithm algorithm) {
    this.algorithm = algorithm;
  }
  
  public boolean isAllowed(String key) {
    return algorithm.isAllowed(key);
  }
}

Takeaway

The LLD version of the rate limiter exposes the algorithmic options as a clean strategy hierarchy. Combined with the HLD version (where state lives across nodes), you have the full picture. The LLD is the in-process algorithm; the HLD is the distributed state — both matter.