Implement a fourth algorithm: fixed window counter

Nobody has started this yet — be first.

Business impact

Not every product need justifies the sliding window's extra complexity -- some quota shapes (a daily export limit, a per-billing-period cap) are naturally and correctly expressed as a plain fixed window, and forcing every customer-facing quota through the sliding window's blending logic is more code, more to explain to customers who ask "how exactly does my limit work," and more surface for the class of bug in task 09. This ticket is also a direct test of the codebase's central design promise -- if it can't be done cleanly, that's a signal the abstraction underpinning every future rate-limiting feature needs rework before the product commits to more policies built on top of it.

Problem

The README explicitly calls this out as the intended extension point: "Add a fourth algorithm: implement ratelimit.Limiter (Allow/AllowN) in a new file under pkg/ratelimit/; nothing else in the codebase needs to change." There is no plain fixed-window counter yet. A stub exists at pkg/ratelimit/fixed_window.go that currently ignores its configured limit entirely and allows everything.

Current behavior

FixedWindowMemory.AllowN always returns Allowed: true regardless of how many requests have already been made for a key -- the configured limit has no effect.

Expected behavior

Time is divided into fixed-size, non-overlapping windows of length window (clock-aligned to window boundaries). Each key tracks a single counter for "requests seen in the current window." A request is allowed if counter + n <= limit, and the counter resets to 0 the instant the wall clock crosses into a new window -- no blending with the previous window.

Steps to reproduce

fw := ratelimit.NewFixedWindowMemory(5 /* limit */, time.Minute, time.Hour) for i := 0; i < 6; i++ { res, _ := fw.Allow(ctx, "user-1") } // got: the 6th request in the same window is allowed (the stub always returns Allowed: true) // want: the 6th request in the same window is denied; the counter resets once the window rolls over

Why this matters

This is the extension path the codebase was explicitly designed for. Doing it once is what proves (or disproves) the claim that the Limiter interface is actually sufficient abstraction for "any future algorithm" -- if you find yourself needing to touch code outside pkg/ratelimit/ for the core memory implementation to work, that's worth noticing.

Suggested approach

This is structurally the "current window" half of sliding_window.go with the "blend with previous window" part deleted -- read that file for the window-alignment (curStart, via now / window * window) trick and the per-key entry/mutex-or-atomic pattern, then decide for yourself whether a single counter needs a mutex or can be done with atomic.Int64 + CAS. Reuse the existing generic janitor (pkg/ratelimit/janitor.go) for idle-key eviction rather than reinventing it.

Acceptance criteria

A fresh key admits exactly limit requests within one window, then denies further ones until the window rolls over.
Concurrent callers for the same key, within one window, never jointly exceed limit (go test -race).
A new window resets the counter to 0 (previous window's count has no effect).
go test -race ./test/ -run TestTask12 -v passes.

Verification

go test -race ./test/ -run TestTask12 -v

Hints (0/2)

Try it without hints first — the reading is the exercise.

Working on this ticket

Work on a branch named for the ticket — that's what you'll submit.

Branch off your fork

$git checkout -b feat/fixed-window-algorithm

Fix it and commit

Meet every acceptance criterion, and add a test that would have caught this.

Push the branch

$git push -u origin feat/fixed-window-algorithm

Submit it below

Paste your fork URL and the branch name, with a short write-up of the root cause.

Submit your fix

Questions

Stuck on something?

Ask about anything unclear in the ticket — the maintainer and anyone who has solved it can answer. Please don't post full solutions.

No questions yet. If something in this ticket reads ambiguously, you are probably not the only one — ask.

The project

Rate Limiter (Token Bucket + Sliding Window + Leaky Bucket)

Three interchangeable rate-limiting algorithms -- token bucket, sliding window, and leaky bucket -- each with an in-memory and a Redis-backed implementation behind one Go interface, plus a runnable HTTP service -- fifteen ways the concurrency, correctness, and operability details of a production rate limiter quietly go wrong.

Fork on GitHub

Download

Setup

Rate Limiter (Token Bucket + Sliding Window + Leaky Bucket)

git clone <your-fork>
cd GolangDevTraining/ratelimiter
docker compose up --build   # app + redis + redis-commander UI, hot-reloading on save

This starts the service on (Redis on , a Redis-browsing UI on ). Verify it's up, then try the seeded rules: