Distributed Rate Limiter Challenge

🎯 Challenge Overview

Build a distributed rate limiting system that can handle millions of API requests while protecting backend services from abuse. This challenge is inspired by the rate limiting systems used by Twitter (X) API, GitHub API, and other high-scale platforms that need to balance service availability with fair usage policies.

🏢 Real-World Context

Major API platforms process billions of requests daily and need sophisticated rate limiting to:

• Twitter API: Limits tweets per user per day (2,400 for basic tier)
• GitHub API: Implements different limits for authenticated vs. unauthenticated requests
• Stripe: Uses sliding window rate limiting for payment processing
• AWS APIs: Employs token bucket algorithms with burst capacity

Your challenge is to build a system that can enforce rate limits across multiple servers and handle various limiting strategies.

📋 Requirements

Core Features

1. Multiple Rate Limiting Algorithms:

   • Token Bucket (supports bursts)
   • Sliding Window Log (precise but memory-intensive)
   • Sliding Window Counter (balanced approach)
   • Fixed Window Counter (simple and efficient)

2. Distributed Architecture:

   • Works across multiple application servers
   • Consistent rate limit enforcement
   • Handles server failures gracefully

3. Flexible Configuration:

   • Per-user, per-IP, per-API-key limits
   • Different limits for different endpoints
   • Time-based limits (requests per minute/hour/day)

Technical Specifications

• Handle 100,000+ requests per second across the cluster
• Sub-millisecond latency for rate limit checks
• 99.9% availability even during Redis failover
• Support for both sync and async operations

🛠 Implementation Guide

Phase 1: Algorithm Implementation

// Token Bucket Algorithm Example
class TokenBucket {
    constructor(capacity, refillRate, refillPeriod) {
        this.capacity = capacity;
        this.tokens = capacity;
        this.refillRate = refillRate;
        this.refillPeriod = refillPeriod;
        this.lastRefill = Date.now();
    }
    
    async tryConsume(tokens = 1) {
        await this.refill();
        if (this.tokens >= tokens) {
            this.tokens -= tokens;
            return true;
        }
        return false;
    }
}

Phase 2: Redis Integration

Implement Lua scripts for atomic operations:

-- sliding_window_counter.lua
local key = KEYS[1]
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local current_time = tonumber(ARGV[3])

-- Remove expired entries
redis.call('ZREMRANGEBYSCORE', key, 0, current_time - window)

-- Count current requests
local current_requests = redis.call('ZCARD', key)

if current_requests < limit then
    -- Allow request and record it
    redis.call('ZADD', key, current_time, current_time)
    redis.call('EXPIRE', key, math.ceil(window / 1000))
    return {1, limit - current_requests - 1}
else
    -- Reject request
    return {0, 0}
end

Phase 3: API Integration

Build middleware for popular frameworks:

// Express.js middleware
const rateLimiter = require('./rate-limiter');

function createRateLimitMiddleware(config) {
    return async (req, res, next) => {
        const key = config.keyGenerator(req);
        const result = await rateLimiter.isAllowed(key, config);
        
        if (result.allowed) {
            res.set({
                'X-RateLimit-Limit': config.limit,
                'X-RateLimit-Remaining': result.remaining,
                'X-RateLimit-Reset': result.resetTime
            });
            next();
        } else {
            res.status(429).json({
                error: 'Too Many Requests',
                retryAfter: result.retryAfter
            });
        }
    };
}

📊 Success Metrics

• Throughput: Handle 100k+ requests/second
• Latency: <1ms for rate limit checks
• Accuracy: 99.9% correct rate limit enforcement
• Memory Efficiency: <1KB memory per active user
• Fault Tolerance: Continue operating during Redis failover

🎁 Bonus Challenges

1. Adaptive Rate Limiting: Automatically adjust limits based on system load
2. Geographic Distribution: Different rate limits by user location
3. Smart Queuing: Queue excess requests instead of rejecting immediately
4. Analytics Dashboard: Real-time monitoring of rate limit violations
5. Machine Learning: Detect and prevent coordinated abuse patterns

📚 Learning Outcomes

After completing this challenge, you'll understand:

• Different rate limiting algorithms and their trade-offs
• Distributed systems consistency challenges
• Redis Lua scripting for atomic operations
• API design patterns for scalable systems
• Monitoring and observability for high-traffic services

🔧 Technical Stack Recommendations

• Backend: Node.js, Go, or Python
• Cache: Redis or Redis Cluster
• Monitoring: Prometheus + Grafana
• Load Testing: Apache Bench, wrk, or k6
• Container: Docker for easy deployment

🚀 Getting Started

1. Choose your rate limiting algorithm (start with Token Bucket)
2. Set up Redis and implement basic single-node version
3. Add Lua scripts for atomic Redis operations
4. Build the distributed coordination layer
5. Create API middleware and test with high load
6. Add monitoring and alerting capabilities

🔗 Helpful Resources

• Redis Rate Limiting Patterns
• Token Bucket Algorithm
• Sliding Window Rate Limiting
• System Design: Rate Limiter

Ready to protect APIs at scale? Build a rate limiter that can handle the next viral app launch! 🚀