Course contentsShow
← System Design
Lesson 1816 of 1,91943. Real-World System: Rate Limiter ServiceFree lesson

Approximation Techniques for Ultra-High Scale

Trade perfect accuracy for efficiency using probabilistic data structures like count-min sketch at massive scale.

Approximation Techniques for Ultra-High Scale

What you'll learn: How to sacrifice perfect accuracy for massive performance gains using probabilistic data structures when exact counting becomes prohibitively expensive at ultra-high scale.

Why Approximate?

At billions of requests per second, maintaining exact counters for every user and every time window becomes a bottleneck. Even with Redis and Lua scripts, you hit limits: memory explodes, network latency adds up, and coordination overhead kills throughput. Sometimes "good enough" is vastly better than "perfectly accurate but impossibly slow."

The Core Idea

Approximation techniques use probabilistic data structures that provide estimates with bounded error guarantees instead of exact counts. The most popular for rate limiting is the count-min sketch: a compact data structure that can answer "how many times has user X made requests?" with high confidence but small error margins (e.g., ±1% accuracy).

How It Works

Think of a count-min sketch like multiple hash tables with collisions intentionally allowed. When a request arrives, you hash the user ID multiple times and increment counters at those positions. To check the count, you query all positions and take the minimum (hence "count-min"). Collisions cause overcounting, but the minimum reduces that error significantly.

Trade-off: You use ~10KB per sketch instead of gigabytes for exact logs, accept 1-2% overcounting (slightly stricter limits), and gain 10-100x throughput improvements.

When to Use

  • Traffic exceeds millions of requests per second per node
  • Slight overcounting is acceptable (blocking 101 requests instead of 100 is fine)
  • Memory or network bandwidth is constrained
  • Latency must stay sub-millisecond

Key Takeaway: At extreme scale, probabilistic structures like count-min sketch let you trade tiny accuracy losses for enormous gains in speed and memory efficiency—perfect when exact counting becomes the bottleneck itself.