java-topology/docs/tickets/envoy-0001-previous-hosts-retry-predicate-linear-scan.md

envoy-0001: PreviousHostsRetryPredicate std::find O(n) per retry attempt → O(n²)

Target: envoyproxy/envoy Severity: HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity) File: source/extensions/retry/host/previous_hosts/previous_hosts.h Status: PATCHED

Description

PreviousHostsRetryPredicate::shouldSelectAnotherHost() performs std::find on attempted_hosts_ (a std::vector<HostDescription const*>). This method is called by the load balancer inside a host-selection retry loop (ZoneAwareLoadBalancerBase::chooseHost) for every candidate host on every retry attempt. With R retries and H previously-attempted hosts, the total work is O(R × H) comparisons — O(n²) in the worst case where max_attempts equals the cluster size.

Location	Pattern
previous_hosts.h:10	std::find(attempted_hosts_.begin(), attempted_hosts_.end(), &candidate_host)
load_balancer_impl.cc:668	outer loop: for (size_t i = 0; i < max_attempts; ++i) calling shouldSelectAnotherHost
thread_aware_lb_impl.cc:232	same pattern in thread-aware variant

Root cause

// previous_hosts.h — O(n) scan per call
bool shouldSelectAnotherHost(const Upstream::Host& candidate_host) override {
    return std::find(attempted_hosts_.begin(), attempted_hosts_.end(),
                     &candidate_host) != attempted_hosts_.end();
}
void onHostAttempted(Upstream::HostDescriptionConstSharedPtr attempted_host) override {
    attempted_hosts_.emplace_back(attempted_host.get());
}
private:
    std::vector<Upstream::HostDescription const*> attempted_hosts_;

Caller loop in load_balancer_impl.cc:658:

const size_t max_attempts = context ? context->hostSelectionRetryCount() + 1 : 1;
for (size_t i = 0; i < max_attempts; ++i) {
    host = chooseHostOnce(context);
    if (!host || !context || !context->shouldSelectAnotherHost(*host)) {
        return host;  // O(attempted_hosts) per iteration
    }
}

With a cluster of N=100 endpoints and max_attempts=100, a single load-balancing decision may require up to 100 × 100 = 10,000 pointer comparisons. In a busy proxy handling thousands of requests/second, this compounds.

Fix

Replace attempted_hosts_ vector with absl::flat_hash_set<> or std::unordered_set<>. Pointer identity is the key, so no custom hash is needed — pointer addresses hash trivially.

#include "absl/container/flat_hash_set.h"

bool shouldSelectAnotherHost(const Upstream::Host& candidate_host) override {
    return attempted_hosts_.contains(&candidate_host);  // O(1)
}
void onHostAttempted(Upstream::HostDescriptionConstSharedPtr attempted_host) override {
    attempted_hosts_.insert(attempted_host.get());  // O(1) amortized
}
private:
    absl::flat_hash_set<Upstream::HostDescription const*> attempted_hosts_;

Ops/ns numbers (Java benchmark)

See defects/envoy/unit/EnvoyTest.java. At R=100 retries, H=100 hosts: slow ~5050 ops, fast ~100 ops → >50× speedup.