Loading...
Rate Limiting helps to protect services against abusive behaviors targeting the application layer like Denial-of-service (DOS) attacks, brute-force password attempts, brute-force credit card transactions, etc. These attacks are usually a barrage of HTTP/S requests which may look like they are coming from real users, but are typically generated by machines (or bots). As a result, these attacks are often harder to detect and can more easily bring down a service, application, or an API.
Rate limiting is also used to prevent revenue loss, to reduce infrastructure costs, to stop spam, and to stop online harassment. Following is a list of scenarios that can benefit from Rate limiting by making a service (or API) more reliable:
Scale requirements:
Other requirements:
Assumptions
Storage Estimates: N/A since data retention is not needed as stated in the requirement.
Bandwidth Estimates: If every write operation has an average size of 500 bytes, with 1 million write operations daily, we will have approximately 500MB of incoming data daily. For the read requests, given the 100:1 read to write ratio, there will be 100 million read requests daily. Therefore, the service will serve approximately 50GB of data daily for the read requests.
Memory Estimates for Cache: If we want to cache some of the hot URLs that are frequently accessed, and let's say we want to cache 20% of daily read requests, we would need to cache 20 million URLs. Assuming each URL takes 500 bytes in memory, we would need about 10GB of memory.
Our system can expose the following REST APIs:
POST /shouldAllowRequest
Request body:
{
"clientId": "123",
"timestamp": "2023-07-13T07:20:50.52Z"
}
Response:
{ "allowed": true }
or
{ "allowed": false }
Database Type
Given the nature of the data we are dealing with (mostly key-value pairs for users and their request counts), and the requirement for high speed reads and writes, a NoSQL database would be a good fit. Specifically, an in-memory data store like Redis could be used due to its high performance and features such as atomic operations and TTL (time-to-live) on keys, which can be handy for implementing the rate limiter.
Database Partitioning
Given the massive scale of the system (100 million daily active users), we would need to partition or shard our data to distribute it across multiple databases or servers for improved performance and scalability. There are several partitioning methods, but for our use case, a simple partitioning scheme such as consistent hashing could be used. Consistent hashing would distribute our users evenly across the database nodes and minimize data movement when nodes are added or removed.
Database Replication
Since data retention is not a requirement, and our rate limiting doesn't need to be super strict or fair, you can afford to lose some data in the event of a node going down. Also, without the need for long-term data storage (retention requirement is 0 day), the cost and complexity of replication might not be justified.
In your scenario, each node could independently rate limit requests based on its own data. If a node fails, the clients it was serving would be redistributed among the remaining nodes. Their request counts would effectively be reset, as the new node would have no knowledge of their previous requests. Depending on your system's rate limits and the frequency of node failures, this might result in some clients being able to exceed their rate limits, but as you've mentioned, this isn't a major concern in your case.
Data Retention and Cleanup
In the context of rate limiting, data retention isn't typically a major concern as we only need to track the user requests for a short period (the duration of the rate limit window). We do not need to keep this data once it's no longer relevant. Redis provides a feature called TTL (time-to-live), which automatically removes keys after a specified duration. We can set the TTL of each user key to the window size of our rate limiter. This way, the data would automatically be cleaned up by Redis once it's no longer relevant. This not only saves space but also simplifies the system as we do not have to manage the cleanup process ourselves.
Concurrency
Concurrency is a significant concern when designing a system like a rate limiter. It should accurately track and limit requests without errors.
Let's first understand what the problem could be. Consider a scenario where a user sends two requests at the same time, and these requests are processed concurrently by the server. Both requests fetch the user's current request count (let's say it's 9 and the limit is 10), increment it (both get a new count of 10), and then save it back to the database. The user's final request count in the database is 10, but it should be 11. Hence, the user has effectively exceeded their rate limit without the system noticing.
Here's how we can address this concurrency issue:
Atomic Operations: In Redis, you can use multi/exec commands to ensure that all commands in the block are executed sequentially without any interference from other clients, which effectively solves the concurrency problem. Similarly, most databases support transactions that allow you to perform multiple operations as a single, atomic operation. Here's an example of how you could use Redis' multi/exec commands:
MULTI
INCR user:request_count
EXPIRE user:request_count 60
EXEC
In this example, the INCR and EXPIRE commands will be executed as a single, atomic operation. If two requests come in at the same time, one will have to wait for the other to finish its multi/exec block before it can start its own, ensuring the request count is updated correctly. Distributed Locks: In a distributed system where multiple nodes might be updating a user's request count, you could use a distributed lock to ensure that only one node can update the count at a time. This is a more complex solution and could impact performance due to the time taken to acquire and release locks, so it's generally only used when necessary. Sharding: Distributing requests from the same user to the same server (also known as sticky sessions) can also help with concurrency. If all requests from the same user go to the same server, then that server can use local locks or single-threaded operations to ensure the request count is updated correctly.
Clients (e.g. browsers, mobile apps) request some services via API Gateway.
Services, who need rate limiting, send is_allowed() calls to Rate Limiting Service (RLS).
RLS, using configuration stored in the database, and buckets stored in Cache, decide if the request is allowed or not.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
The choice of a rate-limiting algorithm often depends on your specific use case and system requirements, including factors such as how strictly you need to enforce the rate limits and how much complexity you're willing to manage. Here are a few common rate-limiting algorithms and their trade-offs:
Fixed Window Counter
This simple algorithm allows a fixed number of requests in each time window, such as 1000 requests per hour. The problem with the fixed window is that it does not prevent traffic spikes. For example, if a user makes all 1000 requests at the end of one hour and another 1000 at the start of the next hour, the system experiences a spike of 2000 requests. Here's the sample implementation for Fixed Window Counter:
counter = 0
WINDOW_SIZE = 3600 # 1 hour in seconds
RATE_LIMIT = 1000
def allow_request():
global counter
current_time = time.time()
# Reset the counter if we're in a new time window
if current_time > window_start_time + WINDOW_SIZE:
counter = 0
window_start_time = current_time
# Check if the request can be allowed
if counter < RATE_LIMIT:
counter += 1
return True
else:
return False
Sliding Window Log This algorithm keeps a log of all the requests from the past window and checks the number of requests before allowing a new one. This eliminates the problem of traffic spikes seen in the fixed window counter but requires more storage and computation since you're maintaining a log of requests. Here's a sample implementation of Sliding Window Log:
log = []
WINDOW_SIZE = 3600 # 1 hour in seconds
RATE_LIMIT = 1000
def allow_request():
current_time = time.time()
# Remove outdated requests from the log
while log and current_time - log[0] > WINDOW_SIZE:
log.pop(0)
# Check if the request can be allowed
if len(log) < RATE_LIMIT:
log.append(current_time)
return True
else:
return False
Token Bucket
This algorithm works like an actual bucket holding tokens. The bucket has a certain capacity, and tokens are added to the bucket at a fixed rate up to the maximum capacity. When a request arrives, the rate limiter tries to remove a token from the bucket. If a token is available (i.e., if the bucket is not empty), the request is allowed; otherwise, the request is rejected. The key characteristic of the Token Bucket algorithm is that it allows for burstiness as long as the average rate of requests doesn't exceed the token refill rate. In other words, it can handle a sudden influx of requests by using the tokens stored in the bucket.
tokens = 0
LAST_REQUEST_TIME = 0
TOKEN_RATE = 1 # 1 token per second
BUCKET_SIZE = 1000
def allow_request():
global tokens, LAST_REQUEST_TIME
current_time = time.time()
# Refill tokens based on the time passed
tokens += (current_time - LAST_REQUEST_TIME) * TOKEN_RATE
tokens = min(tokens, BUCKET_SIZE)
LAST_REQUEST_TIME = current_time
# Check if the request can be allowed
if tokens >= 1:
tokens -= 1
return True
else:
return False
One of the important challenges of this problem is the rapid number of requests. Earlier, we took the decision to store the bucket counters in an external cache service (e.g. Redis) instead of Rate Limiting Service. This allows us to replicate RLS servers and load-balance among them. Consistent hashing may be used to distribute the load evenly among them.
We need to make sure Cache service is scalable. Although the counters (at 32GB) would fit in one Cache server, we should still partition them so that one server does not receive overwhelming number of requests. A bucket is identified by a combination of user_id and API. We can use the hash of (user_id, API) combination as a portioning key.
Even with partitioning, a hot key issue is possible. If one user suddenly starts hitting one API rapidly, it may overwhelm the cache.
One mitigation would be for RLS to increment the counter locally, and update the bucket counter in one out of K (e.g. 10) times. We need to decide which buckets need this special logic, by configuration, or by auto-configuration based on monitoring.
RLS servers are stateless. Therefore, if one of the RLS servers becomes unavailable (crashes, network partition, extreme slowness, etc.), another can take over without a major downtime. A coordination service, e.g., ZooKeeper can be used to keep track of membership of the servers.
When a cache service becomes unavailable, that would be more challenging. Bucket counters would be lost. RLS may have to resort to blocking all requests (fail closed), or starting all the bucket counters from 0, allowing many requests which should be blocked.
We can add read backup replicas to cache service. By keeping the same information between the leader and the replicas, the replicas can take over for the leader in case the leader becomes unavailable.
We need to do careful performance measurement and analysis to decide if this is an effective approach. For example, if most of the rate limiters are configured for each second (e.g. 100 requests per second), the recovery from a replica may not be effective. If it takes more than 1 second for the replica to take over, it might not be worth the effort to synchronize data between the leader and the replicas. In that case, having a replica that is ready to take over for the leader (but does not have bucket numbers synchronized with the leader) may suffice.
On the other hand, if most of the rate limiters are of per-minute granularity (e.g., 10,000 requests per minute), the replication method would make sense.
In this solution, we restricted the RL configuration to user and rate. In the real world, there would be many more configurations:
It would require enrichment of the components we designed.