educative.io

Reg Rate Limiter Algorithm | Sliding window log | Slide 4

Courses
, ,
#1

Hello,
Can someone explain the statement in slide 4 of the illustration for Sliding Window Log Algorithm? It reads as follows -
A new request comes in at 02:25, and we start our new window from there. We keep one last window (from 01:25 to 02:25) in the log. The old data is removed from the log, and the size is reduced accordingly

I am not able to understand the timestamp.

1 Like
#2

Hi Spandan Mishra,

In the example, we have a maximum rate limit of two requests in a minute. In other words, the log size is set to two. So the number of requests per minute can’t increase the limit 2.

Let’s break down the steps described in the slide 4:

  1. A new request arrives at the system’s timestamp 02:25.
  2. The algorithm checks the time frame or window to determine which requests are within the latest time frame and which ones are outdated. The latest time frame is defined according to the timestamp of the new request, spanning the last minute from 01:25 to 02:25.
  3. Any requests sent before 01:25 are considered outdated because they fall outside the latest time frame, which covers the past minute. Since the log has reached its maximum size limit, two outdated timestamps are removed from the log to make space for new requests.
  4. After removing the outdated timestamps, the log size becomes 2, indicating that there is space available in the log to accommodate the new request.
  5. Since there is now space available in the log after removing outdated entries, the new request with the timestamp 02:25 is accepted and added to the log.

I hope this clears the doubts.

Happy learning!