Want larger LFT/UFT tables, better resistance against churn

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[^1]. 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).

[^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.

Start by reviewing the UFTs and layers that use stateful actions, then run or inspect the linked flow-table benchmark and its BTreeMap measurements. Compare lookup and insertion behavior at the larger cardinalities described, including the effect of write locking. Done means supporting substantially larger tables while preserving fast lookups and reducing churn-related processing and memory costs.