envoyproxy / envoyproxy/envoy

Scalable route configuration

Open
#6,602 21 comments 2 reactions 1 assignee Claimed by @snowp View on GitHub
area/http design proposal help wanted
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.