Rate limiting - A Probabilistic Approach

The Simple Explanation

Imagine you're managing a very popular restaurant. You need to know two things:

• How many different people visited today?

• How many times did each person order food?

There two clever tools: HyperLogLog (HLL) and Count-Min Sketch.

HyperLogLog (HLL) - The Unique Visitor Counter

Think of HLL like a magical guest book that:

• Only needs a tiny amount of space (1.5KB)

• Can estimate millions of unique visitors

• Might be off by 2% (which is totally fine!)

graph TD
    A["Visitors"] --> B["Magic Guest Book (HLL)"]
    B --> C["Approximate Count"]
    style B fill:#f9f,stroke:#333

Count-Min Sketch - The Smart Traffic Counter

This is like having multiple security cameras counting how often each person comes in:

• Each camera counts a bit differently

• By combining all cameras' counts, we get a good estimate

• Catches people who are visiting too frequently

graph LR
    A["Requests"] --> B["Multiple Counters"]
    B --> C["Counter 1"]
    B --> D["Counter 2"]
    B --> E["Counter 3"]
    C & D & E --> F["Final Count"]

The Technical Deep-Dive

Now let's look under the hood at how these systems actually work.

HyperLogLog Implementation

class HyperLogLog {
    constructor(precision = 14) {
        this.precision = precision;
        this.m = 1 << precision; // Number of registers
        this.registers = new Array(this.m).fill(0);
    }

    add(element) {
        const hash = this.hashFunction(element);
        const bucket = hash & (this.m - 1); // Determine register
        const w = hash >>> this.precision;
        this.registers[bucket] = Math.max(
            this.registers[bucket],
            this.leadingZeros(w) + 1
        );
    }

    estimate() {
        // Harmonic mean calculation for cardinality estimation
        const harmonicMean = this.registers.reduce((sum, val) => 
            sum + Math.pow(2, -val), 0);
        return (this.m * this.m) / harmonicMean;
    }
}

Count-Min Sketch Technical Details

class CountMinSketch {
    constructor(width, depth) {
        this.width = width;
        this.depth = depth;
        this.table = Array.from(
            { length: depth },
            () => new Array(width).fill(0)
        );
        this.hashFunctions = this.generateHashFunctions();
    }

    add(item, count = 1) {
        this.hashFunctions.forEach((hashFunc, i) => {
            const j = hashFunc(item) % this.width;
            this.table[i][j] += count;
        });
    }

    estimate(item) {
        return Math.min(
            ...this.hashFunctions.map((hashFunc, i) => 
                this.table[i][hashFunc(item) % this.width]
            )
        );
    }
}

Real-World Implementation at Scale

graph TD
    A["Incoming Request"] --> B["Edge Node"]
    B --> C["HLL Counter"]
    B --> D["Count-Min Sketch"]
    C & D --> E["Redis Cluster"]
    E --> F["Rate Limit Decision"]
    style B fill:#96f,stroke:#333
    style E fill:#f96,stroke:#333

Key Technical Considerations

• Memory Efficiency: Both algorithms use constant memory regardless of traffic volume

• Error Bounds: HLL provides ±2% error rate, Count-Min Sketch error is configurable

• Distributed System: Uses Redis CRDTs for counter synchronization across edge nodes

• Performance: O(1) time complexity for both updates and queries

By combining these probabilistic data structures, we can efficiently track and limit millions of requests per second, all while maintaining minimal memory usage and providing accurate rate limiting capabilities.

Real-World Use Cases

API Management: An API processing 10M requests per day uses CMS to identify abusive clients without tracking individual IPs.
E-commerce: HLL prevents coupon abuse by estimating unique users during flash sales.
Cybersecurity: The combination of both algorithms detects DDoS attacks with minimal memory overhead.

Comparison: Traditional vs. Probabilistic Approach

When To Avoid This Approach

• Banking transaction systems requiring exact counts

• Legal compliance scenarios needing 100% accuracy

• Systems with burst-spike allowances

References:

https://redis.io/docs/latest/develop/data-types/probabilistic