Advanced Rate Limiting trong Laravel: Sliding Window, Token Bucket và Distributed Limiting

Giới Thiệu

Rate limiting là kỹ thuật quan trọng để bảo vệ API khỏi abuse, DDoS attacks, và đảm bảo fair usage. Laravel cung cấp rate limiting cơ bản, nhưng cho production systems phức tạp, bạn cần hiểu và implement các thuật toán nâng cao.

Tại Sao Cần Advanced Rate Limiting?

Fixed Window (Basic)	Advanced Algorithms
Có thể burst ở ranh giới window	Smooth traffic distribution
Không fair với users	Fair queueing
Dễ bị exploit	Resistant to gaming
Single server only	Distributed support

Các Thuật Toán Rate Limiting

1. Fixed Window Counter (Laravel Default)

Window 1 (00:00-01:00)  |  Window 2 (01:00-02:00)
     [████████████]     |     [████████████]
     100 requests       |     100 requests

Vấn đề: 100 requests ở 00:59 + 100 ở 01:01 = 200 requests trong 2 phút

2. Sliding Window Log

Sliding window tracks exact timestamps:
|----window (60s)----|
     ↓  ↓↓ ↓  ↓↓↓  ↓
Requests within window counted

3. Sliding Window Counter

Combines fixed windows with weighted average:

Previous window: 60 requests (40% weight at 24s into current)
Current window: 30 requests (60% weight)

Effective count = 60 * 0.4 + 30 = 54 requests

4. Token Bucket

Bucket capacity: 100 tokens
Refill rate: 10 tokens/second

[████████████████████] 100/100 tokens
Request comes → take 1 token
[███████████████████ ] 99/100 tokens
Refill → add tokens over time

5. Leaky Bucket

Requests enter bucket, processed at fixed rate:

    ↓ ↓ ↓ (incoming requests)
   [█████]  bucket
      ↓ (constant output rate)

Implementation

Sliding Window Counter

// app/Services/RateLimiting/SlidingWindowLimiter.php
<?php

namespace App\Services\RateLimiting;

use Illuminate\Support\Facades\Redis;

class SlidingWindowLimiter
{
    public function __construct(
        private string $prefix = 'rate_limit:sliding:'
    ) {}
    
    /**
     * Check if request is allowed using sliding window counter
     */
    public function attempt(
        string $key,
        int $maxRequests,
        int $windowSeconds
    ): RateLimitResult {
        $now = microtime(true);
        $currentWindow = floor($now / $windowSeconds);
        $previousWindow = $currentWindow - 1;
        
        $currentKey = $this->prefix . $key . ':' . $currentWindow;
        $previousKey = $this->prefix . $key . ':' . $previousWindow;
        
        // Get counts from Redis
        $pipe = Redis::pipeline();
        $pipe->get($currentKey);
        $pipe->get($previousKey);
        $results = $pipe->execute();
        
        $currentCount = (int) ($results[0] ?? 0);
        $previousCount = (int) ($results[1] ?? 0);
        
        // Calculate weighted count
        $windowPosition = $now - ($currentWindow * $windowSeconds);
        $previousWeight = 1 - ($windowPosition / $windowSeconds);
        
        $effectiveCount = ($previousCount * $previousWeight) + $currentCount;
        
        if ($effectiveCount >= $maxRequests) {
            $retryAfter = $windowSeconds - $windowPosition;
            
            return new RateLimitResult(
                allowed: false,
                remaining: 0,
                retryAfter: (int) ceil($retryAfter),
                limit: $maxRequests
            );
        }
        
        // Increment current window counter
        $pipe = Redis::pipeline();
        $pipe->incr($currentKey);
        $pipe->expire($currentKey, $windowSeconds * 2);
        $pipe->execute();
        
        return new RateLimitResult(
            allowed: true,
            remaining: (int) floor($maxRequests - $effectiveCount - 1),
            retryAfter: 0,
            limit: $maxRequests
        );
    }
    
    /**
     * Get current rate limit status without incrementing
     */
    public function status(string $key, int $maxRequests, int $windowSeconds): RateLimitResult
    {
        $now = microtime(true);
        $currentWindow = floor($now / $windowSeconds);
        $previousWindow = $currentWindow - 1;
        
        $currentKey = $this->prefix . $key . ':' . $currentWindow;
        $previousKey = $this->prefix . $key . ':' . $previousWindow;
        
        $pipe = Redis::pipeline();
        $pipe->get($currentKey);
        $pipe->get($previousKey);
        $results = $pipe->execute();
        
        $currentCount = (int) ($results[0] ?? 0);
        $previousCount = (int) ($results[1] ?? 0);
        
        $windowPosition = $now - ($currentWindow * $windowSeconds);
        $previousWeight = 1 - ($windowPosition / $windowSeconds);
        
        $effectiveCount = ($previousCount * $previousWeight) + $currentCount;
        
        return new RateLimitResult(
            allowed: $effectiveCount < $maxRequests,
            remaining: max(0, (int) floor($maxRequests - $effectiveCount)),
            retryAfter: $effectiveCount >= $maxRequests 
                ? (int) ceil($windowSeconds - $windowPosition) 
                : 0,
            limit: $maxRequests
        );
    }
}

Token Bucket Algorithm

// app/Services/RateLimiting/TokenBucketLimiter.php
<?php

namespace App\Services\RateLimiting;

use Illuminate\Support\Facades\Redis;

class TokenBucketLimiter
{
    public function __construct(
        private string $prefix = 'rate_limit:bucket:'
    ) {}
    
    /**
     * Attempt to consume tokens from bucket
     */
    public function attempt(
        string $key,
        int $bucketSize,
        int $refillRate, // tokens per second
        int $tokensToConsume = 1
    ): RateLimitResult {
        $script = <<<'LUA'
            local key = KEYS[1]
            local bucket_size = tonumber(ARGV[1])
            local refill_rate = tonumber(ARGV[2])
            local tokens_to_consume = tonumber(ARGV[3])
            local now = tonumber(ARGV[4])
            
            -- Get current state
            local bucket = redis.call('hmget', key, 'tokens', 'last_refill')
            local tokens = tonumber(bucket[1]) or bucket_size
            local last_refill = tonumber(bucket[2]) or now
            
            -- Calculate tokens to add based on time passed
            local time_passed = now - last_refill
            local tokens_to_add = time_passed * refill_rate
            tokens = math.min(bucket_size, tokens + tokens_to_add)
            
            -- Check if we have enough tokens
            if tokens < tokens_to_consume then
                -- Calculate wait time
                local tokens_needed = tokens_to_consume - tokens
                local wait_time = tokens_needed / refill_rate
                return {0, tokens, wait_time}
            end
            
            -- Consume tokens
            tokens = tokens - tokens_to_consume
            
            -- Update bucket
            redis.call('hmset', key, 'tokens', tokens, 'last_refill', now)
            redis.call('expire', key, bucket_size / refill_rate * 2)
            
            return {1, tokens, 0}
        LUA;
        
        $result = Redis::eval(
            $script,
            1,
            $this->prefix . $key,
            $bucketSize,
            $refillRate,
            $tokensToConsume,
            microtime(true)
        );
        
        return new RateLimitResult(
            allowed: (bool) $result[0],
            remaining: (int) floor($result[1]),
            retryAfter: (int) ceil($result[2]),
            limit: $bucketSize
        );
    }
    
    /**
     * Get current bucket status
     */
    public function getTokens(string $key, int $bucketSize, int $refillRate): int
    {
        $data = Redis::hmget($this->prefix . $key, ['tokens', 'last_refill']);
        
        $tokens = (float) ($data['tokens'] ?? $bucketSize);
        $lastRefill = (float) ($data['last_refill'] ?? microtime(true));
        
        $timePassed = microtime(true) - $lastRefill;
        $tokensToAdd = $timePassed * $refillRate;
        
        return (int) min($bucketSize, $tokens + $tokensToAdd);
    }
}

Leaky Bucket Algorithm

// app/Services/RateLimiting/LeakyBucketLimiter.php
<?php

namespace App\Services\RateLimiting;

use Illuminate\Support\Facades\Redis;

class LeakyBucketLimiter
{
    public function __construct(
        private string $prefix = 'rate_limit:leaky:'
    ) {}
    
    /**
     * Attempt to add request to leaky bucket
     */
    public function attempt(
        string $key,
        int $bucketSize,
        int $leakRate // requests per second
    ): RateLimitResult {
        $script = <<<'LUA'
            local key = KEYS[1]
            local bucket_size = tonumber(ARGV[1])
            local leak_rate = tonumber(ARGV[2])
            local now = tonumber(ARGV[3])
            
            -- Get current state
            local bucket = redis.call('hmget', key, 'water', 'last_leak')
            local water = tonumber(bucket[1]) or 0
            local last_leak = tonumber(bucket[2]) or now
            
            -- Leak water based on time passed
            local time_passed = now - last_leak
            local water_to_leak = time_passed * leak_rate
            water = math.max(0, water - water_to_leak)
            
            -- Check if bucket has room
            if water >= bucket_size then
                -- Calculate wait time
                local wait_time = (water - bucket_size + 1) / leak_rate
                return {0, bucket_size - water, wait_time}
            end
            
            -- Add water (request) to bucket
            water = water + 1
            
            -- Update bucket
            redis.call('hmset', key, 'water', water, 'last_leak', now)
            redis.call('expire', key, bucket_size / leak_rate * 2)
            
            return {1, bucket_size - water, 0}
        LUA;
        
        $result = Redis::eval(
            $script,
            1,
            $this->prefix . $key,
            $bucketSize,
            $leakRate,
            microtime(true)
        );
        
        return new RateLimitResult(
            allowed: (bool) $result[0],
            remaining: max(0, (int) $result[1]),
            retryAfter: (int) ceil($result[2]),
            limit: $bucketSize
        );
    }
}

Rate Limit Result DTO

// app/Services/RateLimiting/RateLimitResult.php
<?php

namespace App\Services\RateLimiting;

readonly class RateLimitResult
{
    public function __construct(
        public bool $allowed,
        public int $remaining,
        public int $retryAfter,
        public int $limit
    ) {}
    
    public function headers(): array
    {
        $headers = [
            'X-RateLimit-Limit' => $this->limit,
            'X-RateLimit-Remaining' => $this->remaining,
        ];
        
        if (!$this->allowed) {
            $headers['Retry-After'] = $this->retryAfter;
            $headers['X-RateLimit-Reset'] = time() + $this->retryAfter;
        }
        
        return $headers;
    }
}

Middleware Integration

Flexible Rate Limit Middleware

// app/Http/Middleware/AdvancedRateLimit.php
<?php

namespace App\Http\Middleware;

use App\Services\RateLimiting\SlidingWindowLimiter;
use App\Services\RateLimiting\TokenBucketLimiter;
use Closure;
use Illuminate\Http\Request;
use Symfony\Component\HttpFoundation\Response;

class AdvancedRateLimit
{
    public function __construct(
        private SlidingWindowLimiter $slidingWindow,
        private TokenBucketLimiter $tokenBucket
    ) {}
    
    public function handle(Request $request, Closure $next, string $limiterConfig): Response
    {
        $config = $this->parseConfig($limiterConfig);
        $key = $this->resolveKey($request, $config);
        
        $result = match ($config['algorithm']) {
            'sliding_window' => $this->slidingWindow->attempt(
                $key,
                $config['max_requests'],
                $config['window_seconds']
            ),
            'token_bucket' => $this->tokenBucket->attempt(
                $key,
                $config['bucket_size'],
                $config['refill_rate']
            ),
            default => throw new \InvalidArgumentException("Unknown algorithm: {$config['algorithm']}")
        };
        
        if (!$result->allowed) {
            return response()->json([
                'error' => 'Too Many Requests',
                'message' => 'Rate limit exceeded. Please try again later.',
                'retry_after' => $result->retryAfter,
            ], 429, $result->headers());
        }
        
        $response = $next($request);
        
        // Add rate limit headers to successful response
        foreach ($result->headers() as $header => $value) {
            $response->headers->set($header, $value);
        }
        
        return $response;
    }
    
    private function parseConfig(string $config): array
    {
        // Format: algorithm:param1,param2|key_type
        // Example: sliding_window:100,60|user
        // Example: token_bucket:100,10|ip
        
        [$limiter, $keyType] = explode('|', $config) + [null, 'user'];
        [$algorithm, $params] = explode(':', $limiter);
        $params = array_map('intval', explode(',', $params));
        
        return match ($algorithm) {
            'sliding_window' => [
                'algorithm' => 'sliding_window',
                'max_requests' => $params[0],
                'window_seconds' => $params[1],
                'key_type' => $keyType,
            ],
            'token_bucket' => [
                'algorithm' => 'token_bucket',
                'bucket_size' => $params[0],
                'refill_rate' => $params[1],
                'key_type' => $keyType,
            ],
            default => throw new \InvalidArgumentException("Unknown algorithm: {$algorithm}")
        };
    }
    
    private function resolveKey(Request $request, array $config): string
    {
        $prefix = $request->route()->getName() ?? $request->path();
        
        return match ($config['key_type']) {
            'user' => $prefix . ':user:' . ($request->user()?->id ?? 'guest'),
            'ip' => $prefix . ':ip:' . $request->ip(),
            'api_key' => $prefix . ':key:' . $request->header('X-API-Key', 'none'),
            default => $prefix . ':' . $config['key_type']
        };
    }
}

Route Configuration

// routes/api.php
use App\Http\Middleware\AdvancedRateLimit;

// Sliding window: 100 requests per 60 seconds, keyed by user
Route::middleware('advanced.rate:sliding_window:100,60|user')->group(function () {
    Route::get('/users', [UserController::class, 'index']);
    Route::get('/posts', [PostController::class, 'index']);
});

// Token bucket: 100 tokens, refill 10/second, keyed by IP
Route::middleware('advanced.rate:token_bucket:100,10|ip')->group(function () {
    Route::post('/webhooks', [WebhookController::class, 'handle']);
});

// Stricter limits for auth endpoints
Route::middleware('advanced.rate:sliding_window:5,60|ip')->group(function () {
    Route::post('/login', [AuthController::class, 'login']);
    Route::post('/register', [AuthController::class, 'register']);
});

Distributed Rate Limiting

Redis Cluster Support

// app/Services/RateLimiting/DistributedRateLimiter.php
<?php

namespace App\Services\RateLimiting;

use Illuminate\Support\Facades\Redis;

class DistributedRateLimiter
{
    private const LOCK_TTL = 5; // seconds
    
    public function __construct(
        private string $prefix = 'rate_limit:distributed:'
    ) {}
    
    /**
     * Distributed sliding window with Redis cluster support
     */
    public function attempt(
        string $key,
        int $maxRequests,
        int $windowSeconds
    ): RateLimitResult {
        // Use Lua script for atomic operation
        $script = <<<'LUA'
            local key = KEYS[1]
            local max_requests = tonumber(ARGV[1])
            local window_seconds = tonumber(ARGV[2])
            local now = tonumber(ARGV[3])
            
            -- Remove old entries
            local window_start = now - window_seconds
            redis.call('zremrangebyscore', key, '-inf', window_start)
            
            -- Count current requests
            local count = redis.call('zcard', key)
            
            if count >= max_requests then
                -- Get oldest entry to calculate retry time
                local oldest = redis.call('zrange', key, 0, 0, 'WITHSCORES')
                local retry_after = 0
                if #oldest > 0 then
                    retry_after = oldest[2] + window_seconds - now
                end
                return {0, max_requests - count, retry_after}
            end
            
            -- Add current request
            redis.call('zadd', key, now, now .. ':' .. math.random())
            redis.call('expire', key, window_seconds)
            
            return {1, max_requests - count - 1, 0}
        LUA;
        
        $result = Redis::eval(
            $script,
            1,
            $this->prefix . $key,
            $maxRequests,
            $windowSeconds,
            microtime(true)
        );
        
        return new RateLimitResult(
            allowed: (bool) $result[0],
            remaining: max(0, (int) $result[1]),
            retryAfter: max(0, (int) ceil($result[2])),
            limit: $maxRequests
        );
    }
    
    /**
     * Reset rate limit for a key
     */
    public function reset(string $key): void
    {
        Redis::del($this->prefix . $key);
    }
    
    /**
     * Get current count for a key
     */
    public function count(string $key, int $windowSeconds): int
    {
        $windowStart = microtime(true) - $windowSeconds;
        
        return Redis::zcount(
            $this->prefix . $key,
            $windowStart,
            '+inf'
        );
    }
}

Tiered Rate Limiting

Subscription-Based Limits

// app/Services/RateLimiting/TieredRateLimiter.php
<?php

namespace App\Services\RateLimiting;

use App\Models\User;

class TieredRateLimiter
{
    private array $tiers = [
        'free' => [
            'requests_per_minute' => 20,
            'requests_per_hour' => 100,
            'requests_per_day' => 1000,
            'burst_size' => 10,
        ],
        'basic' => [
            'requests_per_minute' => 60,
            'requests_per_hour' => 1000,
            'requests_per_day' => 10000,
            'burst_size' => 30,
        ],
        'pro' => [
            'requests_per_minute' => 300,
            'requests_per_hour' => 5000,
            'requests_per_day' => 50000,
            'burst_size' => 100,
        ],
        'enterprise' => [
            'requests_per_minute' => 1000,
            'requests_per_hour' => 30000,
            'requests_per_day' => 500000,
            'burst_size' => 500,
        ],
    ];
    
    public function __construct(
        private SlidingWindowLimiter $slidingWindow,
        private TokenBucketLimiter $tokenBucket
    ) {}
    
    public function attempt(User $user, string $endpoint): RateLimitResult
    {
        $tier = $this->tiers[$user->subscription_tier] ?? $this->tiers['free'];
        $key = "user:{$user->id}:{$endpoint}";
        
        // Check all limits
        $results = [];
        
        // Per-minute limit (sliding window)
        $results[] = $this->slidingWindow->attempt(
            $key . ':minute',
            $tier['requests_per_minute'],
            60
        );
        
        // Per-hour limit
        $results[] = $this->slidingWindow->attempt(
            $key . ':hour',
            $tier['requests_per_hour'],
            3600
        );
        
        // Per-day limit
        $results[] = $this->slidingWindow->attempt(
            $key . ':day',
            $tier['requests_per_day'],
            86400
        );
        
        // Burst protection (token bucket)
        $results[] = $this->tokenBucket->attempt(
            $key . ':burst',
            $tier['burst_size'],
            $tier['burst_size'] / 10 // refill in 10 seconds
        );
        
        // Find the most restrictive result
        foreach ($results as $result) {
            if (!$result->allowed) {
                return $result;
            }
        }
        
        // All limits passed, return the one with lowest remaining
        return collect($results)->sortBy('remaining')->first();
    }
    
    public function getLimitsForUser(User $user): array
    {
        return $this->tiers[$user->subscription_tier] ?? $this->tiers['free'];
    }
}

Cost-Based Rate Limiting

Different Costs for Different Endpoints

// app/Services/RateLimiting/CostBasedLimiter.php
<?php

namespace App\Services\RateLimiting;

class CostBasedLimiter
{
    private array $endpointCosts = [
        'GET /api/users' => 1,
        'GET /api/users/*' => 1,
        'POST /api/users' => 5,
        'GET /api/reports' => 10,
        'POST /api/reports/generate' => 50,
        'POST /api/exports' => 100,
        'GET /api/search' => 5,
    ];
    
    public function __construct(
        private TokenBucketLimiter $tokenBucket
    ) {}
    
    public function attempt(string $endpoint, string $method, string $userKey): RateLimitResult
    {
        $cost = $this->getCost($method, $endpoint);
        
        // User has 1000 tokens per hour, refills at ~0.28 tokens/second
        return $this->tokenBucket->attempt(
            "cost:{$userKey}",
            bucketSize: 1000,
            refillRate: 1000 / 3600, // ~0.28 tokens/second
            tokensToConsume: $cost
        );
    }
    
    private function getCost(string $method, string $endpoint): int
    {
        $key = "{$method} {$endpoint}";
        
        // Check exact match
        if (isset($this->endpointCosts[$key])) {
            return $this->endpointCosts[$key];
        }
        
        // Check wildcard matches
        foreach ($this->endpointCosts as $pattern => $cost) {
            $regex = str_replace(['*', '/'], ['[^/]+', '\/'], $pattern);
            if (preg_match("/^{$regex}$/", $key)) {
                return $cost;
            }
        }
        
        return 1; // default cost
    }
}

Monitoring & Analytics

Rate Limit Metrics

// app/Services/RateLimiting/RateLimitMetrics.php
<?php

namespace App\Services\RateLimiting;

use Illuminate\Support\Facades\Redis;
use Illuminate\Support\Facades\Log;

class RateLimitMetrics
{
    public function record(string $key, RateLimitResult $result): void
    {
        $metrics = [
            'key' => $key,
            'allowed' => $result->allowed,
            'remaining' => $result->remaining,
            'timestamp' => now()->toIso8601String(),
        ];
        
        // Record to Redis for real-time monitoring
        Redis::lpush('rate_limit:metrics', json_encode($metrics));
        Redis::ltrim('rate_limit:metrics', 0, 9999);
        
        // Record rate limit hits for analytics
        if (!$result->allowed) {
            $hourKey = 'rate_limit:hits:' . now()->format('Y-m-d:H');
            Redis::hincrby($hourKey, $key, 1);
            Redis::expire($hourKey, 86400 * 7);
            
            Log::channel('rate_limit')->warning('Rate limit exceeded', $metrics);
        }
    }
    
    public function getHits(string $key, int $hours = 24): array
    {
        $results = [];
        
        for ($i = 0; $i < $hours; $i++) {
            $hourKey = 'rate_limit:hits:' . now()->subHours($i)->format('Y-m-d:H');
            $hits = Redis::hget($hourKey, $key);
            
            $results[now()->subHours($i)->format('Y-m-d H:00')] = (int) $hits;
        }
        
        return array_reverse($results);
    }
    
    public function getTopOffenders(int $hours = 24, int $limit = 10): array
    {
        $totals = [];
        
        for ($i = 0; $i < $hours; $i++) {
            $hourKey = 'rate_limit:hits:' . now()->subHours($i)->format('Y-m-d:H');
            $hits = Redis::hgetall($hourKey);
            
            foreach ($hits as $key => $count) {
                $totals[$key] = ($totals[$key] ?? 0) + $count;
            }
        }
        
        arsort($totals);
        
        return array_slice($totals, 0, $limit, true);
    }
}

Best Practices

1. Choose the Right Algorithm

Use Case	Recommended Algorithm
API general	Sliding Window
Burst protection	Token Bucket
Queue processing	Leaky Bucket
Cost-based billing	Token Bucket với costs

2. Multiple Layers

// Apply multiple rate limits
Route::middleware([
    'advanced.rate:sliding_window:1000,3600|user',  // 1000/hour per user
    'advanced.rate:sliding_window:100,60|ip',       // 100/minute per IP
    'advanced.rate:token_bucket:50,5|user',         // burst protection
])->group(function () {
    // routes
});

3. Graceful Degradation

// Return cached/stale data when rate limited
if (!$result->allowed && $cachedData = Cache::get($cacheKey)) {
    return response()->json([
        'data' => $cachedData,
        'stale' => true,
        'message' => 'Rate limited, returning cached data',
    ], 200, $result->headers());
}

Kết Luận

Advanced rate limiting giúp:

Smooth traffic với sliding window
Handle bursts với token bucket
Fair queueing với leaky bucket
Scale horizontally với distributed limiting
Flexible pricing với cost-based limiting

Checklist Implementation

Chọn thuật toán phù hợp với use case
Implement distributed limiting với Redis
Set up tiered limits theo subscription
Add cost-based limiting cho expensive endpoints
Monitor và alert rate limit hits
Graceful responses với retry-after headers