A good day to trie-hard: saving compute 1% at a time

Cutting Per-Request Overhead at the Edge

Cloudflare’s network processes over 60 million HTTP requests per second on average. A meaningful share of that traffic flows through pingora-origin, the service responsible for the final hop to a request’s destination server. Before any request leaves Cloudflare’s infrastructure, the service strips internal routing and measurement headers. At roughly 35 million requests per second globally, that cleanup runs in one of the hottest hot paths in the company.

The function that performs this cleanup, clear_internal_headers, consumes more than 1.7% of pingora-origin’s total CPU time. With the service using about 40,000 compute-seconds per second — equivalent to 40,000 fully saturated cores — that translates to roughly 680 cores dedicated solely to evaluating this one function. The code is simple and readable, which makes it an attractive target for optimization.

// PERF: heavy function: 1.7% CPU time
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
    INTERNAL_HEADERS.iter().for_each(|h| {
        request_header.remove_header(h);
    });
}

Benchmarking the Baseline

Using the criterion Rust crate, the team benchmarked clear_internal_headers against a large set of synthesized requests with a random number of internal and non-internal headers. The original implementation ran in an average of 3.65µs per call. That baseline provided a reference point for measuring alternative approaches against the same input set.

Flipping the Lookup Direction

The original function iterates over a list of 100+ internal header names, calling request_header.remove_header(h) for each one. Since the average request carries only 10–30 headers, the function was performing far more reads than necessary. Inverting the logic — iterating over the request’s headers and checking membership in the internal set — reduces the number of reads while producing the same intersection.

Because Rust’s http::HeaderMap does not yet have a retain method, the function collects the internal headers in a separate step before removing them from the request.

This small restructuring alone improved runtime from 3.65µs to 1.53µs — a 2.39x speedup. Projecting that improvement to production CPU usage suggested the function would drop from 1.71% to roughly 0.717% of total CPU time, saving about 0.993%. The team believed they could do better.

Choosing a Better Data Structure

With the search now running against a static set of internal header names instead of the request itself, the implementation is free to choose its storage structure. The first attempt used std::HashMap, which offers O(1) asymptotic reads with respect to table size. However, computing a string hash requires reading every byte, making hash lookup linear over key length — O(L).

Sorted sets like BTreeSet rely on comparisons, giving O(log(L)) behavior over key length, but they are also logarithmic in size. Even fast implementations like the fst crate were about 50 ns slower in benchmarks than the standard hashmap. State machines — common in parsers and regex engines — can reject non-matching strings at any step, which is valuable since only one or two headers per request are typically internal. Benchmarking a regex-based implementation took roughly twice as long as the hashmap version, which is respectable for regex but still not optimal.

What the team needed was something between a data structure and a state machine: a trie.

Why a Trie Fits

A trie is a tree structure where each node represents a substring of characters found in the initial set of strings, and edges represent the characters that can follow a prefix. This layout allows early elimination of non-matching strings. A request header that doesn’t start with one of the internal header prefixes can be rejected at the root node. Misses — which occur over 90% of the time — take roughly O(log(L)) time, while hits still take O(L).

Existing trie implementations on crates.io are typically optimized for keyboard-event-driven autocomplete systems rather than high-throughput request processing. The fastest available option, radix_trie, still ran a full microsecond slower than the hashmap. That gap led the team to write a custom trie optimized for their specific use case.

Introducing trie-hard

The result is trie-hard, now open-sourced under Cloudflare’s GitHub organization. It achieves its speed by encoding node relationships in the bits of unsigned integers and keeping the entire tree in a contiguous memory block. Benchmarks show trie-hard bringing clear_internal_headers to an average runtime of 0.93µs — under a microsecond for the first time.

Projecting that runtime to production implies the function’s CPU utilization drops from 1.71% to about 0.43%, a net savings of 1.28% of pingora-origin’s total compute.

Production Validation

Local benchmarks only go so far. Trie-hard has been running in production since July 2024, with performance metrics collected via statistical sampling of pingora-origin’s stack traces. The sampled CPU utilization for the different versions of clear_internal_headers closely matches what the benchmarks predicted, confirming that the optimization holds under real traffic conditions.

Small Wins Add Up

Optimizing a function measured in microseconds may seem like a marginal gain. But when that function runs tens of millions of times per second, even a 1% reduction in CPU utilization translates directly into capacity for handling more of the world’s web traffic. The broader lesson is that knowing where your code spends its time — through flame graphs, profiling, and benchmarking — matters just as much as the optimization techniques themselves. Small improvements in measured hot paths compound into significant operational savings.