Rate Limiting, Throttling and Quota Management Questions

Approach: implement a token-bucket keeping currentTokens (capped by burstSize) and lastRefill time. acquire() updates tokens on each call, returns immediately if tokens>0 else enqueues a Promise resolver. A single timer wakes queued waiters when enough tokens accumulate. Support cancel/timeout via AbortSignal and optional timeout ms. Node's single-threaded nature avoids races; careful bookkeeping ensures correctness under high concurrency.

class TokenBucket {
  constructor({ burstSize, refillRate }) {
    this.capacity = burstSize;
    this.refillRate = refillRate; // tokens per second
    this._tokens = burstSize;
    this._last = Date.now();
    this._queue = []; // [{resolve, reject, tokensNeeded, signal, timer}]
    this._timer = null;
  }

  _refill() {
    const now = Date.now();
    const elapsedSec = (now - this._last) / 1000;
    if (elapsedSec <= 0) return;
    this._tokens = Math.min(this.capacity, this._tokens + elapsedSec * this.refillRate);
    this._last = now;
  }

  async acquire({ signal = null, timeoutMs = null } = {}) {
    if (signal && signal.aborted) throw new Error('aborted');
    this._refill();
    if (this._tokens >= 1) {
      this._tokens -= 1;
      return;
    }

    return await new Promise((resolve, reject) => {
      const entry = { resolve: () => { clear(); resolve(); }, reject: (err) => { clear(); reject(err); } };
      const clear = () => {
        if (entry.timer) clearTimeout(entry.timer);
        if (entry.unsub) entry.unsub();
      };

      if (timeoutMs != null) {
        entry.timer = setTimeout(() => entry.reject(new Error('timeout')), timeoutMs);
      }

      if (signal) {
        entry.unsub = () => signal.removeEventListener('abort', onAbort);
        const onAbort = () => entry.reject(new Error('aborted'));
        signal.addEventListener('abort', onAbort);
      }

      this._queue.push(entry);
      this._scheduleTimer();
    });
  }

  _scheduleTimer() {
    if (this._timer || this._queue.length === 0) return;
    const now = Date.now();
    this._refill();
    if (this._tokens >= 1) {
      // fulfill as many queued requests as tokens allow
      while (this._tokens >= 1 && this._queue.length) {
        this._tokens -= 1;
        const e = this._queue.shift();
        e.resolve();
      }
      if (this._queue.length === 0) return;
    }
    // compute ms until next token
    const tokensNeeded = 1 - this._tokens;
    const ms = Math.max(0, Math.ceil((tokensNeeded / this.refillRate) * 1000));
    this._timer = setTimeout(() => {
      this._timer = null;
      this._scheduleTimer();
    }, ms);
  }
}

Key points:

• O(1) per acquire amortized; queue length bounded by callers waiting.
• Correct under high concurrency because operations are atomic in event loop.
• Supports abort via AbortSignal and timeout.
  Edge cases: very small refillRate, burstSize 0, callers that cancel — queue cleanup prevents leaks.

Approach: implement a thread-safe token bucket that refills tokens at a steady rate up to a capacity. Use a mutex and store last refill timestamp so Allow is O(1) and safe under concurrency. For testability inject a Clock interface (real or fake) so tests can control time.

package ratelimit

import (
	"sync"
	"time"
)

// Clock allows deterministic tests.
type Clock interface {
	Now() time.Time
	Since(t time.Time) time.Duration
}

type realClock struct{}
func (realClock) Now() time.Time                    { return time.Now() }
func (realClock) Since(t time.Time) time.Duration   { return time.Since(t) }

// TokenBucket is a concurrency-safe token bucket rate limiter.
type TokenBucket struct {
	mu       sync.Mutex
	capacity int           // max tokens (burst)
	tokens   float64       // current tokens (can be fractional)
	rate     float64       // tokens per second
	last     time.Time     // last refill time
	clk      Clock
}

// NewTokenBucket creates a limiter that refills at 'rate' tokens/sec and allows bursts up to capacity.
func NewTokenBucket(rate float64, capacity int) *TokenBucket {
	if rate <= 0 { panic("rate must be > 0") }
	if capacity <= 0 { capacity = 1 }
	return &TokenBucket{
		capacity: capacity,
		tokens:   float64(capacity),
		rate:     rate,
		last:     time.Now(),
		clk:      realClock{},
	}
}

// Allow tries to take n tokens. Returns true if allowed, false otherwise.
func (tb *TokenBucket) Allow(n int) bool {
	if n <= 0 { return true }
	if n > tb.capacity { return false } // never allow requests larger than capacity

	tb.mu.Lock()
	defer tb.mu.Unlock()

	// refill
	now := tb.clk.Now()
	elapsed := now.Sub(tb.last).Seconds()
	if elapsed > 0 {
		tb.tokens += elapsed * tb.rate
		if tb.tokens > float64(tb.capacity) {
			tb.tokens = float64(tb.capacity)
		}
		tb.last = now
	}

	if tb.tokens >= float64(n) {
		tb.tokens -= float64(n)
		return true
	}
	return false
}

// Remaining returns the count of whole tokens currently available.
func (tb *TokenBucket) Remaining() int {
	tb.mu.Lock()
	defer tb.mu.Unlock()
	// Note: we don't advance time here; Remaining() may be slightly stale unless caller expects refills.
	return int(tb.tokens)
}

Key concepts:

• refill on-demand using elapsed time avoids background goroutine.
• use float tokens to allow fractional refill for smoothness.
• mutex ensures correctness under concurrency.

Complexity:

• Time: O(1) per Allow/Remaining.
• Space: O(1).

Edge cases:

• requests larger than capacity are rejected.
• clock skew—inject Clock for deterministic tests.

Testing under concurrent load:

• Unit tests with fake clock: advance time deterministically and assert Allowed/Denied transitions.
• Concurrency test: spawn many goroutines calling Allow(1); count successes with atomic counter; ensure successes approximate rate*duration + capacity.
• Stress test: run high goroutine count for several seconds, verify no data races (go test -race) and verify throughput <= configured rate+burst.
• Add benchmarks to measure contention and latency.

Requirements & goals:

• Protect backend from traffic spikes while preserving fair access for users.
• Per-user (or per-API-key) and global limits, support bursts, predictable degradation, clear client signals, safe rollout with monitoring and rollback.

High-level design:

• Edge layer (API gateway / CDN) enforces rate limits. Gateway consults a fast in-memory store (Redis or in-process token bucket) and a centralized policy service for dynamic rules. Downstream services assume limited, smoothed traffic.

Components:

1. Policy store: central store of limits (per-user, per-plan, global) with versioning.
2. Enforcement at edge:
   • Local cache of policies for low latency.
   • Counters stored in Redis (sharded by key) with TTLs for sliding-window or token-bucket state.
3. Metrics/monitoring: per-key/throttle metrics, error rates, latency, backend saturation metrics; alerting on abnormal reject rates or downstream CPU/queue rise.
4. Dashboard & audit logs for impacted keys.

Rate-limit model & burst handling:

• Use token-bucket per user: capacity = burst allowance, refill rate = steady allowed rate. Token-bucket supports bursts up to bucket size then enforces steady rate.
• Global limiter: leaky-bucket/queue-like smoothing or aggregate token-bucket to cap total throughput.
• Combine: per-user token-bucket + global token-bucket. If global exhausted, return prioritized or degraded responses.

Token-bucket vs Leaky-bucket trade-offs:

• Token-bucket: flexible bursts, easy per-key state, good UX. Slightly complex to synchronize across distributed edge nodes (use Redis for global counters).
• Leaky-bucket: enforces smooth output, simpler for global smoothing, but less accommodating to legitimate bursts.
• Recommendation: token-bucket per-user + leaky-bucket/aggregate smoothing at global level.

Client signaling:

• Use standard RFC 6585/429 with headers:
  • Retry-After: seconds when appropriate
  • X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset (per-user)
  • X-Global-RateLimit-Remaining, X-Global-RateLimit-Reset (optional)
• Provide informative error body JSON with link to docs and plan-specific limits.

Rollout and monitoring plan:

1. Start with conservative non-blocking mode ("soft-limit" or 429 but also accept) and log all events for 1–2 weeks.
2. Run canary: enable enforcement for <1% of traffic or low-risk tenants; compare errors and support tickets.
3. Gradually increase enforcement (5% → 25% → 100%) with automated health checks (backend 5xx, latency, SLO burn rate).
4. Provide customer communication: docs, dashboard, per-customer telemetry, email for high-volume keys nearing limits.
5. Autoscaling & emergency overrides: when limits trigger false positives, allow temporary overrides and dynamic rule adjustments.

Monitoring & SLOs:

• Track reject rate, user impact, support tickets, backend queue depth, CPU/memory.
• Alert if rejects spike without corresponding backend protection benefit (e.g., backend healthy but many 429s).
• Periodic review: adjust refill rates/burst sizes based on observed legitimate traffic patterns.

Edge cases & best practices:

• Distinguish read vs write endpoints (tighter limits on expensive ops).
• Grace period for new keys; allow warm-up bursts.
• Client-identification: prefer API keys over IP; fallback to IP-based limits to curb anonymous abuse.
• Synchronization: use local token caches with Redis fallback to reduce latency and avoid thundering herd.

This design balances availability, fairness, and UX while enabling safe rollout and observability.

Approach: use a token-bucket that stores current tokens, capacity, and refill rate (tokens/sec). On each allow_request() we refill based on elapsed time, cap at capacity, then consume a token if available. Use mutex for concurrency. For global limits across instances, persist/coordinate token state in Redis (Lua script for atomic refill+consume) or use a centralized proxy/load‑balancer (Envoy/NGINX) or token server.

package ratelimit

import (
	"sync"
	"time"
)

// TokenBucket is an in-memory token bucket.
type TokenBucket struct {
	mu        sync.Mutex
	capacity  float64       // max tokens
	tokens    float64       // current tokens (fractional allowed)
	rate      float64       // tokens per second
	lastCheck time.Time
}

func NewTokenBucket(capacity, rate float64) *TokenBucket {
	return &TokenBucket{
		capacity:  capacity,
		tokens:    capacity,
		rate:      rate,
		lastCheck: time.Now(),
	}
}

// allowRequest returns true if a token could be consumed.
func (tb *TokenBucket) AllowRequest() bool {
	tb.mu.Lock()
	defer tb.mu.Unlock()

	now := time.Now()
	elapsed := now.Sub(tb.lastCheck).Seconds()
	tb.lastCheck = now

	// Refill
	tb.tokens += elapsed * tb.rate
	if tb.tokens > tb.capacity {
		tb.tokens = tb.capacity
	}

	if tb.tokens >= 1.0 {
		tb.tokens -= 1.0
		return true
	}
	return false
}

Key points:

• Use float tokens to allow fractional refill and smoothness.
• Mutex prevents races; for very high QPS consider sharding buckets or using atomic ops.
• Time complexity: O(1) per request; space: O(1) per bucket.

Distributed/global coordination options:

• Redis + Lua script: atomically compute refill based on stored last timestamp and tokens, then decrement if possible. Scales well and is single source of truth.
• Use a centralized token server or sidecar per service that requests tokens from a central allocator.
• Offload to API gateway/proxy (Envoy, NGINX) which provides built-in distributed rate limiting.
• If strict per-user limits at extreme scale, use consistent hashing to partition keys across a Redis cluster to avoid a single hot key.

Edge cases:

• Clock skew across nodes: use monotonic clocks where possible; in Redis approach, server time is authoritative.
• Burst credit persistence: if you want long-term carryover, persist tokens+timestamp; otherwise resets are acceptable.
• Avoid thundering herd by smoothing refill or using jitter when rejecting/retrying.

Approach: Use per-tenant token buckets for steady-rate enforcement + a global weighted fair-share allocator that redistributes spare tokens periodically. Persist tenant limits in a config store (etcd/Consul) and distribute via watches. Use local in-memory buckets for low latency and a periodic global reconcile to keep cluster-wide fairness.

Core components:

• TenantTokenBucket: capacity, refill_rate (QPS), tokens, last_refill
• GlobalAllocator: collects spare capacity from underutilized tenants and assigns extras proportional to tenant weight
• Store watcher: subscribes to etcd for tenant configs
• Sync protocol: leader-based or CRDT/gossip for eventual consistency; prefer leader (Raft via etcd) to compute global allocations to avoid conflicts

Algorithm sketch + sample async implementation:

import time, asyncio
from collections import defaultdict

class Bucket:
    def __init__(self, rate, burst):
        self.rate = rate
        self.capacity = burst
        self.tokens = burst
        self.last = time.monotonic()
    def refill(self):
        now = time.monotonic(); dt = now - self.last
        self.tokens = min(self.capacity, self.tokens + dt * self.rate)
        self.last = now
    def try_consume(self, n=1):
        self.refill()
        if self.tokens >= n:
            self.tokens -= n; return True
        return False

Global allocator (leader) periodically:

• Read all buckets' utilization snapshots (local nodes report usage via heartbeat)
• Compute spare = sum(max(0, capacity - current_rate)) and distribute shares = spare * (tenant_weight / total_weight)
• Send extra temporary rate tokens to nodes (TTL) via config updates in etcd

Persistence & distribution:

• Store tenant limits, weights, and burst in etcd; nodes watch for changes and update local buckets.
• For cluster-wide state (usage metrics), use a metrics stream (Prometheus pushgateway or gRPC) to leader; leader computes fair-share and writes per-tenant temporary overrides to etcd with short TTL.
• Use leader election (etcd/consul) to avoid split-brain. For high availability, fallback to local best-effort allocation if leader unreachable.

Consistency, safety, and HA:

• Enforce hard limit via local bucket to prevent overload even if allocator inconsistent.
• Make extra capacity advisory and time-limited; always respect per-tenant max.
• Monitor allocator lag and add alerts when divergence > threshold.

Complexities:

• Latency: local checks O(1). Allocation periodic cost O(N) for N tenants.
• Edge cases: clock skew (use monotonic), network partitions (fall back to local limits), burst storms (use max burst caps).