Sliding Window Log Algorithm - Rate Limiter

The Sliding Window Log Algorithm is an advanced rate-limiting mechanism designed to overcome some of the limitations of simpler algorithms like the Fixed Window Algorithm. By keeping track of individual requests using a timestamp, the Sliding Window Log Algorithm offers a more granular and precise control over request rates. This algorithm smooths out traffic spikes and is ideal for environments where consistent traffic flow is critical.

The Sliding Window Log algorithm is widely used in distributed systems, APIs, and microservices where high accuracy in controlling request rates is required, and where burst traffic can cause system overload.

---

How It Works

1. Logging Requests: Every request made by the user is logged with a timestamp.
2. Sliding Time Window: The system evaluates requests within a sliding time window, typically of a predefined length (e.g., 1 minute). Requests outside this window are discarded from the count.
3. Request Limits: If the user exceeds the request limit within the sliding window, additional requests are denied until earlier requests "fall out" of the window.

Unlike the Fixed Window Algorithm, which counts requests based on fixed intervals, Sliding Window Log provides a continuous window that dynamically moves based on request timestamps. This makes it more responsive to traffic patterns and better at handling burst traffic.

---

Details

Let’s break down how the Sliding Window Log Algorithm accurately tracks requests over a sliding window, using timestamps, and how it continuously evaluates requests within the last 60 seconds. This method ensures that the system isn’t just counting requests based on fixed time intervals but is always looking at the past 60 seconds from the moment a request is made.

Scenario

Suppose a user is allowed to make 100 API requests per minute. The sliding window will track how many requests the user has made in the last 60 seconds at any given moment—not just from the start of a specific minute on the clock.

• Within the Sliding Window: If a user sends 50 requests at the 30-second mark, they can send 50 more in the next 30 seconds. After the 60-second mark, the system continuously adjusts the window, removing older requests as new ones come in.

Key Difference: Sliding Window vs. Fixed Time

Unlike a fixed time window where the count resets at the start of each minute (e.g., 12:00 to 12:01), the sliding window keeps a dynamic view. It looks back at the last 60 seconds, regardless of what time it is on the clock. For example, if a user makes a request at 12:30:45, the system checks all the requests made between 12:29:45 and 12:30:45.

How Requests Are Tracked in Sliding Time

1. Start: Every time a request is made, the system logs it with a timestamp.
2. Continuous Evaluation: As new requests come in, the system continuously evaluates the previous 60 seconds to determine how many requests were made.
3. Sliding Window: The window "slides" with every new request. Requests that were made more than 60 seconds ago "fall out" of the window and are no longer counted.

Example

Let’s assume a user sends requests at the following times:

• T=0s: Request 1
• T=30s: Request 2
• T=60s: Request 3
• T=90s: Request 4

At T=90 seconds, Request 1 will have "fallen out" of the window, as the system only looks at requests made in the last 60 seconds, from T=30s to T=90s.

How Sliding Window Tracks Requests Over Time

1. Log Each Request with a Timestamp: The system logs every request with the exact time it was made.
2. Evaluate Requests in Sliding Window: As new requests come in, the system looks back at the last 60 seconds from the current request.
3. Exceeded Limit?: If the number of requests in the last 60 seconds exceeds the limit (e.g., 100 requests), the system rejects the new request.
4. Update Sliding Window: As time moves forward, older requests automatically fall out of the sliding window, making room for new ones.

This diagram visually represents how the system dynamically tracks requests within the sliding time window, discarding older ones and allowing the system to maintain a real-time count.

Key Takeaways

1. Always Looking at the Last 60 Seconds: The algorithm doesn’t reset at the start of each minute. Instead, it constantly looks at the last 60 seconds, so it’s always evaluating the most recent activity.
2. Requests Fall Out of the Window: As time progresses, older requests (like Request 1 in the diagram) fall out of the 60-second window. This ensures that the system is only considering the most recent requests.
3. Continuous Monitoring: By logging timestamps and constantly evaluating requests, the Sliding Window Log Algorithm ensures that the system smoothly handles traffic without arbitrary resets, preventing spikes from sudden bursts of activity.

---

Limitations

While the Sliding Window Log Algorithm provides more precise control, it has some limitations:

1. Memory Usage: Since the system needs to log every request with a timestamp, it consumes more memory compared to simpler algorithms like Fixed Window.
2. Complexity: Managing individual logs of each request increases complexity, making it less efficient for very high-traffic systems where memory and computational overhead are critical concerns.

Handling Bursts

Unlike the Fixed Window Algorithm, Sliding Window Log effectively handles burst traffic. By continuously sliding and evaluating requests over the last X seconds, it prevents users from sending all their requests in a burst at the boundary of two fixed windows.

---

Benefits Over Fixed Window

The Sliding Window Log Algorithm resolves many of the limitations of the Fixed Window Algorithm:

• Prevents Burst Traffic: By continuously sliding, it smooths out traffic and prevents the system from being hit with too many requests at once.
• Accurate Request Counting: It provides precise control by tracking every request, avoiding the problem of sudden traffic spikes.

---

FAQs

Q1: What happens when a request is logged outside the time window?

Requests that fall outside the sliding time window are automatically discarded from the count. The system only evaluates requests within the defined window (e.g., the last 60 seconds).

Q2: How does the Sliding Window Log Algorithm improve traffic control?

Unlike the Fixed Window, which counts requests in fixed intervals, Sliding Window Log provides a dynamic, continuous evaluation of requests. This prevents users from sending all their requests at the end of one window and the start of the next, ensuring smoother traffic flow.

Q3: Why is memory usage higher in Sliding Window Log?

Since the algorithm logs every request with a timestamp and continuously evaluates the sliding window, it consumes more memory than simpler methods, which only count requests in fixed intervals.