Count Blocked Rate-Limited Requests

You are given an in-memory request log for a web platform. Each log entry has:

• timestamp: an ISO-8601 UTC timestamp
• request_ip: the client IPv4 address
• host: the hostname being requested

The log is already sorted by time in ascending order, and you may assume it fits in memory.

A request is evaluated against a sliding window of T seconds. For a request at time t, only earlier requests with timestamps in the interval (t - T, t) are counted. A request that happened exactly T seconds earlier is not in the window.

Important rules:

• A request that gets blocked must still be counted in the history for future requests.
• If multiple requests have the same timestamp, process them in input order.
• In part 2, if a request violates both rules, it should be counted as one blocked request, not two.

Part 1: Per-IP rate limiting

Implement logic to count how many requests would be blocked by this rule:

• A request from IP x is blocked if there have already been at least IPReqMax requests from the same IP in the previous T seconds.

In other words, the current request is blocked when:

• count(previous requests from same IP in (t - T, t)) >= IPReqMax

Example

Input log:

timestamp,request_ip,host
2024-01-01T00:00:00+00:00,127.0.0.1,example1.com
2024-01-01T00:00:01+00:00,127.0.0.1,example2.com
2024-01-01T00:01:02+00:00,127.0.0.1,example1.com
2024-01-01T00:01:03+00:00,127.0.0.1,example2.com
2024-01-01T00:01:04+00:00,127.0.0.1,example1.com
2024-01-01T00:02:04+00:00,127.0.0.1,example1.com

With IPReqMax = 1 and T = 60:

• Request 1 -> succeed
• Request 2 -> blocked
• Request 3 -> succeed
• Request 4 -> blocked
• Request 5 -> blocked
• Request 6 -> succeed

So the answer is 3 blocked requests.

Part 2: Per-IP and per-(IP, host) rate limiting

Now add a second rule:

• A request from IP x to host h is also blocked if there have already been at least IPHostReqMax requests from the same IP to the same host in the previous T seconds.

A request is blocked if either of these is true:

1. count(previous requests from same IP in (t - T, t)) >= IPReqMax
2. count(previous requests from same IP and same host in (t - T, t)) >= IPHostReqMax

Again, blocked requests still contribute to both counters for future requests.

Example

Input log:

timestamp,request_ip,host
2024-01-01T00:00:00+00:00,127.0.0.1,example1.com
2024-01-01T00:00:01+00:00,127.0.0.1,example2.com
2024-01-01T00:00:10+00:00,127.0.0.1,example1.com
2024-01-01T00:00:11+00:00,127.0.0.1,example3.com
2024-01-01T00:01:04+00:00,127.0.0.1,example3.com
2024-01-01T00:01:11+00:00,127.0.0.1,example1.com

With IPReqMax = 3, IPHostReqMax = 1, and T = 60:

• Request 1 -> succeed
• Request 2 -> succeed
• Request 3 -> blocked by per-(IP, host) rule
• Request 4 -> blocked by per-IP rule
• Request 5 -> blocked by per-(IP, host) rule
• Request 6 -> succeed

So the answer is 3 blocked requests.

Task

Write an efficient function or program that, given the sorted request log and the parameters:

• T
• IPReqMax
• optionally IPHostReqMax

returns:

1. the number of blocked requests under the per-IP rule only, and
2. the number of blocked requests under the combined per-IP and per-(IP, host) rules.

Aim for an approach that is efficient for large logs loaded into memory.

Count Blocked Rate-Limited Requests

Constraints

• Logs are sorted ascending by timestamp
• Same-timestamp requests are processed in input order

Hints

1. Maintain deques of timestamps per key and evict expired entries.