Rate Limiting, Throttling and Quota Management Questions

Approach (summary):
Use a distributed token-bucket per customer enforced at each API gateway instance. Back the counters with Redis for low-latency, atomicity and cross-instance coordination. Each customer has a bucket defined by capacity=10000 and refill_rate=10000 tokens/minute (~166.66 tokens/sec). Gateways request tokens from Redis; if granted, forward request.

Redis implementation (atomic via Lua):

# Python pseudo-code using redis-py and a Lua script
GET_TOKENS_LUA = """
local key = KEYS[1]
local now = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local capacity = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local bucket = redis.call('HMGET', key, 'tokens', 'last')
local tokens = tonumber(bucket[1]) or capacity
local last = tonumber(bucket[2]) or now

-- refill
local elapsed = math.max(0, now - last)
tokens = math.min(capacity, tokens + elapsed * refill_rate)
if tokens < requested then
  redis.call('HMSET', key, 'tokens', tokens, 'last', now)
  redis.call('EXPIRE', key, 120)
  return 0
else
  tokens = tokens - requested
  redis.call('HMSET', key, 'tokens', tokens, 'last', now)
  redis.call('EXPIRE', key, 120)
  return 1
end
"""
# Call with: EVAL GET_TOKENS_LUA 1 bucket:{customer_id} <now> <refill_per_sec> 10000 1

Why Redis + Lua:

• Lua script executes atomically, preventing race conditions across concurrent gateways.
• Using HMSET stores tokens and last timestamp; EXPIRE cleans inactive buckets.
• Refill is continuous (tokens += elapsed * refill_rate) for smoother behavior.

Correctness under race conditions:

• Atomic Lua prevents interleaving updates; concurrent requests are serialized at Redis for that key.
• If many gateways issue simultaneous requests, Redis will sequentially run the script ensuring no double-counting.
• Use consistent key hashing or Redis Cluster with requests routed to correct shard so the key is located on a single shard (or use client-side routing).

Failover and availability:

• Redis single node is a SPOF — use a Redis Cluster or primary-replica with automatic failover (Sentinel) to maintain availability.
• During primary failover there is a short window where requests may be rejected or accepted twice if clients connect to both old primary and new primary—mitigate by:
  • Keep bucket state durable (RDB/AOF) and tune AOF for low-latency fsync (appendfsync everysec) balancing durability vs performance.
  • Use conservative limits: e.g., slightly lower effective capacity to absorb transient duplication.
  • Implement gateway-side local leaky-bucket as fallback: allow a small local cache of tokens (burst buffer) and periodically reconcile with Redis. This reduces pressure and provides availability when Redis latency spikes, but you must bound the local buffer to limit overshoot.

Operational considerations:

• Shard keys by customer_id to distribute load.
• Monitor Redis latency, error rates, and token consumption metrics; emit per-customer usage to alert on hotspots.
• Rate-limit configuration and emergency overrides stored in a config service and cached with TTL.
• Test failover scenarios (primary failover, network partition, heavy bursts) and measure overshoot.

Alternatives:

• Centralized token-bucket service (stateless gateways call gRPC service) with in-memory local caches and persisted checkpoints — simpler to reason about but adds another service to scale and make highly available.
• Use Redis atomic INCR with fixed window for simplicity, but it is less smooth and vulnerable to boundary bursts.

This design balances correctness (atomicity via Lua), performance (Redis latency), and availability (clustering, local fallback) appropriate for data ingestion at scale.

Requirements & constraints:

• Functional: enforce 1,000 requests/minute per tenant globally (across 2 regions) with low request-path latency.
• Non-functional: tolerable small accuracy drift, high availability, low added latency (<~1–5ms ideally), support multi-region failover.

Algorithm choice:

• Token bucket fits better: it supports bursts (you can allow short bursts above steady rate) and is simple to implement. Leaky bucket enforces a strict drain rate (smoother) but is less flexible for bursts which ingestion systems often need.
• Use fixed window or sliding window counters for strictness? Sliding-window or windowed token-bucket gives better accuracy across region boundaries than naive fixed windows.

Architecture (hybrid, recommended):

• Global authoritative store: a low-latency in-memory datastore accessible from both regions (e.g., Redis primary in region A + cross-region read replicas, or a managed multi-region Redis/Cluster with strong replication). This holds per-tenant global counters / token balances.
• Local per-region caches: each region keeps a local token-bucket replica for each active tenant to make the common fast-path entirely local (zero cross-region hop).
• Token leasing / refill protocol: local nodes lease tokens from the global store in batches (e.g., lease 100 tokens at a time). Local requests consume from the local bucket; when it falls below threshold, the region re-requests a lease. Leases are time-bound to avoid token hoarding.

Synchronization strategy:

• Lease-based approach avoids per-request global calls. Choose lease size and refill frequency to balance accuracy vs latency.
• Reconcile occasional overshoot by having the global store decrement when leases are issued; if two regions request simultaneously, the global store enforces remaining capacity atomically (use Redis INCRBY/DECRBY with Lua script for atomic check-and-decrement).
• Implement a small jitter/backoff on lease attempts to avoid thundering herd.

Failure modes and mitigations:

• Global store unavailable: regions cannot get new leases. Options:
  • Fail-open (recommended for ingestion pipelines where availability is critical): continue serving from local cache until tokens exhausted OR switch to degraded per-region limit (e.g., allow 50% of global rate per region). Emit alerts, metrics, and start reconciliation when store recovers.
  • Fail-closed (if enforcement is safety-critical): reject requests; high availability sacrifice. Use only if accepting overload is unacceptable.
• Network partition between regions: the lease model prevents double-spend because the global store controls total tokens; if partition isolates a region from global store, that region must use its remaining lease tokens and then either degrade (fail-open) or stop traffic (fail-closed).
• Clock skew: use TTL-based leases and server-side timestamps to avoid relying on local clocks.

Accuracy vs latency trade-offs:

• Larger lease sizes => lower global load and latency, greater chance of transient over-limit (accuracy loss).
• Smaller leases => better accuracy, more global calls, higher latency.
• Tune lease size by tenant (high-volume tenants smaller leases) and by SLA.

Implementation notes:

• Use Redis with Lua scripts to allocate leases atomically and persist per-tenant remaining tokens and last-refill time. Consider clustered Redis or cloud-managed multi-region cache.
• Instrument per-tenant metrics, SLOs, alerts for exhausted global capacity, and background reconciliation job to correct overshoots.
• Consider sliding-window token bucket variant for better cross-boundary accuracy if you must avoid bursts being double-counted.

Recommendation summary:

• Use token-bucket with global authoritative Redis and regional local buckets that lease tokens in batches. Fail-open by default for ingestion availability, with conservative degradations and strong monitoring. Tune lease sizes per tenant to balance latency and strictness.