Optimizing BPF Hash Table Performance

In this lesson, you will learn how to select the right BPF map type based on your cardinality and traffic patterns to ensure high-throughput metric collection.

The Trade-off: Hashing vs. Array-based Access

When building high-throughput monitoring tools, we often default to BPF_MAP_TYPE_HASH for its flexibility. However, hash tables come with overhead: memory allocation for new entries, hash collisions, and the constant overhead of the hashing algorithm itself. If your metrics have low cardinality or predictable keys (like small integers), a hash table is likely hindering your performance.

Cardinality and Frequency Analysis

To optimize, categorize your data streams:

1. Fixed, High-Frequency Keys (Use BPF_MAP_TYPE_ARRAY): If you are tracking events across a finite set of IDs (e.g., tracking per-CPU latency or a fixed list of syscalls), use a BPF_MAP_TYPE_PERCPU_ARRAY. This avoids the hashing cost entirely and eliminates lock contention, as each CPU accesses its own pre-allocated memory slot via a simple offset.

   // High-performance path: No hashing, no collisions
   struct {
       __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
       __uint(max_entries, 256); // Pre-allocated fixed size
       __type(key, u32);
       __type(value, u64);
   } metrics_map SEC(".maps");
   

2. High-Cardinality, Sparse Keys (Use BPF_MAP_TYPE_HASH): If your keys are dynamic (e.g., storing metrics per unique connection IP), use BPF_MAP_TYPE_HASH. To optimize this, ensure your max_entries is tuned correctly. If your map fills up, the BPF program will incur overhead from lookup failures or eviction logic. Use BPF_F_NO_PREALLOC only if you expect extreme memory pressure and can tolerate the cost of dynamic allocation per-entry, though pre-allocation is generally preferred for stable throughput.

3. Read/Write Frequency: For write-heavy scenarios, always prioritize PERCPU variants of both maps. By using BPF_MAP_TYPE_PERCPU_HASH, you keep writes local to the CPU. During your user-space collection phase, you simply aggregate the results from each CPU's entry. This shifts the performance burden from the critical path of the eBPF program to the (less frequent) polling interval in your monitoring daemon.

Key Takeaway: Choose ARRAY maps for fixed-key frequency metrics to eliminate hashing overhead, and rely on PERCPU variants for all write-heavy maps to prevent cross-core cache line contention.