envoyproxy/envoy

Scalable route configuration

Open

#6,602 opened on Apr 16, 2019

View on GitHub
 (21 comments) (2 reactions) (1 assignee)C++ (5,373 forks)batch import
area/httpdesign proposalhelp wanted

Repository metrics

Stars
 (27,997 stars)
PR merge metrics
 (Avg merge 8d) (378 merged PRs in 30d)

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

Research direction
Study the current Envoy RouteConfiguration implementation, focusing on linear evaluation and regular expression matching. Investigate optimizations like trie based routing or prefix/suffix matching. Propose a prototype for one of the suggested solutions.
Tech stack
cpp
Domain
backendinfrastructurenetworking
Issue type
Feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
3
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
Over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Mostly clear
Prerequisites
C++Data structures
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
15