1. The problem: why does Instagram need rate limiting?

Every action on Instagram — liking, following, commenting, logging in, searching — is an API call that consumes CPU, database writes and network. Most users do a few hundred of these a day. But Instagram's openness invites people (and programs) who want to do millions:

• Spam and growth bots follow 5,000 accounts an hour hoping for follow-backs, then unfollow them; they mass-like and mass-comment ("🔥 DM us for collab!") to promote scams.
• Credential stuffing: attackers take username/password pairs leaked from other websites and try them against Instagram's login endpoint at thousands of attempts per second.
• Scrapers crawl profiles and posts to harvest personal data.
• Buggy clients: a mobile app release with a retry loop bug can make millions of phones hammer one endpoint simultaneously — an accidental DDoS from your own users.
• Noisy neighbours: one third-party integration or one heavy user consuming a disproportionate share of capacity slows everyone else down.

Without limits, these callers degrade the experience for everybody, inflate the infrastructure bill, and can cascade into outages when a downstream database is overwhelmed. A rate limiter sets a ceiling per caller so that no one can consume more than their fair share.

1.1 Why, in one list

2. Where to rate limit

Limits can be enforced at several layers — and real systems use more than one (defence in depth).

3. What to limit by: the rate-limit key

A rate limiter keeps a counter per key. Choosing the key decides who is being limited.

A request is typically checked against several rules at once, and is rejected if any rule is exceeded:

rules for POST /v1/users/{id}/follow:
  - key: "user:{uid}:all"         limit: 100 req / 1 s     # general API budget
  - key: "user:{uid}:follow"      limit: 200   / 1 h       # anti-spam action limit
  - key: "user:{uid}:follow:day"  limit: 1000  / 24 h
  - key: "device:{did}:follow"    limit: 300   / 1 h       # catches multi-account farms
  - key: "ip:{ip}:follow"         limit: 2000  / 1 h       # generous: shared IPs

4. The algorithms

All rate-limiting algorithms answer one question per request: "given what this key has done recently, allow or reject?" They differ in how they remember "recently", how they treat bursts, and how much memory they need.

4.1 Token bucket

Imagine a bucket that holds at most B tokens (the capacity or burst size). Tokens are added at a constant refill rate R per second, and the bucket never overflows. Each request takes one token (or a cost c for expensive requests). No token → reject.

      refill: R tokens/second  (e.g. 2/s)
                 │
                 ▼
          ┌─────────────┐
          │ ● ● ● ● ●   │   capacity B = 10 tokens
          │ ● ● ● ●     │   current = 9
          └──────┬──────┘
                 │ each request removes 1 token
                 ▼
   request ──▶ token available? ── yes ──▶ ALLOW (tokens -= 1)
                                 └─ no ──▶ REJECT 429

Behaviour: a user who has been idle can burst up to B requests instantly, then is held to R per second on average. Over any interval of length t, at most B + R·t requests can pass.

The clever implementation trick: you don't need a timer adding tokens. Store just two numbers per key — tokens and last_refill_time — and compute the refill lazily on each request:

function allow(key, cost = 1):
    now = current_time_seconds()
    state = store.get(key) or { tokens: B, last: now }
    elapsed = now - state.last
    state.tokens = min(B, state.tokens + elapsed * R)   # lazy refill
    state.last = now
    if state.tokens >= cost:
        state.tokens -= cost
        store.put(key, state)
        return ALLOW
    else:
        store.put(key, state)
        retry_after = (cost - state.tokens) / R          # seconds until enough tokens
        return REJECT(retry_after)

Worked example: B = 10, R = 1 token/s. A user idle for a minute sends 15 requests at once: the first 10 pass, the next 5 get 429 with Retry-After: 1. Two seconds later 2 tokens have refilled, so 2 more requests pass.

Pros: allows natural bursts (opening the app triggers a flurry of calls), O(1) memory (two numbers per key), easy to reason about, supports per-request cost. Cons: two parameters to tune; a full bucket allows a burst that might still hurt a fragile downstream. Used by AWS API Gateway, Stripe, NGINX-like limiters and most cloud APIs.

4.2 Leaky bucket

Picture a bucket with a small hole in the bottom. Requests pour into the bucket (a FIFO queue of capacity B) and leak out at a constant rate R to be processed. If the bucket is full, new requests overflow and are rejected.

   bursty input ──▶ ┌───────────┐
   ▌▌▌  ▌    ▌▌▌▌   │ queue (B) │  ◀── full? → REJECT (overflow)
                    │ ▌▌▌▌▌     │
                    └─────┬─────┘
                          │ constant drain: R requests/second
                          ▼
   smooth output:   ▌ ▌ ▌ ▌ ▌ ▌ ▌ ▌ ▌   ──▶ backend

queue = BoundedQueue(capacity = B)

on_request(req):
    if queue.full(): return REJECT
    queue.push(req)                       # will be processed later

worker loop (runs every 1/R seconds):
    if not queue.empty():
        process(queue.pop())

# "Leaky bucket as a meter" variant (no queue, just a counter):
function allow(key):
    now = time()
    s = store.get(key) or { level: 0, last: now }
    s.level = max(0, s.level - (now - s.last) * R)   # leak since last request
    s.last = now
    if s.level + 1 <= B:
        s.level += 1; store.put(key, s); return ALLOW
    store.put(key, s); return REJECT

Behaviour: output rate is perfectly smooth at R, no matter how bursty the input. The meter variant is mathematically equivalent to a token bucket (level = B − tokens); the queue variant actually delays requests rather than rejecting them.

Pros: protects a downstream that needs a steady rate (e.g. a partner SMS gateway allowing 100 messages/s); O(B) or O(1) memory. Cons: queued requests wait, adding latency; a burst of old requests can starve new ones; not great for interactive APIs where users expect instant answers. Used in traffic shaping (network routers), NGINX's limit_req (leaky-bucket based, with optional burst queueing), and outbound job processing.

4.3 Fixed window counter

Divide time into fixed windows (e.g. each calendar minute: 12:00:00–12:00:59). Keep one counter per key per window. Increment on each request; if it exceeds the limit, reject until the next window starts.

 limit = 5 per minute
   window 12:00                       window 12:01
 |-----------------------------|-----------------------------|
   ✔ ✔ ✔        ✔ ✔  ✖ ✖          ✔ ✔ ✔ ✔ ✔  ✖
   count: 1 2 3   4 5  6 7          1 2 3 4 5  6

function allow(key, limit, window_seconds):
    window_id = floor(now() / window_seconds)
    counter_key = key + ":" + window_id          # e.g. "user:42:follow:28950012"
    count = store.incr(counter_key)              # atomic increment
    if count == 1:
        store.expire(counter_key, window_seconds)
    return count <= limit

The boundary burst problem: with limit 100/minute, a client can send 100 requests at 12:00:59 and another 100 at 12:01:00 — 200 requests in 2 seconds, double the intended rate, because they fall into different windows.

              12:00:00                    12:01:00                    12:02:00
                 |---------- window A ---------|---------- window B ---------|
                                      ▌▌▌▌▌▌▌▌▌|▌▌▌▌▌▌▌▌▌
                                     100 reqs  | 100 reqs
                                      └──── 200 requests within ~2 s ────┘

Pros: trivial, one counter per key, works perfectly with Redis INCR + EXPIRE. Cons: up to 2× bursts at window edges; all clients' windows reset at the same instant, causing synchronised "thundering herd" retries at the top of the minute.

4.4 Sliding window log

Keep a log of timestamps of each accepted request per key (e.g. a Redis sorted set). On each request, delete timestamps older than now − window, count what remains, and allow if the count is below the limit.

 limit = 3 per 60 s, request arrives at t=100
 log before: [ 30, 45, 70, 95 ]
 drop < 100-60=40:        [ 45, 70, 95 ]   → count 3 ≥ 3 → REJECT
 at t=106:   drop < 46:   [ 70, 95 ]       → count 2 < 3 → ALLOW, log = [70, 95, 106]

function allow(key, limit, window):
    now = now_ms()
    store.zremrangebyscore(key, 0, now - window)      # evict old entries
    if store.zcard(key) < limit:
        store.zadd(key, score=now, member=now + ":" + random())
        store.expire(key, window)
        return ALLOW
    return REJECT

Pros: exact — at most limit requests in any rolling window; no boundary bursts. Cons: memory is O(limit) per key. For a limit of 1,000/hour and 10M active keys that's up to 10 billion timestamps (~8 bytes each plus overhead → easily 100+ GB). Also more work per request. Use it when limits are small and accuracy matters (e.g. 5 password-reset emails per hour).

4.5 Sliding window counter

A clever approximation that combines fixed-window cheapness with sliding-window smoothness. Keep counters for the current and previous fixed windows, and estimate the count in the rolling window by weighting the previous window by how much of it still overlaps:

estimated = current_count + previous_count × (1 − elapsed_in_current / window)

 limit = 100/min, request at 12:01:15  (25% into current window)
            previous window (12:00)            current window (12:01)
      |------------------------------------|------------------------------------|
                 count = 84                    count = 36
                          ◀──────────── rolling 60 s window ────────────▶
                          (75% of previous)        (25% elapsed)
 estimate = 36 + 84 × 0.75 = 99   → 99 < 100 → ALLOW (count becomes 37)

function allow(key, limit, window):
    now = now_seconds()
    cur_id  = floor(now / window)
    elapsed = now - cur_id * window
    cur  = store.get(key + ":" + cur_id) or 0
    prev = store.get(key + ":" + (cur_id - 1)) or 0
    estimate = cur + prev * (window - elapsed) / window
    if estimate >= limit: return REJECT
    store.incr(key + ":" + cur_id)
    store.expire(key + ":" + cur_id, 2 * window)
    return ALLOW

It assumes requests in the previous window were evenly spread, so it's an approximation — but in practice the error is small. Cloudflare has publicly reported that, measured on real traffic, only a tiny fraction (~0.003%) of requests were wrongly allowed or limited with this approach. Pros: two counters per key, smooths edge bursts, fast. Cons: approximate; slightly more complex than fixed window.

4.6 Comparison

Two related ideas: GCRA (Generic Cell Rate Algorithm), a token-bucket variant that stores a single "theoretical arrival time" per key (used by libraries such as redis-cell and throttled); and concurrency limits, which cap the number of in-flight requests rather than requests per second (useful for long or expensive calls).

5. Distributed rate limiting with Redis

Instagram runs hundreds of gateway instances. If each kept its own counters, a user could get limit × number_of_instances by having requests spread across them. The counters must be shared — typically in a Redis cluster, because it's in-memory (sub-millisecond), supports atomic operations and key expiry, and shards horizontally. See Caching (Redis).

5.1 Fixed window with INCR + EXPIRE

key = "rl:user:42:like:" + floor(now/3600)      # hourly window
MULTI
  INCR   key
  EXPIRE key 3600 NX      # set TTL only if none (Redis 7+); older: check INCR result == 1
EXEC
if result_of_INCR > 200 → 429

INCR is atomic, so two concurrent requests can never both read 199 and write 200. The EXPIRE makes old windows disappear automatically, so memory stays bounded.

5.2 Race conditions: why "read, then write" breaks

Algorithms that read state, compute, then write (token bucket, sliding window log) have a classic race when two gateway instances handle the same user simultaneously:

 Gateway A                         Redis (tokens=1)                Gateway B
   GET tokens  ─────────────────▶  1
                                   1  ◀─────────────────────────── GET tokens
   1 ≥ 1 → allow, SET tokens=0 ─▶  0
                                   0  ◀─────────────────────────── 1 ≥ 1 → allow, SET tokens=0
   Result: 2 requests allowed with only 1 token  ✖

Fixes: make the whole read-modify-write atomic on the Redis server. Options are MULTI/EXEC with WATCH (optimistic locking, retries under contention), or — the standard answer — a Lua script. Redis executes a Lua script atomically: no other command runs in the middle. It also saves round trips.

5.3 Token bucket as a Redis Lua script

-- KEYS[1] = bucket key, ARGV = capacity, refill_per_sec, now_ms, cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local cost     = tonumber(ARGV[4])

local data   = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(data[1]) or capacity
local ts     = tonumber(data[2]) or now

local elapsed = math.max(0, now - ts) / 1000
tokens = math.min(capacity, tokens + elapsed * rate)

local allowed = 0
local retry_ms = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
else
  retry_ms = math.ceil((cost - tokens) / rate * 1000)
end

redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
-- expire idle buckets once they would be full again
redis.call("PEXPIRE", KEYS[1], math.ceil(capacity / rate * 1000) + 1000)
return { allowed, math.floor(tokens), retry_ms }

The gateway calls it with EVALSHA <sha> 1 rl:user:42:api 100 50 <now_ms> 1. Details that matter in production:

• Clock source: different gateway machines have slightly different clocks. Either pass a time from a well-synchronised clock (NTP) and tolerate small skew, or use Redis's own TIME command inside the script so one clock is authoritative.
• Cluster keys: in Redis Cluster all keys a script touches must hash to the same slot; use hash tags like rl:{user:42}:cur and rl:{user:42}:prev.
• Sharding: keys spread naturally across shards by user ID (see consistent hashing). Watch for hot keys — e.g. a single per-IP key for a huge carrier NAT.

5.4 Latency and availability concerns

A Redis round trip within a data center is ~0.2–1 ms. Fine for one check — but a request might hit 3–5 rules, at millions of requests per second. Mitigations:

• Evaluate all rules for a request in one Lua script or one pipelined batch → one round trip.
• Co-locate Redis with gateways in the same zone/region; don't make cross-region calls for rate limiting.
• Decide fail-open vs fail-closed when Redis is down: fail open for ordinary traffic (an outage of the limiter shouldn't take down Instagram), fail closed (or fall back to strict local limits) for sensitive endpoints like login and OTP.
• Per-region counters: a user's requests normally stay in one region, so global (cross-region) exactness is rarely worth the latency. Accept that a determined attacker spreading across regions gets slightly more.

5.5 Local + global hybrid

To avoid a network hop on every request, each gateway instance keeps local in-memory token buckets and synchronises with the global store only periodically:

1. Local fast path: each instance checks a local bucket in memory (nanoseconds). Obvious abusers are rejected without touching Redis.
2. Batch sync: every ~100 ms–1 s, each instance pushes its local counts to Redis (INCRBY) and reads back the global total for active keys.
3. Lease / quota allocation variant: an instance "borrows" a chunk of the user's budget (e.g. 10 tokens) from the global store and spends it locally; when exhausted, it asks for another chunk.
4. Trade-off: between syncs, a user spread over many instances can slightly exceed the limit. For anti-abuse limits measured per hour, overshooting by a few requests is irrelevant; for strict limits (OTP attempts), go straight to the global store.

6. Telling the client: HTTP 429 and rate-limit headers

A well-behaved limiter tells clients what happened and when to try again, so good clients back off instead of retrying blindly.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 120
X-RateLimit-Limit: 200
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1793098920

{
  "error": {
    "code": "RATE_LIMITED",
    "message": "You're doing that too often. Please try again later.",
    "retry_after_seconds": 120
  }
}

• 429 Too Many Requests — the standard status for "you, specifically, are over your limit". (Contrast with 503 Service Unavailable — "the server is overloaded for everyone", used by load shedding.)
• Retry-After — seconds to wait (or an HTTP date). Clients should honour it.
• X-RateLimit-Limit / -Remaining / -Reset — the de-facto convention (GitHub, Twitter/X and many APIs) telling clients their budget on every response, so they can self-throttle. Reset is often a Unix timestamp. An IETF draft standardises unprefixed RateLimit and RateLimit-Policy headers.

Client behaviour on 429: stop, wait Retry-After, then retry with exponential backoff plus jitter (random spread) so millions of clients don't all retry at the same instant. See Resilience patterns.

7. Soft vs hard limits, and quotas

8. Rate limiting vs load shedding vs backpressure

These three are often confused in interviews. They solve different problems:

A healthy system uses all three: rate limits stop individual abusers, load shedding protects the whole service from global surges, and backpressure keeps async pipelines from drowning. See Resilience patterns.

9. How Instagram uses rate limiting

9.1 Action limits against spam bots

Assume a real human rarely follows more than ~50 accounts in an hour, while a growth bot wants thousands. Layered limits in the Follow/Graph service and Like & Comment service:

9.2 A follow request, through every layer

1. The app debounces repeated taps and backs off if it recently got a 429.
2. The edge checks per-IP request rates (cheap, catches floods).
3. The gateway authenticates the user and checks the general per-user API budget (token bucket in Redis, local hybrid).
4. The Graph service checks the follow-specific rules (user, device, account age) via one Lua script evaluating all rules at once.
5. If allowed, the follow is written and a follow.created event goes to Kafka. If a soft limit is hit, the response asks the app to show a challenge; if a hard limit, a 429 with a friendly message.
6. Breach events are logged to the anti-abuse pipeline (ML models), which can tighten limits on suspicious accounts.

9.3 Rough capacity numbers

Assume 1.5M API req/s at peak, each checked against ~3 rules → 4.5M rule checks/s.
With one Lua script per request → 1.5M Redis script calls/s.
If one Redis shard handles ~100k script calls/s → ~15 shards (+ replicas), or fewer with
a local hybrid that syncs every 100 ms.

Memory (sliding window counter, 2 counters × ~50 bytes incl. key overhead):
  100M active users × 5 rules × 100 B ≈ 50 GB → fits in a modest Redis cluster.
Sliding window LOG for a 500/hour rule instead: 100M × 500 × ~16 B ≈ 800 GB → why we avoid it at scale.

9.4 Third-party API limits

Partner and developer apps that use Meta's Graph APIs (e.g. to schedule posts for businesses) are limited by a combination of app-level limits (scaled by the app's number of users), per-user-token limits, and per-endpoint cost. Usage is reported back in response headers, and apps exceeding limits are throttled. This is a classic quota system: a long window, tied to the app ID and token, enforced at the gateway.

10. Trade-offs & common pitfalls

Common pitfalls

• Per-instance counters only — the effective limit becomes limit × instances, and changes when you autoscale.
• Non-atomic read-modify-write — race conditions allow overshoot; use INCR or Lua.
• Limiting only by IP — punishes everyone behind a carrier NAT or university network while attackers rotate through residential proxies.
• Fixed windows aligned for everyone — all clients' budgets reset at :00 and stampede; add jitter or use sliding windows/token buckets.
• Clients that retry immediately on 429 — amplifies load; require backoff with jitter and honour Retry-After.
• Failing closed on limiter outage for all traffic — the limiter becomes a single point of failure for the whole product.
• Rate limiting in place of capacity planning — if legitimate users routinely hit limits, you need more capacity or better limits, not more 429s.
• Counting rejected requests toward the limit forever — a client that keeps retrying never recovers; decide deliberately whether rejections consume budget.

11. Real-world technologies

12. Interview corner

13. Check your understanding

Related lessons

• API Gateway — where most rate limits are enforced
• Caching (Redis & Memcached) — the in-memory store that holds the counters
• Authentication & Authorization — login attempt limits and identity used as rate-limit keys
• Resilience patterns — backoff, jitter, load shedding and circuit breakers
• Security & Privacy — DDoS protection, bots and abuse defences
• Social Graph & Follow Service — where follow limits are applied
• Likes, Comments & Counters — action limits on likes and comments