Sliding Window Log Algorithm

We keep track of the timestamp for each request. When new request comes in, we double check the history and see if we need to pop out the old requests.

For example:

When allowing 2 requests per minute. First we allow a time box of 2 requests.

• From 1:00:00: time box is empty
• From 1:00:01: time box has (1/2) requests
• From 1:00:30: time box has (2/2) requests
• From 1:00:50: we reject the new request comes in. Time box hsa (2/2) requests
  • However in the book it says they remain the timestamp in the box - I don't think this is correct
• From 1:01:40: we remove all the request that's before 1:00:40 in the timebox, therefore we cross out 1:00:01 and 1:00:50. We add a request 1:01:40 in

Pros and cons

Pros

• Accurate

Cons

• Lots of memory consumption