# 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!)
    

```mermaid
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
    

```mermaid
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

```jsx
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

```jsx
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

```mermaid
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

| Feature | Database Counters | HLL+CMS Approach |
| --- | --- | --- |
| Memory Usage | O(n) | O(1) |
| Distributed Sync | Complex | [CRDT-friendly](https://tech.sedhu.me/conflict-free-replicated-data-types-crdts) |
| Error Margin | 0% | 1-2% |
| Throughput | 10k RPS | 1M+ RPS |

### 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](https://redis.io/docs/latest/develop/data-types/probabilistic/)