Courses › Low-Level Design › Problem Walkthroughs

Design an HTTP Router

A segment trie with static, parameter and wildcard precedence, 404 vs 405, and middleware.

"Design an HTTP router" is the core of every web framework: given a method and a path such as GET /users/42/orders, find the handler and extract the parameters (id = 42). It's a popular machine-coding question at infrastructure and API companies because it combines a trie, clear matching rules, and a middleware chain, in code you can finish in an hour.

Requirements

• Register routes: router.add("GET", "/users/:id/orders", handler).
• Path segments can be static (users), parameters (:id) or a wildcard (*path, matches the rest of the path).
• router.resolve(method, path) returns the handler and the extracted parameters.
• Precedence: static beats parameter, which beats wildcard. /users/me should match a /users/me route before /users/:id.
• Return 404 if no path matches, and 405 if the path matches but the method doesn't.
• Middleware: functions that run before and after handlers (logging, authentication), globally or per route group.

Why a trie

Checking every route one by one with a regular expression is O(routes) per request, and the order you register routes in changes which one wins. A trie of path segments makes lookups proportional to the path length, and the precedence rules become a fixed search order at each node.

(root)
 └─ users
     ├─ me            GET → current_user
     └─ :id           GET → get_user
         └─ orders    GET → list_orders, POST → create_order
 └─ static
     └─ *path         GET → serve_file

Implementation

class Node:
    def __init__(self):
        self.static = {}            # segment -> Node
        self.param = None           # (name, Node) for ":name"
        self.wildcard = None        # (name, handlers) for "*name"
        self.handlers = {}          # method -> handler


class RouteConflict(Exception): ...


class Router:
    def __init__(self):
        self.root = Node()

    @staticmethod
    def _split(path):
        return [s for s in path.split("/") if s]

    def add(self, method, path, handler):
        node = self.root
        segments = self._split(path)
        for i, seg in enumerate(segments):
            if seg.startswith("*"):
                if i != len(segments) - 1:
                    raise ValueError("wildcard must be the last segment")
                if node.wildcard is None:
                    node.wildcard = (seg[1:], {})
                elif node.wildcard[0] != seg[1:]:
                    raise RouteConflict(f"conflicting wildcard names at {path}")
                self._set(node.wildcard[1], method, handler, path)
                return
            if seg.startswith(":"):
                name = seg[1:]
                if node.param is None:
                    node.param = (name, Node())
                elif node.param[0] != name:
                    raise RouteConflict(f"conflicting parameter names at {path}")
                node = node.param[1]
            else:
                node = node.static.setdefault(seg, Node())
        self._set(node.handlers, method, handler, path)

    @staticmethod
    def _set(handlers, method, handler, path):
        if method in handlers:
            raise RouteConflict(f"duplicate route {method} {path}")
        handlers[method] = handler

    def resolve(self, method, path):
        """Returns (status, handler, params)."""
        found = self._match(self.root, self._split(path), 0, {})
        if found is None:
            return 404, None, {}
        handlers, params = found
        if method not in handlers:
            return 405, None, {"allow": sorted(handlers)}
        return 200, handlers[method], params

    def _match(self, node, segs, i, params):
        if i == len(segs):
            if node.handlers:
                return node.handlers, params
            if node.wildcard:                        # "/static/" with "*path" -> empty path
                return node.wildcard[1], {**params, node.wildcard[0]: ""}
            return None
        seg = segs[i]
        child = node.static.get(seg)                  # 1. static
        if child:
            found = self._match(child, segs, i + 1, params)
            if found:
                return found
        if node.param:                                # 2. parameter
            name, child = node.param
            found = self._match(child, segs, i + 1, {**params, name: seg})
            if found:
                return found
        if node.wildcard:                             # 3. wildcard takes the rest
            name, handlers = node.wildcard
            return handlers, {**params, name: "/".join(segs[i:])}
        return None

Backtracking matters: for /users/me/orders with routes /users/me and /users/:id/orders, the static branch me matches the segment but has no orders child, so the search falls back to the parameter branch.

r = Router()
r.add("GET", "/users/me", "current_user")
r.add("GET", "/users/:id", "get_user")
r.add("GET", "/users/:id/orders", "list_orders")
r.add("POST", "/users/:id/orders", "create_order")
r.add("GET", "/static/*path", "serve_file")

print(r.resolve("GET", "/users/me"))              # (200, 'current_user', {})
print(r.resolve("GET", "/users/42"))              # (200, 'get_user', {'id': '42'})
print(r.resolve("GET", "/users/me/orders"))       # (200, 'list_orders', {'id': 'me'})
print(r.resolve("GET", "/static/css/site.css"))   # (200, 'serve_file', {'path': 'css/site.css'})
print(r.resolve("DELETE", "/users/42/orders"))    # (405, None, {'allow': ['GET', 'POST']})
print(r.resolve("GET", "/nope"))                  # (404, None, {})

Middleware

Middleware wraps a handler: it can act before the call, after it, or stop the request entirely. The neat way to build the chain is to compose functions, each taking the next handler. This is the Chain of Responsibility pattern.

def logging_mw(next_handler):
    def handle(request):
        response = next_handler(request)
        request.setdefault("log", []).append(f"{request['path']} -> {response[0]}")
        return response
    return handle


def auth_mw(next_handler):
    def handle(request):
        if not request.get("user"):
            return (401, "unauthorized")
        return next_handler(request)
    return handle


def build(handler, middleware):
    for mw in reversed(middleware):            # first in the list runs first
        handler = mw(handler)
    return handler


def get_user(request):
    return (200, f"user {request['params']['id']}")


app = build(get_user, [logging_mw, auth_mw])
req = {"path": "/users/7", "params": {"id": "7"}, "user": "ana"}
print(app(req), req["log"])        # (200, 'user 7') ['/users/7 -> 200']
anon = {"path": "/users/7", "params": {"id": "7"}}
print(app(anon), anon["log"])      # (401, 'unauthorized') ['/users/7 -> 401']

Design decisions to explain

• Precedence is decided by the trie's search order, not by registration order. Routes behave the same however they're registered.
• Conflicts fail at registration time: two handlers for the same method and path, or /:id and /:user_id at the same position. Failing at startup is much better than surprising behavior in production.
• 404 vs 405: a path that exists with the wrong method should say which methods are allowed (the Allow header).
• Lookup cost is O(segments) without backtracking. In the worst case backtracking adds more, but real route tables are shallow.

Follow-ups

• Route groups: router.group("/api/v1", middleware=[auth]) prefixes paths and adds middleware to every route inside.
• Typed parameters: /users/:id<int> converts the value, and doesn't match if conversion fails.
• Trailing slashes and case: decide whether /users/ equals /users, and either normalize or redirect.
• Reverse routing: generate a URL from a route name and parameters, for links.
• Performance: compress chains of single-child static nodes into one node (a radix tree), as fast routers do.
• Concurrency: routes are usually registered at startup and only read afterwards, so no locks are needed if registration is closed before serving.

[!TIP] Practice Design an HTTP Router · Trie · Design Patterns