Title:Don’t Stall Me Now: Hiding Memory Latency in eBPF
Authors:Farbod Shahinfar, Marco Molè (Politecnico di Milano); Aurojit Panda (New York University); Gianni Antichi (Politecnico di Milano & Queen Mary University of London)
Introduction
eBPF has become a popular platform for building high-performance I/O programs such as load balancers, firewalls, and key-value store accelerators, offering I/O overhead comparable to kernel-bypass solutions like DPDK while being easier to deploy and manage. However, eBPF’s programming model severely restricts developers’ ability to optimize cache locality and hide memory latency — programs can only use generic runtime-provided maps with opaque data layouts, and must process packets individually in a run-to-completion fashion without prefetch instructions or computation overlapping. As a result, performance plummets as working sets grow: the authors measure up to 59% throughput drop on Katran (Meta’s production load balancer) when scaling from 1 to 1 million flows. This paper introduces Beeswax, a systematic approach that combines kernel runtime extensions, multi-phase data structures, and batched stage-based execution to allow eBPF programs to hide cache miss overheads, achieving up to 99% throughput improvement on Katran.
Key Idea and Contribution
Beeswax’s core philosophy is to “hide memory stalls with computation.” Rather than a single patch, the contribution is a four-layer systematic solution:
-
1. Kernel runtime extensions. The authors add a
bpf_prefetchhelper for explicit prefetch instructions, and modify XDP hooks and Mellanox/virtio drivers to submit packets in batches rather than one-by-one. These changes (~1,700 lines of C) create the foundational capability for overlapping computation with memory access. -
2. Multi-phase data structure abstraction. This is Beeswax’s most elegant design. Traditional eBPF map operations are atomic and non-interruptible. Beeswax splits a single lookup (e.g., hash table or LPM trie) into multiple phases: Phase 1 computes the target bucket/node address, issues a prefetch, and returns immediately without waiting for data; Phase 2 performs the actual read/write once data is in cache. For Katran’s connection tracking hash map, the authors create a two-phase version: the first phase identifies the correct bucket and prefetches the bucket list head; the second traverses the list. This exposes internal data-structure memory waits to the upper scheduler rather than stalling the entire pipeline. Combined with eBPF Arena for custom memory layout (e.g., compact trie nodes), cache locality is further improved.
-
3. Interleaved batch scheduling. Beeswax provides macros (
BAX_STAGE,BAX_NEXT_STAGE) to split single-packet sequential logic into multiple stages. The key scheduling semantics: all packets in a batch complete the same stage before moving to the next. For an LPM router, the FIRST stage extracts keys and prefetches the trie root; while packet 0 waits for its prefetch, the CPU immediately processes packet 1’s FIRST stage — memory stall cycles are filled with useful computation on other packets. Per-packet cross-stage state is passed through per-CPU arrays to avoid stack overflow. -
4. Systematic adoption recipe and helper library. To avoid blind prefetch insertion, the authors provide a two-step hotspot identification method (static source analysis + perf profiling), only transforming truly frequent random accesses (map lookups, packet data beyond the first cache line). The Beeswax library (383 lines of AWK/C) automatically translates macro-annotated multi-stage C code into compliant eBPF bytecode, requiring only 720 and 407 lines of changes to Katran and BMC respectively — proving the approach’s practicality on complex real-world code.
Evaluation
The authors evaluate on CloudLab with dual directly-connected servers (AMD EPYC 7302P + Mellanox ConnectX-5), running eBPF/Beeswax programs on a single isolated core.
-
Katran (production L4 load balancer): Baseline throughput drops 59% as flows scale from 1 to 1 million, correlating with rising L1/LLC cache misses. With Beeswax, throughput improves by 18–99% across various flow counts and Zipf skewness settings, with the largest gains under low skew (high miss rates). This result is significant because it demonstrates that a production-grade, widely-deployed eBPF application can more than double its throughput without compromising safety — simply by restructuring data structures and program logic to hide memory latency.
-
BMC (Memcached accelerator): Under Facebook’s real-world workload, Beeswax improves throughput by 17% at 1 million records. However, with only 1 record (no misses), throughput drops 3% due to multi-stage overhead — showing Beeswax is beneficial only when cache misses are a real bottleneck.
-
Microbenchmark (LPM router): Beeswax’s LPM trie achieves 47% higher throughput than a pure Arena implementation (no prefetch/multi-phase), and custom data layout adds another 12–16% improvement. Gains hold across different Zipf skewness factors.
Beeswax demonstrates that eBPF programs can systematically use software prefetching and batching to hide memory latency with manageable code changes (1,700 kernel lines, hundreds of application lines). This significantly expands eBPF’s performance envelope, ensuring kernel-state dataplanes maintain high throughput under large working sets — addressing a fundamental weakness previously considered inherent to the platform.
Q1: Does batching increase end-to-end packet latency?
A1: No. Batching itself does not add extra latency because the Linux kernel already processes packets in batches at the XDP layer — Beeswax simply aligns with this existing mechanism rather than introducing new delays. Batch size remains a tunable parameter for different scenarios.
Q2: Does this approach bypass the eBPF verifier or compromise safety?
A2: Not at all. The verifier still treats Beeswax programs as slightly more complex for loops and performs the same rigorous static safety checks. eBPF’s security guarantees remain intact. Beeswax’s philosophy is to treat the verifier as an immutable black box and improve performance through execution model and data structure restructuring — not by circumventing security restrictions.
Personal Thoughts
What struck me most is that eBPF programs slow down not because of “interpretation overhead” or “sandbox costs,” but because the CPU sits idle waiting for memory. This insight feels refreshing — instead of attacking the hardest “security vs. performance” trade-off in eBPF head-on, the authors go around the back and find leverage from the computer architecture level.
What I find most valuable about Beeswax is its toolkit mentality — it doesn’t propose a new programming paradigm you have to learn from scratch, but gives you a step-by-step “migration manual” (profile first, redesign data structures, then split into stages). For someone like me who’s still figuring out how to do systems research, this engineering-driven approach is quite instructive. If I ever work on eBPF in the future, I now know at least one debugging direction: “when in doubt, check cache misses.”