Aivorab

api-performance · rate-limiting · algorithms · backend

Rate Limiting Algorithms: A Technically Conservative Guide for Indie Developers

A practical comparison of token bucket, sliding window, and fixed window rate limiting algorithms—what they trade off, when to use each, and how to implement fair throttling without overcomplicating your stack.

Published:

Rate Limiting Algorithms: A Technically Conservative Guide for Indie Developers

Rate limiting is one of those infrastructure problems that looks simple until you actually have to build it. You want to cap requests per user, per IP, or per API key. You add a counter, you return 429 when it exceeds the limit, and you call it a day. But the moment you ship that to production, three things happen: legitimate users get throttled unfairly, your counters leak memory, or your “simple” implementation collapses under burst traffic.

This guide walks through the three most common rate limiting algorithms—fixed window, sliding window, and token bucket—so you can pick the right one for your API without falling into the classic traps.

Why Algorithm Choice Matters

Rate limiting algorithms differ in three dimensions that matter to indie teams: accuracy, memory cost, and burst behavior. A fixed window counter is cheap and easy but allows bursts at window boundaries. A sliding window is more accurate but requires more storage. A token bucket handles bursts gracefully but needs careful tuning to avoid starvation.

Your choice depends on what you’re protecting. If you’re limiting login attempts to prevent credential stuffing, accuracy matters more than burst tolerance. If you’re protecting a search endpoint from abuse, a token bucket may be the right call. If you’re building a public API with tiered pricing, fairness across user classes becomes the priority.

Fixed Window Counters

The fixed window algorithm divides time into discrete intervals—say, one minute—and counts requests within each interval. When the counter exceeds the limit, subsequent requests are rejected until the next window starts.

How it works: You store a counter keyed by (user_id, window_start). On each request, you increment the counter. If it exceeds the limit, you return 429. When the window expires, you delete the key and start fresh.

The trade-off: Fixed window counters are the simplest to implement and the cheapest in terms of memory. You only store one integer per user per window. But they have a well-known flaw: the boundary problem. A user can make twice the allowed rate in a single second if their requests straddle two windows. For example, if the limit is 100 requests per minute, a user could send 100 requests in the last second of window 1 and another 100 in the first second of window 2—effectively doubling their rate at the boundary.

When to use it: Fixed window counters work fine for low-stakes rate limiting where occasional bursts are acceptable. They’re also a reasonable starting point if you’re implementing rate limiting for the first time and want to ship something quickly. Cloudflare’s basic rate limiting rules use a fixed window approach under the hood, which is why they’re fast to configure but sometimes feel imprecise at the edges.

Sliding Window Counters

The sliding window algorithm improves on fixed window by tracking requests across a rolling time window rather than discrete intervals. Instead of asking “how many requests in this minute?” it asks “how many requests in the last 60 seconds?”

How it works: There are two common implementations. The first stores a timestamped log of every request and counts how many fall within the window on each check. This is accurate but memory-intensive—you store a timestamp for every request. The second, more practical approach uses multiple fixed windows and interpolates between them. For example, you might store counters for the current minute and the previous minute, then estimate the window count as a weighted average. This is called the sliding window counter or sliding window log, and it’s what many production systems use.

The trade-off: Sliding window counters are more accurate than fixed window—they eliminate the boundary burst problem. But they cost more in memory and computation. The interpolated approach reduces memory compared to a full timestamp log but still requires storing multiple counters per user. If you’re rate limiting at scale across millions of users, this memory cost adds up quickly.

When to use it: Sliding window counters are the right choice when accuracy matters and you can afford the memory cost. They’re commonly used for protecting sensitive endpoints like login or password reset, where the boundary burst problem could allow an attacker to double their effective rate. Cloudflare’s Advanced Rate Limiting, which counts requests based on HTTP characteristics beyond just IP address, uses sliding window logic internally to provide more precise throttling.

Token Bucket Algorithm

The token bucket algorithm is the most flexible of the three. Instead of counting requests, it tracks tokens. A bucket holds a maximum number of tokens and refills at a constant rate. Each request consumes one token. If the bucket is empty, the request is rejected.

How it works: You store the number of tokens remaining in the bucket and the last refill time. On each request, you calculate how many tokens should have been added since the last request based on elapsed time, cap the total at the bucket maximum, then subtract one token if available. If no tokens remain, you return 429.

The trade-off: Token buckets handle bursts gracefully because the bucket can accumulate tokens during idle periods. A user who hasn’t made requests for a while will have a full bucket and can burst up to the bucket capacity. This is both a feature and a bug—it allows legitimate burst traffic but can also let a single user consume disproportionate resources if the bucket is too large.

The refill rate determines the sustained throughput, while the bucket capacity determines the burst size. Tuning both parameters is essential. A bucket that refills too slowly starves users; a bucket that refills too quickly defeats the purpose of rate limiting.

When to use it: Token buckets are ideal when you need to allow controlled bursts while maintaining a steady average rate. They’re widely used in API gateways and CDN edge logic. Cloudflare Workers’ Rate Limiting API, for example, is backed by token bucket infrastructure. AWS Elastic Load Balancing also uses the token bucket algorithm for its API throttling, with separate buckets for different API versions and action types.

Fair Rate Limiting

Regardless of which algorithm you choose, fairness is the harder problem. Fair rate limiting means that legitimate users are not penalized by the behavior of malicious or misconfigured clients sharing the same identity space.

The IP problem: Traditional IP-based rate limiting breaks down when multiple users share an IP address. Carrier-grade NAT, corporate proxies, and mobile networks mean that thousands of users may share a single public IP. Throttling that IP throttles everyone. Cloudflare noted this explicitly in their Advanced Rate Limiting announcement: “IPs are rarely static; nowadays, mobile operators use carrier-grade network address translation (CGNAT) to share the same IP amongst thousands of individual devices or users.”

Better identity signals: Fair rate limiting requires counting against identifiers that map one-to-one—or as close as possible—to individual users. API keys are the gold standard for authenticated APIs. User IDs from authentication systems work well for session-based rate limiting. For unauthenticated endpoints, you can combine multiple signals: user agent, cookie values, and request patterns. Cloudflare’s Advanced Rate Limiting allows counting by URI, method, headers, cookies, and body fields, giving you the flexibility to build rules that target specific abuse patterns without collateral damage to legitimate traffic.

Tiered limits: Fairness also means different limits for different user classes. A free tier and a paid tier should have different rate limits. This is straightforward to implement: include the user’s tier in your rate limit key and configure separate limits per tier. Cloudflare Workers’ Rate Limiting API supports this natively—you can define different limits for different namespaces and apply them based on user attributes.

Implementation Checklist

Before you ship rate limiting to production, verify these items:

  1. Choose the right algorithm for your threat model. Fixed window for simplicity, sliding window for accuracy, token bucket for burst tolerance.
  2. Pick the right identity key. API key or user ID for authenticated endpoints. Multiple signals for unauthenticated ones.
  3. Set sensible limits. Start conservative and adjust based on observed traffic. AWS recommends monitoring throttling events and adjusting retry logic before requesting quota increases.
  4. Handle 429 responses gracefully. Implement exponential backoff with jitter. AWS’s guidance on timeouts, retries, and backoff with jitter is the standard reference here.
  5. Monitor and alert. Track rate limit hits, rejected requests, and false positives. CloudWatch dashboards and Cloudflare analytics can help you spot problems before they impact users.
  6. Plan for scale. If you’re rate limiting across millions of users, consider distributed implementations using Redis or a dedicated rate limiting service rather than in-process counters.

FAQ

Q: Can I just use a library instead of implementing this myself?

Yes. Most modern frameworks have rate limiting middleware. The question is whether the library’s default algorithm and configuration match your needs. If you’re building something custom, understanding these algorithms helps you configure the library correctly and debug issues when they arise.

Q: How do I handle distributed rate limiting across multiple servers?

You need a shared state store. Redis is the most common choice—use INCR with EXPIRE for fixed window counters, or a sorted set for sliding window logs. Token buckets in a distributed system require careful coordination; consider using a centralized rate limiting service or a library like Bucket4j that handles the distributed state for you.

Q: What’s the difference between rate limiting and throttling?

Rate limiting caps the number of requests over a time period. Throttling is a broader term that includes rate limiting but also encompasses congestion control, backpressure, and other techniques for managing load. In practice, the terms are often used interchangeably.

Q: Should I rate limit at the API gateway or in the application?

Both. API gateway rate limiting protects your infrastructure from volumetric attacks and reduces load before requests reach your application. Application-level rate limiting gives you finer-grained control based on business logic—different endpoints, user tiers, and abuse patterns. Cloudflare and AWS WAF provide gateway-level rate limiting; your application should enforce its own limits for endpoint-specific protection.

Sources