Scalable route configuration
- Dominant language
- C++
- Stars
- 28.9k
- Forks
- 5.6k
- Avg merge
- 1d 22h
- Merged PRs (30d)
- 430
Description
The existing Envoy `RouteConfiguration` must be evaluated linearly and contains match criteria with hard to predict execution time (regular expressions). For scale-up Envoy instances where very large route configurations for a host may be present (let's say O(1m)) or multi-tenant Envoy instances, this becomes problematic.
There are many ways this could be solved:
1. Envoy could optimize based on presented configuration, for example a trie could be recovered from repeated patterns or a specific match order. This is challenging if the existing linear semantics are to be preserved and involves Envoy complexity.
2. We could have variants of regular expressions, e.g. prefix/suffix/glob or RE2 that are cheaper and more predictable to evaluate.
3. We could have a parallel `RouteConfiguration` with trie-like semantics, where evaluation order is designed for efficiency.
Some combination of (2) and (3) seems likely to yield a clean solution IMHO, but I'm keen to hear from others.
@jmarantz @mattklein123 @dmitri-d @yanavlasov
Contributor guide
Assessment
This issue has not been assessed yet.