Rate Limiting, Throttling and Quota Management Questions

1) Approach (brief)
Implement a thread-safe in-memory token-bucket per client. Each client record stores tokens, capacity, refill_rate (tokens/sec), last_timestamp and a lock. allow(client_id) computes tokens to add since last_timestamp, updates tokens atomically, and returns whether one token could be consumed. Add a background sweeper to evict inactive clients.

2) Code (Python, threadsafe)

import time, threading

class Bucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last = time.monotonic()
        self.lock = threading.Lock()
        self.last_seen = self.last

class RateLimiter:
    def __init__(self, capacity, rate, ttl=300, sweep_interval=60):
        self.capacity = capacity
        self.rate = rate
        self.ttl = ttl
        self.buckets = {}
        self.map_lock = threading.Lock()
        self._stop = False
        t = threading.Thread(target=self._sweeper, args=(sweep_interval,), daemon=True)
        t.start()

    def allow(self, client_id):
        now = time.monotonic()
        # get or create bucket
        with self.map_lock:
            b = self.buckets.get(client_id)
            if b is None:
                b = Bucket(self.capacity, self.rate)
                self.buckets[client_id] = b
        # operate on bucket
        with b.lock:
            elapsed = now - b.last
            add = elapsed * b.rate
            if add > 0:
                b.tokens = min(b.capacity, b.tokens + add)
                b.last = now
            b.last_seen = now
            if b.tokens >= 1:
                b.tokens -= 1
                return True
            return False

    def _sweeper(self, interval):
        while not self._stop:
            time.sleep(interval)
            now = time.monotonic()
            with self.map_lock:
                to_del = [cid for cid, b in self.buckets.items() if (now - b.last_seen) > self.ttl]
                for cid in to_del:
                    del self.buckets[cid]

    def stop(self):
        self._stop = True

3) Key concepts & reasoning

• Use per-bucket locks to reduce contention vs a single global lock.
• Use time.monotonic for safe elapsed calculations.
• Refill is calculated lazily on allow() to avoid extra goroutines/timers per client.

4) Complexity

• allow() average O(1). Memory is O(n) for n active clients.
• Sweeper runs O(n) occasionally.

5) Memory & eviction strategies

• Default: TTL + background sweeper removes buckets idle > ttl.
• For very large cardinality: use approximate eviction (LRU cache), use an external store (Redis with built-in expirations), fold seldom-seen clients into a shared leaky bucket, or sample-based eviction. Persist minimal state per client (e.g., last_seen and a compact token value) to reduce footprint.

6) Trade-offs

• In-process is low-latency but not shared across processes; for multi-process scale, use a centralized store (Redis) or consistent-hashed local buckets with sticky sessions.

Overview of algorithms

• Token Bucket: Tokens added at rate R; request consumes tokens. Allows bursts up to bucket size. Low cost; common in network/proxy rate limiting.
• Leaky Bucket (queue emulation): Requests enter queue and are drained at fixed rate. Smooths bursts (drops if queue full); less permissive of bursts.
• Fixed Window: Count requests in fixed interval (e.g., minute). Simple but vulnerable to boundary spikes.
• Sliding Window Log: Store timestamps of each request; exact sliding-window semantics. Accurate but storage/CPU heavy.
• Sliding-window Counter (two-window approximation): Keep current and previous window counts weighted by time overlap. Good accuracy/cost tradeoff.

Which for bursty traffic

• Token bucket is best: explicit burst capacity with sustained rate control.
• Leaky bucket limits bursts more strictly (good when you must smooth traffic).
• Fixed window and sliding-window counter can let bursts through at window edges; sliding-window log prevents that but is heavier.

Approximating sliding windows in distributed systems

• Use the two-window counter approximation (current + previous bucket weighted) to avoid per-request logs.
• Implement counters in a fast, centralized store (Redis) with atomic operations or Lua scripts to avoid race conditions.
• Shard keys by user/region with consistent hashing; use local token buckets on each instance refreshed from a central quota to reduce coordination.
• For higher scale, use probabilistic sketches or rate-limiter tokens issued by a small set of leader nodes.

Applying limits: per-user, per-API-key, global

• Enforce hierarchical limits: check most specific → less specific (user/api-key → tenant → global).
• Store counters/namespaces in Redis: rate:user:{id}, rate:api:{key}, rate:global. Use atomic pipeline/Lua to check & decrement multiple keys in one operation to avoid races.
• For performance, combine local fast-path (in-memory token bucket) with periodic reconciliation to central store to allow low-latency bursts while preserving global quotas.
• Apply different policies: stricter global limits for DDoS protection, per-key/user for fair usage, and priority queues for high-value clients.

Recommendations: use token bucket with Redis-backed counters + Lua for distributed correctness; approximate sliding windows with two-bucket weighting; shard and cache to scale while maintaining hierarchical checks.

Approach overview
I’d implement a hybrid token-bucket + sliding-window counters system: token-bucket for smooth per-IP and per-account throttling, sliding-window for strict bursts and analytics. Add a global emergency throttle that can be toggled automatically from aggregated metrics.

Algorithms

• Per-IP & per-account: token bucket (tokens refilled per minute). On request, atomically consume token; reject when empty.
• Global emergency: aggregated rate across regions; when threshold exceeded, apply progressive backoff (increase cost per request or short global denylist).
• Analytics: sliding-window counters for forensics and anomaly detection.

Storage & consistency

• Fast path: local in-memory token buckets (per node) for latency.
• Shared state: Redis (clustered, primary-replicas) with Lua scripts for atomic token consume when cross-check needed.
• Multi-region convergence: use CRDT-based counters (e.g., PN-Counters) or Redis GCS with periodic reconciliation for global metrics. CRDTs avoid coordination and eventual-consistent summation for emergency decisions.

Cross-region enforcement

• Default: enforce locally using IP/account mapping to the nearest region; periodically sync counts to central ranking via CRDTs.
• Strong enforcement for critical accounts: use a global Redis write (tradeoff: higher latency) or route auth requests through a global rate-check service (cache results).
• Emergency decisions derived from aggregated CRDT counters and a leader-election (fast path) to avoid split-brain.

Avoiding false positives (NAT/proxies)

• Use progressive checks: if many users share IP, prefer per-account limit over per-IP; raise IP threshold if it maps to known carrier NAT ranges.
• Integrate device fingerprinting and TLS client hello entropy to distinguish users.
• Allow higher burst allowance and CAPTCHA/challenge for suspicious sources instead of hard blocking.
• Maintain dynamic allowlists for known CDNs/proxies and apply weighted tokens per sub-IP (X-Forwarded-For parsing when trusted).

Operational considerations

• Use Redis Lua scripts for atomic operations and metrics emission to Kafka for offline analysis.
• Circuit-breakers and graceful degradation: when Redis unavailable, fall back to local token-bucket with conservative limits.
• Metrics/alerts: SLOs for false positives, request rejection rate, and global throttle activations; automated rollback for misconfigurations.

This balances low-latency enforcement, global visibility, and reduced false positives for users behind shared IPs.