Per-Client API Rate Limiter: Sliding Window Log to Sliding Window Counter at Scale

Quick Overview

Implement a per-client API rate limiter where clients are identified by IP address or API key. The question compares fixed window, sliding window log, sliding window counter and token bucket, asks for a tested sliding window log, then a sliding window counter that keeps storage small for one million clients.

Per-Client API Rate Limiter: Sliding Window Log to Sliding Window Counter at Scale

Company: Docker

Role: Software Engineer

Category: Software Engineering Fundamentals

Difficulty: medium

Interview Round: Technical Screen

You are building an API rate limiter that stops clients from sending too many requests in a short period of time. Each client is identified by an id, such as an IP address or an API key. Implement a function that enforces a rate limit per client id: for every incoming request it decides whether to allow or reject it. The prompt fixes neither an interface nor the limits. A workable shape is a limiter configured with a maximum of `max_requests` requests per `window` seconds for each client, with a method `allow(client_id, timestamp) -> bool` that receives the request time from the caller so tests can control the clock; confirm this with the interviewer. You write and run the code in your own editor, and the round has three steps: compare the standard algorithms, implement and test one, then rework it for a very large number of clients. ### Clarifying Questions - Is the limit the same for every client, or configured per client or per plan? - Must the limit hold exactly over any rolling window, or is a close approximation acceptable? - Is time passed in by the caller or read from a clock, and can the timestamps of one client arrive out of order? - Does the limiter run in one process, or must several servers share the same limits? - Do rejected requests count toward the limit? - How should invalid input be handled: an empty client id, a non-positive limit or window? ### Part 1 — Compare the algorithms Before writing code, compare fixed window, sliding window log, sliding window counter and token bucket for this problem, and choose one to implement first. ```hint Look at the window edge Picture a client that uses its full quota just before one window ends and again just after the next one starts. Which of the four algorithms notice, and what does each one store per client? ``` #### What This Part Should Cover - Accuracy, especially at window boundaries and under bursts - Memory per client and time per request - How each algorithm's behavior matches the requirement agreed in the clarifying questions ### Part 2 — Implement the sliding window log Implement the limiter with a sliding window log: a request is allowed only if fewer than `max_requests` earlier allowed requests from the same client fall within the last `window` seconds. Then write tests covering invalid input, boundary cases and the limiting logic itself. ```hint Drop what can no longer matter For one client, which stored timestamps can never affect a future decision, and when is the cheapest moment to remove them? ``` #### Clarifying Questions for this Part - Does a request exactly `window` seconds older than the current one still count? #### What This Part Should Cover - The per-client data structure, eviction, and the cost per request - A consistent boundary convention and input validation - Deterministic tests for the limit, the boundary, independence between clients and invalid input ### Part 3 — Scale to one million clients With one million active clients, storing a timestamp for every request becomes the bottleneck. Replace the log with a sliding window counter, implement it, and explain how much accuracy you give up. ```hint What the previous window still contributes Think about what fraction of the previous fixed window still lies inside the rolling window that ends at the current request, and how to use that fraction without keeping individual timestamps. ``` #### What This Part Should Cover - Per-client state, and a rough memory comparison with the log at one million clients - How the rolling count is estimated and compared with `max_requests` - The error the approximation introduces, and cleanup of idle clients ### What a Strong Answer Covers - An interface and edge-case decisions agreed with the interviewer before coding - Trade-offs among the four algorithms tied to the stated requirement, not recited - Correct, readable implementations of both versions with the same boundary convention - Tests that control time explicitly and cover validation, boundaries and per-client isolation - Memory reasoning at one million clients, plus awareness of concurrency and of sharing limits across servers ### Follow-up Questions - How would you make the limiter thread-safe without a single global lock becoming a bottleneck? - The service runs on many servers behind a load balancer. How do the limits stay consistent across them? - How would you support different limits per API key tier and change them without a restart? - What should a rejected client receive in the response so that it can back off correctly?

Overview: Implement a per-client API rate limiter where clients are identified by IP address or API key. The question compares fixed window, sliding window log, sliding window counter and token bucket, asks for a tested sliding window log, then a sliding window counter that keeps storage small for one million clients.

Read the full Docker Software Engineer interview experience this question came from

Docker logo
Docker
Nov 16, 2026
mediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals
0
0

You are building an API rate limiter that stops clients from sending too many requests in a short period of time. Each client is identified by an id, such as an IP address or an API key. Implement a function that enforces a rate limit per client id: for every incoming request it decides whether to allow or reject it.

The prompt fixes neither an interface nor the limits. A workable shape is a limiter configured with a maximum of max_requests requests per window seconds for each client, with a method allow(client_id, timestamp) -> bool that receives the request time from the caller so tests can control the clock; confirm this with the interviewer. You write and run the code in your own editor, and the round has three steps: compare the standard algorithms, implement and test one, then rework it for a very large number of clients.

Clarifying Questions Guidance

  • Is the limit the same for every client, or configured per client or per plan?
  • Must the limit hold exactly over any rolling window, or is a close approximation acceptable?
  • Is time passed in by the caller or read from a clock, and can the timestamps of one client arrive out of order?
  • Does the limiter run in one process, or must several servers share the same limits?
  • Do rejected requests count toward the limit?
  • How should invalid input be handled: an empty client id, a non-positive limit or window?

Part 1 — Compare the algorithms

Before writing code, compare fixed window, sliding window log, sliding window counter and token bucket for this problem, and choose one to implement first.

What This Part Should Cover Guidance

  • Accuracy, especially at window boundaries and under bursts
  • Memory per client and time per request
  • How each algorithm's behavior matches the requirement agreed in the clarifying questions

Part 2 — Implement the sliding window log

Implement the limiter with a sliding window log: a request is allowed only if fewer than max_requests earlier allowed requests from the same client fall within the last window seconds. Then write tests covering invalid input, boundary cases and the limiting logic itself.

Clarifying Questions for this Part Guidance

  • Does a request exactly window seconds older than the current one still count?

What This Part Should Cover Guidance

  • The per-client data structure, eviction, and the cost per request
  • A consistent boundary convention and input validation
  • Deterministic tests for the limit, the boundary, independence between clients and invalid input

Part 3 — Scale to one million clients

With one million active clients, storing a timestamp for every request becomes the bottleneck. Replace the log with a sliding window counter, implement it, and explain how much accuracy you give up.

What This Part Should Cover Guidance

  • Per-client state, and a rough memory comparison with the log at one million clients
  • How the rolling count is estimated and compared with max_requests
  • The error the approximation introduces, and cleanup of idle clients

What a Strong Answer Covers Guidance

  • An interface and edge-case decisions agreed with the interviewer before coding
  • Trade-offs among the four algorithms tied to the stated requirement, not recited
  • Correct, readable implementations of both versions with the same boundary convention
  • Tests that control time explicitly and cover validation, boundaries and per-client isolation
  • Memory reasoning at one million clients, plus awareness of concurrency and of sharing limits across servers

Follow-up Questions Guidance

  • How would you make the limiter thread-safe without a single global lock becoming a bottleneck?
  • The service runs on many servers behind a load balancer. How do the limits stay consistent across them?
  • How would you support different limits per API key tier and change them without a restart?
  • What should a rejected client receive in the response so that it can back off correctly?