Design an HTTP router with path parameters

01The design, in the six-step framework

1. Requirements and use cases

A web framework registers routes such as GET /users/:id and GET /files/*path. For an incoming method and path, the router finds the handler and extracts the named parameters. When several routes could match, the most specific wins: a fixed segment beats a parameter, a parameter beats a catch-all. Unknown paths give 404, and a known path with the wrong method gives 405. Middleware wraps handlers. Registering two routes with the same shape is an error, and routes can be added while traffic is flowing.

Out of scope: parsing HTTP itself, query strings, regular-expression segments and content negotiation.

Constraints: lookup must not depend on the number of routes, only on path depth, since a service can have thousands; reads vastly outnumber writes and must not block; conflicts are found at registration, not at request time.

2. Core entities and relationships

• Router: owns the root of the route tree, the writer lock and the middleware list.
• Node: one path position in a segment trie: fixed children by segment text, at most one parameter child, at most one catch-all, and handlers by HTTP method.
• Match: the result of a lookup, a handler plus the extracted parameters.
• Request, Response: small immutable values.
• RouteConflict: raised for duplicates and for two parameter names at the same position.

The router composes one root node, and each node composes its children, so the whole tree belongs to one router. Handlers sit in a per-method table on the terminal node, which is what makes 405 distinguishable from 404.

3. Interfaces and key methods

Handler = Callable[["Request"], "Response"]
Middleware = Callable[["Request", Handler], "Response"]

@dataclass(frozen=True)
class Match:
    handler: Handler
    params: Mapping[str, str]

class Router:
    def add(self, method: str, pattern: str, handler: Handler) -> None:
        """Register '/users/:id/posts/*rest'; raises RouteConflict on a duplicate shape."""
    def resolve(self, method: str, path: str) -> Match | None:
        """Most specific route: static beats :param beats *catchall."""
    def use(self, middleware: Middleware) -> None: ...
    def dispatch(self, request: "Request") -> "Response": ...   # 404 and 405 handled here

Invariants: a position has at most one parameter name; a catch-all is always the last segment; at most one handler exists per method per route shape; the tree that _root points at is never modified once published.

4. Design patterns and the choices behind them

A trie by segment, not a list of patterns

A list of regular expressions is simple, and every request then tries them in order, which is linear in routes and makes precedence depend on registration order. A trie keyed on path segments costs only the depth of the path. Precedence is structural: _walk tries static, then parameter, then catch-all.

Backtracking for correctness

Greedy descent is a subtle bug. With /a/b/c and /a/:x/d registered, the path /a/b/d enters the static child b and dead-ends, and the parameter route must then be tried. _walk is therefore recursive and falls back. Worst case is two branches per level; real route tables rarely approach that.

Copy-on-write for adding routes under traffic

The reported follow-up asks about adding routes under live traffic. A read-write lock is the textbook answer, and it adds a lock operation to every request. Here a writer holds one lock, copies the nodes along the path it changes, and publishes by assigning _root. Readers take one reference at the start and see a complete tree, old or new, never a half-built one. Writes are rare, so their extra cost is the right place to spend it.

Middleware as a chain

Each middleware receives the request and the next handler and can stop the chain, for example on failed authentication. The router builds the chain per dispatch from the outside in, so the first registered middleware runs first.

5. Core flow and code

1. add("GET", "/users/:id", show): under the write lock the root and path nodes are copied, a static child users and a parameter child named id are created, and GET is stored. The new root is published.
2. add("GET", "/users/me", profile) adds a static sibling.
3. resolve("GET", "/users/me"): static users, static me, handlers found; profile wins over the parameter route.
4. resolve("GET", "/users/42"): static users, no static 42, so the parameter child is taken with id=42.
5. dispatch(Request("POST", "/users/42")): the path exists but POST does not, and allowed returns GET, so the response is 405.
6. For a match, middleware wraps the handler and the chain runs with the extracted parameters on the request.

from __future__ import annotations
import threading
from dataclasses import dataclass, field
from typing import Callable, Mapping

@dataclass(frozen=True)
class Request:
    method: str
    path: str
    params: Mapping[str, str] = field(default_factory=dict)

@dataclass(frozen=True)
class Response:
    status: int
    body: str = ""

Handler = Callable[[Request], Response]
Middleware = Callable[[Request, Handler], Response]

class RouteConflict(ValueError):
    pass

@dataclass(frozen=True)
class Match:
    handler: Handler
    params: Mapping[str, str]

@dataclass
class Node:
    static: dict[str, "Node"] = field(default_factory=dict)
    param: "Node | None" = None
    param_name: str = ""
    catchall: "tuple[str, dict[str, Handler]] | None" = None
    handlers: dict[str, Handler] = field(default_factory=dict)

    def copy_path(self) -> "Node":
        """Shallow copy so a writer can replace nodes without touching the live tree."""
        return Node(dict(self.static), self.param, self.param_name, self.catchall, dict(self.handlers))

def segments(path: str) -> list[str]:
    return [s for s in path.split("/") if s]

class Router:
    def __init__(self) -> None:
        self._root = Node()                    # readers load this reference once
        self._write_lock = threading.Lock()
        self._middleware: list[Middleware] = []

    def add(self, method: str, pattern: str, handler: Handler) -> None:
        with self._write_lock:
            root = self._root.copy_path()      # copy-on-write: only the touched path is new
            self._insert(root, segments(pattern), method.upper(), handler)
            self._root = root                  # one atomic reference swap publishes the route

    def _insert(self, node: Node, parts: list[str], method: str, handler: Handler) -> None:
        for i, seg in enumerate(parts):
            if seg.startswith("*"):
                if i != len(parts) - 1:
                    raise ValueError("catch-all must be the last segment")
                name, table = node.catchall or (seg[1:], {})
                if name != seg[1:] or method in table:
                    raise RouteConflict(seg)
                node.catchall = (name, {**table, method: handler})
                return
            if seg.startswith(":"):
                if node.param is not None and node.param_name != seg[1:]:
                    raise RouteConflict(f"{seg} clashes with :{node.param_name}")
                node.param = node.param.copy_path() if node.param else Node()
                node.param_name = seg[1:]
                node = node.param
            else:
                child = node.static.get(seg)
                node.static[seg] = child.copy_path() if child else Node()
                node = node.static[seg]
        if method in node.handlers:
            raise RouteConflict(f"duplicate {method} route")
        node.handlers[method] = handler

    def _walk(self, node: Node, parts: list[str], i: int, params: dict[str, str]) -> "tuple[dict[str, Handler], dict[str, str]] | None":
        if i == len(parts):
            return (node.handlers, params) if node.handlers else None
        seg = parts[i]
        if seg in node.static:                 # static first
            found = self._walk(node.static[seg], parts, i + 1, params)
            if found: return found
        if node.param is not None:             # then :param, with backtracking
            found = self._walk(node.param, parts, i + 1, {**params, node.param_name: seg})
            if found: return found
        if node.catchall is not None:          # finally *rest
            name, table = node.catchall
            return table, {**params, name: "/".join(parts[i:])}
        return None

    def resolve(self, method: str, path: str) -> Match | None:
        found = self._walk(self._root, segments(path), 0, {})
        if not found:
            return None
        table, params = found
        handler = table.get(method.upper())
        return Match(handler, params) if handler else None

    def allowed(self, path: str) -> list[str]:
        found = self._walk(self._root, segments(path), 0, {})
        return sorted(found[0]) if found else []

    def use(self, middleware: Middleware) -> None:
        self._middleware.append(middleware)

    def dispatch(self, request: Request) -> Response:
        match = self.resolve(request.method, request.path)
        if match is None:
            return Response(405 if self.allowed(request.path) else 404)
        req = Request(request.method, request.path, match.params)
        chain = match.handler
        for mw in reversed(self._middleware):
            chain = (lambda m, nxt: lambda r: m(r, nxt))(mw, chain)
        return chain(req)

6. Extensions, concurrency and what interviewers probe

• Per-method routing: already handled by the handler table. Note that a path could match a parameter route for GET and a static route for POST; resolve here selects the path first, so confirm which behaviour the interviewer wants.
• Catch-all: captures the remaining segments joined, and an empty remainder is a design decision to state.
• Atomic step: the assignment to _root. It works only because readers never see a node being changed; the copied nodes are private until that line runs.
• Trailing slashes and encoding: segments drops empty parts, so /a/ equals /a. Decide this and URL-decoding deliberately; both are classic security bugs.
• Test first: precedence, the backtracking case above, 404 versus 405, duplicate route, conflicting parameter names, and a thread adding routes while others resolve.
• Common mistake: descending greedily without backtracking, or mutating the live tree during add so a reader sees a node with no handlers yet.

02Where this question was reported

• Hello Interview · Hello Interview Google L5 guide lists it among senior coding questions; also in the L4 guide https://www.hellointerview.com/guides/google/l4
• Codemia · Codemia Hard 'Middleware Chain' is the adjacent design problem
• PracHub · Tagged Data Structure Design; trees
• PracHub · Pattern matching with placeholders
• Hello Interview · 'Implement HTTP route matching for a web framework' listed as commonly asked at mid-level