🎓 A1Learner
🔍
0 of 42 lessons completed

Fixed and Sliding Windows

A fixed window is a counting period with a set start and end, such as one minute. A sliding window is a counting period that moves with time, and this lesson deep-dives both forms.

A fixed window resets its count

Requests are counted inside the current window only. The last arrival falls in a new window, so its count starts again from the bottom.

limit = 5
window = 0
count = 0
arrivals = [(10, 1), (20, 2), (30, 3), (40, 4), (50, 5), (55, 6), (70, 7)]

for time, n in arrivals:
    current = time // 60
    if current != window:
        window = current
        count = 0
    count += 1
    print("request", n, "at second", time, "accepted" if count <= limit else "rejected")

The boundary flaw, in small numbers

A burst lands just before a boundary and another just after it. Each half stays within its own window, so every request passes in a short span.

limit = 5
counts = {}
arrivals = [56, 57, 58, 59, 59, 60, 60, 61, 62, 63]
passed = 0

for t in arrivals:
    w = t // 60
    counts[w] = counts.get(w, 0) + 1
    if counts[w] <= limit:
        passed += 1
        print("second", t, "accepted")
    else:
        print("second", t, "rejected")

print("passed in total", passed)
print("first at second", arrivals[0], "last at second", arrivals[-1])

A sliding log closes the hole

The same arrivals now face a moving period over the most recent stretch. Late arrivals still see the earlier burst inside the period, so they are rejected.

limit = 5
log = []
arrivals = [56, 57, 58, 59, 59, 60, 60, 61, 62, 63]

for t in arrivals:
    log = [x for x in log if x > t - 60]
    if len(log) < limit:
        log.append(t)
        print("second", t, "accepted, in window", len(log))
    else:
        print("second", t, "rejected, in window", len(log))

Example

arrivals = [56, 57, 58, 59, 59, 60, 60, 61, 62, 63]
limit = 5
counts = {}
fixed_passed = 0

for t in arrivals:
    w = t // 60
    counts[w] = counts.get(w, 0) + 1
    if counts[w] <= limit:
        fixed_passed += 1

log = []
sliding_passed = 0

for t in arrivals:
    log = [x for x in log if x > t - 60]
    if len(log) < limit:
        log.append(t)
        sliding_passed += 1

print("fixed window passed", fixed_passed)
print("sliding window passed", sliding_passed)
print("limit per window", limit)

Key points

  • Fixed window: a counting period with a set start and end, and a count that resets at each new period.
  • Sliding window: a counting period that moves with time, covering the most recent stretch up to now.
  • Worked limit: each user may make 100 requests inside one window in this design.
  • Boundary burst: 100 requests at the end of one minute plus 100 at the start of the next make 200 requests in a few seconds.
  • Sliding log: the store keeps the time of each recent request, and the count covers only times inside the moving period.

In this example, the same scripted burst runs against a fixed window and then against a sliding window. The fixed form passes the whole burst across its boundary, and the sliding form holds the burst to the limit.

Note

the sliding form closes the boundary hole, and its cost is storing one time per recent request.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Why can a fixed window pass more than the limit inside a short burst?