API Request Rate Limiter in Go

Rate limiting is a crucial technique for protecting APIs from abuse, preventing denial-of-service attacks, and ensuring fair usage. This challenge asks you to implement a basic rate limiter in Go that restricts the number of requests a user can make within a given time window. A well-implemented rate limiter is essential for maintaining API stability and a positive user experience.

Problem Description

You are tasked with creating a RateLimiter struct in Go that enforces a rate limit on incoming requests. The rate limiter should track requests per user (identified by a unique key, such as a user ID or API key) and reject requests exceeding the defined limit.

What needs to be achieved:

• Implement a RateLimiter struct with a configurable rate limit (requests per time window) and a time window duration.
• Provide a AllowRequest(userID string) bool method that checks if a request from a given user is allowed based on the configured rate limit. If the request is allowed, it should increment the request count for that user. If the request is denied, it should not increment the request count.
• The rate limiter should use a sliding window approach to track requests. This means that the request count should be reset based on the time window, not just at fixed intervals.

Key Requirements:

• Sliding Window: The rate limiting should be based on a sliding window of time.
• User Identification: The rate limiter must be able to identify requests by a unique user ID.
• Configurable Rate Limit: The rate limit (requests per time window) should be configurable.
• Configurable Time Window: The time window duration should be configurable.
• Thread Safety: The rate limiter should be thread-safe to handle concurrent requests.

Expected Behavior:

• AllowRequest(userID) should return true if the request is allowed (i.e., the user has not exceeded the rate limit within the time window).
• AllowRequest(userID) should return false if the request is denied (i.e., the user has exceeded the rate limit within the time window).
• When a request is allowed, the request count for the user should be incremented.
• The request count for each user should be automatically reset when it falls outside the time window.

Edge Cases to Consider:

• New User: The rate limiter should handle requests from users who have not made any previous requests.
• Concurrent Requests: The rate limiter must be thread-safe to handle multiple requests from the same user concurrently.
• Time Window Boundary: Consider how the rate limiter behaves when a request is made just before or after the time window boundary.
• Zero Rate Limit: Handle the case where the rate limit is set to zero.

Examples

Example 1:

Input: RateLimit: 2 requests per second, userID: "user123"
Sequence of calls to AllowRequest("user123"):
1. AllowRequest("user123") -> true
2. AllowRequest("user123") -> true
3. AllowRequest("user123") -> false
4. Wait 1 second
5. AllowRequest("user123") -> true

Explanation: The first two requests are allowed. The third request is denied because the rate limit (2 requests per second) has been exceeded. After waiting one second, the rate limit resets, and the fourth request is allowed.

Example 2:

Input: RateLimit: 5 requests per 10 seconds, userID: "user456"
Sequence of calls to AllowRequest("user456"):
1. AllowRequest("user456") -> true
2. AllowRequest("user456") -> true
3. AllowRequest("user456") -> true
4. AllowRequest("user456") -> true
5. AllowRequest("user456") -> true
6. AllowRequest("user456") -> false
7. Wait 5 seconds
8. AllowRequest("user456") -> true

Explanation: The first five requests are allowed. The sixth request is denied. After waiting 5 seconds, the rate limit partially resets, but the user still has some requests remaining within the 10-second window.

Example 3: (Edge Case - New User)

Input: RateLimit: 3 requests per 30 seconds, userID: "newuser"
Sequence of calls to AllowRequest("newuser"):
1. AllowRequest("newuser") -> true
2. AllowRequest("newuser") -> true
3. AllowRequest("newuser") -> true
4. AllowRequest("newuser") -> false

Explanation: A new user is treated the same as an existing user. The first three requests are allowed, and the fourth is denied.

Constraints

• Rate Limit: The rate limit (requests per time window) must be a positive integer.
• Time Window: The time window duration must be a positive duration (e.g., 1 second, 1 minute).
• User ID: The user ID must be a string.
• Concurrency: The rate limiter must be able to handle at least 100 concurrent requests without significant performance degradation.
• Memory Usage: The memory usage of the rate limiter should be reasonable, especially for a large number of users.

Notes

• Consider using a data structure like a map to store request counts for each user.
• You can use the time.Now() function to get the current time.
• The sync.Mutex type can be used to ensure thread safety.
• A sliding window implementation typically involves tracking timestamps of requests.
• Focus on correctness and thread safety first, then optimize for performance if necessary. A simple, correct solution is better than a complex, potentially buggy, optimized solution.
• You don't need to implement any external storage (e.g., database). The rate limiter should be in-memory.