Add route evaluation statistics

[eziskind]

Add statistics for the number of route rule evaluations (broken down by rule type, ie. exact match, prefix, regex, etc) This could live under the HCM or router scope, eg. http.{prefix}.rds.{route}.evaluations.prefix http.{prefix}.rds.{route}.evaluations.exact http.{prefix}.rds.{route}.evaluations.regex

[eziskind]

cc @htuch

[mattklein123]

I don't have any high level objection to this, but I do want to try to think through what other stats we might want to add in the future, since route matching is very complicated and will only get more complicated in the future as we add sub-linear matching options (hash and trie matching prior to optional linear matching). cc @snowp who I have been recently discussing this with and is working on adding sub-linear matching to the generic matching proposal.

[htuch]

Another complementary approach might be to make information available to access log sinks indicating which route rule was selected. This could take the form of a compressed list of integers representing the field selection as the route table was traversed, I'm thinking something like the way that comments are identified in Protobuf's SourceCodeInfo. Or it could be similar to a FieldMask.

This doesn't capture exactly what @eziskind was after, since it would only give the final route selection, so wouldn't deal with filters modifying routes and forcing a recalculation. But, I think it's very powerful as it allows deep insight into how a route table is used offline and can be used to understand how an individual request ended up being routed.

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had activity in the last 30 days. It will be closed in the next 7 days unless it is tagged "help wanted" or "no stalebot" or other activity occurs. Thank you for your contributions.