Last active
November 24, 2025 20:34
-
-
Save lukebarton/9589420a2a6340a73133152756c14f68 to your computer and use it in GitHub Desktop.
Rate Limiter Design
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import { match } from "assert"; | |
| import { test, expect } from "vitest"; | |
| const STATUS_REJECTED = 429; | |
| const STATUS_ACCEPTED = 200; | |
| type HttpRequest = { id: string; path: string; user_id: string }; | |
| type HttpResponse = { request_id: string; status: number }; | |
| interface RequestHandler { | |
| handle(request: HttpRequest): HttpResponse | undefined; | |
| } | |
| // 1. split out the request handler | |
| class StdRequestHandler { | |
| handle(request: HttpRequest) { | |
| return { request_id: request.id, status: STATUS_ACCEPTED }; | |
| } | |
| } | |
| test("Handler handles", () => { | |
| const handler = new StdRequestHandler(); | |
| const request = { id: "1234", path: "", user_id: "" }; | |
| expect(handler.handle(request)).toEqual({ | |
| request_id: "1234", | |
| status: STATUS_ACCEPTED, | |
| }); | |
| }); | |
| // 2. Generic rate limiter, now with a "next" handler as I described | |
| class RateLimiter { | |
| count: number = 0; | |
| constructor( | |
| private limit: number, | |
| private next: RequestHandler, | |
| ) {} | |
| handle(request: HttpRequest) { | |
| if (this.count >= this.limit) { | |
| return { request_id: request.id, status: STATUS_REJECTED }; | |
| } | |
| const result = this.next.handle(request); | |
| if (result !== undefined && result.status === STATUS_ACCEPTED) { | |
| this.count += 1; | |
| } | |
| return result; | |
| } | |
| } | |
| test("RateLimiter limits", () => { | |
| const limiter = new RateLimiter(1, new StdRequestHandler()); | |
| const request_1: HttpRequest = { id: "1234", path: "", user_id: "" }; | |
| const accepted: HttpResponse = { | |
| request_id: "1234", | |
| status: STATUS_ACCEPTED, | |
| }; | |
| const rejected: HttpResponse = { | |
| request_id: "1234", | |
| status: STATUS_REJECTED, | |
| }; | |
| expect(limiter.handle(request_1)).toEqual(accepted); | |
| expect(limiter.handle(request_1)).toEqual(rejected); | |
| }); | |
| // 2. A handler being able to return undefined if the request wasn't handled at all was required | |
| // This predicate handler would be generic enough to handle paths and users (and other similar reqs) | |
| const matchesPath = (path: string) => (request: HttpRequest) => | |
| request.path === path; | |
| const matchesUser = (user_id: string) => (request: HttpRequest) => | |
| request.user_id === user_id; | |
| const and = | |
| ( | |
| a: (request: HttpRequest) => boolean, | |
| b: (request: HttpRequest) => boolean, | |
| ) => | |
| (request: HttpRequest) => | |
| a(request) && b(request); | |
| class PredicateHandler implements RequestHandler { | |
| constructor( | |
| private predicate: (request: HttpRequest) => Boolean, | |
| private next: RequestHandler, | |
| ) {} | |
| handle(request: HttpRequest): HttpResponse | undefined { | |
| if (!this.predicate(request)) { | |
| return undefined; | |
| } | |
| return this.next.handle(request); | |
| } | |
| } | |
| test("PredicateHandler optionally applies", () => { | |
| const globalRateLimiter = new RateLimiter(3, new StdRequestHandler()); | |
| const limiter = new PredicateHandler( | |
| matchesPath("/limited_path"), | |
| new RateLimiter(1, globalRateLimiter), | |
| ); | |
| const global_request: HttpRequest = { id: "1234", path: "/", user_id: "" }; | |
| const limited_request: HttpRequest = { | |
| id: "999", | |
| path: "/limited_path", | |
| user_id: "", | |
| }; | |
| expect(limiter.handle(limited_request)).toEqual({ | |
| request_id: "999", | |
| status: STATUS_ACCEPTED, | |
| }); | |
| expect(limiter.handle(limited_request)).toEqual({ | |
| request_id: "999", | |
| status: STATUS_REJECTED, | |
| }); | |
| expect(limiter.handle(global_request)).toEqual(undefined); | |
| }); | |
| // This Fallthrough handler has the ability to walk over handlers until one of them handles the request | |
| // This would work well with the PredicateHandler | |
| class FallthroughHandler { | |
| constructor(private handlers: RequestHandler[]) {} | |
| handle(request: HttpRequest) { | |
| let index = 0; | |
| let response: HttpResponse | undefined = undefined; | |
| while (response === undefined) { | |
| response = this.handlers[index].handle(request); | |
| index++; | |
| } | |
| return response; | |
| } | |
| } | |
| test("FallthroughHandler", () => { | |
| const globalRequestHandler = new StdRequestHandler(); | |
| const globalRateLimiter = new RateLimiter(3, globalRequestHandler); | |
| const handlerUnderTest = new FallthroughHandler([ | |
| new PredicateHandler( | |
| matchesPath("/limited_path"), | |
| new RateLimiter(1, globalRateLimiter), | |
| ), | |
| globalRateLimiter, | |
| ]); | |
| const global_request: HttpRequest = { id: "1234", path: "/", user_id: "" }; | |
| const limited_request: HttpRequest = { | |
| id: "999", | |
| path: "/limited_path", | |
| user_id: "", | |
| }; | |
| expect(handlerUnderTest.handle(limited_request)).toEqual({ | |
| request_id: "999", | |
| status: STATUS_ACCEPTED, | |
| }); | |
| expect(handlerUnderTest.handle(limited_request)).toEqual({ | |
| request_id: "999", | |
| status: STATUS_REJECTED, | |
| }); | |
| expect(handlerUnderTest.handle(global_request)).toEqual({ | |
| request_id: "1234", | |
| status: STATUS_ACCEPTED, | |
| }); | |
| }); | |
| // Example use: | |
| const requestHandler = new StdRequestHandler(); // this handles all requests | |
| const globalRateLimiter = new RateLimiter(1_000_000, requestHandler); // this limits the requests globally | |
| const resourceIntensivePathHandler = new PredicateHandler( // this will limit our expensive path globally | |
| matchesPath("/limited_path"), | |
| new RateLimiter(1_000, globalRateLimiter), | |
| ); | |
| const handler = new FallthroughHandler([ | |
| new PredicateHandler( // this limits our expensive path for a specific user | |
| and(matchesPath("/limited_path"), matchesUser("666")), | |
| new RateLimiter(10, resourceIntensivePathHandler), | |
| ), | |
| new PredicateHandler( | |
| and(matchesPath("/another_limited_path"), matchesUser("666")), | |
| new RateLimiter(1, globalRateLimiter), | |
| ), | |
| resourceIntensivePathHandler, // catch any requests to the resource intensive path | |
| globalRateLimiter, // catch the rest | |
| ]); | |
| handler.handle({ id: "1234", path: "/blah_blah", user_id: "666" }); // would hit the globalRateLimiter | |
| // Now that I've gotten here, I can see an even better approach: | |
| // Have something similar to the FallthroughHandler, except that instead of the limiters decorating the requestHandler (ie. "next"), | |
| // instead all stack the limiters, pass through any unlimited requests and put the requestHandler right at the end. | |
| // This would need the request and response to be passed back through each of the | |
| // limiters that have been passed through once a request has been accepted or rejected, so | |
| // that those limiters can update their counts/rates as appropriate |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment