The sliding window mechanism monitors the timestamps of all requests occurring within a defined time interval, ensuring that the request rate remains within a specified limit.
let's walk through an example of a sliding window log algorithm with a request limit of 3 per minute. In this scenario, we want to log incoming requests and ensure that no more than 3 requests are accepted within any 1-minute window.
Let's say our system receives the following requests over a period of time:
12:00:00 - Request 1 (Accepted)
12:00:20 - Request 2 (Accepted)
12:00:35 - Request 3 (Accepted)
12:01:10 - Request 4 (Accepted)
12.01:15 - Request 5 (Rejected)
12:01:25 - Request 6 (Accepted)
12:01:30 - Request 7 (Rejected)
12:02:30 – Request 8 (Accepted)
Let’s elaborate on each step.
1. Requests 1, 2, and 3 (Accepted):
At 12:00:00, Request 1 is accepted, and its timestamp is logged.
At 12:00:20, Request 2 is accepted, and its timestamp is logged.
At 12:00:35, Request 3 is accepted, and its timestamp is logged.
At this point, the current window contains [Request 1, Request 2, Request 3], which is within the limit of 3 requests per minute.
2. Request 4 (Accepted):
When processing Request 4, the algorithm determines the time range from its timestamp to 60 seconds before (12:01:10 - 60 seconds = 12:00:10).
The algorithm then examines all timestamps within this time range and discards any timestamps that fall outside it. This ensures that only timestamps within the current window are considered.
In our example, Request 1's timestamp (12:00:00) falls outside the current window's time range (12:00:10 to 12:01:10) and is therefore discarded.
After discarding Request 1's timestamp, the algorithm counts the remaining timestamps within the current window (Request 2 and Request 3) and checks if the count is less than the maximum limit (3). Since the count is less than 3, Request 4 is accepted and added to the current window.
Accepted requests in the current window are : [R2, R3, R4]
Request 5 (rejected)
Request 5 is received at 12.01:15
The algorithm examines all timestamps within the determined time range (12:00:15 to 12:01:15) to check if any fall outside the current window.
In this example, none of the timestamps fall outside the current window's time range, so all previous timestamps (Request 2, Request 3, and Request 4) remain within the window.
The total count of accepted requests within this window is 3 (Request 2, Request 3, and Request 4).
Since the count of accepted requests is equal to the maximum limit of 3, there is no room to accept the new request (Request 5). Therefore, Request 5 is rejected due to the window being full.
Request 6 (Accepted)
Request 6 is received at 12:01:25.
The algorithm examines all timestamps within the determined time range (12:00:25 to 12:01:25) to check if any fall outside the current window.
In our example, Request 2's timestamp (12:00:20) falls outside the current window's time range (12:00:25 to 12:01:25) and is therefore discarded.
After discarding Request 2's timestamp, the algorithm counts the remaining timestamps within the current window (Request 3 and Request 4) and checks if the count is less than the maximum limit (3). Since the count is less than 3, Request 6 is accepted and added to the current window.
Request 7 (Rejected)
Request 7 is received at 12:01:30.
The algorithm examines all timestamps within the determined time range (12:00:30 to 12:01:30) to check if any fall outside the current window.
In this example, none of the timestamps fall outside the current window's time range, so all previously accepted timestamps (Request 3, Request 4, and Request 6) remain within the window.
The total count of accepted requests within this window is 3 (Request 3, Request 4, and Request 6).
Since the count of accepted requests is equal to the maximum limit of 3, there is no room to accept the new request (Request 7). Therefore, Request 7 is rejected due to the window being full.
Request 8 (Accepted)
Request 8 is received at 12:02:30.
The algorithm examines all timestamps within the determined time range (12:01:30 to 12:02:30) to check if any fall outside the current window.
In this example, all the accepted timestamps R3, R4 and R6 are fall within the range, so these will get deleted and Request 8 is added to the current log window.
Pseudo code for Sliding window log algorithm
// Initialize variables
windowDurationInSeconds = 60 // 60 seconds window duration
maxRequests = 3 // Maximum number of requests allowed per window
currentWindow = []
currentTimestamp = getCurrentTimestamp()
// Function to process a request
function processRequest():
// Remove expired requests from the window
while currentWindow is not empty and currentTimestamp - currentWindow[0] >= windowDurationInSeconds:
currentWindow.popFront()
// Check if number of requests in the current window exceeds the limit
if length(currentWindow) < maxRequests:
// Accept the request
acceptRequest()
// Add current timestamp to the window
currentWindow.pushBack(currentTimestamp)
else:
// Reject the request
rejectRequest()
// Example usage
while true:
// Simulate incoming requests
incomingRequest = receiveRequest()
// Process each incoming request
processRequest()
// Update current timestamp
currentTimestamp = getCurrentTimestamp()
The provided code implements a sliding window log algorithm to manage incoming requests within a defined time window. It begins by initializing variables such as the duration of the sliding window (windowDurationInSeconds) and the maximum number of requests allowed per window (maxRequests). The algorithm maintains a currentWindow list to track timestamps of accepted requests within the window and updates the currentTimestamp to the current time.
In the processRequest() function, the algorithm first removes expired requests from the currentWindow by iterating through the list and popping front elements until the difference between the current timestamp and the timestamp of the first request in the window exceeds the window duration. It then checks if the number of requests in the current window is less than the maximum limit. If so, the incoming request is accepted, and its timestamp is added to the window. If the limit is exceeded, the request is rejected.
No comments:
Post a Comment