Skip to content

The Fork in the Path

Edit source

Matching a URL to one of a thousand routes in time that ignores how many there are.

Part 5 of 38ofFamiliars
  1. 1Session Zero
  2. 2Rolling for a Name
  3. 3The Haunted Handler
  4. 4The Sparse Wheel
  5. 5The Fork in the Path
  6. 6The Planet as a Prefix
  7. 7The Long Division
  8. 8The Line You Usually Cancel
  9. 9Sixteen Bytes Too Far
  10. 10Packing a UUID
  11. 11Bytes You Can Type
  12. 12The Shunting Yard
  13. 13Interchangeable Parts
  14. 14One Loop Per Core
  15. 15The Seam
  16. 16Append Only
  17. 17Who Owns the Tree
  18. 18Down the Flume
  19. 19The Syscalls That Lie
  20. 20Asking the Machine
  21. 21The Earth Is Not a Ball
  22. 22Smith and Schmidt
  23. 23Many Ways to Be Similar
  24. 24Built to Disappear
  25. 25Sometimes a Mutex Is Right
  26. 26Work, Not Threads
  27. 27Before the Program Runs
  28. 28No Collisions, Ever
  29. 29The Names Enums Throw Away
  30. 30The Bag of Holding
  31. 31A Map of Blocks
  32. 32Certainly Absent
  33. 33A Tree Made of Types
  34. 34Everything but the Views
  35. 35Who Owns the Wheel
  36. 36A Guest on the Loop
  37. 37Acknowledged Means Durable
  38. 38Sorted as Bytes

Part of Familiars: the small, sharp libraries I carved out of Xapiand. The sparse wheel is the strangest thing in the engine; this one is the first thing every request meets: radix-router.

A request arrives as a URL, and before anything real can happen, something has to decide which handler owns it. /documents/count goes here, /documents/42 goes there, /static/css/site.css goes somewhere else entirely. That decision happens on every single request, so it sits squarely on the hot path, and the naive way to make it is the way that quietly kills you as the server grows.

The router that gets slower as you succeed

Section titled “The router that gets slower as you succeed”

The first router anyone writes is a list. Register each pattern, and on every request walk the list comparing until one matches. It is fine at ten routes. It is O(routes): every endpoint you add makes every lookup a little slower, and a miss, a URL that matches nothing, is the worst case, because it has to check the entire table before it can say no. A mature service has hundreds of endpoints. You built more features and made the router slower, and the slowest path is the 404 an attacker can send you a million times.

radix-router is the structure that breaks that coupling. It stores the routes in a radix tree, a prefix trie with the single-child chains compressed out, so a lookup walks the shared prefixes of the path rather than scanning the table. The cost is O(path length), and path length does not grow when you add routes. Flat. On the same pattern language, here is each lookup’s cost in nanoseconds against the linear scan, across growing tables:

routeslinear ns/opradix ns/opspeedup
843.811.33.9x
128692.919.335.9x
10245048.624.7204x
1024 (miss)10587.924.0440x

The radix line barely moves, 11 to 24 nanoseconds, and only because a deeper tree touches more cache lines. The linear line just tracks the route count. This is the structure httprouter popularized and that Gin and Echo are built on; radix-router is the same idea in header C++.

A trie that only held static paths would be easy, and it would not be worth a post. The interesting part is that real routes are not all static. Two segment kinds turn the tree from a lookup into a search:

r.insert("/documents/count", 1);
r.insert("/documents/:id", 2); // ":id" matches one segment
r.insert("/static/*path", 3); // "*path" matches the rest

A :name param matches any one segment; a *name catch-all swallows the remainder. Now /documents/count is ambiguous: it matches the static count and the param :id. The router has to prefer the more specific one, which means that when a promising branch dead-ends deeper down, it cannot just fail. It has to back up to the last fork where a param or catch-all was waiting and try that instead. A trie became a maze with forks, and matching is a walk that sometimes has to retrace its steps.

Backtracking is exactly where routers get dangerous, because naive backtracking is exponential. Stack enough overlapping :param and static segments and a single crafted path can make the matcher explore a combinatorial number of dead ends, the routing equivalent of catastrophic regex backtracking, a denial of service delivered as one innocent-looking URL. The whole trick of a serious router is to keep the backtracking bounded: explore the param and catch-all alternatives at each fork in a fixed order, never re-descend a subtree you have already ruled out, and let the worst case stay a function of the path’s depth, not of how cleverly an attacker overlapped your routes. A miss is fast, and with the backtracking bounded, a miss is safe.

Reach for it wherever you match one input against many patterns and the count of patterns is going to grow: an HTTP server, obviously, but also a command dispatcher, a permission matcher, any /-separated namespace. Captured :id and *path values come back through a Params object as string views, no copies, so a lookup allocates nothing once its Params has grown. It is header C++, one type, and it does the one thing a router must never get wrong: it stays flat, and it stays bounded, no matter what you throw at it.

The next familiar leaves the server’s front door for something much older and much larger. It takes the whole surface of the Earth and turns it into search terms a plain text index can answer, by tiling the planet in triangles.