Add efficient path-based prefix matching

[howardjohn]

Title: Add efficient path-based prefix matching

Description:
The Kubernetes Ingress spec, and soon the gateway-api spec (kubernetes-sigs/gateway-api#866) implement a different form of prefix path matching than Envoy. From the spec:

Prefix: Matches based on a URL path prefix split by /. Matching is case sensitive and done on a path element by element basis. A path element refers to the list of labels in the path split by the / separator. A request is a match for path p if every p is an element-wise prefix of p of the request path.

Essentially, if we want to match prefix=/foo in this manner we have two options:

• Convert to a regex match (like https://github.com/projectcontour/contour/blob/2b3376449bedfea7b8cea5fbade99fb64009c0f6/internal/envoy/v3/route.go#L78)
• Create two routes, one with prefix=/foo/ and one with exact=/foo.

The first option has a runtime cost in route matching. The second has a cost in Envoy+Control plane during XDS processing.

Given how common this is/will be in Envoy users, it would be great if there was a more efficient way to control this. For example, setting a bool var like case_sensitive to control the behavior or defining some new type of path_specifier.

cc @jpeach @youngnick @lambdai

[jpeach]

Xref kubernetes-sigs/gateway-api#869

[youngnick]

As @howardjohn said above, we've chosen to go with the "replace with regex" option for now in Contour, but strong +1 that this would be very nice for us.

[alyssawilk]

cc @htuch @envoyproxy/api-shepherds for thoughts

[mattklein123]

We already do support control over route case sensitivity in matching.

What is the actual feature request here? I'm a little confused. Why doesn't prefix=/foo work for your example?

[howardjohn]

The problem is prefix=/foo is a string prefix. The spec has "element-wise"/label prefix. So in the spec, /foo would match /foo/bar but NOT /foobar. In envoy, it would match both.

This is semantically equivalent to existing Envoy matching capabilities: prefix=/foo/ OR exact=/foo, or converting to a regex (https://github.com/projectcontour/contour/blob/2b3376449bedfea7b8cea5fbade99fb64009c0f6/internal/envoy/v3/route.go#L78). Both of these incur a performance penality

[mattklein123]

OK, so you want a "path splitting prefix mode?" That seems simple enough.

[htuch]

There's some overlap with #7763, which also provides matching with path fragments.

[tpetkov-VMW]

I can try to do this, if it isn't obsoleted by the issue above.

[kyessenov]

It would be nice to use unified matchers here. I imagine we'd need some sublinear implementation to deal with categories of templates (like in API gateway cases).

[tpetkov-VMW]

It would be nice to use unified matchers here. I imagine we'd need some sublinear implementation to deal with categories of templates (like in API gateway cases).

@kyessenov, you mean having a new match pattern here?
api/envoy/type/matcher/v3/string.proto
As far as I could tell, this would need a change in the xds project as well:
https://github.com/cncf/xds/blob/main/xds/type/matcher/v3/string.proto
What is the process of submitting code in the xds project?
Just raise an issue + PR there and then bump in api/bazel/repository_locations.bzl ?

[kyessenov]

I was thinking something like https://www.envoyproxy.io/docs/envoy/latest/api-v3/config/common/matcher/v3/matcher.proto#config-common-matcher-v3-matcher-matchertree but with a custom matcher for templated URLs. There is already a prefix matcher but I think it's the simple prefix.

[tpetkov-VMW]

I was thinking something like https://www.envoyproxy.io/docs/envoy/latest/api-v3/config/common/matcher/v3/matcher.proto#config-common-matcher-v3-matcher-matchertree but with a custom matcher for templated URLs. There is already a prefix matcher but I think it's the simple prefix.

Sounds like straight up implementing #7763
I've a much simpler prototype that just does the path-based prefix matching in the simplest way possible, albeit with some duplicated code for now.
I'll open a PR, so people can check out the code, and if it's not the correct thing to do, It should at least be easier to discuss.