Hone logo
Hone
Problems

Go Rate Limiter Middleware

Rate limiting is a crucial technique for protecting APIs and services from abuse, preventing denial-of-service attacks, and ensuring fair resource allocation. This challenge asks you to implement a rate limiter middleware in Go that restricts the number of requests a client can make within a given time window. This middleware will intercept incoming requests, check against the rate limit, and either allow the request to proceed or reject it with an appropriate error response.

Problem Description

You are tasked with creating a Go middleware that implements a token bucket rate limiter. The middleware should:

  1. Accept Configuration: Take a RateLimit struct as input, containing the Capacity (maximum number of requests allowed) and RefillRate (number of tokens added per second).
  2. Identify Clients: Identify clients based on their IP address. The middleware should extract the client's IP address from the incoming request.
  3. Token Bucket Logic: Maintain a token bucket for each client. The bucket should be refilled at the specified RefillRate.
  4. Request Handling: For each incoming request:
    • Check if the client has enough tokens in their bucket.
    • If tokens are available, consume a token and allow the request to proceed to the next handler in the chain.
    • If no tokens are available, reject the request with a 429 Too Many Requests HTTP status code and a descriptive error message.
  5. Middleware Interface: Implement the middleware as a function that takes an http.Handler and returns a new http.Handler. This new handler will wrap the original handler with the rate limiting logic.

Examples

Example 1:

Input:
RateLimit{Capacity: 5, RefillRate: 1}
Incoming requests from IP "192.168.1.1":
- Request 1: Allowed (bucket has 5 tokens)
- Request 2: Allowed (bucket has 4 tokens)
- Request 3: Allowed (bucket has 3 tokens)
- Request 4: Allowed (bucket has 2 tokens)
- Request 5: Allowed (bucket has 1 token)
- Request 6: Rejected (bucket is empty, returns 429)
- Request 7: Rejected (bucket is empty, returns 429)
After 1 second: Bucket refilled to 2 tokens (due to RefillRate of 1 token/second)
- Request 8: Allowed (bucket has 2 tokens)

Output: Requests 1-5 are processed. Requests 6 and 7 return 429. Request 8 is processed.

Explanation: The token bucket starts with 5 tokens. Each request consumes a token. After 1 second, the bucket refills, allowing another request.

Example 2:

Input:
RateLimit{Capacity: 2, RefillRate: 0.5}
Incoming requests from IP "10.0.0.1":
- Request 1: Allowed
- Request 2: Allowed
- Request 3: Rejected
- Request 4: Rejected
After 1 second: Bucket refilled to 2.5 tokens (0.5 tokens/second * 1 second)
- Request 5: Allowed (bucket has 2.5 tokens, effectively 2)

Output: Requests 1 and 2 are processed. Requests 3 and 4 return 429. Request 5 is processed.

Explanation: The bucket refills at a rate of 0.5 tokens per second. Fractional tokens are handled correctly (e.g., 2.5 tokens).

Example 3: (Edge Case - Concurrent Requests)

Input:
RateLimit{Capacity: 3, RefillRate: 1}
Incoming requests from IP "172.16.0.1" (concurrently):
- Request 1: Allowed
- Request 2: Allowed
- Request 3: Allowed
- Request 4: Rejected
- Request 5: Rejected

Output: Requests 1, 2, and 3 are processed. Requests 4 and 5 return 429.

Explanation: The middleware must handle concurrent requests safely, ensuring that the token bucket is accessed and updated atomically to prevent race conditions.

Constraints

  • RateLimit Capacity: Must be between 1 and 100 (inclusive).
  • RefillRate: Must be a positive floating-point number (e.g., 0.5, 1.0, 2.0).
  • Concurrency: The middleware must be thread-safe and handle concurrent requests correctly.
  • IP Address Extraction: Assume the IP address is available in the req.RemoteAddr field of the http.Request struct.
  • Performance: The middleware should introduce minimal overhead to the request processing pipeline. Avoid unnecessary allocations or complex operations.

Notes

  • Consider using a sync.Mutex to protect access to the token bucket for each client.
  • You can use time.NewTicker to implement the token refill mechanism.
  • The http.Handler interface provides flexibility in how you integrate the middleware with existing applications.
  • Focus on correctness and thread safety first, then optimize for performance if necessary.
  • Error handling should be minimal; simply return a 429 status code with a descriptive message. No need to log errors.
  • The token bucket should be reset when a client's IP address is no longer seen for a certain period (e.g., 1 minute). This is not required for the base implementation but is a good consideration for a production-ready rate limiter.
Loading editor...
go