Routing table using Envoy's Matchers API instead of Routes List

Description: When using Envoy with a high number of routes, the routes list linear matching drastically reduce the maximum number of req/s that can be handled by a worker thread depending on which routes match the requests. In high throughput environment, careful consideration needs to be taken to design the route such that the highest throughput routes are placed higher in the routing list. This work is tedious and error prone.

Envoy offers an alternative that, AFAIK, isn't used in any of the open-source control planes (contour, emissary-ingress, envoy-gateway): the matchers API. The matchers API is a more recent Envoy API that allow the control plane to generate a route tree, thus allowing for O(min{input key length, longest prefix match}) time complexity instead of linear.

Relevant Info:

• Sublinear route matching with Matchers API instead of linear with routes list

• Summary of a quick benchmark: this shows the impact of the linear matching:

Routes list:
Requests match first route: 67.7k req/s, 90th latency is 1.7ms
Requests match last route: 11.1k req/s, 90th latency is 11.6ms

Matcher tree:
Requests match (any route, always same result): 66.4k req/s, 90th latency is 1.7ms

Envoy was configured with 2000 unique prefix routes, each using direct_response (so really testing Envoy raw performance only). The client was saturating Envoy, configured with only 1 worker.

• From @arkodg on the Slack channel:

This would impacts 2 layers:
- gateway-api layer which sorts based on a specific logic to implement the default first match
- xds-translator layer will takes that info and programs the route matcher