Syllabus Lesson 4 of 141 · The blind start
The blind start

Baseline 3: a rate limiter on a small box

AI off This is a baseline exam. The tutor is switched off and there are no hints. Work alone, the way you would with no assistant open. Nothing here is a trick: every rule is written in the exercise. Your result is only compared with your own final exam at the end of the course.

A small public API needs a rate limiter. It runs for months on one tiny machine, and its traffic comes from thousands of clients that send a few requests and are never seen again.

The worked example

s = new_state(2, 10)       # 2 requests per 10 seconds
allow(s, 'a', 0)    # True
allow(s, 'a', 3)    # True
allow(s, 'a', 9)    # False: 0 and 3 are in (-1, 9]
allow(s, 'b', 9)    # True: b is separate
allow(s, 'a', 10)   # True: 0 has left the window (0, 10]
allow(s, 'a', 13)   # True: 3 has left (3, 13]
allow(s, 'a', 14)   # False
allow(s, 'a', 23)   # True
Your turn

Write new_state(limit, window) and allow(state, client, t). allow returns True if the client had fewer than limit allowed requests in the last window seconds, that is with times in (t - window, t], and then counts this one; otherwise it returns False (refused requests do not count). t is a whole number of seconds and never goes down from one call to the next. Keep everything in state: no globals.
Memory: over 20,000 calls, more than 5,000 different clients pass through, most sending a few requests and never coming back. With limit=3, window=60, your state may hold at most 2,500 items at any time, counted like kept() (deques and OrderedDicts count every item too), checked every 100 calls.

AI off: no tutor, hints or worked solution on this one. Your own thinking only.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus