An API gateway sits in front of every upstream call, so its router is the hottest code path in the fleet. A linear scan over registered patterns is O(N) in the number of routes: at 500 routes and 20k req/s you are doing ten million string comparisons a second before a single handler runs. The standard library’s net/http ServeMux got real pattern matching in Go 1.22 with {param} wildcards and per-method registration, and its internal prefix tree is fine for a service with tens of routes. But a gateway with thousands of endpoints, host-based tenancy, per-route middleware, and priority rules that do not fit stdlib semantics needs a router built for the job. That is where a radix (compressed trie) tree earns its keep: lookup cost tracks the length of the path, not the number of routes.

Segments, not characters

HttpRouter, the design that made Go routers fast a decade ago, compresses the trie at the character level: common prefixes are shared into single nodes. For routing purposes you can compress at the segment level instead and get the same asymptotic story with much simpler code – each path component is a node, a static segment matches exactly, and a :param node matches any single component. Building it is straightforward, and lookup stays a few hundred nanoseconds regardless of how many routes you register.

A compact implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package router

import "net/http"

type node struct {
	segment    string
	children   []*node
	paramChild *node
	paramName  string
	handler    http.Handler
}

func (n *node) insert(segs []string, h http.Handler) {
	if len(segs) == 0 {
		n.handler = h
		return
	}
	seg := segs[0]
	if len(seg) > 0 && seg[0] == ':' {
		p := n.paramChild
		if p == nil {
			p = &node{paramName: seg[1:]}
			n.paramChild = p
		}
		p.insert(segs[1:], h)
		return
	}
	for _, c := range n.children {
		if c.segment == seg {
			c.insert(segs[1:], h)
			return
		}
	}
	c := &node{segment: seg}
	n.children = append(n.children, c)
	c.insert(segs[1:], h)
}

func (n *node) lookup(segs []string, params map[string]string) (http.Handler, bool) {
	if len(segs) == 0 {
		if n.handler != nil {
			return n.handler, true
		}
		return nil, false
	}
	for _, c := range n.children {
		if c.segment == segs[0] {
			if h, ok := c.lookup(segs[1:], params); ok {
				return h, true
			}
		}
	}
	if n.paramChild != nil {
		params[n.paramChild.paramName] = segs[0]
		if h, ok := n.paramChild.lookup(segs[1:], params); ok {
			return h, true
		}
		delete(params, n.paramChild.paramName)
	}
	return nil, false
}

The interesting parts are :param handling and failure semantics. Parameters are stored in a map populated during lookup, so a failed match at a deeper level must roll back the parameter it set – otherwise a partially matched /users/:id node can leave a bogus id behind. Static children are matched before the parameter child, so a concrete route beats a parameter route at the same position (/users/me should win over /users/:id), which matches the precedence users expect.

The linear for loop over children is fine up to a few hundred routes. Past that, sort children and binary-search them, or move to a per-node map[string]*node. The router in front of our public API sorts children and keeps parameters in a small ring buffer instead of a map; lookup on 4,000 routes runs around 400-500ns.

The numbers that matter

For a 12-segment path like /v2/tenants/abc-123/services/payments/operations/refund:

The linear scan degrades linearly, which is the whole problem. The trie is flat because it never looks at more than the path’s own segments. ServeMux stays sub-microsecond – credit to the stdlib team – but it cannot give you per-route middleware priorities or host-based namespacing without contortions.

Building the tree once

Radix trees reward immutability. Build the tree at startup from a static route manifest, then serve from it. Dynamic inserts at runtime force rebalancing and complicate concurrency: readers have to be safe while a writer mutates shared nodes, which drags locking onto a path that should be allocation-free and lock-free. If a gateway occasionally adds routes, build a fresh tree and swap it in behind an atomic.Pointer (Go 1.19+) rather than mutating in place.

Production lessons

• Compress at the segment level unless character-level compression buys you measurable memory; the extra code is not worth it otherwise.
• Match static segments before :param nodes and roll back parameters on partial-match failure.
• Keep the tree immutable and swap via atomic.Pointer when routes change; the router should be lock-free.
• Benchmark lookup against your real route list in CI; a regression to linear behavior is easy to introduce.
• For most single services, ServeMux in Go 1.22+ is genuinely fine. Build a radix router when you are a gateway: thousands of routes, host tenancy, or per-route middleware ordering.