potential map lookup optimization: maintain LRU of previous lookup

[mtfriesen]

Describe the feature you'd like supported

For networking workloads in particular, and perhaps more general workloads, it is very common for a consecutive series of packets (or inspection contexts) to share attributes. This is implemented in NIC hardware in many cases, i.e., some NICs are known to sort and indicate all packets for flow A, then flow B, then flow C, even if they arrived on the wire in an interleaved order.

Therefore, we may be able to maintain an LRU cache within eBPF maps of the most recent (small) key lookup, and if the next key lookup matches the cached value, we can skip hashing the key.

Proposed solution

Consider maintaining an LRU cache of size one in each eBPF map. There will be complications around:

1. Avoiding contention of the LRU cache across multiple processors
2. Avoiding use of LRU cache for large key sizes
3. Invaliding the LRU when the table itself is updated

Additional context

No response

[Alan-Jowett]

Should this be map global or per-cpu?

[shankarseal]

Thx @mtfriesen for this idea. I have converted this to a discussion. @mtfriesen, @Alan-Jowett - please use this to brainstorm a potential solution.