Machine Coding Problem

API Rate Limiter

3rd April 20264.082.0k views15 min read
maco30maco60macoAllinfrastructuretoken-bucketsliding-window
Commonly Asked By:StripeGoogleAmazonMicrosoftLyft

Requirements & System Scope

Functional Scope (In-Scope)

  • Pluggable Algorithms: Supports dynamic strategies including Token Bucket, Leaky Bucket, and Sliding Window Log configurations.
  • Lazy Evaluation Math: Refills and leaks are calculated on-the-fly dynamically on arrival of requests, preventing background resource hogging.
  • Fail-Safe Modes: Preservation parameters that offer swappable fail-open and fail-closed rules on unregistered client lookups.
  • Fine-Grained Thread Safety: Direct mutex locking on rate-limiter objects to prevent race conditions during heavy concurrent spikes.

Explicit Boundaries (Out-of-Scope)

  • No Distributed Cache Integration: All limit state structures are localized in-memory. Out-of-scope to coordinate network transactions.
  • No Client IP Geolocation Parsing: Client unique identity mapping is managed upstream by API gateways.

Class Diagram & Entity Relationships

Structural blueprint showing Strategy abstractions and client limit containers:

Loading...
  • Polymorphic Limiters: Different limiting rules implement a common RateLimiter interface, letting the service orchestrate algorithms transparently.
  • Fail-Safe Controller: RateLimiterService routes incoming calls to the registered strategy, falling back on custom safety parameters.

Design Patterns & SOLID Principles

  • Strategy Pattern (Limiting Policies): By implementing swappable strategies (Token Bucket, Sliding Window Log, Leaky Bucket) conforming to a common contract, the system is fully Open-Closed compliant.
  • Lazy Evaluation Pattern (Resource Protection): State computations (refilling buckets and leaking water levels) happen on-demand on incoming requests, avoiding thread pool timers.
  • Single Responsibility Principle (SRP): Each concrete limiter class is only responsible for calculating its algorithmic metrics. The service is responsible for mapping client IDs and failover behavior.

Core Execution Workflows

1. Lazy Token Bucket Check Workflow

  1. Client invokes isAllowed(clientId).
  2. If client is unregistered, fallback to return the failOpen boolean parameter.
  3. Acquire exclusive ReentrantLock on client's limiter.
  4. Execute Lazy Refill check:
    1. addedTokens = (currentTime - lastRefillTime) * refillRatePerMs.
    2. tokens = min(capacity, tokens + addedTokens).
    3. Set lastRefillTime = currentTime.
  5. Verify balance:
    1. If tokens >= 1.0, deduct 1.0 token and return true.
    2. Otherwise, reject request and return false.
  6. Release lock.

Concurrency & Thread Safety Strategy

API Gateways evaluate rate limiting metrics concurrently across multiple incoming request threads:

  • Client-Level Mutex Locks: Encapsulate operations behind a local ReentrantLock instance, ensuring multi-threaded requests are serialized per client without blocking other clients.
  • Concurrent Collections: Store mappings in thread-safe ConcurrentHashMap configurations to accommodate dynamic runtime registrations.

Complete Clean Code Blueprint

Clean reference designs showing thread-safe token bucket and sliding window log limits in Java and Python:

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

interface RateLimiter {
    boolean allow();
}

class TokenBucketLimiter implements RateLimiter {
    private final double capacity;
    private final double refillRateMs; // tokens per millisecond
    private double tokens;
    private long lastRefillTime;
    private final ReentrantLock lock = new ReentrantLock();

    public TokenBucketLimiter(double capacity, double refillRatePerSecond) {
        this.capacity = capacity;
        this.refillRateMs = refillRatePerSecond / 1000.0;
        this.tokens = capacity;
        this.lastRefillTime = System.currentTimeMillis();
    }

    @Override
    public boolean allow() {
        lock.lock();
        try {
            refill();
            if (tokens >= 1.0) {
                tokens -= 1.0;
                return true;
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    private void refill() {
        long now = System.currentTimeMillis();
        double added = (now - lastRefillTime) * refillRateMs;
        if (added > 0.0) {
            tokens = Math.min(capacity, tokens + added);
            lastRefillTime = now;
        }
    }
}

class SlidingWindowLogLimiter implements RateLimiter {
    private final int limit;
    private final long windowSizeMs;
    private final List<Long> requestLog = new ArrayList<>();
    private final ReentrantLock lock = new ReentrantLock();

    public SlidingWindowLogLimiter(int limit, long windowSizeMs) {
        this.limit = limit;
        this.windowSizeMs = windowSizeMs;
    }

    @Override
    public boolean allow() {
        lock.lock();
        try {
            long now = System.currentTimeMillis();
            long boundary = now - windowSizeMs;

            // Evict expired timestamps
            requestLog.removeIf(t -> t < boundary);

            if (requestLog.size() < limit) {
                requestLog.add(now);
                return true;
            }
            return false;
        } finally {
            lock.unlock();
        }
    }
}

class LeakyBucketLimiter implements RateLimiter {
    private final double capacity;
    private final double leakRateMs; // water units per millisecond
    private double waterLevel = 0.0;
    private long lastLeakTime;
    private final ReentrantLock lock = new ReentrantLock();

    public LeakyBucketLimiter(double capacity, double leakRatePerSecond) {
        this.capacity = capacity;
        this.leakRateMs = leakRatePerSecond / 1000.0;
        this.lastLeakTime = System.currentTimeMillis();
    }

    @Override
    public boolean allow() {
        lock.lock();
        try {
            leak();
            if (waterLevel + 1.0 <= capacity) {
                waterLevel += 1.0;
                return true;
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    private void leak() {
        long now = System.currentTimeMillis();
        double leaked = (now - lastLeakTime) * leakRateMs;
        if (leaked > 0.0) {
            waterLevel = Math.max(0.0, waterLevel - leaked);
            lastLeakTime = now;
        }
    }
}

class RateLimiterService {
    private final Map<String, RateLimiter> limiters = new ConcurrentHashMap<>();
    private boolean failOpen = true;

    public void setFailOpen(boolean failOpen) {
        this.failOpen = failOpen;
    }

    public void registerClient(String clientId, String type, double limit, double rate) {
        if ("token_bucket".equalsIgnoreCase(type)) {
            limiters.put(clientId, new TokenBucketLimiter(limit, rate));
        } else if ("sliding_window".equalsIgnoreCase(type)) {
            limiters.put(clientId, new SlidingWindowLogLimiter((int)limit, (long)rate));
        } else if ("leaky_bucket".equalsIgnoreCase(type)) {
            limiters.put(clientId, new LeakyBucketLimiter(limit, rate));
        }
    }

    public boolean isAllowed(String clientId) {
        RateLimiter limiter = limiters.get(clientId);
        if (limiter == null) {
            return failOpen; // Fail-open configuration preservation
        }
        return limiter.allow();
    }
}

// ─── DRIVER CLASS ──────────────────────────────────────────────────────────
public class RateLimiterDriver {
    public static void main(String[] args) throws Exception {
        System.out.println("=== API RATE LIMITER DRIVER SIMULATION ===");
        RateLimiterService service = new RateLimiterService();

        // Register client A: Token Bucket (Capacity 2, refill rate 1 per second)
        service.registerClient("ClientA", "token_bucket", 2.0, 1.0);
        // Register client B: Sliding Window Log (Limit 2, window size 1 second)
        service.registerClient("ClientB", "sliding_window", 2.0, 1000.0);

        System.out.println("\n--- ClientA (Token Bucket) Burst test ---");
        System.out.println("Req 1: " + (service.isAllowed("ClientA") ? "ALLOWED" : "BLOCKED"));
        System.out.println("Req 2: " + (service.isAllowed("ClientA") ? "ALLOWED" : "BLOCKED"));
        System.out.println("Req 3: " + (service.isAllowed("ClientA") ? "ALLOWED" : "BLOCKED")); // should block

        System.out.println("Waiting 1.1 seconds for refill...");
        Thread.sleep(1100);
        System.out.println("Req 4 (after wait): " + (service.isAllowed("ClientA") ? "ALLOWED" : "BLOCKED")); // allowed

        System.out.println("\n--- ClientB (Sliding Window) test ---");
        System.out.println("Req 1: " + (service.isAllowed("ClientB") ? "ALLOWED" : "BLOCKED"));
        System.out.println("Req 2: " + (service.isAllowed("ClientB") ? "ALLOWED" : "BLOCKED"));
        System.out.println("Req 3: " + (service.isAllowed("ClientB") ? "ALLOWED" : "BLOCKED")); // should block

        System.out.println("\n--- Fail-Safe Mode Preservation test ---");
        System.out.println("Unregistered client request (Fail-Open): " + (service.isAllowed("ClientUnknown") ? "ALLOWED" : "BLOCKED"));
        service.setFailOpen(false);
        System.out.println("Unregistered client request (Fail-Closed): " + (service.isAllowed("ClientUnknown") ? "ALLOWED" : "BLOCKED"));
    }
}

💬Review

Help Us Improve

How helpful was this walkthrough?

Click a star to rate. We actively use this feedback to refine and update our system design content.

Placeholder
Optional but highly appreciated!

Discussion

Share your thoughts, ask questions, or help others.

Loading comments...