Designing a Highly Available Distributed Rate Limiter with Redis

The Challenge of Distributed Rate Limiting

Building a rate limiter for a single service instance is straightforward, but it becomes a complex distributed systems problem when multiple instances are behind a load balancer. The core challenge is maintaining a consistent global request count per user across all instances while ensuring the system remains responsive and resilient to failures. A naive in-memory counter on each node fails to provide global limits and is susceptible to process restarts and network partitions.

Applying the CAP Theorem to Rate Limiters

The CAP theorem states that a distributed system can only guarantee two out of Consistency, Availability, and Partition Tolerance. For a rate limiter, this translates into a crucial architectural decision:

• Strong Consistency (C): Every node must agree on the exact request count. In a network partition, this would mean rejecting requests (unavailability) until nodes reconverge.
• Availability (A): The system continues to process requests even during partitions. This means accepting eventual consistency, where nodes might have slightly different counts, potentially allowing brief over-limits.

Implementing an AP Rate Limiter with Redis

A robust distributed rate limiter can be built using Redis, leveraging its atomic operations and key expiration features. Each service instance communicates with a shared Redis cluster to increment and check request counts for users. Redis's design, particularly in a clustered setup, often leans towards AP characteristics, making it suitable for this use case.

type RedisLimiter struct {
  client *redis.Client
  limit int
  window time.Duration
  keyPref string
}

func (l *RedisLimiter) Allow(userID string) (bool, error) {
  key := l.keyPref + userID
  count, err := l.client.Incr(context.Background(), key).Result()
  if err != nil {
    return false, err
  }
  if count == 1 {
    l.client.Expire(context.Background(), key, l.window)
  }
  return count <= int64(l.limit), nil
}

This Redis-backed approach offers several advantages: atomic increments ensure correct counting even with concurrent requests, key expiration simplifies window management, and the shared Redis state allows for global rate limits across all service instances. While it may experience slight inconsistencies during extreme network partitions within the Redis cluster itself, the system remains highly available, fulfilling the AP requirement.