Implement a Fixed Window Rate Limiter in Go

Web applications often need to protect themselves from abuse or overload by limiting the number of requests a client can make within a certain time frame. This challenge asks you to implement a fixed window rate limiter as middleware for an HTTP server in Go. This is a fundamental building block for robust API design.

Problem Description

You need to create an HTTP middleware function in Go that enforces a rate limit on incoming requests. The rate limiting strategy to implement is the "Fixed Window" algorithm.

Key Requirements:

1. Middleware Function: Create a function that takes an http.Handler as input and returns a new http.Handler. This new handler should wrap the original handler, applying rate limiting before it's executed.
2. Fixed Window Algorithm:
   • Requests are counted within discrete time windows (e.g., 60 seconds).
   • A client is identified by its IP address.
   • Each IP address has a maximum number of requests allowed within a given window.
   • When a new request arrives, check if the client has exceeded its limit for the current window.
   • If the limit is exceeded, reject the request with an appropriate HTTP status code (e.g., 429 Too Many Requests).
   • If the limit is not exceeded, allow the request to proceed and increment the counter for that IP in the current window.
3. Configuration: The rate limiter should be configurable with:
   • The maximum number of requests allowed per window (limit).
   • The duration of the time window (windowSize).
4. Data Storage: You'll need a mechanism to store the request counts and the start times of the windows for each IP address. A sync.Map or a regular map protected by a sync.Mutex can be used for this. For simplicity in this challenge, you can assume a single-server environment and do not need to consider distributed systems.
5. Error Handling: When a rate limit is exceeded, the middleware should respond with http.StatusTooManyRequests and an informative body.

Expected Behavior:

• A client making limit requests within windowSize will be allowed.
• The limit + 1-th request from the same client within the same windowSize will be rejected.
• After windowSize has passed since the start of the window, a new window begins, and the counters reset for all IPs.

Edge Cases to Consider:

• Concurrent requests from different IPs.
• Concurrent requests from the same IP (though this is naturally handled by the rate limiting logic).
• What happens when windowSize is very small or very large.
• Handling of invalid IP addresses (though for this challenge, you can assume valid IPv4/IPv6 addresses).

Examples

Example 1: First few requests within the limit

• Configuration: limit = 5, windowSize = 10s
• Scenario: Client 192.168.1.100 makes 3 requests over 5 seconds.

Request 1 (from 192.168.1.100) at T=0s: Allowed. Counter for 192.168.1.100 in window [0s, 10s) is 1.
Request 2 (from 192.168.1.100) at T=2s: Allowed. Counter for 192.168.1.100 in window [0s, 10s) is 2.
Request 3 (from 192.168.1.100) at T=4s: Allowed. Counter for 192.168.1.100 in window [0s, 10s) is 3.

Example 2: Exceeding the limit

• Configuration: limit = 5, windowSize = 10s
• Scenario: Client 192.168.1.100 has already made 5 requests within the current 10s window. A 6th request arrives.

Request 6 (from 192.168.1.100) at T=8s: Rejected. Status: 429 Too Many Requests. Counter for 192.168.1.100 in window [0s, 10s) remains 5 (or attempt to increment to 6, but it's denied).

Example 3: New window begins

• Configuration: limit = 5, windowSize = 10s
• Scenario: Client 192.168.1.100 made 5 requests between T=0s and T=9s. The window [0s, 10s) ends. A new request comes at T=11s.

Request 1 (from 192.168.1.100) at T=0s: Allowed. Counter for 192.168.1.100 in window [0s, 10s) is 1.
... (4 more requests within [0s, 10s))
Request 5 (from 192.168.1.100) at T=9s: Allowed. Counter for 192.168.1.100 in window [0s, 10s) is 5.

--- Window [0s, 10s) ends ---

Request 6 (from 192.168.1.100) at T=11s: Allowed. A new window [10s, 20s) begins. Counter for 192.168.1.100 in window [10s, 20s) is 1.

Constraints

• 1 <= limit <= 1000
• 1s <= windowSize <= 600s (1 minute)
• The middleware should handle incoming requests efficiently. The time to check the rate limit should be minimal.
• The underlying HTTP server and handler execution time are not factored into the rate limiting logic itself.

Notes

• You can use net/http for building the server and handlers.
• The time package will be crucial for managing window durations.
• Consider how to extract the client's IP address from http.Request. Be aware of potential proxy headers like X-Forwarded-For. For this challenge, you can simplify by using r.RemoteAddr or a specific header if you're simulating behind a proxy.
• The data structure for tracking requests should be thread-safe if your HTTP server is configured to handle requests concurrently (which is the default for net/http).
• Think about how to reset window counts. A common approach is to associate each IP with a timestamp and a count. When a request arrives, check if the current time is beyond the timestamp + windowSize. If it is, reset the timestamp and count to the current time and 1, respectively. Otherwise, increment the count if it's within the limit.