Phase 4 · Chapter 2

Rate Limiting

Every algorithm, from scratch, with the race conditions most engineers never see

What this chapter does to you: Rate limiting looks simple until you implement it seriously. Then it becomes a distributed systems problem with race conditions, clock skew, and burst attacks. After this chapter, you will be able to implement any rate limiting algorithm correctly in Redis — not by using a library, but by deriving each algorithm from first principles and knowing exactly where each one breaks.

Part 1: Why Rate Limiting Exists

Your AttemptIQ API has no rate limiting. What can go wrong?

Scenario 1 — Accidental abuse: A student writes a script to auto-submit test answers. It fires 2,000 requests in 10 seconds. Your Node.js event loop gets saturated. Other students' requests queue up. Site crawls for everyone.

Scenario 2 — Deliberate attack: Someone runs a credential stuffing attack — trying thousands of username/password combinations against your login endpoint. No rate limit = unlimited attempts.

Scenario 3 — Downstream protection: Your API calls an external SMS provider for OTP. No rate limit on your /send-otp endpoint = a single user can trigger 10,000 SMS messages at ₹0.15 each = ₹1,500 bill before you notice.

Scenario 4 — Fair usage: Your free-tier users hammering the API starve your paying users.

Rate limiting is not just about attacks. It's about protecting your system from any traffic pattern that exceeds what you've designed for — malicious or not. Every production API needs it.

Part 2: Fixed Window Counter — The Naive Approach

How It Works

Divide time into fixed windows. Count requests per user per window. If count exceeds limit, reject.

Window size: 1 minute
Limit: 100 requests per minute

user:123, minute 12:00 → counter: 1, 2, 3... 100 → 101st request: REJECT
user:123, minute 12:01 → counter resets to 0 → new window, new budget

Redis implementation:

async function fixedWindowRateLimit(userId, limit, windowSeconds) {
  const now = Math.floor(Date.now() / 1000)
  const windowStart = Math.floor(now / windowSeconds) * windowSeconds
  const key = `ratelimit:${userId}:${windowStart}`

  const count = await redis.incr(key)       // atomic increment, returns new value

  if (count === 1) {
    // First request in this window — set expiry
    await redis.expire(key, windowSeconds)
  }

  if (count > limit) {
    return { allowed: false, remaining: 0 }
  }

  return { allowed: true, remaining: limit - count }
}

Why INCR and not GET + compare + SET? Because INCR is atomic. It reads, increments, and writes in a single operation. No other command can run between those steps. This is the first lesson of Redis rate limiting: always use atomic operations.

The GET + SET approach has a race condition:

The Critical Flaw: Boundary Attack

Fixed window has a fundamental weakness. With a limit of 100 requests/minute:

Timeline:  ─────────────────────│─────────────────────
                  Minute 1      │      Minute 2
                            12:00:59    12:01:01

User sends: 100 requests at 12:00:59 (last second of minute 1) → all allowed
            100 requests at 12:01:01 (first second of minute 2) → all allowed

Result: 200 requests in 2 seconds. Both windows are technically valid.
        Your system just absorbed 200 requests/2 seconds = 100 RPS for 2 seconds.

If your system can only handle 100 requests/minute smoothly, it just got 200 in 2 seconds. This boundary attack is a real vulnerability.

When to use Fixed Window: Background jobs, non-critical rate limiting, situations where boundary attacks don't matter. Simple, O(1) memory, O(1) time. If you need something quick and good enough — this is it.

Part 3: Sliding Window Log — The Accurate Approach

How It Works

Instead of counting per window, log the timestamp of every request. On each new request, look back exactly windowSize seconds and count how many requests exist in that window.

Window: 60 seconds, limit: 100 requests

At 12:01:30, user makes a request.
Look back to 12:00:30.
Count all logged timestamps in that range.
If count < 100: allow, log this timestamp.
If count >= 100: reject.

Redis implementation using Sorted Sets:

async function slidingWindowLog(userId, limit, windowMs) {
  const now = Date.now()
  const windowStart = now - windowMs
  const key = `ratelimit:sliding:${userId}`

  // Pipeline: multiple commands sent together, one round-trip
  const pipeline = redis.pipeline()
  pipeline.zremrangebyscore(key, 0, windowStart)    // remove old entries
  pipeline.zadd(key, now, `${now}-${Math.random()}`) // add this request
  pipeline.zcard(key)                                // count requests in window
  pipeline.expire(key, Math.ceil(windowMs / 1000))   // auto-cleanup

  const results = await pipeline.exec()
  const count = results[2][1]   // result of ZCARD

  if (count > limit) {
    // Undo the add — we rejected this request
    await redis.zrem(key, `${now}-${Math.random()}`)
    return { allowed: false, remaining: 0 }
  }

  return { allowed: true, remaining: limit - count }
}

We use a Sorted Set with the timestamp as score. ZREMRANGEBYSCORE key 0 windowStart removes all entries older than the window. ZCARD key counts remaining entries — exactly the request count in the window.

No boundary attack. At 12:01:30, the window is 12:00:30 → 12:01:30. Always exactly 60 seconds. A user sending 100 at 12:00:59 and 100 at 12:01:01 would have the 12:00:59 batch in-window at 12:01:01 — correctly counted.

The Cost

Memory: Every request stores a timestamp in the sorted set. 100 requests/minute × 10,000 users = 1 million sorted set entries. Each entry ≈ 20–40 bytes → ~40MB just for rate limit logs. At higher request rates or more users, this grows proportionally.

Time: O(log N) per request (sorted set operations are O(log N)).

When to use Sliding Window Log: When you need perfect accuracy and have a small number of high-value clients (API keys, not end users). Not for consumer-scale rate limiting with millions of users.

Part 4: Sliding Window Counter — The Practical Hybrid

The Insight

Fixed window is O(1) but has the boundary flaw. Sliding window log is accurate but memory-expensive.

Can we get accuracy with O(1) memory?

Almost. With approximation.

The observation: The boundary attack works because we have zero visibility into the previous window's distribution. But we don't need perfect distribution — we just need a good estimate.

The algorithm:

Keep two counters: current window and previous window. Use a weighted average based on how far into the current window we are.

Window: 1 minute, limit: 100
Current time: 12:01:45 (45 seconds into minute 12:01)

previous_window_count = 80  (requests in minute 12:00)
current_window_count  = 30  (requests so far in minute 12:01)

Elapsed in current window: 45/60 = 0.75
Time remaining from previous window: 1 - 0.75 = 0.25

Weighted estimate = current_count + previous_count × (1 - elapsed_ratio)
                  = 30 + 80 × 0.25
                  = 30 + 20
                  = 50 requests in the virtual sliding window

The intuition: if 80 requests happened in the previous minute, roughly 25% of them (the last 15 seconds' worth) would still be "in window" if we used a true sliding window. We approximate this as previous_count × (1 - elapsed).

Redis implementation:

async function slidingWindowCounter(userId, limit, windowSeconds) {
  const now = Date.now() / 1000
  const currentWindowStart = Math.floor(now / windowSeconds) * windowSeconds
  const prevWindowStart = currentWindowStart - windowSeconds

  const currentKey = `ratelimit:${userId}:${currentWindowStart}`
  const prevKey = `ratelimit:${userId}:${prevWindowStart}`

  const [currentCount, prevCount] = await redis.mget(currentKey, prevKey)

  const elapsed = (now - currentWindowStart) / windowSeconds   // 0.0 to 1.0
  const estimate = (parseInt(currentCount) || 0)
                 + (parseInt(prevCount) || 0) * (1 - elapsed)

  if (estimate >= limit) {
    return { allowed: false, remaining: 0 }
  }

  // Allow — increment current window
  const pipeline = redis.pipeline()
  pipeline.incr(currentKey)
  pipeline.expire(currentKey, windowSeconds * 2)   // keep for 2 windows
  await pipeline.exec()

  return { allowed: true, remaining: Math.floor(limit - estimate - 1) }
}

Accuracy: Studies at Cloudflare show this algorithm has < 0.003% error rate compared to a true sliding window. For rate limiting purposes: essentially perfect.

Memory: O(1) — two Redis keys per user regardless of request volume. Time: O(1) — two GETs, one INCR.

This is what Cloudflare and most production systems use. O(1) memory, O(1) time, near-perfect accuracy. The approximation error is irrelevant in practice.

Part 5: Token Bucket — The Industry Standard

The Intuition

Imagine a bucket that holds tokens.

• The bucket has a maximum capacity (burst limit)
• Tokens are added at a fixed rate (refill rate)
• Each request consumes one token
• If no tokens available: request is rejected
• If bucket is full and more tokens added: overflow, tokens are discarded

Capacity: 10 tokens (burst of 10 allowed)
Refill rate: 2 tokens/second

t=0:  bucket = 10 (full)
t=0:  5 requests arrive → bucket = 5
t=1:  2 tokens added → bucket = 7
t=1:  8 requests arrive → 7 allowed, 1 rejected
t=2:  2 tokens added → bucket = 2 (was 0, +2)

The key property: A user can burst up to the bucket capacity instantly, then sustains at the refill rate. This is realistic — real users have natural bursts (opening a page loads 10 resources at once) but sustained load should be limited.

Fixed window and sliding window treat a burst and a sustained load identically. Token bucket handles bursts gracefully while still limiting sustained throughput.

Redis Implementation

The trick: you don't need a background process refilling tokens. You store the last refill time and calculate how many tokens to add on each request.

async function tokenBucket(userId, capacity, refillRate) {
  // refillRate = tokens per second
  const key = `ratelimit:token:${userId}`
  const now = Date.now() / 1000

  // Use a Lua script for atomicity — more on this below
  const luaScript = `
    local key = KEYS[1]
    local capacity = tonumber(ARGV[1])
    local refill_rate = tonumber(ARGV[2])
    local now = tonumber(ARGV[3])

    local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
    local tokens = tonumber(bucket[1]) or capacity
    local last_refill = tonumber(bucket[2]) or now

    -- Calculate tokens to add since last refill
    local elapsed = now - last_refill
    local new_tokens = math.min(capacity, tokens + elapsed * refill_rate)

    if new_tokens < 1 then
      -- Not enough tokens
      redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill', now)
      redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) + 1)
      return 0   -- rejected
    end

    -- Consume one token
    redis.call('HMSET', key, 'tokens', new_tokens - 1, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) + 1)
    return 1   -- allowed
  `

  const result = await redis.eval(luaScript, 1, key, capacity, refillRate, now)
  return { allowed: result === 1 }
}

Why Lua? This algorithm requires multiple Redis commands that must be atomic: read current state → calculate → write new state. If two requests run this concurrently between the read and write, both see the same token count and both consume the same token. Race condition.

Lua scripts in Redis run atomically — the entire script executes as a single operation. No other Redis command runs while your Lua script is executing. This is the correct tool when you need atomic multi-step Redis operations.

When to use Token Bucket:

• APIs where burst is acceptable (loading a page = 10 simultaneous requests)
• Scenarios where you want to define both burst capacity and sustained rate separately
• Most API rate limiting — it's the most natural model for real user behavior

Before going further, race them. One stream of requests, three limiters: predict who lets the burst through, and who falls for the boundary attack.

Part 6: Leaky Bucket — Smoothing Outbound Traffic

The Intuition

Token bucket allows bursting. What if you need perfectly smooth output?

Leaky bucket: requests enter a queue (the bucket). They're processed at a fixed rate (the leak). If the queue is full, new requests are dropped.

Leak rate: 10 requests/second
Queue capacity: 50

Users can burst up to 50 requests into the queue.
But they exit the queue at exactly 10/second — perfectly smooth.

Where It's Used

Leaky bucket is not commonly used for inbound API rate limiting (you want to accept bursts, not queue them). It's used for outbound rate limiting — controlling the rate at which you call external services.

// You're calling an SMS provider limited to 10 requests/second
// BullMQ + limiter option IS a leaky bucket implementation

const queue = new Queue('sms')
const worker = new Worker('sms', async job => {
  await smsProvider.send(job.data)
}, {
  limiter: {
    max: 10,          // process at most 10 jobs
    duration: 1000    // per 1000ms
  }
})

BullMQ's limiter option implements a leaky bucket. Jobs queue up, processed at a fixed rate. Your SMS provider never sees more than 10 RPS regardless of how many jobs enter the queue.

When to use Leaky Bucket:

• Calling external APIs with strict rate limits (SMS, payment, email providers)
• Anywhere you need perfectly smooth output, not just average-limited output

Part 7: Distributed Rate Limiting — Where It Gets Hard

The Problem

You're running 4 Node.js instances behind a load balancer. User:123 is allowed 100 requests/minute.

If each Node.js instance has its own in-memory counter:

Instance 1: user:123 → 25 requests
Instance 2: user:123 → 30 requests
Instance 3: user:123 → 25 requests
Instance 4: user:123 → 20 requests
Total:                  100 requests → at limit

But each instance sees only 25-30 requests and allows all of them. The user actually sent 100 requests — exactly at limit. So far, fine.

Instance 1: user:123 → 30 requests → thinks: 30/100, allow
Instance 2: user:123 → 30 requests → thinks: 30/100, allow
Instance 3: user:123 → 30 requests → thinks: 30/100, allow
Instance 4: user:123 → 30 requests → thinks: 30/100, allow
Total:                  120 requests → over limit, but no instance knows

In-memory rate limiting doesn't work with multiple instances. The counter must be shared. Redis is the shared state.

The Race Condition in Naive Redis Implementation

Now that we're using Redis, the obvious approach:

// WRONG — has a race condition
async function naiveRateLimit(userId, limit) {
  const key = `ratelimit:${userId}`
  const count = parseInt(await redis.get(key)) || 0    // Step 1: read

  if (count >= limit) return { allowed: false }        // Step 2: check

  await redis.set(key, count + 1, 'EX', 60)            // Step 3: write
  return { allowed: true }
}

Race condition:

Two requests both got through at the limit. The user sent 101 requests but both 100th and 101st were allowed because both instances read 99 before either wrote.

Fix: Use INCR

// CORRECT — INCR is atomic
async function correctRateLimit(userId, limit, windowSeconds) {
  const window = Math.floor(Date.now() / 1000 / windowSeconds)
  const key = `ratelimit:${userId}:${window}`

  const count = await redis.incr(key)        // atomic: read + increment + write

  if (count === 1) {
    await redis.expire(key, windowSeconds)   // set TTL on first request
  }

  return { allowed: count <= limit, count }
}

INCR is a single atomic command. It reads the current value, adds 1, stores it, and returns the new value — in one indivisible operation. No race condition possible.

But wait — there's still a subtle issue.

The INCR + EXPIRE race condition:

Request A: INCR → returns 1 (first request in window)
                                    ← server crashes here
                                    ← EXPIRE never runs
                                    ← key lives forever

If the server crashes or the connection drops between INCR and EXPIRE, the key never gets an expiry and stays forever. Rate limit key accumulates even after the window closes.

Fix: Use SET with NX and EX in one command, or use a pipeline:

async function robustRateLimit(userId, limit, windowSeconds) {
  const window = Math.floor(Date.now() / 1000 / windowSeconds)
  const key = `ratelimit:${userId}:${window}`

  // Single atomic command: SET key 0 NX EX windowSeconds
  // NX = only if not exists. Sets initial value with TTL in one command.
  await redis.set(key, 0, 'NX', 'EX', windowSeconds)

  // Now increment — key definitely has TTL set
  const count = await redis.incr(key)

  return { allowed: count <= limit, remaining: Math.max(0, limit - count) }
}

SET key 0 NX EX seconds atomically creates the key with TTL only if it doesn't exist. INCR then atomically increments. Two commands, but neither has the race condition that matters — the key always has its TTL.

Lua for True Atomicity

For token bucket and any multi-step algorithm, Lua scripts are the right tool.

// Check-and-increment as a single atomic unit
const script = `
  local current = redis.call('GET', KEYS[1])
  if current and tonumber(current) >= tonumber(ARGV[1]) then
    return 0   -- over limit
  end
  local new_val = redis.call('INCR', KEYS[1])
  if new_val == 1 then
    redis.call('EXPIRE', KEYS[1], ARGV[2])
  end
  return 1   -- allowed
`
const allowed = await redis.eval(script, 1, key, limit, windowSeconds)

Redis executes Lua scripts atomically — no other commands run mid-script. This is the guarantee that makes complex multi-step algorithms correct.

Part 8: Where to Put the Rate Limiter

Rate limiting can sit at multiple layers. Each has different tradeoffs.

Layer 1: Nginx / API Gateway (Before Your App)

limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;

location /api/ {
  limit_req zone=api burst=20 nodelay;
  proxy_pass http://localhost:3000;
}

Advantage: Requests are rejected before they reach Node.js. Zero cost to your application. Protects against pure traffic floods.

Disadvantage: IP-based only. One IP can be many users (shared NAT, university network). Can't do user-ID-based limits at this layer.

Layer 2: Application Middleware (Your Node.js Code)

app.use('/api/', rateLimitMiddleware)

async function rateLimitMiddleware(req, res, next) {
  const userId = req.user?.id || req.ip
  const { allowed, remaining } = await tokenBucket(userId, 100, 10)

  res.setHeader('X-RateLimit-Remaining', remaining)

  if (!allowed) {
    return res.status(429).json({
      error: 'Too many requests',
      retryAfter: 60
    })
  }
  next()
}

Advantage: Full access to user identity, endpoint-specific limits, custom responses with Retry-After headers.

Disadvantage: Request reaches your Node.js app before being rejected. Under extreme flood, your app still does JWT parsing, middleware chain, etc.

Layer 3: Endpoint-Specific Limits

Different endpoints need different limits:

// Login: 5 attempts per 15 minutes (brute force protection)
app.post('/login', rateLimit({ max: 5, window: 900 }), loginHandler)

// OTP send: 3 per hour (SMS cost protection)
app.post('/send-otp', rateLimit({ max: 3, window: 3600 }), otpHandler)

// API reads: 1000 per minute (normal usage)
app.get('/api/*', rateLimit({ max: 1000, window: 60 }), apiHandler)

The right architecture: Nginx handles flood protection (IP-level, high volume), application middleware handles user-level limits (identity-aware, business logic).

Part 9: The Response — Telling Clients What Happened

When you reject a request, the response matters. Standard headers:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1705312800       ← Unix timestamp when limit resets
Retry-After: 47                     ← seconds until they can retry
Content-Type: application/json

{
  "error": "rate_limit_exceeded",
  "message": "Too many requests. Try again in 47 seconds.",
  "retryAfter": 47
}

Retry-After is the most important header. Without it, clients don't know when to retry — they either poll aggressively (making your problem worse) or give up. A good client reads Retry-After and waits exactly that long.

Status code: 429 Too Many Requests — not 400, not 503. 429 is the specific HTTP status for rate limiting. Clients can handle it programmatically.

Part 10: Algorithm Comparison

Algorithm            | Memory      | Accuracy    | Burst handling | Use when
─────────────────────┼─────────────┼─────────────┼────────────────┼──────────────────────────
Fixed Window         | O(1)        | Low*        | Hard cutoff    | Simple needs, low risk
Sliding Window Log   | O(requests) | Perfect     | Hard cutoff    | Small # high-value clients
Sliding Window Ctr   | O(1)        | ~Perfect    | Hard cutoff    | Consumer APIs at scale
Token Bucket         | O(1)        | Perfect     | Configurable   | Most API rate limiting
Leaky Bucket         | O(queue)    | Perfect     | Smoothed       | Outbound to 3rd-party APIs

* Fixed window vulnerable to boundary attack (2× burst at window edges)

The decision tree:

Part 11: The Vocabulary Map

Part 12: Practice Problems

Problem 1 (The Boundary Attack): Your API allows 60 requests per minute using fixed window. A user sends 60 requests at 11:59:55pm and 60 requests at 12:00:05am.

Draw the timeline. How many requests actually go through? What does a sliding window counter return for the same traffic pattern? Show the weighted calculation.

Problem 2 (Algorithm Choice): For each of these AttemptIQ endpoints, name the rate limiting algorithm, the limit, the window, and explain why:

a) POST /login — brute force protection b) POST /test/:id/submit — prevent double submission c) GET /api/tests — fair usage for free tier (100 req/day) vs pro tier (10,000 req/day) d) POST /send-otp — protect SMS cost e) Internal job: notifyUserOfResults() which calls an email API

Problem 3 (Race Condition): A colleague writes this rate limiter:

async function rateLimit(userId, limit) {
  const key = `rl:${userId}`
  const count = parseInt(await redis.get(key) || '0')
  if (count >= limit) return false
  await redis.setex(key, 60, count + 1)
  return true
}

Identify every race condition and correctness bug in this code. There are at least three. Rewrite it correctly.

Problem 4 (Production Design): AttemptIQ launches a new feature: live competitive quizzes. During a quiz, 5,000 students each send one answer per question, with 10 questions in 5 minutes. That's 50,000 requests in 5 minutes = ~167 req/second peak.

Your single Redis instance handles 100,000 ops/second. Seems fine.

But you also have rate limiting running on every request. Each rate limit check does 2 Redis commands. 167 req/sec × 2 = 334 Redis ops/sec — still fine.

Now you add: leaderboard update (1 ZADD), session check (1 GET), analytics event (1 LPUSH). That's 5 Redis ops per request × 167/sec = 835 ops/sec.

Still under 100,000. Why might you still have a problem? What is the real bottleneck that ops/second alone doesn't capture?

Problem 5 (Go Deeper — Connect to Previous Chapters): You've implemented token bucket rate limiting using a Lua script in Redis. Redis is single-threaded.

When 10,000 concurrent requests hit your API simultaneously:

1. Each request goes to Node.js (event loop — Chapter 1)
2. Each Node.js handler runs redis.eval(luaScript, ...) (async, non-blocking)
3. Redis processes each Lua script atomically (single-threaded — this chapter)

Trace this full flow. Where is actual parallelism happening? Where is concurrency without parallelism happening? Where is neither — pure serial execution?

Use the exact vocabulary from Chapter 1 (event loop, libuv, epoll, blocking, non-blocking) and this chapter (atomic, single-threaded, Lua) to give a complete answer.

What's Coming in Chapter 3 of Phase 4

Rate Limiting done. You now have the tools to protect any API at any scale.

Chapter 3 is Authentication Internals — the layer that most engineers implement by copying an example without understanding what's actually happening.

We'll go byte-by-byte through a JWT, understand why HS256 vs RS256 is an architectural decision not a checkbox, see exactly what gets stolen in a credential attack, and understand why httpOnly cookies beat localStorage for tokens — not as a rule to follow but as a consequence of how browsers work.

After Chapter 3, when someone says "our auth is broken," you will know exactly which layer to look at and why.

End of Phase 4, Chapter 2. Estimated reading time: 70-85 minutes. Practice problems: 60-90 minutes. Do not proceed to Chapter 3 until you can answer Problem 3 — finding all three bugs and rewriting correctly. Correctness under concurrency is the single most important skill in distributed backend engineering.