Regex vs Prefix Route Matching Performance

Every request that reaches a gateway pays a route-matching tax before any policy runs or any byte is proxied. On a route table of a few dozen entries that tax is invisible, but on a fleet carrying tens of thousands of routes — or one route table containing a single badly written regular expression — it becomes the difference between a flat P99 and a worker thread pinned at 100% CPU by one crafted URI. This page benchmarks the two dominant matching strategies, radix/prefix matching versus regular-expression matching, explains why RE2-backed safe_regex is safe where PCRE-style backtracking is not, and shows exactly how to configure and bound each in Kong 3.x and Envoy 1.32+.

Prerequisite concepts

This is a deep dive within path and header-based routing; read that first for the mechanics of how a gateway evaluates candidate routes in priority order and how header predicates layer on top of path matching. The broader trade-offs — deterministic evaluation order, config propagation, and where route matching sits in the request lifecycle — are covered in the advanced routing and API versioning overview. If your regex routes exist to serve versioned APIs, the routing-decision model in that overview explains why the matching strategy has direct latency consequences at step four of the request pipeline.

How the two matchers actually work

A prefix matcher stores routes in a radix tree (a compressed trie) keyed on the URI path. Shared leading segments such as /api/v2/ are stored once, and matching walks the tree character by character, branching only where paths diverge. Lookup cost is bounded by the length of the incoming path, not by the number of routes, so adding the ten-thousandth route barely moves the match time. This is the near-constant-time behavior that lets a gateway hold a large route table without P99 degradation.

A regex matcher stores each pattern as a compiled automaton and, because two regexes can both match the same input, evaluates candidates in explicit priority order until one wins. Cost therefore scales with how many regex routes are tried before the match, plus the per-pattern evaluation cost. The per-pattern cost depends entirely on the engine: a finite-automaton engine such as RE2 is linear in input length, while a backtracking engine such as PCRE can, on adversarial input, explore an exponential search space.

The practical takeaway: prefix matching is the default because its cost is bounded and predictable. Regex is a tool you reach for deliberately, and when you do, the engine choice is a security decision, not just a performance one.

Benchmarking route-match latency

Route-match cost is easy to mismeasure because end-to-end latency is dominated by network and upstream time. To see the matcher in isolation, remove everything else: point the gateway at a local upstream that returns 200 immediately, warm the process so route compilation and any JIT are complete, then drive constant-rate load against two paths — a best case that matches the first route and a worst case that matches the last route or forces the longest regex to evaluate. Compare the gateway-internal request-duration metric, not curl timings.

# k6 — constant-arrival-rate probe isolating router cost against a no-op upstream
# Run twice: URL=/api/v2/orders/1 (best case) and a crafted worst-case path.
cat > router-bench.js <<'EOF'
import http from 'k6/http';
export const options = {
  scenarios: {
    match: {
      executor: 'constant-arrival-rate',
      rate: 5000, timeUnit: '1s', duration: '60s',
      preAllocatedVUs: 200, maxVUs: 500,
    },
  },
  thresholds: { http_req_duration: ['p(99)<5'] },
};
export default function () {
  http.get(`http://gateway.local:8000${__ENV.PATH}`);
}
EOF

PATH=/api/v2/orders/1 k6 run router-bench.js         # best case
PATH=/api/v2/orders/$(python3 -c "print('9'*4096)") k6 run router-bench.js  # adversarial

Read the P99 of the gateway’s own timing, exposed by Kong as kong_latency_ms (the time Kong itself spent, excluding upstream) and by Envoy as the envoy_http_downstream_rq_time histogram minus upstream time. A healthy prefix table shows a P50/P99 gap of well under a millisecond that does not widen with the adversarial input. A vulnerable PCRE route shows the adversarial P99 blowing out by orders of magnitude while the best case stays flat — that divergence is the whole point of the test.

Prefix matching: Kong and Envoy

Both gateways make prefix matching the fast path. In Kong 3.x, a route that lists paths with the ~ regex prefix omitted is treated as a plain prefix and folded into the router’s trie:

# Kong 3.x — plain-prefix route (radix-tree fast path, no regex)
_format_version: "3.0"
services:
  - name: orders-api
    url: http://orders.internal:8080
    routes:
      - name: orders-v2
        # No leading "~" => prefix match, compiled into the router trie
        paths: ["/api/v2/orders"]
        strip_path: false
        # router flavor "expressions" (default in 3.x) keeps prefix
        # and regex routes in separate, independently-optimized matchers

Kong 3.x defaults to the expressions router, which keeps prefix predicates in a trie and only falls back to regex evaluation for routes that actually use a pattern. Envoy expresses the same intent with an explicit prefix (or path for exact) matcher on the route:

# Envoy 1.32+ — prefix and exact matchers (no regex engine invoked)
routes:
  - match:
      prefix: "/api/v2/orders"
    route: { cluster: orders_v2 }
  - match:
      path: "/healthz"          # exact match, cheapest of all
    route: { cluster: health_sink }

Envoy evaluates routes within a virtual host in order, but prefix and path matches are simple string operations with no backtracking risk. Keep these ahead of any regex routes in the list so the common case never reaches the regex matcher.

Regex matching done safely: RE2 and safe_regex

When a route key is genuinely a pattern — a captured id, a version token, several legacy shapes collapsing onto one upstream — use regex, but force an RE2 engine. Envoy exposes this directly through safe_regex, which is RE2-only and therefore immune to catastrophic backtracking:

# Envoy 1.32+ — RE2 safe_regex on a captured, length-bounded id
routes:
  - match:
      safe_regex:
        # RE2 semantics: linear time, no backtracking possible.
        # Anchored, explicit char class, explicit length bound {1,16}.
        regex: "^/api/v2/orders/[0-9]{1,16}$"
    route: { cluster: orders_v2 }
  - match:
      prefix: "/api/v2/"
      headers:
        - name: "x-api-version"
          string_match:
            safe_regex:
              regex: "^v2\\.(0|1|2)$"
    route: { cluster: orders_v2_pinned }

Kong 3.x compiles route regexes with RE2 as well (the expressions router and the traditional router both use RE2 for path regexes), and you opt into a regex route with the ~ prefix:

# Kong 3.x — regex route (RE2-compiled), anchored and length-bounded
_format_version: "3.0"
services:
  - name: orders-api
    url: http://orders.internal:8080
    routes:
      - name: orders-by-id
        # Leading "~" marks this as a regex path; Kong compiles it with RE2.
        paths: ["~/api/v2/orders/[0-9]{1,16}$"]
        # Give plain-prefix routes a higher priority so this regex is
        # only reached when the cheaper matchers miss.
        regex_priority: 10

The three disciplines that make either configuration safe are visible in both snippets: anchor the pattern (^ … $) so it cannot match unexpectedly deep in a long string, use an explicit character class ([0-9]) instead of the dot wildcard so the matcher rejects junk early, and bound the quantifier ({1,16}) so input length is capped. Even under RE2 these keep the linear-time constant small and the route intent obvious to reviewers.

Bounding regex you cannot avoid

RE2 guarantees linear time, but “linear in a 1 MB URI” is still work you may not want to do on the hot path. Bound the input before it reaches the matcher. In Envoy, cap the request line and header sizes at the connection manager so an oversized path is rejected with a 431 before routing:

# Envoy 1.32+ — reject oversized request lines before the router runs
http_connection_manager:
  max_request_headers_kb: 16
  common_http_protocol_options:
    max_headers_count: 100
  # Paths longer than this are 431'd at parse time, never regex-matched.

In Kong, the underlying Nginx layer bounds the request line with large_client_header_buffers, and you should keep the number of regex routes small and prioritized so the router reaches them rarely. If you are stuck with a legacy PCRE-based system that you cannot move to RE2 — for example a custom Lua plugin using ngx.re in PCRE mode — compile with the jit and o flags for caching but, critically, never run an unbounded PCRE pattern against untrusted input without an explicit match-timeout guard, because that is exactly the configuration that lets one request stall a worker.

Decision matrix

The rule that falls out of the matrix: make prefix the default, promote it above regex routes in priority so the common request never touches the regex matcher, and when a pattern is unavoidable, keep it RE2, anchored, classed, and length-bounded.

Gotchas and failure signals

A single unanchored regex poisons the whole table. A pattern like ~/orders/[0-9]+ without a trailing $ matches /orders/1/../../admin, silently routing traffic you did not intend. The failure signal is upstream logs showing paths the route “should not” reach. Always anchor both ends.

Regex priority inversion. In Kong, if a regex route is given a higher regex_priority than a more specific prefix route, the regex wins and you lose the fast path. Watch for a rising kong_latency_ms P99 after adding regex routes — it means requests that used to hit the trie are now being regex-evaluated.

Envoy route order shadowing. Envoy stops at the first matching route in a virtual host. A broad prefix: "/" placed above a safe_regex route makes the regex dead config that never matches; the signal is a route with zero envoy_vhost_vcluster traffic despite live paths that should hit it.

PCRE timeout absent. If you must run PCRE in a custom plugin, the absence of a match timeout turns one adversarial path into sustained CPU saturation and connection-pool exhaustion. The signal is a worker at 100% CPU with a flat request count — work is happening, but no requests complete.

Validation

• Every regex route is anchored with ^ and $ and uses explicit character classes, not . wildcards.
• Every quantifier in a route regex has an explicit upper bound ({1,16}), not an open + or * on untrusted segments.
• All path and header regexes run under RE2 (safe_regex in Envoy, ~-prefixed paths in Kong 3.x) — no unbounded PCRE on request input.
• Prefix / exact routes are prioritized above regex routes so the common request never reaches the regex matcher.
• Request-line and header size limits are set (max_request_headers_kb, large_client_header_buffers) so oversized paths are rejected before matching.
• Router latency is benchmarked with best-case and adversarial paths, comparing gateway-internal P99 (kong_latency_ms, Envoy request-time histogram).
• No route regex uses a backreference or nested quantifier that would require a backtracking engine.

FAQ

Is regex route matching always slower than prefix matching?

For a single route, a compiled RE2 regex on a short URI is only microseconds slower than a radix-tree prefix lookup, and the difference is usually invisible against network latency. The problem is scale and worst case. Prefix matching stays near-constant time as the route table grows because a radix tree shares common path segments, while a flat list of regex routes is evaluated in priority order until one matches, so match cost grows roughly linearly with the number of regex routes ahead of the winner. PCRE-style engines can also degrade to exponential time on pathological input. Use prefix matching for the bulk of routes and reserve regex for the handful of cases that genuinely need it.

What is catastrophic backtracking and how do RE2 and safe_regex prevent it?

Catastrophic backtracking happens when a backtracking regex engine such as PCRE explores an exponential number of ways to match a pattern with nested or overlapping quantifiers, for example (a+)+ against a long non-matching string. A single crafted URI can stall a worker thread for seconds. RE2, the engine behind Envoy safe_regex and Kong 3.x router regex, compiles the pattern to a finite automaton and matches in time linear to the input length with no backtracking, so it cannot be forced into exponential blowup. It rejects a few PCRE features such as backreferences that require backtracking, which is an acceptable trade for guaranteed linear time on untrusted input.

How do I benchmark route-match latency in isolation?

Isolate the router from upstream and network time. Point the gateway at a local no-op upstream that returns 200 immediately, warm the process so JIT and route compilation are complete, then drive it with a constant-rate load generator such as k6 or wrk against both a best-case path (matches the first route) and a worst-case path (matches the last route or forces backtracking). Compare P50 and P99 of the gateway-internal request duration metric, not end-to-end latency, and include an adversarial input that exercises your longest or most complex regex. The gap between P50 and P99 on the worst-case path is the real signal.

When is regex route matching actually unavoidable?

Regex is justified when the routing key is genuinely a pattern rather than a fixed prefix: capturing a variable path segment such as a tenant slug or resource id, matching a version token like v2.1 in a header, or normalizing several legacy path shapes onto one upstream. Even then, anchor the pattern with a leading caret, keep it under an explicit length bound, use character classes instead of the dot wildcard, and run it under an RE2 engine. If the requirement is simply longest-prefix selection, use the native prefix or path parameter matcher instead, which is faster and cannot backtrack.

Parent: Path & Header-Based Routing

Related

• Routing by API Key vs JWT Claims — header-predicate routing where the matcher choice interacts with credential inspection.
• Advanced Routing & API Versioning — where route matching sits in the request lifecycle and why evaluation order must be deterministic.
• Scaling Limits & Capacity Planning — route-table growth ceilings and when to decompose into domain-scoped gateways.