19. Machine Coding Case Study 3: Rate Limiter (Token Bucket, Leaky Bucket, Sliding Window) • Low-Level Design (LLD) & Object-Oriented Machine Coding • Rishabh Ki Kaksha

1. **Token Bucket (AWS / Stripe Standard 👑):** Tokens fixed rate par bucket me refill hote hain; burst traffic allow karta hai.
2. **Leaky Bucket:** Constant rate par requests process karta hai (Smooth output stream).
3. **Fixed Window Counter:** Simple reset at time boundary (Vulnerable to 2x burst at window edge!).
4. **Sliding Window Log:** Exact timestamps track karta hai (Accurate but memory heavy).

---

### 2. Thread-Safe Token Bucket Implementation

```typescript
class TokenBucketRateLimiter {
    private tokens: number;
    private lastRefillTimestamp: number;

constructor(
        private readonly capacity: number,       // Max burst tokens (e.g. 10)
        private readonly refillRatePerSecond: number // Refill tokens/sec (e.g. 2)
    ) {
        this.tokens = capacity;
        this.lastRefillTimestamp = Date.now();
    }

public synchronizedTryAcquire(): boolean {
        this.refill();

if (this.tokens >= 1) {
            this.tokens -= 1;
            return true; // ⚡ Request Allowed!
        }
        return false; // 🚫 Rate Limit Exceeded (429 Too Many Requests)!
    }

private refill() {
        const now = Date.now();
        const elapsedTime = (now - this.lastRefillTimestamp) / 1000;
        const newTokens = elapsedTime * this.refillRatePerSecond;

if (newTokens > 0) {
            this.tokens = Math.min(this.capacity, this.tokens + newTokens);
            this.lastRefillTimestamp = now;
        }
    }
}
```

---

### 3. Master Comparison Matrix

| Algorithm | Burst Traffic Support | Memory Consumption | Accuracy |
| :--- | :--- | :--- | :--- |
| **Token Bucket** | ✅ **Yes (Up to capacity)** | ⚡ **$O(1)$ (Tokens + Timestamp)** | High |
| **Leaky Bucket** | ❌ No (Strict smooth rate) | $O(1)$ | High |
| **Fixed Window** | ❌ No | $O(1)$ | ⚠️ Edge-burst flaw |
| **Sliding Window Log**| ✅ Yes | 💥 $O(\text{Requests})$ | 100% Exact |

---

### 4. Interview Ke 3 Sawal Is Topic Se

1. **Distributed environment me Rate Limiter race conditions se kaise bachega?** -> Redis Lua Scripting use karke token checking aur decrement ko atomic single transaction banana.
2. **Rate limited user ko kaunse HTTP headers return karne chahiye?** -> `X-RateLimit-Limit`, `X-RateLimit-Remaining`, aur `Retry-After: <seconds>`.
3. **Sliding Window Counter algorithm Sliding Window Log se kam memory kyu leti hai?** -> Current window aur previous window ke counts ka weighted percentage calculate karti hai bina individual timestamps store kiye.

---
**Next Topic:** 20. Machine Coding Case Study 4: Splitwise / Expense Sharing App with Graph Simplification

Loading lesson content...

Python 3.12

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track