DFA-based Request Routing

Routing Invariant

For a given request path and configuration snapshot, routing resolution must be deterministic and bounded. A request must either resolve to a single eligible endpoint or fail explicitly, without fallback to ambiguous or order-dependent matching. Path matcher must be able to support both static and dynamic route paths.

Problem

The gateway must resolve incoming requests to a concrete upstream endpoint based on path templates and client-specific configuration, while remaining on the hot path for every request.

A naïve approach based on sequential regex matching introduces unbounded and configuration-dependent runtime cost, making worst-case behavior difficult to reason about as the number of endpoints grows.

Why Naïve Approaches Fail

Regex-based routing requires evaluating patterns sequentially until a match is found. This makes routing cost proportional to both the number and ordering of endpoint definitions.

As endpoint sets evolve, this approach couples routing performance to configuration shape rather than request structure, creating hidden hot paths and unpredictable latency under load.

Solution

Routing rules are compiled into a deterministic finite automaton (DFA) at configuration load time, converting path templates into a prevalidated state machine.

At request time, routing becomes a bounded state traversal driven by request path segments, eliminating regex evaluation from the hot path and making routing cost predictable.

Constraints

Hot-path latency: Routing executes on every request and cannot perform dynamic allocation or external lookups.

Configuration churn: Endpoint definitions change over time and must be applied without downtime.

Debuggability: Routing behavior must remain explainable to engineers without requiring automata theory expertise.

Deferred Complexity

Problem: DFA rebuilds occur asynchronously when configuration changes.

During rebuild windows, requests may briefly route using stale definitions. Eliminating this entirely would require distributed coordination or versioned routing plans, which was not justified at the current scale.

Binary representation: Routing tables are currently serialized using Go's gob encoding to minimize memory footprint and reduce cache pressure for large in-memory structures. The representation favors compactness over long-term schema evolution.

This choice simplifies early development but makes versioning and backward compatibility of binary structures harder to reason about. As routing structures stabilize and cross-version compatibility becomes more important, this layer is expected to migrate to a schema-driven format such as Protobuf.

Tradeoffs Accepted

Memory over CPU: DFA tables consume additional memory but provide stable routing cost regardless of configuration size.

Compile-time complexity: Routing logic is shifted into configuration load time, simplifying request handling at the cost of more complex setup paths.

What I'd Change at Scale

Introduce versioned routing plans to allow lock-free DFA swaps and eliminate rebuild races once configuration churn or request volume increases significantly.