Day12: The Prefix-Tree Router: route matching logic

Day 12: The Prefix-Tree Router: Unlocking High-Scale Route Matching

Welcome back, architects and engineers! In our last session, we dove deep into the world of immutable HTTP messages with PSR-7, setting the stage for robust request handling. Today, we tackle one of the most critical components in any high-scale web system: the router.

At 100 million requests per second, traditional PHP routing strategies crumble. The "bootload tax" – the overhead of re-initializing your application on every request in a shared-nothing architecture – becomes an astronomical cost. But with modern, persistent PHP runtimes (like those powered by Swoole or RoadRunner), we have a new opportunity: building and maintaining state between requests. This is where our Prefix-Tree Router truly shines, transforming route matching from a performance bottleneck into a lightning-fast operation.

Agenda for Today:

• The Routing Dilemma at Scale: Why traditional regex-based routers fall short.

• Core Concept: The Prefix-Tree (Trie): What it is and why it's a game-changer for routing.

• Architecting the Trie Router: How it fits into our high-scale CMS.

• Control Flow & Data Flow: Request URI to route match.

• Hands-on: Building the Trie Structure: Populating routes segment by segment.

• Assignment: Implementing the core route matching logic.

The Routing Dilemma at Scale: Beyond Regular Expressions

Imagine a CMS with thousands, tens of thousands, or even hundreds of thousands of routes. Each time a request hits your server, your router needs to find the one correct handler. Most frameworks traditionally rely on iterating through a list of routes, applying complex regular expressions to the incoming URI until a match is found.

This approach introduces several critical issues at scale:

1. Linear Scan Overhead: In the worst case, you might iterate through many routes before finding a match, or worse, finding no match. O(N) where N is the number of routes.

2. Regex Compilation Cost: Regular expressions are powerful but expensive. Compiling a regex pattern for each route on every request, especially in a shared-nothing PHP environment, adds significant CPU overhead. Even with caching, the matching itself is not always optimal for path-like structures.

3. Ambiguity & Prioritization: Managing overlapping routes and ensuring the correct one is picked (e.g., /users/new vs. /users/{id}) becomes a complex, error-prone task.

At 100M RPS, every millisecond counts. We need a routing mechanism that offers deterministic, near-constant-time performance regardless of the number of routes.

Core Concept: The Prefix-Tree (Trie)

Enter the Prefix-Tree, also known as a Trie (from retrieval). It's a tree-like data structure used for efficient retrieval of a key in a dataset of strings. Each node in the tree represents a character or, in our case, a segment of a URL path.

How it works for routing:
Instead of comparing full paths or regex patterns, we traverse the URI segment by segment, following the tree branches.

Consider these routes:

• /users

• /users/{id}

• /users/{id}/profile

• /posts

• /posts/{slug}

A Trie for these routes would look something like this:

When a request for /users/123/profile comes in:

1. Start at (root).

2. Match users -> move to users node.

3. Match 123. The users node has a {id} child. This is a parameter segment. We match it and store 123 as the id parameter. Move to {id} node.

4. Match profile. The {id} node has a profile child. Move to profile node.

5. End of URI. The profile node is an "end of route" node. We have a match!

Why it's superior: