Principles and Implementation of Routing Systems

Principles and Implementation of Routing Systems

Problem Description
The routing system is a core component of backend frameworks, responsible for mapping client requests (such as HTTP requests) to corresponding handling logic (such as controller methods). In interviews, its design principles, matching rules, priority handling, and performance optimization strategies are often examined. For example: How to design a routing system that supports static routes, parameter routes (like /users/:id), and wildcards? How to efficiently match request paths?

1. Basic Functions of Routing
The core task of a routing system is to parse the request's URL and HTTP method (GET, POST, etc.) to determine which handler function to execute. For example:

  • Request GET /users/123 → maps to UserController.getUser(123)
  • Request POST /login → maps to AuthController.login()

2. Types of Routing Rules
Common routing rules are divided into three categories:

  • Static Routes: Exact path matching, e.g., /api/users.
  • Parameter Routes: Paths containing placeholders (e.g., /users/:id), where the placeholder part is parsed as a parameter.
  • Wildcard Routes: Uses * to match multi-level paths (e.g., /files/*path), often used for static resource handling.

3. Storage Structure of Routing Tables
For efficient matching, routes are usually compiled into internal data structures:

  • Hash Table: Suitable for static routes, allowing fast lookup via URL string hashing.
  • Prefix Tree (Trie Tree): Core structure for handling parameter routes and wildcards.
    • Example: Store /users/:id and /users/profile in a prefix tree, with the common prefix /users as a shared node, and :id and profile as child nodes.

4. Step-by-Step Process of Route Matching
Take the request GET /users/123 as an example:
Step 1: Group by HTTP Method
First, filter all routing rules for the GET method to narrow down the matching scope.

Step 2: Path Segmentation and Traversal
Split the path into segment arrays ["users", "123"] using /, and traverse the prefix tree starting from the root node:

  • The first segment "users" matches the static node users, moving to the child node.
  • The second segment "123" has no matching static node, but if the current node has a parameter child node (e.g., :id), then "123" is parsed as the parameter id=123.

Step 3: Parameter Extraction and Priority
If both a static route /users/profile and a parameter route /users/:id exist, prioritize matching the more specific static route. The matching order is typically:

  1. Static Routes (Highest Priority)
  2. Parameter Routes
  3. Wildcard Routes (Lowest Priority)

4. Key Performance Optimizations

  • Route Compilation: Pre-compile routing rules into a prefix tree at startup to avoid re-parsing for each request.
  • Cache Matching Results: Cache the handler function for frequently requested paths (e.g., /api/users).
  • Regex Optimization: Use regular expression constraints for parameter routes (e.g., restricting :id to numbers) to terminate invalid matches early.

5. Practical Application Example
Take Express.js as an example; its routing implementation is based on a structure similar to a prefix tree:

// Route Registration
app.get('/users/:id', (req, res) => {
  res.send(`User ID: ${req.params.id}`);
});

// Internal Matching Process:
// 1. Build tree nodes: root → "users" → :id
// 2. When requesting /users/123, match :id along the tree nodes and extract params = {id: '123'}

Summary
The core of a routing system is to efficiently match URLs through data structures (such as prefix trees), while ensuring accuracy through priority rules. Understanding its compilation, matching, and optimization processes helps design high-performance frameworks for high-concurrency scenarios.