HEY ROBOT

Day 14/60 - System Design Series 🚀 Design a Rate Limiter - Part 4 Rate limiter in a distributed environment: Scaling the system to support multiple servers and concurrent threads is a different story. There are two challenges: - Race condition - Synchronization issue Race condition: - Assume the counter value in Redis is 3. - If two requests concurrently read the counter value before either of them writes the value back, each will increment the counter value by one and write it back without checking the other thread. - Both requests (threads) believe they have the correct counter value 4. - However, the correct counter value should be 5. Sorted Set Solution: Locks are the most obvious solution for solving race conditions. However, locks will significantly slow down the system. Sorted sets data structure in Redis can be used to solve this problem. Instead of keeping a count, Redis keeps a timestamped list of every action the user has taken recently, using a sorted set. Every time a user tries to do something, five things happen as one uninterruptible unit (atomic transaction): 1. Throw out old entries delete anything older than the rate-limit window (e.g., older than 1 minute ago) 2. Look at what's left fetch all the remaining timestamps 3. Record this attempt add the current timestamp to the set (whether or not it will end up being allowed). 4. Set an expiration so Redis automatically cleans up the whole set if the user goes inactive. 5. Decide, after the fact count how many timestamps are left. If that's more than the limit, reject the action. You can also check the most recent previous timestamp to enforce a "not too soon after the last one" rule (like max 2 actions per 3 seconds). Because all five steps happen together as one atomic block, there's no gap where two simultaneous requests could both "read" the same stale count and both get approved. Whoever's transaction commits first sees the other's timestamp. The trade-off Because the timestamp is added before the decision is made, a rejected attempt still leaves a mark in the set. So if someone hammers the limit continuously, their rejected attempts keep the set "full," which can block every subsequent attempt rather than letting some through periodically. Synchronization issue: To support millions of users, one rate limiter server might not be enough to handle traffic. When multiple rate limiter servers are used, synchronization is required. If client 1 sends request to rate limiter 1 and client 2 sends request to rate limiter 2. If no synchronization happens, rate limiter 1 does not contain any data about client 2. Thus, the rate limiter cannot work properly. One possible solution is to use sticky sessions but its neither scalable nor flexible. A better approach is to use centralized data stores like redis. #SystemDesign #DistributedSystem

Day 13/60 - System Design Series 🚀 Design a Rate Limiter - Part 3 High Level Architecture: Idea is simple, at the high level, we need a counter to keep track of how many requests are sent from the same user, IP address, etc. If the counter is larger than the limit, the request is disallowed. Where shall we store counters? Using the database is not a good idea due to slowness of disk access. In-memory cache is chosen because it is fast and supports time-based expiration strategy. Redis is best option it offers two commands: INCR and EXPIRE. INCR: increases stored counter by 1. EXPIRE: sets a timeout for the counter. If timeout expires, counter is automatically expired. Design Deep Dive: High level does not answer following questions: - How are rate limiting rules created? Where are the rules stores? - How to handle requests that are rate limited? Rate Limiting rules examples - Please check following image. Exceeding the rate limit - In case a request is rate limited, APIs return HTTP response code 429 (too many requests) to the client. Depending on the use case, we can enqueue the rate-limited requests to be processed later. Rate limiter headers - X-Ratelimit-Remaining: Remaining number of allowed requests within the window. X-Ratelimit-Limit: Indicates how many calls the client can make per time window. X-Ratelimit-Retry-After: Number of seconds to wait until you can make a request again without being throttled. Detailed Design Flow: - Rules are stored on the disk. Workers frequently pull rules from the disk and store them in cache. - When a client sends a request to the server, the request is sent to the rate limiter middleware first. - Rate limiter middleware loads rules from the cache. It fetches counters and last request timestamp from redis cache. Based on the response, rate limiter decides: - if the request is not rate limited, it is forwarded to API servers. - if the request is rate limited, rate limiter returns 429 too many requests error to the client. In the meantime, the request is either dropped or forwarded to the enqueue. Rate limiter in a distributed environment: Scaling the system to support multiple servers and concurrent threads is a different story. There are two challenges: - Race condition - Synchronization issue Let's discuss these challenges in next post!! #SystemDesign #DistributedSystems