Want larger LFT/UFT tables, better resistance against churn

[FelixMcFelix]

We currently have table limits of around 65k entries per direction and per layer in our UFTs and layers which rely on stateful actions. Customer deployments of front-facing guests, particularly of web services, are liable to have far larger flow counts in practice—potentially $O(10^6)$. We need to be able to support flowtables of larger cardinality, and to keep lookups fast.

There are a few things to keep in mind.

• Table sizes (capacity) may need to dynamically scale up and down to minimise memory use on the host.
• We need datastructures optimised for lookup at this scale. We use BTreeMaps today because a) they are provided by alloc::collections:: and b) they provide faster lookup without needing to hash keys.

However, a significant problem with the use of BTreeMaps is that addition/removal of entries at large table sizes is going to leave us having a very bad time. What's giving me pause is that at, e.g. 8192 elements, we have a mean insertion time of 50.590 µs in the linked benchmark¹. For context, the modal packet processing times on dogfood today are around 512–768 ns when everything is in the fastpath. So you can see that's a very long time to hold the write lock, and a slow-path packet will pay it several times (NAT in/out, Firewall in/out, UFT) before all is said and done. Under high churn, an individual port can be locked for a very large portion of time like this.

We probably want a mix of things—some form of two-tier Map setup to minimise the cost of slowpath processing (and keep UFT hits at BTreeMap speed), and some means of making sure that a slow-path operation doesn't necessarily lockout a UFT query. Part of this is that with BTreeMap vs hashbrown::HashMap (or similar #[no_std]-compatible implementation) the HashMap's $O(1)$ lookups are going to beat out BTreeMap at some point, and we need to emprically measure what that crossover point looks like (and possibly swap between representations at runtime).

Footnotes

1. Obviously we're using different lookup keys for our flow tables versus the RouteKeys linked in there. Aside from noting that InnerFlowIds are larger types, the main concern is the scaling characteristic in terms of $n$ entries. HashMaps have more expensive lookups, but insertion time looks to scale a bit less aggressively. ↩

[FelixMcFelix]

What's giving me pause is that at, e.g. 8192 elements, we have a mean insertion time of 50.590 µs in the linked benchmark.

Looking back on this, the BTreeMap numbers seem strange. Having recreated a similar test suite (branch flowtable-scale), I believe in those numbers we're dropping a particularly irksome struct in with an awful Drop cost (e.g., BTreeMap<RouteKey, Arc<...>>). None of the other tests there seem affected. The below results work around this.

Early results lacking randomness:

What I get from testing in userland up to ~4e6 InnerFlowId->Arcs (with a single fixed key) looks to be:

Insert:

Get:

I'd like to keep these microbenchmarks checked in (but probably out of CI), but I think this suggests that we might actually be fine if we swap over to hashbrown and just run with that.

[FelixMcFelix]

Redone the above with log-scales and using a shared random sequence of elements for add/remove rather than one known element. This should better show off crossover points for insert/lookup and be more general across choices of key (but still fair). I think we have good evidence for considering hashbrown at this point, but we'd need to think through what capacity reclamation would look like.

To reiterate, we're comparing BTreeMap with various hashmaps backed by hashbrown using three different hash functions (siphash, foldhash, ahash). The Rust standard library itself uses siphash. All hash functions considered here are keyed, so should offer some HashDos resistance. The difference lies in their claims against an observer being able to deduce the seed based on direct observation (or indirect, via e.g. timings) of operations on the hashmap. I believe siphash is known to be strong here. Ahash claims HashDos resistance, while foldhash states that it is 'minimally' resistant and leaves open the possibility of indirect observations like the above.

We should be able to manually build/seed these in a kmod context, regardless.

Insert 1 element

At $2^{22}$ elements in the set (mean):

• BTreeMap - 250.75 ns
• ahash - 45.308 ns
• foldhash - 46.168 ns
• siphash - 72.785 ns

Get 1 element

At $2^{22}$ elements in the set (mean):

• BTreeMap - 316.58 ns
• ahash - 46.452 ns
• foldhash - 33.541 ns
• siphash - 107.54 ns

EDIT: updated 2025-06-26 with ahash.