Implement a rate limiter

Solution: Token Bucket

class TokenBucketRateLimiter {
    constructor(capacity, refillRate) {
        this.capacity = capacity;  // Max tokens
        this.refillRate = refillRate;  // Tokens per second
        this.buckets = new Map();  // userId -> bucket state
    }

    // Returns true if request is allowed, false if rate limited
    allowRequest(userId) {
        const now = Date.now() / 1000;  // Current time in seconds

        if (!this.buckets.has(userId)) {
            // First request from this user
            this.buckets.set(userId, {
                tokens: this.capacity - 1,  // Consume 1 for this request
                lastRefill: now
            });
            return true;
        }

        const bucket = this.buckets.get(userId);

        // Calculate tokens to add since last refill
        const timePassed = now - bucket.lastRefill;
        const tokensToAdd = timePassed * this.refillRate;

        // Refill bucket (up to capacity)
        bucket.tokens = Math.min(
            this.capacity,
            bucket.tokens + tokensToAdd
        );
        bucket.lastRefill = now;

        // Check if we have a token available
        if (bucket.tokens >= 1) {
            bucket.tokens -= 1;
            return true;  // Request allowed
        }

        return false;  // Rate limited
    }

    // Get current token count for user (for debugging)
    getTokens(userId) {
        if (!this.buckets.has(userId)) {
            return this.capacity;
        }

        const bucket = this.buckets.get(userId);
        const now = Date.now() / 1000;
        const timePassed = now - bucket.lastRefill;
        const tokensToAdd = timePassed * this.refillRate;

        return Math.min(this.capacity, bucket.tokens + tokensToAdd);
    }
}

// Test
const limiter = new TokenBucketRateLimiter(5, 1);  // 5 tokens, refill 1/sec

// Make 5 quick requests
for (let i = 0; i < 5; i++) {
    console.log(`Request ${i + 1}:`, limiter.allowRequest("user1"));
}
// All should be true

console.log("Request 6:", limiter.allowRequest("user1"));
// false (rate limited)

// Wait 2 seconds
setTimeout(() => {
    console.log("After 2 seconds:", limiter.allowRequest("user1"));
    // true (2 tokens refilled)

    console.log("Tokens remaining:", limiter.getTokens("user1"));
    // ~1 token
}, 2000);

Alternative: Sliding Window Log

class SlidingWindowRateLimiter {
    constructor(limit, windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
        this.requests = new Map();  // userId -> array of timestamps
    }

    allowRequest(userId) {
        const now = Date.now();
        const windowStart = now - this.windowMs;

        if (!this.requests.has(userId)) {
            this.requests.set(userId, []);
        }

        const userRequests = this.requests.get(userId);

        // Remove old requests outside window
        while (userRequests.length > 0 &&
               userRequests[0] < windowStart) {
            userRequests.shift();
        }

        // Check if under limit
        if (userRequests.length < this.limit) {
            userRequests.push(now);
            return true;
        }

        return false;  // Rate limited
    }
}

// Test
const limiter2 = new SlidingWindowRateLimiter(3, 1000);  // 3 per second

console.log(limiter2.allowRequest("user1"));  // true
console.log(limiter2.allowRequest("user1"));  // true
console.log(limiter2.allowRequest("user1"));  // true
console.log(limiter2.allowRequest("user1"));  // false (rate limited)

setTimeout(() => {
    console.log(limiter2.allowRequest("user1"));  // true (window moved)
}, 1100);

Alternative: Fixed Window Counter

class FixedWindowRateLimiter {
    constructor(limit, windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
        this.windows = new Map();  // userId -> {count, windowStart}
    }

    allowRequest(userId) {
        const now = Date.now();
        const windowStart = Math.floor(now / this.windowMs) * this.windowMs;

        if (!this.windows.has(userId)) {
            this.windows.set(userId, {count: 0, windowStart});
        }

        const window = this.windows.get(userId);

        // New window?
        if (window.windowStart < windowStart) {
            window.count = 0;
            window.windowStart = windowStart;
        }

        // Check limit
        if (window.count < this.limit) {
            window.count++;
            return true;
        }

        return false;
    }
}

Comparison

Algorithm	Memory	Accuracy	Burst Handling
Fixed window	O(users)	Poor (edge bursts)	Poor
Sliding log	O(users × limit)	Perfect	Good
Token bucket	O(users)	Good	Excellent
Sliding counter	O(users)	Good	Good

Production Considerations

Storage: Use Redis with TTL for persistence and scaling across servers.

Distributed: Need atomic operations (Redis INCR, Lua scripts) to avoid race conditions.

Failure mode:

• Fail open: Allow requests if rate limiter fails (better UX, risk of abuse)
• Fail closed: Deny requests if rate limiter fails (safer, bad UX)

Response headers: Return rate limit info to client:

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 47
X-RateLimit-Reset: 1612345678

Complexity

Operation	Token Bucket	Sliding Log	Fixed Window
allowRequest()	O(1)	O(n)*	O(1)
Space per user	O(1)	O(limit)	O(1)

* n = number of requests in window

Follow-Up Questions

• Different limits per user tier? Store limit in user object or config
• Rate limit by IP vs user? Same algorithm, different key
• Multiple rate limits? Check each (e.g., 100/hour AND 1000/day)
• Global rate limit? Single bucket for all users, more complex in distributed system

Related Problems

• Storing 1 million phone numbers - System design problems
• Server to Process Fair Number of Functions - Fair scheduling algorithms
• Building a Stack with a getMax() function - Data structures for systems