Rate Limiter System Design: Token Bucket, Leaky Bucket, Scaling

[00:03] many requests to GitHub, Stripe or AWS and your requests get rejected. How do this system work? Ray limiters control how many requests a client can make to an API in a given time window. They protect systems from overload while

[00:17] maintaining fair access for legitimate users. Let's tackle the core design challenges. Let's go over the requirements first. The system should limit incoming requests based on configurable rules like 100 API requests

[00:31] per minute per user. When limits are exceeded, the system should reject requests with HTTP 429 and include helpful headers showing rate limit remaining and reset time. The system should introduce minimal latency

[00:45] overhead, say under 3 millisecond P95 per check. The system should be highly available and accessible by multiple servers. Now that we understand what we need to build, let's start with the simplest

[00:58] approach, fixed window counting. We divide time into fixed windows like one minute intervals. Each user gets a counter that resets at the start of each window. Here's how it works. A user is allowed 100 requests per minute. At the

[01:12] start of each minute, their counter resets to zero. Each request increments to counter. When they hit 100 requests, we reject additional requests until the next minutes begins. We need to store these counters somewhere fast. The

[01:27] database is too slow for this. Today's video is sponsored by Warped, the best way to code with AI agents. Too often, agents write code that's almost right, leaving developers stuck debugging instead of shipping. Warp is different.

[01:41] Rank top of terminal bench and bench verified. Warps agent understands your context and writes production ready code out of the box. Prom, review, and refine all in one interface. No context switching, no wasted time. You stay in

[01:55] control and it pays off. On average, users are saving over an hour a day with Warp. Download Warp by clicking the link in the description. We're adding a database query to every request, which could overload the very

[02:09] system we're trying to protect. What about in-memory storage and this server? This would be very fast, but it only works for a single server. When we scale to multiple servers, each server would have its own separate counters. A user

[02:22] could make 100 requests to server A and 100 requests to server B, effectively getting 200 requests per minute instead of 100. Reddit solves both problems. Is an in-memory data store that's shared across all our servers. Reddis provides

[02:37] primitives to increment counters and reset them automatically. But fix window have a critical flaw. Consider this scenario. A user makes 100 requests in the last 10 seconds of a minute, then 100 more requests in the first 10

[02:51] seconds of the next minute. Both bursts are within the 100 requests per minute limit individually, but they've made 200 requests in just 20 seconds, which clearly violates the intended ray limit. This edge case happens at every window

[03:06] algorithm. The token bucket algorithm solves the fixed window problem. It's the industry standard used by companies like AWS and Stripe. Think of it like this. Imagine a bucket that hosts tokens. New tokens are

[03:21] added at a steady rate. Each request consume one token. When there are no tokens left, we reject the request. Let's see how this fixes our window boundary problem. We set a bucket capacity of 100 tokens that refills at

[03:35] 100 tokens per minute. During quiet periods, tokens accumulate. When user makes burst requests across window boundaries, they consume accumulated tokens but can't exceed the refill rate over time. The key insight is that

[03:49] tokens accumulate during quiet period. This allow legitimate traffic bursts while maintaining the overall rate limit. A user can game the system by timing the request to window boundaries. The algorithm uses two parameters.

[04:03] Bucket capacity determines burst size and refill rate determines sustained throughput. A capacity of 100 with a refill rate of 100 per minute allows up to 100 requests instantly that maintains exactly 100 requests per minute

[04:17] long-term. There are other algorithms like sliding window logs, sliding window counters, and leaking buckets that solve the fixed window problem differently. balance between simplicity and effectiveness for most use cases. Now

[04:33] that we have our algorithm, we need to decide where to implement it in our options for where to place our ray limiter. Client side ray limiting puts the logic in client applications, but we can't trust clients to enforce their own

[04:47] limits. Malicious users can modify the code or bypass restrictions entirely. Serverside ray limiting embeds the logic in our application code. This gives us complete control over the algorithm and keeps everything in one place. The

[05:02] downsides is that ray limiting gets mixed with business logic and each service needs its own implementation. Middleware ray limiting uses a dedicated service between clients and the APIs. This could be an API gateway, a reverse

[05:16] proxy or a custom service. This keeps ray limiting separate from business logic and provides a single place to manage policies. The trade-off is an increase in system complexity. Which should we choose? It depends on our

[05:29] situation. If we already have an API gateway handling authentication, adding rate limiting there makes sense. If we need a custom algorithm, server side gives us flexibility. For most systems, middleware offers the best balance of

[05:44] control and operational simplicity. Our system architecture looks like this. We store ray limiting rules in a configuration service. These rules define limits like premium users get a th00and requests per hour or free users

[05:58] get 100 requests per hour. The middleware fetches these rules and stores token bucket state in Reddus. When a request arrives, the middleware identifies the user, fetches their token bucket from Reddus and checks if tokens

[06:11] are available. If yes, it decrements the token count and forwards the request to API servers. If no token remains, it returns HTTP 429 with header showing when the user can retry. This works great for a single rail limited server.

[06:26] But what happens when we need to scale to multiple servers, we run into race conditions. Here's what happens. Server A reads a counter value of three from radius. At the same time, server B also reads three. Both servers check their

[06:39] limits, decide the request is okay, increment the value to four, and write it back to Reddus. The counter now shows four instead of the correct value of five. We've lost a count. We can solve this with atomic operations. Reddus

[06:53] supports these two lure scripts that bundle the read, check, and increment into a single indivisible unit. This prevents race condition entirely. We've covered the essential building blocks for ray limiters in this video. There

[07:06] are other interesting topics we didn't cover. How do we handle geographic latency with multi-reion deployment? How do we handle hot keys when a few users generate most traffic? How do we upload rate limiting rules without restarting

[07:19] servers? Should the system fail open or fail closed when key components go down? These are all interesting topics worth exploring. Ready to ace your next technical interview? Join our community where we

[07:32] offer comprehensive courses on system design, coding, behavioral questions, machine learning, and object-oriented design. Learn more at byitebico.com.