Distributed Rate Limiting — Consistent Enforcement Across Regions

In this tutorial, you will learn about Distributed Rate Limiting. We cover key concepts, practical examples, and best practices to help you master this topic.

Distributed rate limiting enforces rate limits consistently across multiple server instances, data centers, and geographic regions using shared state in Redis Cluster, with trade-offs between consistency, availability, and latency.

What You'll Learn

• Challenges of rate limiting across regions
• Redis Cluster for multi-region rate limiting
• Consistent hashing for key distribution
• Eventual consistency trade-offs

Why It Matters

Single-region rate limiting is straightforward. Multi-region introduces latency, consistency, and partitioning challenges. A client in Europe might receive a rate limit from the US region that a European instance does not know about.

Real-World Use

Durga Antivirus Pro has API gateways in US, Europe, and Asia. A global partner should have a 10,000 req/hour limit across all regions. The gateway uses Redis Cluster with CRDT-based counters to maintain approximate consistency across regions.

flowchart LR
    subgraph "US Region"
        USGW["Gateway US"] --> USRedis["Redis US"]
    end
    subgraph "EU Region"
        EUGW["Gateway EU"] --> EURedis["Redis EU"]
    end
    subgraph "Asia Region"
        ASIAGW["Gateway Asia"] --> ASIARedis["Redis Asia"]
    end
    USRedis <--> EURedis <--> ASIARedis
    Client["Global Client"] --> USGW
    Client --> EUGW
    Client --> ASIAGW
    style USRedis fill:#dbeafe,stroke:#2563eb
    style EURedis fill:#dbeafe,stroke:#2563eb
    style ASIARedis fill:#dbeafe,stroke:#2563eb

Centralized Redis with Cross-Region Replication

import redis
import time

class GlobalRateLimiter:
    def __init__(self, redis_urls, local_region):
        self.local = redis.Redis.from_url(redis_urls[local_region])
        self.regions = redis_urls
        self.local_region = local_region

    def allow_request(self, client_id, global_limit, window_seconds):
        key = f"global:{client_id}:{self._window_key(window_seconds)}"
        local_count = self.local.incr(key)
        if local_count == 1:
            self.local.expire(key, window_seconds * 2)

        # Subtract local count from global limit for approximate check
        # Using local limit = global_limit / number_of_regions
        region_count = len(self.regions)
        local_limit = global_limit // region_count

        if local_count > local_limit:
            return False
        return True

    def _window_key(self, window_seconds):
        return int(time.time()) - (int(time.time()) % window_seconds)

Consistent Hashing for Key Distribution

import hashlib

class ConsistentHashRing:
    def __init__(self, nodes, replicas=100):
        self.replicas = replicas
        self.ring = {}
        self.sorted_keys = []

        for node in nodes:
            for i in range(replicas):
                key = self._hash(f"{node}:{i}")
                self.ring[key] = node
                self.sorted_keys.append(key)
        self.sorted_keys.sort()

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def get_node(self, key):
        if not self.ring:
            return None
        hash_key = self._hash(key)
        for ring_key in self.sorted_keys:
            if ring_key >= hash_key:
                return self.ring[ring_key]
        return self.ring[self.sorted_keys[0]]

# Route rate limit checks to specific Redis nodes
ring = ConsistentHashRing(["redis-us", "redis-eu", "redis-asia"])
redis_node = ring.get_node("client-12345")

Rate Limit Synchronization with Gossip Protocol

import asyncio
import json

class GossipRateSync:
    def __init__(self, node_id, peers):
        self.node_id = node_id
        self.peers = peers
        self.local_counts = {}

    async def sync(self):
        while True:
            for peer in self.peers:
                try:
                    data = {
                        "node_id": self.node_id,
                        "counts": self.local_counts,
                        "timestamp": time.time()
                    }
                    await self._send(peer, data)
                except Exception as e:
                    print(f"Sync to {peer} failed: {e}")
            await asyncio.sleep(5)

    def merge_counts(self, peer_counts):
        for key, count in peer_counts.items():
            if key not in self.local_counts or count > self.local_counts[key]:
                self.local_counts[key] = count

Common Mistakes

1. Assuming Strong Consistency Across Regions

Cross-region replication has latency. Rate limit counters may be stale by seconds. Design for eventual consistency.

2. Not Handling Redis Failover

If the local Redis fails, rate limiting should degrade gracefully. Use a local in-memory fallback with relaxed limits.

3. Using Global Windows Across Timezones

A "daily" limit should use UTC midnight, not local time. Different regions would otherwise reset at different times.

4. Over-Engineering for Small Deployments

A single Redis instance handles millions of requests per second. Only need distributed limiting for multi-region or extreme scale.

5. Ignoring Network Partition Scenarios

When regions cannot communicate, each region should enforce its own limits conservatively. Reconcile when the partition heals.

Practice Questions

1. What are the main challenges of distributed rate limiting across regions?
2. How does consistent hashing help distribute rate limit keys?
3. Why is eventual consistency acceptable for rate limiting?
4. How do you handle a regional Redis outage?
5. What is the gossip protocol and how does it help sync rate limits?

Answers:

1. Cross-region latency, network partitions, clock skew, and the trade-off between consistency and availability.
2. Consistent hashing maps each client to a specific Redis node, ensuring the same node handles all requests for that client.
3. A few extra requests during sync lag are acceptable for most APIs. Strong consistency would add unacceptable latency.
4. Fall back to local in-memory rate limiting with conservative limits (halve the limit). Reconnect when Redis recovers.
5. Gossip protocol periodically shares state with random peers to achieve eventual consistency without a central coordinator.

Challenge: Design a distributed rate limiting system for 3 regions (US, EU, Asia) with a global limit of 100,000 req/hour. Define the local limit per region, the sync mechanism, and the failure mode for each region.

FAQ

Mini Project

Build a distributed rate limiter with 3 simulated regions (US, EU, Asia). Each region has its own Redis instance. Implement a gossip protocol that syncs rate limit counts every 10 seconds. Test with a global client making requests across all regions.

What's Next

Continue with IP-Based Rate Limiting for per-address enforcement, or explore User-Based Rate Limiting for authenticated clients.