---
title: 'Design a Distributed Rate Limiter with an Ex-Meta Staff Engineer: System Design Breakdown'
source: 'https://youtube.com/watch?v=MIJFyUPG4Z4'
video_id: 'MIJFyUPG4Z4'
date: 2026-08-04
duration_sec: 3357
---

# Design a Distributed Rate Limiter with an Ex-Meta Staff Engineer: System Design Breakdown

> Source: [Design a Distributed Rate Limiter with an Ex-Meta Staff Engineer: System Design Breakdown](https://youtube.com/watch?v=MIJFyUPG4Z4)

## Summary

This video provides a comprehensive system design walkthrough for building a distributed rate limiter, guided by Evan, a former Meta staff engineer. It covers the entire design process from requirements gathering to deep dives on scalability, availability, and latency, using the token bucket algorithm and Redis for state management.

### Key Points

- **Introduction to Rate Limiting** [00:02] — Rate limiters control how many requests a client can make in a specific time frame, protecting backend services from abuse. Example: 100 requests per minute per user.
- **Functional Requirements** [04:10] — Identify clients (by user ID, IP, or API key), limit requests based on configurable rules, and return proper error headers and status codes.
- **Scale and Non-Functional Requirements** [06:10] — Assume 100 million daily active users and 1 million requests per second. Non-functional requirements include availability over consistency, low latency (<10ms), and scalability.
- **High-Level Design: Placement Options** [14:29] — Rate limiter can be placed in each microservice (no global coordination), as a separate service (adds latency), or at the edge (API gateway/load balancer) for global coordination with minimal latency.
- **Client Identification** [21:26] — Identify clients via user ID, IP address, or API key. A combination is often used, e.g., authenticated users get higher limits than anonymous IPs.
- **Rate Limiting Algorithms** [22:48] — Four main algorithms: fixed window counter (simple but boundary effect), sliding window log (accurate but memory-heavy), sliding window counter (approximation with two counters), and token bucket (handles bursts and steady rate, chosen for this design).
- **Token Bucket Implementation with Redis** [30:10] — Store token count and last refill time in Redis. Use HMGET to fetch both, calculate refill, update counts, and respond pass/fail. Use Lua scripting for atomicity to avoid race conditions.
- **Error Handling and Status Codes** [35:47] — Fail fast approach: reject immediately with HTTP 429 (Too Many Requests). Include headers like X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, and Retry-After.
- **Deep Dive: Scalability** [39:25] — Single Redis instance can handle ~50k ops/sec, so shard across multiple Redis instances using Redis Cluster (hash slots) to reach 1M requests/sec.
- **Deep Dive: Availability and Fault Tolerance** [42:54] — Fail open vs fail close. For a social network, fail close is safer. Use replicas (async replication) to promote on failure. Redis Cluster supports this.
- **Deep Dive: Low Latency** [47:21] — Use connection pooling to avoid TCP handshake overhead. Geographically distribute gateways and Redis instances to be close to users.
- **Dynamic Rule Configuration** [49:27] — Options: pull from DB (adds latency), store rules in Redis (adds ops), or use push-based config with ZooKeeper/etcd for real-time updates without polling.
- **Expectations by Level** [53:15] — Mid-level: breadth over depth, know algorithms and justify choice. Senior: proactive identification of issues, math, and trade-offs. Staff: deep expertise, guide conversation, discuss advanced topics like race conditions.

### Conclusion

The video delivers a thorough, step-by-step system design for a distributed rate limiter, emphasizing the token bucket algorithm, Redis for shared state, and strategies for scalability, availability, and low latency. It also provides clear guidance on what interviewers expect at different seniority levels.

## Transcript

system design interview classic. We're going to be designing a rate limiter. Uh design, this is a fantastic place to start. It's a good problem to get popular at many of the top companies. It's asked a lot at Microsoft, for
example, and many users recently have been reporting that it's being asked at OpenAI lately, too. Uh now, for those of you who are new to the channel, I'm Evan. I'm a former meta staff engineer and I'm the co-founder of Hello
Interview. Hello Interview is a platform that helps people just like you prepare interviews. And so if you haven't already, head over there, check it out. Now, if videos aren't your thing, we have detailed written writeups on this
problem, designing a rate limiter, as well as 26 others. You can see them all here. We also have foundational core concepts, deep dives into technologies, know for system design, as well as plenty of content on DSA, behavioral,
salary negotiation, interview guides. You got it or you name it, we got it. Um, now you can also try this problem yourself using our guided practice. And so you can come here, fill things out step by step, record your answer, get
feedback, and this is going to be evaluating your design in real time for each question along the way, letting you know what you did well, and of course the things that you can do in order to improve. So feel free to give that a go.
The overwhelming majority of the content is free, guided practice. Everybody gets Unfortunately, it's only for premium members. Hope you understand. All right, members. Hope you understand. All right, without further ado, let's get after it.
familiar, but it's good for us to go over it so that we have a a shared system. Rate limiters control how many requests a client can make in a specific time frame. And so, think about you have a social media app. Users are making
requests in order to view news feeds, update posts, etc. And the rate limiter limits them to something like, for example, 100 requests per minute per user. And the whole point here is to protect our backend. It's to protect our
services so that users can't come and abuse our system, spamming us with thousands of requests that ultimately might take down our system or make it unusable for other users. So that's what a rate limiter is. Now, before we jump
into designing it, as we always do in these videos, we're going to outline the both in this video and that I suggest that you follow in any of your real the hello interview delivery framework. We suggest you go step by step through
these steps starting first with your requirements. This is where we're going requirements or the features of the system as well as the non-functional requirements or the qualities of the system. We're also going to outline some
of the core entities. These are usually the nouns of your of your system. These are the uh the rows that you're storing or the um the tables, excuse me, in your database. The things that are exchanged, the resources in your APIs, that's our
core entities. And then we'll do either API or system interface. In the case of back-end component, you know, the client's not necessarily interacting with it directly. We're going to focus on the system interface. Um, for some
system design interviews, data flow makes sense. You could have it make think we'll probably skip it and we'll go right to the highle design where the goal of the highle design is to head over to the whiteboard, draw some boxes
and arrows in order to satisfy those core functional requirements of the system. And so in other words, get a minimal design down early in your system design interview that's able to fulfill the basic features of the system. And
then from there, we can move on to our deep dives where we're going to layer on complexity by satisfying our nonfunctional requirements such that our final design has everything it needs to be able to scale, be low latency, fault
tolerance, all of those things that are really important. And so you'll watch me walk through this step by step. We'll do it together and we'll have some fun.
jump right in then with our functional requirements. Again, functional requirements. Functional requirements are the features of the system. Now, for usually pretty straightforward. A user can write a post, a user can view a
feed, whatever it may be. Uh, in the case of these backend components, it's sometimes a little bit more abstract, but I think it's still rather clear what needs to happen here. And so, I'm going to do this in order of when a request
comes in. Well, the first thing is that the the the application the rate limiter the the the application the rate limiter here needs to be able to identify users by you know something. In our case, maybe this is their ID, their IP or even
important thing is the rate limiter needs to know who is this because I need limit them based on how many requests they've already made. So, that's step one. The second thing and the most important thing is that we need to be
able to limit requests, right? We need to be able to limit requests and these should be based on configurable rules. And so a configurable rule here might be that any user can only make a 100 requests per minute, maybe even to a
specific endpoint, right? And so we got to identify a user and then we'll limit the requests that that user can make based on a set of configurable rules. And then the last thing is that we want to return proper error headers and
status codes to the user. And so we don't want to be ambiguous here. We 500 to the user and them have no idea why. We want to tell them that they're them some additional metadata so that they can deduce how they should uh you
know move forward, what they should do next. So those are our functional requirements of our system at our core. That's what we're designing. Now, before requirements in your interview, my suggestion to you is always check in
with your interviewer at this point and ask them about the scale of the system. Especially in the case of of a rate limiter here, the scale is actually questions that you'd want to ask. And so, I would ask my interviewer, what am
I rate limiting? Is this a userfacing application like a Facebook or something? Is this some developer tooling? Is this rate limits um between intra microervices maybe within a company? What am I rate limiting? And
most popular, you're typically going to be rate limiting some, you know, userf facing application like a social media app. And so we'll say that we have 100 million daily active users and that means 1 million requests per second.
Okay? So we have 1 million requests per second. Um, and we're going to be rate limiting at that particular scale. Now, one other thing I actually want to note this is kind of funny. Candidates would always say to me, "Am I designing a
back-end rate limiter, uh, a serverside rate limiter, or a client side rate this question was always a little bit confusing to me. It's like, of of course we're designing a serverside rate limiter. A client side rate limiter
value in this case. It can obviously be spoofed. You can't trust the clients to spoofed. You can't trust the clients to limit themselves, right? And so I found this because as I was doing some some research to write up our breakdown of
this problem, I saw that most other writeups online start with that the server side or client side. Um, and so I don't know, like I said, I think this is side. There are realistic use cases where client side provides some added
asked in an interview. Um, so bit of a tangent or or an aside from me, but yes, we're going to be doing a server side um rate limiter that is going to rate limit um for an application that has a 100 million daily active users and 1 million
requests per second. And so with that, we can come to our non-functional requirements. And so non-functional requirements trip up a lot of candidates. What is a non-functional requirement first of all?
features of a system, right? what does the system need to be able to do? The non-functional is how does it need to be able to do it? And so this is where right? This is where you're going to talk about scalability, low latency,
durability, um even security, fault tolerance. Now, if you head over to hello.com under the delivery framework section, we list off all the things that you should consider in the non-functional requirement. But most
write all of those things. Everything you write in the non-functional requirements, you're expected to address in your design. This is really crucial. And so you're going to want to call out the specific column illities, right?
Ilies, um, that are directly relevant to this design. Okay? And so pick out the and most interesting and we'll go forward with those. And so the first your non-functional requirements is always cap theorem. And so of course in
CAP theorem, we have consistency, availability, and partition tolerance. Partition tolerance is a must. So your decision is always should my system be strongly consistent meaning should every single read be reading the latest write
or should we opt for high availability and thus eventual consistency is fine. Now in our case we're going to go for availability over consistency. You can
think of this like if somebody was going to push a new rule to our system, would we rather that the rate limiter still works even if it's reading outdated propagating or should we have the rate limiter basically go offline because we
propagated. That's one example of availability versus consistency. Clearly, we want to make sure that our rate limiter is still always just up and available and working because it's protecting our system. Now, the second
thing that is uniquely interesting to a rate limiter is low latency. And so in candidate or I shouldn't say bad but maybe a a less good candidate would come in here and they would write this on the board low latency. And I as the
systems it's good for a system to be low uh have low latency but what do you mean here? And now what a good candidate would do is they would be specific and they would say we have low latency rate limit checks and even better we're going
to aim for under 10 milliseconds. And so what they've done here is that they've both quantified and they've also qualified. So they said, I want low latency in the case of a user making a request. We don't want to add additional
want to make sure that we add less than 10 milliseconds. And this is what they're going to try to design for. Now, of course, this is really important in a is adding additional time to any request from a user. that user requested
something like uh a post and we're going to take time to first check if they're rate limits, but we don't want to take a long time doing it. The user wants to see that post quickly, right? So low latency is important there.
that this was important when we talked about scale question above, but this system needs to be scalable. So scalability, right? So it needs to be scalable scalable and we want to scale again to quantify it to that 1 million
again to quantify it to that 1 million requests per second. And so the goal of our functional and our non-functional requirements is to agree with our building. We're basically setting up this contract with them saying that for
things that I'm going to fulfill. And now I as the candidate can hold myself of the interview and I did all of these things well, I kind of did all six of these things here well, then I should feel confident leaving the interview
like I passed and I nailed it. And that's the general goal here. Um, and so interviewer. Ask them, is there anything I'm missing? Is there anything you would change? Otherwise, I'd love to continue and move on to the next sections.
going to admit for these backend components, this is slightly less important again than a userfacing application, but they do form a basis skip, but you can probably do them frankly in in under a minute. And so,
through them. What are the core entities of a system like this? Well, the core entities that you have is a request. This is the request that's incoming. Uh it's how you are going to determine who is making the request, right? And so
like the who I'm going to call them a client, but this is like your IP address. This is your user ID, the things that we talked about earlier, request come in, you have a client, and then you have rules. Of course, these
rules are the things like, you know, 100 requests per user per second, right? So of our system. They're good for getting
on here. and they lead us nicely to what would be either our API or a system interface. Now I'm going to go with system interface instead of API because we want to choose API when we're doing a userfacing application where users are
calling an API. Users are not calling an API in this case. users are are calling an API of for example our social media app right get posts but it's us who are checking the rate limiter and we're doing this via probably an RPC call or
some internal call um which we can define as our system interface and so you can do this however you want I like to do it kind of as a function call and really it's just this one function that we're implemented is this request
allowed right for this client ID in this rule and we're going to return basically rule and we're going to return basically Did it pass? You know, is that allowed? though, if we look back to our functional requirements, we wanted to
return some interesting stuff here. So, the user knows what to do. And some of those interesting things might be, you know, how many remaining requests the user may have if they do pass. Uh, as well as like maybe what time it resets.
algorithm is, which we'll get into in more detail later. But this is the thing that we're implementing, some function that allows us to ask if a request that allows us to ask if a request passes or not. And so if we zoom out
understanding. This was our setup. We have a good understanding of what we requirements, our entities, and our interface. And it's time for us to head fun stuff, start drawing boxes and arrows, nail down our highle design, and
arrows, nail down our highle design, and then our deep dives. actually really simple and methodical. You don't need to overthink this. You're just going to go one by one through your functional requirements in order to make
sure that we can satisfy each of them. And so our first requirement is that the system should be able to identify clients by their user ID or IP address or API key and so on. But importantly, maybe before we can limit anyone,
there's two key questions that we need to be able to to answer. And so I'll write them over here so that we have them in mind. The first is where should our rate limiter live in our architecture? Basically, where do we
place it? Right? And this is going to determine what information we can access and how it integrates with the rest of the system. And then the second question that we're going to need to be able to answer is how should we identify
clients? And so based on those user ID, IP address, uh API key, anything else, And this assures that we of course apply the rate the right rate limits to to any
given user. And so these two questions here, they're closely linked. Your placement choice is going to affect what client information you can easily access. And your identification strategy influences where the rate limiter makes
the most sense to deploy. And so let's start with with the first one here. That's the first thing that we're going to answer. And we have three main to answer. And we have three main options. Now the first option is pretty
maybe obvious and we can start with the simplest thing. Let me draw out why is that so thick? Uh let me draw out what our basic system could look like. Right? We're going to have a microser architecture because we have some large
architecture because we have some large system here like our um uh uh what did we call it? Social media app. Excuse me. Hard to type and think. And so here's just our really basic setup. Okay, clients make requests to
our social media app. It goes to our gateway. Our gateway then forwards that on and routes it to the appropriate micros service. That micros service does client. Okay, so there's the basics of our social media app. And now we need to
talked about putting a rate limiter on the client doesn't make as much sense. We alluded to that in the beginning. So we need some uh rate limiter back here in the back end or in server code. So where can we place it? The first option,
I'll make it blue here, is that we can put our rate limiters directly inside each of our respective microservices. Right now in this setup,
And so when a request comes in, the server is going to check its local memory for the current counts for any given user. It'll update them and then decide whether to allow or reject the request. Now the good thing is this
is happening in memory. There's no network calls. There's no external dependencies. But the downside I think is is really obvious. There's no global picture. And so you can imagine that a user makes two requests where one hits
microser one and one hits micros service 2. And in each case they both think that only one request has come in. However, of course, globally the user has made two requests. And so the lack of coordination makes this a really poor
option. And so what's the the second thing we could do? Well, naturally, we could pull this out and maybe make this rate limiter its own service here, right? Make it global. And so now, every time a request comes into one of these
microservices, the first thing that they're going to do is check with the rate limiter and say, "Hey, am I allowed to process this request?" Basically, is this under our limits? And if yes, they'll end up processing the request uh
gateway or back to the client through the gateway. And so this is great and that it solves that global coordination problem that we were worried about. Wonderful. Um but it also is going to introduce some excess latency. And so
is going to go from the gateway to a microser. The microser is then going to service, a separate server somewhere which is your rate limiter which is do its thing and respond back to the user. And so admittedly this is fairly
user. And so admittedly this is fairly minimal. Um, but just keeping in mind we so we want to make sure this is as quick as possible. Um, and this added network overhead probably isn't worth it. And so how can we keep that global picture but
maybe reduce the latency of that network overhead. And now the the answer and what is used in most production systems is to actually just move the gateway over here to the edge. And so we can place it directly in either our API
gateway or our load balancer, whatever component sits at the front of our now in this setup, every single incoming request is going to hit our rate limiter first. And so right before we determine
just say, hey, can we even service this request based on our our given limits? Right? And so for those of you maybe who like analogies, you can think of this placement of our rate limiter like like a bouncer at the club. I think is the
here, right? And so troublemakers are going to get turned away at the door, not after they're already made it inside the case in the previous approach.
Right? Now, this this still has some some limitations. The first is around that as we get to our non-functional requirements. But more importantly, this limits the amount of context that we have. And so when we had the rate
limiter in our application code, we in theory have context to everything about our system. And so if you want to make complex rate limiting rules like you based on whether they're a premium user or something that was easy to do. But
now as we sit at the edge we only have information that came in via the HTTP request itself. So the headers, the URL, the IP address and and any basic authentication tokens that are present in the actual request. we can't see that
deeper business logic that might exist inside of our application code with access to to some persistent storage like a database. And so this is fine to give that example again. Maybe we want to to do the premium user thing. Premium
users get 10x higher rate limits. Um it's still doable. We just need to make sure that the fact that a user is a premium user is encoded in the request. This is typically via the JWT token which is going to be in the headers. And
so anything the clients send over should say in this case via the JWT that they're a premium user. So we have that context. We do our rate limiting. And then our microservices can focus only on servicing requests. They don't need to
know about anything about how we we rate limit or whether we rate limit. Now we we outlined and that's how should we identify clients. Well to be honest the whole time. We even put it directly in our functional requirement with user
something that you're going to want to bring up and talk to your interviewer about. It's basically what makes a client unique. And those are the three main options. The user ID, the IP address, or the API key. Uh, but this is
a perfect time to ask your interviewer some questions. And I would ask them, are all of our users authenticated? Is this a developer API that's going to require an API key? Etc. These are the sorts of things that you might want to
maybe be the most impressive answer to give your interviewer, is that we're probably going to want a combination. Maybe authenticated users get higher rate limits than anonymous IP addresses. Or as we talked about earlier, premium
users may get even more. This is a reflection of your understanding of like real world systems. And you're not going to enforce just a global limit, but probably have layers of multiple rules. And so you might have Alice can make a
IP address can make a 100 requests per second. Uh an API can handle 50,000 requests per second. You know, whatever it may be. So, we're going to be able to identify all of these things, apply them to different rules, and they're going to
via the request, usually from the request headers. Now, we can move on to our second functional requirement where it's the system should limit requests based on configurable rules. And so this is where we get to the heart of rate
limiting and that is the algorithm that decides whether we should allow or reject any given request. Now importantly in system design interviews this this being the algorithm isn't actually usually the main focus of the
low-level design interviews. Now you're still going to want to be able to options that you can weigh the different trade-offs and explain and justify your choice but you likely won't need to implement it not even in pseudo code. So
rate limiting algorithms, but I think there's four that are worth you knowing. And so let's start with the simplest and we'll work our way up. The simplest is what's known as the fixed window window counter. And it's incredibly
straightforward. Users get n requests per window. So for example, 100 requests a minute. And for each user, we're going to maintain a counter that resets at the start of each window. If the counter exceeds the limit during that window, we
reject the request. And so, let me I probably should have pasted this in a moment ago, but here is the diagram that we have in the article to work with here. And so, these are each window interval. Requests come in. In this
three requests per window until we start to reject. You get to your fourth request, it passes that threshold, and we end up ultimately rejecting it. Um,
really, really trivial to implement. You just need a hash table that can map your client IDs to counter and window start pairs. And so that hash table might Oh,
let's see if I can copy that better. That hash table might look something like this, right? Where you just have Alice at 12, she had 100 requests. At 12:01, she had five requests. Bob, Charlie, Dave, Eve, and Frank,
respectively. So really really really easy to implement. But the downside is what we end up calling the boundary effect. And so a user can make a 100 effect. And so a user can make a 100 requests at 1201 and 59 seconds. And
then at 1202 they can make 100 more requests because they went on either side of the boundary here. And thus they ended up in effect making 200 requests isn't great. The other thing is that there's the option for starvation. And
so if you made your 100 requests at 12:01 and 1 seconds, now you have to wait 59 seconds until you can make any requests at all, which depending on your needs might also be a problem. Now the second approach is called the sliding
second approach is called the sliding window log. Sliding Why am I blue? Sliding window log. And it basically just smooths out the issues that we had with the fixed winner counter. And so
let me get this new drawing in here for you. Right? And as the name implies, we have the sliding window. And so as requests come in, we keep track of this rolling window over the last minute. And we just say something like we can only
have 100 requests in the last rolling minute. Right now, this eliminates the boundary effects and the burst problem from the fixed window counter that we exact time of each request, which is going to give you that perfect accuracy.
However, the downside here is that this is typically implemented implemented with a heap or a deck. Um, and this is going to require a ton more memory. And so, if you have a ton of users, this is going to be tons more memory. Um, it's
need a bunch more instances and it's going to be more expensive. So, that's third algorithm addresses the memory issues that we have with the sliding window log um by using what we call a sliding window counter. And it's
basically the the sliding window log but with some mild optimization so that we stamp that comes in in something like a heap. Right? We can be clever and instead just keep two counters. One for the previous fixed window and one for
the current window we're in right now. And now the key is that we estimate what a true sliding window would look like uh by weighing these two fixed windows based on how far we are into the current window. And so let me just show you an
example. I have an example written here that I can paste in. And so imagine that the previous window from 1 minute to 1 minute 1 second had eight requests. And now we're 42 seconds or 70% into our second window. And so far we have six
requests. Well, should we accept the next request? Right. Well, here's the math. Given that we're 70% through the minute, we can take our current requests minute, we can take our current requests as well as 30% of the last window,
right? 30% of the last window. This is us estimating how many more should we get in the remaining 30% of the window, right? This is going to estimate that we're at 8.4. Now, if our limit was 10, we could say 8.4 is less than 10 and
thus we should pass. And the great thing here is that this gives us much better accuracy than those fixed windows, but we only need to use two integers per user. We don't need to keep a whole heap per user, right? So downside, it's an
approximation. Uh it's not perfect. It's not going to be perfectly evenly or excuse me, it's an approximation and it assumes that requests are pretty perfectly evenly spread across each of these windows, which aren't necessarily
the case. But if you can handle this approximation, it's a pretty decent Now, the last option and and the one that is is arguably most popular and the one that we're probably going to go with is what's called the token bucket. So,
let me paste in my cute little drawing here. Hopefully, you guys like this one, right? But you can think of it as each client has their own bucket that holds a certain number of tokens. And these number of tokens in the bucket, they're
the burst capacity. Okay? And now at the same time, token tokens are being added to the bucket at a steady rate. And these are called the refill rate. And every time a request comes in, we consume one token. If there are no
tokens available, then the request is rejected. Right? So that sounds a little things really nicely. The size of your bucket is how you handle bursts. Those bursts that we talked about earlier. And so if your bucket starts with 100, then
I can handle a burst of 100 at any given moment, right? And then my refill rate, this is like the steady number of requests per minute or per time that I can handle. So if your refill rate was, you know, uh 60 uh 60 a minute, then
we're going to add one new token every minute. And that means that our steady rate is going to be run one request a minute, right? And each time a request comes in, we pull it out. And so an example, a bucket holds, like I just
said, 100 tokens. This is going to allow bursts of up to 100. If the refill rate was 10 tokens per minute, this is a steady rate of 10 requests a minute. And immediately, but then they'll need to wait for the bucket to refill and
this is really great because it handles that sustained load via our refill rate and the temporary bursts by our bucket capacity. It's also shockingly simple to implement. You just need to track the tokens and the last refill time for
every given client. So again, just two numbers, but the challenge is choosing your refill rate and how you handle cold starts and things like this. Um, but it's a pretty elegant algorithm and it's the one that we're going to to choose
for our design here. So we understand how the token bucket algorithm works conceptually. But where and how do we actually store each user's bucket, this? Each bucket needs to track two
pieces of data. the current token count and the last refill time stamp. And the state needs to be shared across all the different instances of the API gateway. And so importantly, in a real production system, you're going to have multiple of
these gateways. And so they need to share some global state. If they don't, we talked about earlier when we sh stored specific uh rate limiters inside of each microser respectively. And so what we can do is we can pull the rate
what we can do is we can pull the rate limiter state out into an in-memory cache something like Reddus. And so these token counts, these token counts and the last refill rate, all of that state can be shared here in Reddus such
that even though we have multiple gateways, they'll all still going to gateways, they'll all still going to read that same shared state. And so what actually is going to happen here? Well, maybe let's let's write this out for
extreme clarity. First a request is going to come in of course. The second thing is that the gateway is going to fetch the token. And last
and typing while you guys all watch is always difficult from Reddus. Okay. And so in Reddus we can use what's called an hm getit. And so what an hm getit is it allows you to get the values of multiple keys. And so we can say for
Alice's bucket, we want the tokens and the last refill, right? So see that We're just saying in one command, give me her current tokens and the last time that it was refilled. Cool. And then what we can do then is calculate based
on when her last refill time was, how many tokens we need to add to her So, if Alice's bucket was last updated 30 seconds ago and her refill rate is one token every second, then the gateway is going to need to add 30 tokens to her
current count, right? So maybe her current count was 20. The last refill rate was 30 seconds ago. We refill at one every second. So now the count is 50, right? So the next step here is update counts based on rate and last
[Music] Great. Right. And then of course we're Great. Right. And then of course we're going to respond pass or fail based on if token after the refill or excuse me if kind of tokens
after that refill is greater than zero. Are there any tokens in the bucket given should have been refilled since the last time that we checked this. Are there greater than zero tokens? If yes then we can pass. Right. And then the fifth
thing is to update the bucket status. And so this is where we will write back and update the token count to whatever that new token count is. Update whatever the the last or update the last refill time to whatever the current time stamp
is. Right? So make sure that everything gets updated. That's the general flow. But importantly, hopefully this makes sense so far. There's a race condition, right? So I want you to imagine I want you to imagine the following. Let me try
to illustrate this. I have gateway A and I have gateway B. And Alice sends in two requests. One request hits A, one request hits B. They both go and read
Reddus for our token counts. Right? So they both go and say, "What is my current token and my current last refill rate?" Well, in both cases, they're going to read the same value. That value might be one, right? It comes back as
one. They both check. Maybe the last time we checked was a second ago. There have been no more tokens added. So they both read. They both say, "Okay, it's going to accept." They both accept and they both go right to Reddus. Maybe this
one writes a nancond before than this one. So this one overwrites the previous. Right? The important bit here is that the race condition is that we have this read after write problem. You can have the read from a from gateway a
then the read from gateway b then the right from a then the write from b when those two things the read and the right for each have to happen atomically right and so the key is that these things the one read from reddus and the two write
postgress database or anything this is done of course like via transactions with locking as well in the case of reddus it supports atomic transactions makes this a little bit easier and it's something called Luis scripting. Louis
into too much detail here, but the general essence is that you can have all of these uh Reddus commands, this hm getit, the h set in order to update the token counts all via a single reddus uh reddice or excuse me, a single reddis
luis script, right? And then it'll go over the wire. It'll do the read and write all in one instance and then return to you whether or not you should atomically and you don't have the race
does everything and the other one waits until the other one is completely finished. Okay, hopefully that makes sense. Um, okay, fantastic. So, what have we done here? Coming back, we have now covered our first and our second
functional requirement. All that's left is that we need to return proper error headers and status codes. And this is this is pretty straightforward. This is the easiest one here. Um, I guess there is one decision that we
want to make. Uh, and that one decision is that if a request, if we've exceeded a rate limit, what do we do? Do we reject immediately or do we cue it and
might seem obvious to many of you listening, and I've almost been alluding to this throughout. We're going to take the approach of what's called fail fast. immediately going to send a failure back to the user. We're not going to cue it.
In a system like this, queueing doesn't make any sense. If a user is asking for posts to view their posts, we cue it. They're waiting and waiting and waiting. They think something is broken anyway. They hit the button again to try to view
their post again. Now we just have a bunch of requests uh sitting in our queue and a backlog is growing. It becomes an even larger issue. And so makes sense like for batch processing systems that can afford to wait. This is
usually like intra service communication. But for the interactive fast API like we have here, this fast failure fail fast is the most common and the right choice. Um, but how do we make sure then that our response is actually
worth noting that you're definitely going to want to know for an interview going to want to know for an interview is that the HTTP status code that you're going to send on failure is a 429. 429 means too many requests and it is
the standard HTTP status code that is used for exactly this. when you want to rate limit somebody because they've had so many requests, you send back a 429. Um, but there's some additional headers that are best practice that you want to
me, I'm going to copy and paste it so you guys don't have to watch me fumble through typing anymore. Let me put them here. Right. So, you want to send back probably three additional things. The X rate limit limit. This is the rate limit
ceiling for the requests. Right? So if you can have 100 per minute, that's what you're going to put in here. The x rate limit remaining, this is the number of requests left in the current window. Of course, the notion of a current window
can get a little bit funky, but you want to give them some notion of where they are. And then the rate limit reset, when is this going to reset? Um, there's other ones like retry after is a common one that's added here too. Retry after.
This will say, you know, try again in 60 seconds. you should know 429. I think interviewers expect you to know the the response code is 429. But when it comes to like memorizing rate limit limit rate
limit remaining rate limit reset retry after. Don't stress it. You do not need would say something like the following. I would say I'm going to make sure that I return a 429 status code with the appropriate headers. Like some headers
that can let the the user know when they can try again or how many are are can try again or how many are are remaining. Pretty clear. place. We're feeling pretty good about it. We chose our algorithm. The basics
are all working here. But now we need to go back to our delivery framework. And next up is our deep dives. And so this is where we uh go one by one through our non-functional requirements in order to expand upon our design to make sure that
requirements are satisfied. And then we can really feel good about what we put around just so that we have a bit more space. You guys will have this uh description for anybody that wants to reference it.
order when we talk about our non-functional requirements. I'm actually going to work with scalability first. We want 1 million requests per second. And if you come back to our current design, it should be relatively
clear why this won't scale to a million requests per second. And the reason is that we have just this single Reddus instance. And so Reddus can handle, you depending on the hardware, maybe a
100,000 requests per second or operations per second. And that's a tenth of what we need to be able to support. But of need to do, we need to do an HM get and
both of those things for every call. So that's two operations. Uh so maybe we can even say that with what we have we can support 50k requests per second. And
what we need to do then is we need to shard. And sharding of course is the strategy for which we can introduce um more instances and shard the data across those instances. Okay. So you can take a large collection of data and then
shard the keys of that data across multiple reddus instances. To put that far more clearly, Alice might be on Reddus instance one, but Bob's bucket might be on Reddus instance two. Okay? And so, let me demonstrate that here by
adding a bunch of those. We need a million requests per second. And so, if we have 1 million divided by our 50K, well, this is 20. So, we'll need at 20 of these. Maybe we want to tell the interviewer that we want a little bit of
room for overhead, so we'd have more than that. But now the question becomes how do we shard? And this is important because the gateway always needs to know that I just got Alice's request. So I need to look in whichever Reddus
instance has Alice's bucket. If we just checked a random bucket, then we might not have Alice. And if we just replicated all the data to each of these buckets, well, we're in the same problem, right? All of the buckets have
all of the data. Um, and so we might run into issues of the actual amount of size that we're storing. These are in memory. So 64 GB, maybe go up to 10 and
store an infinite amount of data. So how do we want to shard? Well, you obviously want to shard based on whatever your client ID is. In this case, the user ID or the IP address or the API key. And
you can use something like consistent hashing. I'll try to remember to put a somewhere on the screen now so you can click on it if you're not familiar with consistent hashing. Um, but in reality, what you'd probably end up doing if you
are using Reddus is that you would use what's called Reddis cluster. And Reddis cluster manages this kind of sharding for you. Um, and it does this not actually using consistent hashing. It uses what's called hash slots. And so it
has something like 60,000 hash slots that it distributes across each of these different Reddus nodes. It handles the distribution into which hash slot any given user is in and thus which Reddice node they're in. Um and then it will all
be handled within what is called as I said reddis cluster and so that would be an easy way to handle this but the main conceptual thing for you to know into multiple instances and thus we need to shard right easy enough.
Um now the next thing that we should talk about then um again I'm going out of order is the availability over consistency and so how do we ensure that we have high availability and that we're also fault tolerant right and so if we
come back here what happens if Reddus fails what happens if any of these particular instances fail if Alice's bucket is on this particular node and this node fails well then now Alice can't be rate limited okay and so the
about is well what happens if that did happen and then we can talk about how we want to prevent it and so if that did happen then we have two options. Option one is fail open and option two is fail close. This is common terminology when
you discuss rate limiters. Fail open means our rate limiter is down and thus every single request should get through. Fail close is the opposite. Our rate limiter is down and now no requests should get through. And so you'll
interviewer in order to understand the requirements of this particular system. rate limiter for some sort of a social network. And so in the case of failing network. And so in the case of failing open, we would be kind of no longer
protecting all of the services that we were here to protect. And it may introduce a bunch of issues downstream. Like there was a rate limiter here for a reason. And it's probably because there are limits to how many times we can read
from our database or our cache or how many uh you know times we can compute something algorithmically within any of our microservices given the limitations that we have in CPU or even GPU respectively. Right? So in our case if
we were to fail open we would basically say just go for it send all requests and then these microservices one by one might be back here and might die and go offline. we might have this cascading set of failures that are even worse. On
the other hand, if we fail close, then now our site is down and you're going to are reporting, oh no, Facebook, Instagram, whatever we're designing this rate limit for is down and that's maybe not good either. There's no right or
you're going to do here is you're going to fail close. The responsibility of the services to some degree. uh and thus if it's down then it needs to take what is the strictest um protection mechanism possible and that is to to reject
everything. Um I will note that there's there's oftent times in real production you would do here than just this binary fail open or close like you can keep gateways themselves of course have memory and so maybe you have like a
single counter in order to do a fixed window counter such that if these fell the fixed window counter using the the doesn't matter that we don't have the coordination between multiple gateway
like this is just a temporary thing while Reddis gets back up. It's better than nothing. It's better than failing open or failing close. At least we still have some rate limiting capacity. So if any of these go down, that's what we
we make sure that a I guess none of these go down and two that you know if they do go down, we get them up as as quickly as possible. And the key as is the case with most distributed systems is replicas,
right? So we can we can configure a replication factor such that each one of our reddish shards each one of our nodes here have one or even two replicas such that all data that gets written to them also then gets propagated to its replica
and if one of these were to go down then its replica would be promoted and all of the reads would then come to the replica instead. Now, similarly like we talked about with um with sharding, Reddis cluster
actually supports this for you. And so with Reddis cluster, sorry about that construction going on. I'll see if I can get that out in post. Um but similar to to to sharding with Reddis cluster, you can configure a number of these backups.
And these backups use async replication. So it's not perfect. We're opting for high availability instead of consistency. That's the trade-off here. consistency. That's the trade-off here. So a write happens um if this fails you
asynchronously then yeah we'll be missing some data there but it's not the end of the world like now we think Alice is at 99 requests instead of 100 right she got one extra request off of us but no big deal so the key to uh the high
availability and the fault tolerance is sharding and read replicas okay and reddis cluster can satisfy both of those now let's talk about the low latency sure that we're sub 10 millisecond latency? Well, every single check now is
to Reddus and this is going to add latency to every single request of course and so Reddus operations are typically sub millisecond, but the network overhead here can be in some cases several milliseconds per request,
right? And then the fact that we have you know these larger requests might make them even slightly longer. Um, and so the most important optimization that connection pooling. And this is so instead of establishing a new TCP
connection to Reddus for each rate limit check, your API gateway is going to connections here. And this is going to eliminate that TCP handshake overhead, milliseconds depending on your network distance. Okay. Um, and we're just going
to reuse those same TCP connections. Now, this is interesting to say in your interview and you should talk to your interviewer about kind of TCP connection clients will handle connection pooling automatically for you. I don't know a
single one that doesn't. It would be crazy if it doesn't. Um, but you may need to tune the pool size based on your request volume and the Reddus response time. So, this is a good thing to know. Um, but in your interviewer, you should
understand that you know this connection pooling will likely be be handled for you by whatever Reddus client you use. The other additional interesting thing to talk about here when it comes to latency is the geographic distribution.
want to make sure that your rate limiter and even your gateway are as close to your users as possible. And so if you have users in Tokyo, then maybe you have a gateway that is somewhere in Asia or somewhere in Japan. And subsequently
Reddus, your Reddus instance is located or colllocated with your gateway ideally even in the same data center as close as possible. Right? These two servers might even be right next to each other to try to minimize that latency as much as
should be feeling pretty good. We have satisfied all of our functional non-functional requirements. But there's one more thing I want to talk to you all comes up in interviews. And I want to make sure that you guys are as well
prepared as possible. And that's how do we handle dynamic rule configurations. assumed that there were static rules like maybe when the gateway was deployed it had some basic rules which said the token refill rate and you know the the
the the token count in the bucket and so we always just use these rates these change it you would need to redeploy your gateway. Now you could also store different things, but we've assumed thus far that they are static. And so what
happens if they were configurable as is the case in most production systems? And rules for different users and different types of things like we talked about would you handle that? Well, let's talk through a couple of options. The first
maybe silly option would be that you your system has a database. This is a database, I'm sure, that your microservices are talking to. And it could store something like last, you know, whatever your rules are, which
know, whatever your rules are, which premium users, last refill or excuse me, refill rate, etc., right? And your gateway could maybe just periodically pull. And so maybe every 20 seconds it pulls like this. Okay, that's an option.
Now, it's not an ideal option because a we have this 20 seconds delay here or 10 seconds delay or even a 5-second delay and you could make it 1 second, but now you're just burning unnecessary gateway CPU that should be doing other things in
order to do this constant pulling, right? So, that's not great. You can like you definitely don't need the database in some of in each of these Reddus shards have that key value with
all of the rules and periodically pull in the rules. Maybe even each time you check a rate limit request, check the actual rules, right? Look up the key rules have changed at all. This is just going to add additional operations to
every single check and it's going to increase your latency unnecessarily considering rules probably aren't going to change that often. So it's an option to change that often. So it's an option but again probably not the best option.
The best option is that you can use a pushbase configuration and actually pushbase configuration and actually zookeeper a bit outdated nowadays I must admit or etc. These are options here. The latter of
which kind of being a bit more invogue than than the old school zookeeper, but I think conceptually the same general thing. And so what these are is that thing. And so what these are is that these are designed in order to maintain
this distributed configuration management. And so the rules can be stored here. And not only can the gateway when it comes online ask for the rules and then store those rules importantly in memory. And it's going to
doesn't have to do a network check every time. It has those rules there. But it time. It has those rules there. But it can also subscribe to watch for changes. And so what it can do is that then opens up a persistent TCP connection such that
up a persistent TCP connection such that anytime a rule changes in Zookeeper that gets pushed over that open TCP connection and then the gateway can update its rules in memory. And so this saves all of the issues with the or
previous two approaches which is that we don't have any additional latency or network requests because the rules are kept here and we don't have to pull. Zookeeper is just going to push. It's ready.
our deep dives and we have a pretty comprehensive design of a distributed rate limiter. Now, if you are a mid-level candidate, then the expectation is that you're going to have more 80% breadth and 20% depth. And so,
I would expect from you as an uh as an interviewer, I would expect that you algorithms and you make a choice and justify that choice appropriately. You them perfectly in depth, but conceptually you should understand them.
limiter would make the most sense existing on the edge of our system and you should propose something in order to share state globally whether that's reddis memcache or otherwise and be able to justify why you're adding it. Beyond
questions as I probe as an interviewer when I point out that there's limitations with a single reddus instance for example or when I ask questions about what happens when something goes down. You should be able
to problem solve and arrive at reasonable answers given my probing and me leading you to the answers. Now for senior candidates on the hand I expect identifying those issues proactively. You're telling me the interviewer that
isn't going to cut it here. Here's the math that proves why. And here's how going to be more proactive in those ways. Talking to me about fault tolerance, but all the things that could potentially go wrong if the system gets
overwhelmed. failing open, failing closed, etc. And then as a staff is not asked nearly as often of staff candidates. Um, it's a little bit maybe maybe. But if you are asked this as a staff candidate, I'm expecting a lot
proactively lead through just about everything that we've talked about here maybe. U but then you'll also guide me towards conversations of things that you know really well. Maybe you have deep experience of Reddis cluster and you can
tell me about times where you had to or you accidentally or incorrectly managed mistakes there and why it's important that it needs to be a particular size. Or you proactively recognize the race condition and you explain to me how
order to solve the race condition. Right? That's a little bit more of an advanced concept. So uh that's how you would break it down. Mid-level um senior and staff respectively. Um, let's see. Anything else that I want
to say here? I will put this diagram in the description. So, if you want it, go videos. Plenty more videos on this YouTube channel will be coming. And 100,000 subscribers at time of recording this. If you liked it, please like,
subscribe, leave a comment down below. I'll answer those. And uh, as always, interview. You guys are going to do great. Take care.