# Design This file fixes the parts that are easy to get wrong. Choose the language and framework that fit the person's project; nothing here depends on them. ## The algorithm All times are whole milliseconds. For a limit of `limit` requests per `window`: ``` interval = window / limit (whole milliseconds, rounded down) stored = the caller's number, or now if there is none start = max(stored, now) ahead = start - now if ahead > window - interval: refuse; retry_after = ahead - (window - interval) else: store start + interval, to expire at start + interval allow; remaining = (window - (start + interval - now)) / interval, rounded down ``` `reset` is `start + interval - now` when allowed and `ahead` when refused. `Retry-After` and `RateLimit-Reset` are those values in seconds, rounded up. A limit with more requests than its window has milliseconds would have an interval of zero. That is a configuration error. Refuse to start with it. ## Cases A limit of 3 requests per 60 seconds, one caller, nothing stored at the start. | Request at, ms | Result | Remaining | Retry after, ms | Stored afterwards | | --- | --- | --- | --- | --- | | 0 | allowed | 2 | | 20000 | | 1000 | allowed | 1 | | 40000 | | 2000 | allowed | 0 | | 60000 | | 3000 | refused | 0 | 17000 | 60000 | | 20000 | allowed | 0 | | 80000 | | 20500 | refused | 0 | 19500 | 80000 | | 100000 | allowed | 2 | | 120000 | The refused request at 3000 gets `Retry-After: 17`. The one at 20500 gets `Retry-After: 20`. ## The store The stored key is the limit's name, a colon and the caller, for example `default:key_3kTn9QxWb2aZ`. The default limit is the `default_limit` input per `default_window_seconds`. | `store` | How the one step is made | | --- | --- | | `redis` | One script that reads, decides and writes, with the key's expiry set to the stored time. Pass `now` in from the app, so tests can set it. | | `database` | One table, `rate_limits(key, stored, expires_at)`. One transaction that locks the row, or one statement that inserts or updates and returns the result. Sweep expired rows once a minute. | | `memory` | A map behind one lock, with the least recently used entry dropped at 100,000. | Hide the three behind one interface with one operation: `take(limits, now)`, where `limits` is a list of key, limit and window. It decides for every entry and writes only if all of them allow. It returns, for each entry, allowed or refused with `remaining`, `retry_after` and `reset`. ## Order of work for a request 1. If the route is the health check, or the caller is exempt, pass. 2. Work out the caller. 3. Take from every limit that applies, in one call. If any refuses, nothing is counted. Answer 429 with the longest `retry_after`. 4. Set the headers from the limit with the least remaining. ## Configuration | Setting | Purpose | | --- | --- | | `REDIS_URL` | Connection string, when `store` is `redis`. | | `DATABASE_URL` | Connection string, when `store` is `database`. | | `TRUSTED_PROXIES` | Addresses or ranges whose forwarding header is believed. Empty by default. | | `RATE_LIMIT_EXEMPT` | API key ids and IP addresses that are never limited. Empty by default. | ## Named here - The app says who is calling through one function, `caller(request)`, which answers with an API key's id, a user's id, or neither. The example app reads the key from `Authorization: Bearer `. - The forwarding header is `X-Forwarded-For`. If every address in it is a trusted proxy, the left-most is used. - An IPv4 address written inside IPv6 is counted as the IPv4 address. - A refused request's body is `{"error": {"code": "rate_limited", "message": "..."}}`. A strict limit with the store down answers 503 with the code `store_unavailable`. - The three headers hold whole numbers, such as `RateLimit-Reset: 17`. When two limits apply they describe the one with less remaining, and the default limit on a tie. ## What this spec leaves to you Where this spec names something, use that name, so that two builds of it agree. Where it does not, the choice is yours. List what you chose in the README.