Distributed Rate Limiting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class ResilientRedisRateLimiter {
  private redis: RedisCluster;
  private localFallback: LocalRateLimiter;
  private healthChecker: HealthChecker;
  private metrics: MetricsClient;
 
  async tryConsume(key: string, limit: number): Promise<RateLimitResult> {
    // Check Redis health
    if (!this.healthChecker.isRedisHealthy()) {
      this.metrics.increment('rate_limit.fallback.local');
      return this.localFallback.tryConsume(key, limit);
    }
 
    try {
      const result = await this.withTimeout(
        this.checkRedis(key, limit),
        50  // 50ms timeout
      );
      this.metrics.timing('rate_limit.redis.latency', result.latencyMs);
      return result;
    } catch (error) {
      this.metrics.increment('rate_limit.redis.error');
      this.healthChecker.recordFailure();
      
      // Fail open or closed based on configuration
      if (this.config.failOpen) {
        this.metrics.increment('rate_limit.fail_open');
        return { allowed: true, remaining: 0, uncertain: true };
      } else {
        this.metrics.increment('rate_limit.fail_closed');
        return { allowed: false, remaining: 0, uncertain: true };
      }
    }
  }
 
  private async checkRedis(key: string, limit: number): Promise<RateLimitResult> {
    const pipeline = this.redis.pipeline();
    
    // Multi-window check in one round-trip
    const windows = ['minute', 'hour', 'day'];
    for (const window of windows) {
      const windowKey = `{ratelimit:${key}}:${window}`;
      pipeline.evalsha(this.scriptSha, 1, windowKey, this.getLimitForWindow(limit, window));
    }
    
    const results = await pipeline.exec();
    return this.aggregateResults(results);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class MultiRegionRateLimiter {
  private localRedis: RedisClient;      // Same-region Redis
  private globalSyncer: GlobalSyncer;   // Cross-region sync service
  private region: string;
 
  async tryConsume(userId: string, limit: number): Promise<RateLimitResult> {
    // Step 1: Check local region's count
    const localKey = `ratelimit:${userId}:${this.region}`;
    const localCount = await this.localRedis.incr(localKey);
    
    // Step 2: Get estimated global count
    // This is eventually consistent but fast
    const globalEstimate = await this.globalSyncer.getEstimatedGlobalCount(userId);
    
    // Step 3: Calculate effective count
    const effectiveCount = localCount + globalEstimate;
    
    // Step 4: Apply limit with buffer for sync lag
    const effectiveLimit = limit * 0.9;  // 10% buffer for sync lag
    
    if (effectiveCount > effectiveLimit) {
      // Rollback local increment
      await this.localRedis.decr(localKey);
      return { allowed: false, remaining: 0 };
    }
    
    // Step 5: Async report to global syncer
    this.globalSyncer.reportUsage(userId, this.region, 1);
    
    return {
      allowed: true,
      remaining: Math.max(0, limit - effectiveCount),
    };
  }
}
 
class GlobalSyncer {
  private regionCounts: Map<string, Map<string, number>>;  // userId -> region -> count
  
  // Called by each region periodically (e.g., every 5 seconds)
  async syncFromRegion(region: string, counts: Map<string, number>): Promise<void> {
    for (const [userId, count] of counts) {
      if (!this.regionCounts.has(userId)) {
        this.regionCounts.set(userId, new Map());
      }
      this.regionCounts.get(userId)!.set(region, count);
    }
  }
 
  getEstimatedGlobalCount(userId: string): number {
    const userCounts = this.regionCounts.get(userId);
    if (!userCounts) return 0;
    
    let total = 0;
    for (const count of userCounts.values()) {
      total += count;
    }
    return total;
  }
}