Use Radix Tree to optimize filter access

[Neverlord]

We can most likely increase the performance of forwarding decisions by using a radix tree for storing peer filters. Currently, the core_actor/stream_governor simply stores all filters as vector<topic> and iterates them with O(n) on each forwarding decision.

[Neverlord]

We ship the radix tree implementation without actually using it for quite some time now. I think we should implement a small benchmark to compare the lookup time of our current vector-based filter type versus a radix_tree-based implementation to see whether it's worthwhile.

[Neverlord]

I've implemented a small micro-benchmark to quantify the performance gain we could gain from switching to the ART (Adaptive Radix Tree). The filter/extend_... test adds 100 entries to a filter. The filter/lookup_... looks up 10 keys from a filter containing 100 entries (more or less evenly distributed). These are the results:

$ ./build/broker/release/bin/micro-benchmark 
2023-03-12T16:36:51+01:00
Running ./build/broker/release/bin/micro-benchmark
Run on (20 X 3600 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB
  L1 Instruction 32 KiB
  L2 Unified 256 KiB (x10)
  L3 Unified 20480 KiB
Load Average: 0.62, 0.70, 0.73
---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
filter/extend_vector     305601 ns       305601 ns         2285
filter/extend_art         15044 ns        15040 ns        46707
filter/lookup_vector       1765 ns         1765 ns       392894
filter/lookup_art           167 ns          167 ns      4169869

It's >10x performance gain in both cases, so I think I'll go ahead and start integrating it.

[Neverlord]

Ok, I've finally sat down with this again. I've started integrating the radix tree when I hit a wall. The implementation made the very unfortunate design decision that the null terminator is part of the key. We store the topics in network representation in a buffer... without a null pointer. We need an interface that allow looking up a prefix with std::string_view. The implementation is also quite complex and it I couldn't just change a few places to get the behavior I wanted. Working with the implementation: this code is also needlessly complex and we don't use even half of it, because it implements a std::map-like interface. All we need is a insertion and prefix lookup.

So I figured I might as well implement a simple trie to see if this implementation is actually worth it. I did two versions of the trie: one that can only hold the 96 printable ASCII characters (our topics should be using only those, after all), trie96, and another trie that can allows any "character", trie256.

I have compared against two filter versions: vector_v1 is the version we currently ship in broker. Basically, a std::vector<topic> with functions for insertion and prefix matching. There's also a vector_v2 version, which is the same std::vector<topic> but with a smarter insertion algorithm.

The add_entries benchmarks will insert 100 keys into a filter. The match benchmarks does 10 match operations on a filter with 100 entries (5 of the keys actually exist).

Without further ado, here's the result:

------------------------------------------------------------------------
Benchmark                              Time             CPU   Iterations
------------------------------------------------------------------------
filter/add_entries_vector_v1       83289 ns        82567 ns         8569
filter/add_entries_vector_v2       38462 ns        38401 ns        18201
filter/add_entries_radix_tree      10549 ns        10450 ns        66899
filter/add_entries_trie96           5338 ns         5296 ns       131616
filter/add_entries_trie256          7252 ns         7194 ns        96104
filter/match_vector_v1              2298 ns         2277 ns       307629
filter/match_radix_tree             54.6 ns         54.0 ns     12853234
filter/match_trie96                 41.7 ns         41.3 ns     16979864
filter/match_trie256                31.6 ns         31.3 ns     22117882

Not only did my simple trie implementations match the performance of the much more complex (adaptive) radix tree, both versions are faster. Now, the one upside the radix tree will have over my implementation is less memory consumption. However, I feel like that's just not a tradeoff we need to make. Broker has one filter for the endpoint plus one filter for each client/peer. Worst case that's a few hundred.

@timwoj, @ckreibich: am I right to assume that Zeek only uses "well-behaved" topic names from the printable ASCII range, or are there some wild use cases where Zeek will treat the topic name basically as a byte sequence? I would prefer going with the trie96 version unless we need to be ultra conservative in what we accept as topic names.

A side note regarding the complexity: my trie implementation has ~210 lines when combining header and source file. The radix_tree header is 1500 lines. Again, the radix_tree is of course much more general and even provides iterator interfaces. We just have no use for them and the way they have implemented key lookup is incompatible with our use case.

[timwoj]

am I right to assume that Zeek only uses "well-behaved" topic names from the printable ASCII range, or are there some wild use cases where Zeek will treat the topic name basically as a byte sequence?

I think that's an ok assumption. Most of the topics are event names, which are guaranteed to be ASCII.