DEV Community

Cover image for The Cardinality Bomb: Defending APIs at the Edge Without an External Cache
Shiyam
Shiyam

Posted on

The Cardinality Bomb: Defending APIs at the Edge Without an External Cache

#go #security #webdev #architecture

How an edge reverse proxy uses fixed-memory sketches to survive infinite-cardinality attacks, credential abuse, and runaway agent loops.

In Part 1, we explored Interpreted Decay — calculating recency-weighted frequency on-the-fly at read time (count >> age) in a single 64-bit word. In Part 2, we looked under the hood at atomic Compare-And-Swap (CAS) state transitions, bit-chipping eviction lotteries, and sub-35ns multi-core scaling.

Data structures prove their real value when applied to infrastructure problems.

Consider a common scenario in backend systems:
A public API sits behind an edge reverse proxy or ingress gateway. Suddenly, an automated scraper or credential-stuffing bot begins rotating through hundreds of thousands of residential IP addresses, randomized query paths, or spoofed tokens.

The standard industry pattern for distributed rate limiting (widely documented by teams like Stripe, GitHub, and Figma) is well-established:

  • Deploy a centralized Redis or Memcached cluster.
  • Track client frequency via sliding-window keys (e.g., rate:limit:<ip>).
  • Query the cache cluster on every incoming HTTP request.

Under normal traffic, this architecture works reliably. But under an intentional high-cardinality flood, distributed counter clusters face distinct operational trade-offs:

  1. Memory & Eviction Collisions: A sliding window allocates a key per client. If an attack fires 500,000 ephemeral IPs across a few minutes, Redis memory surges. Once it reaches maxmemory, it either begins evicting critical application cache data (under LRU policies) or rejects writes (OOM command not allowed), forcing the limiter to fail open.
  2. Network Round-Trip Tax: Querying a remote cache cluster on every single HTTP request adds 2–10ms round-trip latency to the 99th percentile (p99).
  3. Connection Saturation: Under heavy concurrency, connection pool exhaustion and single-threaded Redis event loops often become the bottleneck before the backend itself gets saturated.

The "Cardinality Bomb" Problem

When an attacker distributes requests across a vast botnet (hundreds of thousands of rotating residential IPs), two painful realities emerge:

1. No Per-Key Rate Limiter Blocks a 100% Rotating Key

A key seen for the very first time has an observed frequency of 1. Whether using Redis, a local hash map, or a token bucket, that request falls below any sensible rate limit threshold.
Blocking never-before-seen keys is impossible—doing so would block every legitimate new user visiting the site.

Under a pure IP-rotation attack, every rate limiter forwards the traffic.

2. The Rate Limiter Becomes the Attack Vector

What differs is what the attack does to the rate limiter itself:

  • In-Memory Hash Maps (map[string]*counter): Every new IP allocates a new map entry. Within minutes, heap allocation explodes, triggering aggressive GC thrashing followed by an Out-Of-Memory (OOM) crash.
  • Redis Clusters: Millions of ephemeral keys bloat the cache until Redis either evicts business-critical cache entries or crashes under memory exhaustion.

The attacker doesn't need to take down the application; they turn the rate limiter against itself.

Incoming Attack: 1,000,000 Distinct IPs
               │
               ▼
┌─────────────────────────────────────────┐
│ Traditional Sharded Map / Redis Limiter │
│ ├── Stored Keys: 1,000,000              │
│ ├── Memory: 250 MB ──► 1 GB ──► 2 GB... │──► [ Process OOM-Killed! ]
└─────────────────────────────────────────┘
Enter fullscreen mode Exit fullscreen mode

The engineering goal is not claiming to magically block a never-before-seen IP on request #1. The goal is surviving the rotation in strictly fixed memory while enforcing limits on every non-rotating client, without relying on external databases.

This is the exact purpose of SketchProxy.

Enter SketchProxy: Fixed-Memory Edge Defense

SketchProxy is an edge reverse proxy built on Go's standard library (net/http, httputil.ReverseProxy).

Instead of synchronizing state with an external cache cluster, each proxy instance maintains dedicated in-memory epochsketch tables.

Because an EpochSketch bucket table is allocated once at startup (e.g., 65,536 buckets) and never resizes, its memory consumption is flat and immutable. Whether the proxy processes 100 requests or 10 million distinct IP addresses, its memory footprint remains unchanged.

Fixed-Memory Edge Defense Architecture

The Multi-Layer Request Pipeline

Every incoming request passes through an outermost-first defense pipeline. Any stage that makes an early decision short-circuits the pipeline and never touches the upstream backend:

SketchProxy Request Lifecycle

Each stage is powered by its own dedicated, isolated sketch:

1. Rate Limiting + The Tarpit Slow Lane

Traditional limiters force a binary choice: either 200 OK or an immediate 429 drop. SketchProxy introduces a two-tier volume band:

  • RateLimit.Threshold: The drop line. Requests with estimate >= Threshold receive an immediate 429.
  • Tarpit.Threshold: A lower threshold defining a "suspicious volume" band. Matching requests are delayed with a configurable time.Sleep before forwarding.

Rate Limiting & Tarpit Slow Lane

Tarpitting forces brute-force scrapers to consume their own connection pools and slow down without breaking borderline legitimate users.

Defending Against Self-Inflicted DoS:

Sleeping goroutines hold open connections. If an attacker floods the tarpit band, a naive proxy would exhaust OS file descriptors.

SketchProxy prevents this via Tarpit.MaxConcurrent: once in-flight sleeps hit capacity, further tarpit-eligible requests skip the delay and forward immediately. Defensive delays never sacrifice proxy availability.

2. Wallet Defense: Neutralizing Proxy-Hopping Bots

Real-world attacks are rarely 100% rotating across every dimension. A scraper might rotate residential IPs, but it often reuses the same API token or session credential.

Wallet Defense tracks frequency keyed on the HTTP Authorization header rather than IP address:

$$\text{Key} = \text{sha256}(\text{Authorization Header})$$

Wallet Defense: Stopping Rotating IP Botnets

Extracting this key takes just ~22 ns with 0 heap allocations. Even if a bot rotates across 50,000 IPs, all requests sharing that credential collide in the same token slot and get throttled.

3. First-Sightings as an Anomaly Detection Signal

A flood of brand-new, rotating keys is itself an attack signature.

Because EpochSketch indicates whether an observation was a first-sighting (first == true), SketchProxy gets anomaly detection for free:

  • When rate limiting observes a new key, it can trigger an asynchronous JSON webhook (first_sighting).
  • Zero extra lookups: Reuses the rate-limiting Observe call directly.
  • Zero blocking: Webhook dispatches are capped by Anomaly.MaxConcurrent. If the queue is full, notifications drop silently rather than delaying the HTTP request.

4. Agentic Loop Breakers: Outcome-Based Defense

With the rise of autonomous AI agents, backend services frequently encounter Runaway Agentic Retry Loops.

When an upstream backend returns a transient error (500 or 503), a poorly configured AI agent often retries in a tight loop, firing hundreds of requests per minute and preventing the backend from recovering.

The Agentic Loop Breaker gates on response outcomes, not request volume:

  • A dedicated sketch observes only 5xx responses per caller+path.
  • If a caller crosses the 5xx threshold within an epoch window, subsequent requests from that specific caller+path are blocked with an immediate 503, shielding the backend.
  • The block automatically expires after one TickDuration once errors cease.

Proving Fixed Memory: The "Cardinality Bomb" Demo

To verify that SketchProxy's fixed-memory guarantee holds under real attack conditions, the repository includes cardinalitybomb — a reproducible benchmark stack:

cd ecosystem/cardinalitybomb
docker compose up --build
open http://localhost:9200
Enter fullscreen mode Exit fullscreen mode

This stack launches five containers:

  1. An origin backend stub.
  2. SketchProxy (backed by EpochSketch).
  3. A Naive Baseline rate limiter (a competent 256-shard mutex-protected map).
  4. An attack generator firing escalating-cardinality requests at both proxies identically.
  5. A live dashboard charting real-time memory and latency.

The Result:

  • SketchProxy's memory remains completely flat — holding steady at a few tens of megabytes regardless of how many millions of unique keys are generated.
  • The baseline map climbs continuously as each new IP adds a map entry.
  • Within 60 seconds, the baseline container is OOM-killed by the Docker runtime, while SketchProxy continues answering traffic without interruption.

Memory Usage Under Escalating Cardinality Chart

Operational Simplicity & Performance

SketchProxy is designed for minimal operational footprint:

1. Instant Startup

Protect a backend running on port 5000:

go run ./cmd/sketchproxy -listen :8080 -target http://localhost:5000
Enter fullscreen mode Exit fullscreen mode

2. Microsecond Key Extraction

Benchmarked on an Apple M4 Pro:

  • Request IP+Path extraction: ~14 ns / 0 allocs.
  • Authorization key extraction: ~22 ns / 0 allocs.

3. Zero-Dependency Prometheus Metrics

Exposes hand-rolled Prometheus metrics at /metrics without pulling in large external telemetry dependencies:

  • Eviction rates (CASRetriesExhausted, Chips, Evictions)
  • Tarpit concurrency gauges (sketchproxy_tarpit_active)
  • Loop breaker trip states

What About Cloudflare or Akamai? (Where Does This Fit?)

An obvious architectural question is: “Why not simply put Cloudflare WAF or Akamai in front of the API?”

Cloudflare and Akamai operate at the public Anycast edge, providing indispensable L3/L4 volumetric DDoS mitigation, bot challenges (Turnstile), and global CDN caching. SketchProxy does not replace edge CDNs; it solves problems they cannot address:

  1. Internal Microservices & East-West Traffic: Cloudflare only protects public North-South ingress. It cannot protect internal service-to-service communication, private VPC endpoints, or Kubernetes ingress where internal client bugs or cascading retries threaten downstream databases.
  2. Application-Aware Logic (Wallet Defense & Loop Breakers): Throttling by hashing Authorization headers across rotating IPs or tripping circuit breakers on 5xx error outcomes requires deep application context. Doing this on enterprise CDN tiers requires costly custom edge worker scripting or enterprise plans ($1,000s/mo).
  3. Data Privacy & Air-Gapped Environments: Regulated industries (healthcare, finance, defense) often cannot route sensitive customer payloads or authentication tokens through third-party CDN decryption.
  4. Prompt Caching for LLM Gateways: SketchProxy embeds semantic prompt caching with TinyLFU admission filtering directly adjacent to local model inference runtimes (like vLLM or Ollama), serving hits in microseconds.

In production, combining Cloudflare at the outer perimeter for volumetric protection with SketchProxy at origin or ingress for fixed-memory, application-aware defense provides defense-in-depth.

Summary

Moving frequency tracking directly to the proxy edge with fixed-memory sketches fundamentally shifts defensive architecture:

  • Zero External Storage: Eliminates external cache clusters, network hops, and connection pools for rate limiting.
  • Immune to Cardinality Attacks: Memory is strictly bounded at startup; scrapers cannot trigger OOM crashes.
  • Multi-Vector Protection: Combines Rate Limiting, Tarpitting, Wallet Defense, and Agentic Loop Breaking in a single nanosecond pipeline.

📦 Inspect the Code & Run the Demo:

Top comments (0)